AtCoder Beginner Contest初参加してみた

最初に結論から：やってみて感じたこと

（※個人の感想です）

• ビギナー向けのコンテストは問題の難易度の幅が広いと感じた。舐めとんのかレベルからお手上げするものまで。
• 実行時間制限があるので、計算効率が悪いコードは通らない可能性がある。
• 入力個数や入力桁数など、計算量に直結する上限値は気にする。20万個の整数値をO(N*N)すると馬鹿にならない。
• 出力フォーマットは正確に把握する。
• 使い慣れたエディタ環境を整備し、コーディングの妨げになるような煩わしさを排除できていると良い。
• 頻出する計算方法があるので、ライブラリを整備しておくほうが有利では。（組み合わせ数とか階上みたいな数学的なものや、グラフの経路を解くようなもの。他にも色々ありそう。）
• 過去問を解いて頻出問題やその解法を知っておくと有利。
• 解説を理解するにも知識が必要。本当にビギナーだと全部は理解できない可能性がある。1つ１つわからない用語を調べてステップアップしていくしかないのかもしれない。

なぜ参加したのか？

• AtCoderの社長のTwitterはフォローしていたので存在は知っていた
  • AtCoderのこと呟いているか、フォロワーにいじられている人か、で9割くらい占めているイメージ。
• レートが高いと転職でアピールできるらしい
• やってみないと難易度が想像つかないので、1回くらい試しにやってみたいと思ってた

何に参加したのか

AtCoder Beginner Contest 154。
ABCと略すらしい。
制限時間100分。長くね？

何を準備したのか

1. チュートリアルで問題の提出方法を学び、
2. 提出した問題の判定の用語を学び、
3. コンテストに参加登録をした。
4. macbookにインストールされているXcodeで新しいプロジェクト(c++用)を作った。

以下詳細：

• 開始40分前にコンテストの存在を知る
• AtCoderのサイトを初めて見る
• 参加方法を見てユーザー登録をする
• 提出の練習ページで問題の提出をしてみた
  • 問題Aを掲載されているコードのまま提出してみる
  • 問題Bを掲載されているコードのまま提出してみる
• 問題Bの問題文中にあった TLE や WA という用語がわからなかったので 用語集 を見てみる
• AtCoder Beginner Contest 154の参加登録ボタンを押す
• AtCoderのWeb上のコードエディタは貧弱でコーディングに向かないと思ったので、IDE環境を整える必要性に気づく。
• macbookのXcodeを開いて、c++が開発できる環境を作る(コード補完の効くIDEであれば何でも良かった)
  • Xcodeだとscanfのための入力方法がわからなかったので、コンパイルと実行はCLIで clang++ -Wall main.cpp && ./a.out しようと思った。
• この時点で開始まで残り4分きってた

私のスペック

• 情報系学部(CS学部)を卒業している
  • オーダーって概念は知ってる
    • バブルソートがO(N^2)なのは理解している
    • クイックソートがO(n logn)なのは暗記しているが、理解はしていない。
  • 空間的局所性を意識してコードを書くことがある(pos[x,y]の二重for文でxを内側のfor文にするなど)
  • メモリを多く使うことで計算量を減らせるコードが書けることを知っている(経験上)
  • ソートして二分探索をすることで計算量を減らせるコードが書けることを知っている(経験上)
• 仕事でC++を書いていたことがある（半年前まで)
  • C++のレベルは多少C++11の機能を使っていたレベル。constexprとかtemplateとかの沼には入ってない。
  • 現在はGoでWeb APIを書いている。
  • 業務で小難しいアルゴリズムを駆使することはほぼ無い。
• 競技プログラミングは初めて
  • すごい昔SuperConってのに応募したことあるけど、昔すぎるのでノーカン

コンテストの問題を解く。

A, B は簡単だったので愚直にコードを書きました。

C も ソートして隣り合う数を比較することをすぐに思いつきました。
ただstd::sortって配列でどうやって書くんだっけ、、、って迷ってしまい、
std::arrayで書き直しました。
std::sort(arr.begin(), arr.end())で未初期化領域までソートしちゃったために
結果が意味分かんないことになって焦りました。
std::vector使えばよかったのに。。。

D は 愚直に書いたら TLE (Time Limit Exceeded) になってしまいました。
隣り合うK個の数の総和が大きい場所を探し当てるために、
先頭がi番目のときの総和を毎回求めていたためです。
計算量を減らすために、求めた総和を記録しておき、
i-1番目の数字を総和から減らしi+k番目の数字を総和に足すことで新しい総和を求めるように改善しました。
ただ、今度は WA (Wrong Answer) になってしまいました。
よく問題文を読んでみると、出力の桁数が自分のより多いことに気づき、
printf("%.12f\n", expect); としたらうまくいきました。

E は 桁数と数値の組合わの問題ということは気づいたのですが、
コードには落とし込めませんでした。
あとで解説を見ると「桁DP」と書いてあり、ぐぐってみると競技プログラミングの頻出課題のようです。
DPは動的計画法の略です。聞いたことあるけど、覚えていない。

動的計画法を一言で言うと、

「今までの計算結果を記憶しておくことで、計算量を減らすこと」

となります。
先述の記事の中で例としてフィボナッチ数の求め方がありますが、
実装レベルでは、

「十分な大きさの配列を用意して、ループを回す中での計算結果を逐一配列に代入する」

ことが動的計画法であると言えます。

なるほど、仕事で数回ほど使ったことあるテクニックでした。
ただ、それを理解したからといっても「桁」にどう「DP」を使うのかが思いつかない。
これはテクニック名で呼ばれているくらいなので、過去問で鍛えれば解けるようになる問題かもしれません。

F は全く読んでいません。

コンテスト終了後

• 解説がすぐに見れる。
• 自分のレーティングへの反映は終了直後ではない。少しだけ時間かかる。
• コンテスト結果は https://atcoder.jp/users/uechoco/history/share/abc154 のように残る。
• 最初の数回は正しくレーティング値を算出できていないかもしれないらしい。その場合は「パフォーマンス」の値を見るとよいらしい。

AtCoder コンテストについての tips

パフォーマンスとはざっくり「コンテスト１回分のみのレーティングのようなもので、毎回そのパフォーマンスを取るとそのレーティングに収束する」

今回の私のパフォーマンスは「714」でした。
上記のサイトの「AtCoder 社長による見解を参考にしました。」を参考にすると、

| 800-1200 | 緑 | C | ソフトウェアエンジニアとして申し分ない実力です。 |
| 400-800 | 茶 | D | 各大学の情報系学部でしっかりとプログラミングを勉強して上位 3 割の成績を収めている学生さんの実力です |

のようです。CS学部を卒業しているソフトウェアエンジニアとしては収まるべき点数に収まったのかもしれません。
過去問を解いて頻出テクニックを学べばもっと点数を挙げられそうな気がします。

やってみて感じたこと

冒頭に記載。