もふふろぐ

AtCoderで黄色になりました。

ABC168で69位になったことでAtCoderのレーティング最高値が黄色になりました。 青色になったのは2017年7月29日のARC079なので、約3年振りに最高値の色を更新したことになります。

多くの競プロerがしているように、「○色になるまでにやったこと」を記事にしようと思いました。

問題数

次の図はAtCoder Scoresで表示できる精進グラフです。 上の黄色に達している線はレーティングを、下の広義単調増加している線は解いた問題の点数の合計の0.01倍を示しています。 AtCoderのコンテストにほぼ毎回参加することで沢山の問題を解いていました。

AtCoder Problemsでも解いた問題数を表示することができます。 青色になった当時は84問でしたが、現在では724問です。 2018年の初め頃に競プロに力を入れていたことを読み取れます。

さらに推定された難易度ごとの問題数も可視化できます。

問題を解く際の工夫として、提出したコードをGitHubのリポジトリ（reminjp/competitive）にまとめることで、いつでもどこでも参照できるようにしていました。

ライブラリ

問題を解いて典型的な解法を知るだけではなく、競プロ向けのコード片（いわゆる競プロライブラリ）をまとめることで、コンテストでより早く高得点を取れるように努めています。

ライブラリも解答同様にGitHub（reminjp/algorithm）で管理しています。 解答コードに自動で挿入するようなツールを導入したいと考えていましたが、特に何もしていない状態です。

ライブラリに含まれているアルゴリズムやデータ構造は次の通り。

• 幾何
  • 線分などの交差判定, 距離
  • 外心
  • 凸包
  • 射影点, 反射点
• グラフ
  • ダイクストラ法
• 整数
  • 中国の剰余定理
  • 魔方陣
  • mod combination
  • mod逆数
  • 素数
• 実数
  • 等差級数, 等比級数
• 文字列
  • Morris-Pratt (MP) algorithm
  • split, join
  • トライ木
• 木
  • 区分木 (セグメント木)
  • union-find (素集合データ構造)
• その他
  • 日付
  • HTTP
  • タイマー
  • 台形制御

沢山ありますが、コンテストで主に使用するのはmod関連、union-find、幾何あたりであり、他の大半は日の目を見ていません。 青色までの難易度では、ダイクストラ法を書けなくてもDFS/BFSでこと足りますし、区分木も必要になりませんでした。 とはいえ、コード片を書くためにアルゴリズムを調べた過程には、遠回りながら意味はあったと思います。

もふふ

2017年の秋頃にふわふわなサメのぬいぐるみを購入しました。 ICPCの文化に倣って、オンサイトコンテストにマスコットとして持参しています。 いつの間にかもふふの愛称で呼ばれるようになり、多くの競プロerと知り合うきっかけにもなりました。

もふふ「もふふ」

今後も黄色を維持できる自信はありませんが、コンテスト参加を継続したいと思いました。