AtCoder青になりました

前回の記事にも書きましたが、AtCoderのレートが1600を突破し、青色になることができました！

f:id:betrue12:20180604224841p:plain

「まずは青を目標に」と思ってやってきたので、とても嬉しいです。TwitterやSlackなどで交流や情報交換などしてくださった方々、本当にありがとうございます。今後ともよろしくお願いいたします。

コンテスト履歴＆ちょっと自分語り

コンテスト履歴はこんな感じです。

f:id:betrue12:20180605201840p:plain

先週の時点でレート1465、あと3～5回くらい良いパフォーマンスが出せれば青に届くなーと思っていたら、自己ベスト大幅更新の数値が出て一気に届いてしまいました。嬉しいより前に、超ビックリしました。AGCこわい。

初参加のABCでパフォ1600とか出してたりしますが、情報系で修士を出てエンジニア6年目、数学もプログラミングも元々好きだったので、最初から経験値の高い状態で競プロを始めています。RPGでいうと「初期レベルの高い途中加入のおっさんキャラ」みたいな感じです。そのぶんレベルアップが遅いです。

あとは自分より10歳以上も若くて実力のある人達が本当にたくさんいて、「負けてられない！」と思って精進した、という面も正直あります。

やったこと

前置きはこのくらいにして、やったことを書いていきます。自分の経験とアドバイスが混ざったりしてますが、少しでも参考になれば幸いです。

過去問を600問くらい解いた

微妙に600に届いていないのですが、現時点のAtCoderでのAC数は594です。使用言語は全てRubyです。

主要コンテストであるABC/ARC/AGCの内訳はこんな感じです。

f:id:betrue12:20180605203219p:plain

既に100000007回くらい言われていることですが、とにかく問題を解くことが一番大事だと、これだけは自信を持って主張できます。

埋めた順番は以下の通りです。

ABCのA～D
AGCのA～B（Cも一応開いて、解けそうなら解いた）
ARCのA～B（ABCと重複してないもの。修行でした）

ただ、ABC-Cにまだ少し苦戦するかなって段階であれば、D問題を後回しにしてA～Cを埋めるのがいいと思います。

あと、意見が分かれるかもしれない解説ACについて。私はABC-C, Dについては、1時間くらい考えて全然思い付かなかったらサクサク解説ACしてしまいました。発想よりもテクニックやアルゴリズムを知っていることが重要な問題は、それを知らない状態で考えていてもなかなか解けないので、早く身に付けてしまったほうが良いと個人的には思います。

ただ解説ACする場合でも、「1度愚直解を書いてTLEを食らう」経験は、時間に余裕があればしてみると良いです。愚直解が書ける、全探索が書けるって、とても大事なことだと思います。

コンテストに出た

とにかくAtCoderのコンテストに出ました。非公式コンテストや企業コンテストにも出ました。AtCoderに登録してから開催されたコンテストは同時開催を除けば全て出ています。

コンテスト後にはTwitterで情報を集めました。あと、解説放送を観ました。これ本当に大事だと思います。

そして本番中に取り組んだけど解けなかった問題は、なるべく翌日にACしました。決して本番中に解けなかったとしても、その問題について考えた数十分は絶対に無駄じゃないと思います。記憶が新しいうちに身に付けて、次回以降に活かしましょう。

総じて言えば、コンテスト大事、復習大事。これに尽きます。

バチャに参加した

特にゴールデンウィークにバチャを開催してくれる人がたくさんいたのでひたすら参加しました。ありがとうございました！

解いたことのある問題は復習になるし、解いたことのない問題は適度な緊張感で臨むことができます。またコンテスト後と同じように、同時に参加していた人とは解法の意見交換ができます。良い事ずくめです。

蟻本を読んだ

ひとくちに「読んだ」といっても、ものすごい分量があるので、未だに全部理解できているわけではありません。ただ、最初から最後まで流し読みはしました。

実装まで含めて理解できていなくても、「こんなことができるアルゴ・データ構造があるよ」っていう記憶が頭の片隅にあると、いざ問題を解く時に思い出せるかもしれません。コーディングは、実際に問題を解いていて必要になった時にしていけばいいと思います。

ライブラリを作った

頻出のデータ構造やアルゴリズムは、実際に問題で使う機会があったときに、再利用可能なクラスや関数にするようにしました。

ほぼ全て蟻本の写経ですが、当然蟻本のコードはC++で私はRuby使いなので翻訳が必要になりました。ただ、翻訳するという作業もコードを理解するのに役立ったと思います。

ライブラリとして別ファイルに切り出しているものは以下です。あまり使っていないものも含まれています。

データ構造（ビットセット、優先度付きキュー、union-find、セグメント木、BIT）
グラフ（ベルマン・フォード、ダイクストラ、ワーシャル・フロイド、木の直径、木の重心、クラスカル、LCA）
平面幾何（凸包、線分の交差）
その他（座標圧縮、素数modの階乗・逆元・二項係数、ナップサック問題、部分和問題、LIS）

f:id:betrue12:20180605220546p:plain

一般的なDFS・BFS、二分探索、しゃくとり法などは関数化しにくいので、その都度書いています。エラトステネスの篩やユークリッドの互除法などはRuby標準ライブラリにあるので持っていません。

もちろん、ライブラリを作りすぎると手で書く頻度が減って定着が遅くなるというデメリットはあります。ただ私は、考察が合っているのにコーディングが間に合わなくて解けないというのがとても悔しいので、なるべくコーディングでは楽をしたいです。

あと早いうちにライブラリを作って積極的に使っていると、バグを踏んで直せたり、足りない機能に気づけるようになります。ライブラリは使えば使うだけ成長するものだと思っています。

言語について勉強した

私の使用言語はRubyです。競プロを始めて以降、公式リファレンスを本当にたくさん読むようになりました。

Rubyの標準メソッドは多彩で、特に文字列や配列の操作についてはとても充実しています。標準メソッドを沢山知っていれば、そのぶん自力で書く処理を減らせるので、読みやすくてバグりにくいコードが速く書けるようになります。

また、とにかく実行速度が気になる言語でもあります。アルゴリズムは解説通りなのにTLE、ということはザラに起こります。どのような処理が遅く、どのような処理が速いのか、色々実験しました。時にはRuby処理系のソースコードを読むこともありました。自分の使っている言語の特性を知るのはとても大事なことだと思います。

同じ言語を使っている人の提出コードを読むのも良いと思います。C++とかだと無限に提出がありますが、RubyだとARC/AGCのACコードは読もうと思えば全部読めるくらいの量しかないので、けっこう読み漁ってます。あとPythonのコードもとても参考になるのでよく読んでいます。

ブログ記事を書いた

コンテストごとに記事を書くようにしたのは最近のことですが、それ以前にもネタがあれば何件か書いていました。

記事を書くのは本当に時間がかかりますが…書いていると自分の理解できてないところが洗い出されます。World Wide Webに公開するというプレッシャーもあるので、追加で調べたり色々と実験するようになります。そうすることで理解が深まり、記憶が定着していきます。コードを書くのとは全く違う脳みそを使っている感じがします。

本当に時間がかかるので（二度目）人によりけりだと思いますが、文章を書くのが好きな人にはオススメです。