初めて参加したAtCoderで惨敗した話

2018-07-23
javascript%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0atcoder
    

目次

概要

2018/07/21。

特に事前調査もせず軽いノリで AtCoderに初めて参戦しました。

そして惨敗しました。

敗因を書きます。

状況

今回、参戦したのは「AtCoder Beginner Contest 103」 https://beta.atcoder.jp/contests/abc103 100分 言語は全4門ともJavaScript(nodejs)を選択。

そして....

結果

  • 順位 1810/2188 位
  • 得点 300/1000点
  • パフォーマンス 346
  • レーティング 17
  • A :100 :○
  • B :200 :○
  • C :300 :×
  • D :400 :×

2完。 しかもB問題に少し手間取ったため、レーティングも伸びず。 C問題がクリアできれば、半分より上の順位には入れそうであった。

敗因

ざっと思いつく敗因は以下の通り。

  • 標準入出力に手間取りロジックを考える時間が奪われてしまったこと。
  • 数学的な基礎知識の欠如
  • 配列操作に手こずった

標準入出力に手間取りロジックを考える時間が奪われてしまったこと。

完全に標準入出力を忘れてました。 ここで数分ロスしてしまいました。

数学的な基礎知識の欠如

今回の問題は

入力値を a b c ... とした時

** f(X) = (a mod X) + (b mod X) + (c mod X) + ..... **

で、f(X)が最大になる時のXを求める問題です。

頭では解けたつもりだったが、 どうしてもタイムオーバ(TLE)してしまいクリアできず。

** X = (a + b + c + ....) - length(a + b + c + ....) **

でクリアしている人がおり全く理解できなかった。 とにかく数学的な基礎知識が欠けているんだなと思った。

全探索のような実装でも解けるけど、問題の意図は、 効率的な方法を実装をしなければならないということだと感じました。

データ操作に手こずった

標準入出力から受け取った文字列を任意のデータにするのに時間がかかってしまいました。 回答中に基本的な配列操作方法をググりだしてしまう始末。

そもそも pop push shift unshift などは、実装時にパッと浮かばなきゃマズイと思いました。

と言うわけで

対策

標準入出力の処理をテンプレ化する

AtCoderの問題形式は必ず標準入出力で変数の受け取り、回答の出力を行うので 開始したらとりあえずこれをコピペする(言語でjsを選択した場合)。

まずは、このフォーマットに沿って書けば問題ないかと思います。

function main(arg) {
    // 処理
    console.log(arg)
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

配列操作等の基本操作を完璧にする

pop push shift unshift あたりの基本操作は完璧にする。 この辺を押さえてないとB問題すら解けるか怪しくなると思います

加えて、jsの場合

arr.sort((a,b) => {
    if (a > b) {
        return 1
    } else {
        return -1
    }
})

で簡単にソートができます。

他にも配列操作のメソッドであれば、map、forEach、fillter、といった便利な機能が用意されています。

スクリプト言語を使うのであれば、標準で用意されている配列操作などのメソッドを覚えておくことで、自分でソートなどのロジックを書くことが省けると思います。

スニペットを用意しておく

全加算、全乗算、素数判定、ソートとかの頻繁に出てきそうな処理はスニペットにすると良いかといます。

多分そうやってやっている人もいるんじゃないかな... GolangでAtCoderの問題を解くためのスニペット集

数をこなす / アルゴリズムの基礎知識の向上

細かいテクニックがどうであれ、基本的なアルゴリズムを押さえてないとそもそも太刀打ちできません。

http://osrehun.hatenadiary.jp/entry/2015/12/13/000716

↑ここでも書かれているように、 「探索」や「データ構造」といったアルゴリズムを一つづつ押さえていくことがC、D問題への最短経路になると思います。

まだまだ問題の傾向がつかめていないところもあるので、 まずは、ある程度ABCに参加して傾向を掴みたいと思います。

AtCoderとかでも利用したい、ブラウザで動くエディタ + デバッグ環境を作る ※追記 2018/08

https://tech-blog.s-yoshiki.com/2018/09/585/

Microsoft謹製のエディタ「Visual Studio Code」でも使われているエディタ機能のJavascriptライブラリ「MonacoEditor」を使って自分専用のデバッグ環境を作りました。

AtCoderで初めて色がつくまでの話(茶色) ※追記 2018/11

https://tech-blog.s-yoshiki.com/2018/11/778/

AtCoderで、ついに色がつきました。茶色になりました。 始めた当初は、はっきり言って茶色なんて大したことのないランクだと思っていました。 ここまで来るのに4ヶ月、回数にして10回目の参加での到達で想定よりも時間がかかってしまいました。

また、上記の改良版をGitHubで公開しました。

https://s-yoshiki.github.io/AtCoder-JsDebugger/#/

※追記 | 【AtCoder】ABCで初めてC問題が解けました。 ※追記 2018/12

https://tech-blog.s-yoshiki.com/2018/12/830/

コンテスト内の順位は656位(/1736)。 出したパフォーマンスは1021。 レーティングは468→554(+86)となりました。

C問題を解いたユーザの中では遅い方でしたが、パフォーマンスは1000を超えました。 安定的にパフォーマンス1000を超えるのであればC問題を解くのは必須と言えそうです。

(※ABC問題)

    
s-yoshiki
s-yoshiki
githubtwitterqiita
Web作ってますが、インタラクティブなプログラミングも好きです。
JavaScript / Vue / node.js / PHP / AWS / OpenCV

関連記事

10進数から2進数 2進数から10進数への変換 JavaScript
10進数から2進数 2進数から10進数 テスト 10進数から2進数、2進数から10進数への変換を行うJavaScriptのコードの紹介。 JSの場合、10進数から2進数への変換はメソッド。2進数から1…

JavaScriptの配列ショートハンド (AtCoder用)

JavaScriptでワーシャルフロイド法を実装
AtCoder ABC012 D問題 D - バスと避けられない運命 解説 実装 AtCoder ABC012 の D問題でワーシャルフロイド法が利用できる問題が出てきたので、 JavaScriptで実装しました。 AtCoder ABC012 D問題 D…

JavaScriptによる2分探索(バイナリサーチ) のサンプルコード
2分探索について ソース 参考 JavaScriptで2分探索(バイナリサーチ)を実装してみました。…

Firebase + Nuxt で認証付きページを作るときに参考にしたいところ
Webアプリケーションのセッション管理にJWT導入を検討する際の考え方 Service Worker によるセッション管理 ユーザー セッションの管理 Nuxt.jsとFirebaseでSPA×SSR×PWA×サーバーレスを実現する CookieとセッションとJWT SSR…

JavaScriptで幅優先探索 (bfs) を実装する
bfsソースコード 前提 bfs関数 テストコード JavaScriptで幅優先探索 (bfs) を実装し簡単な最短経路の探索問題を解いてみました。 AtCoderの問題を参考にしています bfsソースコード 前提 bfs 関数の定義について 引数 table…

JavaScriptでbig-integerでできること
定数 メソッド abs add, plus and bitLength compare compareTo compareAmb divide, over divmod equals, eq greater, gt greaterOrEquals, geq…

0埋め・ゼロ埋め処理 のコードJavaScript
サンプル コード 呼び出す 説明 参考 追記 JavaScriptで 0埋め / ゼロ埋め / zero埋め 処理を行うサンプルコード サンプル コード 呼び出す 説明 記事タイトルが…

順列・組み合わせ のサンプルコード JS [permutation] [combination]
順列 - permutation サンプルコード Usage 組み合わせ - combination サンプルコード Usage 順列(permutation) と 組み合わせ(combination) のサンプルコードをJavaScript…

うるう年を求めるプログラム JavaScript
閏年の条件 サンプルコード 判定関数 21世紀のうるう年を算出する うるう年を求める実装メモです。 閏年の条件 閏年の条件は以下の通りとなります。 https://www.nao.ac.jp/faq/a0306.html サンプルコード 判定関数 2…

最新の投稿

SQL整形ツールを作成した
特徴 使い方 FW/ライブラリ等 nuxt sql-formatter-plus Monaco Editor おまけ ソース SQL整形ツールを作成しました。 URLはこちらです。 SQL…

ファイルの1行目を表示 Linuxコマンド head
head コマンド例 headコマンドでファイルの 1行目もしくは指定した行数だけ表示する方法。 head 利用できるオプション コマンド例 の 1行目だけを表示 の 5行目までを表示 カレントディレクトリ以下の全てのtxtファイルの1行目を表示

Amazon S3 と ローカルファイルのチェックサムの比較
s3apiでEtagを取得 検証 マルチアップロード時の注意点 Amazon S3 の Etagを使ってファイルの整合性チェックをする。 s3apiでEtagを取得 S3 APIを利用するとEtagを取得します。この値はmd5のハッシュ値になります。 検証 MD…

github.io / gitlab.ioで公開されている質の高い技術ドキュメント
AWSによるクラウド入門 Pythonプログラミング入門 普通の人が資産運用で99点をとる方法とその考え方 2018年の段階で私が知らないこと github.io / gitlab.io で無料で公開されている興味深いドキュメントのmemo AWS…

10進数から2進数 2進数から10進数への変換 JavaScript
10進数から2進数 2進数から10進数 テスト 10進数から2進数、2進数から10進数への変換を行うJavaScriptのコードの紹介。 JSの場合、10進数から2進数への変換はメソッド。2進数から1…

JavaScriptの配列ショートハンド (AtCoder用)

JavaScriptでワーシャルフロイド法を実装
AtCoder ABC012 D問題 D - バスと避けられない運命 解説 実装 AtCoder ABC012 の D問題でワーシャルフロイド法が利用できる問題が出てきたので、 JavaScriptで実装しました。 AtCoder ABC012 D問題 D…

GitHub Actions で Gatsby をビルドし Amazon S3 にデプロイする
GitHub Actions について あらかじめ準備しておくもの AWS IAM ユーザを環境変数にセットする workflowの記述 ビルド バッジを利用する 終わりに 参考にしたところ Gatsbyで作った静的サイトを、GitHub Actions…

cloudinaryによる画像ファイルの管理 はじめてみる
目的 cloudinary について 他のサービスとの比較 料金プラン アカウントの登録 利用してみる ダッシュボード 画像の編集 APIベースでのアクセス 感想 参考 画像の管理や配信、さらには加工といった事ができるsaas型のcloud…

JavaScriptによる2分探索(バイナリサーチ) のサンプルコード
2分探索について ソース 参考 JavaScriptで2分探索(バイナリサーチ)を実装してみました。…

Tags

Dates

© 2020   404 motivation not found