AtCoder黄色になりました！
AtCoder黄色になりました！
さて、競プロでは色変をしたら記事を書く伝統があるので、私もその伝統に倣って書いていこうと思います。
AtCoder黄色になるまでにやったこと
まず、グラフを見れば分かるように、青色になってからずっとレートは安定しており、正直言って青色適性だと言える期間が1年半ほど続いていました。
ですがここ三か月ほどはずっと黄色パフォーマンスを出すことに成功しており、結果として黄色に到達することができました。
そこで、自身の経験から黄色コーダーになるために何をやったかを書いていきます。
1. 解法ブログを書いた
このブログを見て頂ければ分かりますが、去年の始めまでは解法をブログに上げていました。
ブログに書くことで自分の思考が整理され、また綺麗でより本質的なコードを発見できる機会があり、これ自体は悪くなかったかと思います。
しかし、ブログを編集する時間はかなり長く、その時間があれば精進量をかなり増やせたことを考えると、そこまで効率の良い方法ではなかったかもしれません。
ただ、解法ブログは後進を育成する数少ない手段でもありますから、界隈自体を考えるなら書いた方が良いものでしょう。
私も今年はちゃんと書いていこうかなって思います。
2. 得意な言語に切り替えた
今までC++でずっと競プロを行っていましたが、去年の5月頃からJavaに切り替えました。
それに伴い、今まで競プロ用だからと使い捨て前提で書いていたライブラリを整備し、Javaでライブラリを書く際はいつでも使えるようなライブラリを作ることを目指しています。
AtCoderのコード長制限は512KBとかなり緩いので、ライブラリを長く書き、JavaDocコメントを入れて可読性を向上させても提出に支障はほぼありません(提出欄に貼ると5秒ほど固まる問題はありますが……ｗ)。
この変更により実装力が相対的に向上し、提出速度が速くなったことでレートの底上げに貢献したと考えられます。
実際、夏休み中にライブラリを一通り移行した後の9月からレートは伸びていることを考えると、競プロだからとC++を書くよりは得意な言語を継続して使った方がより良いのかもしれません。
ただし、C++は最後の手段としていつでも使えるようにしておくのもまた必要に思えます。
例えば
atcoder.jp
という問題があり、C++などでは愚直でも最悪ケースが間に合うとして話題になっていたこれですが、このようなC++では間に合いそうだけど自分の言語ではTLE……と悩む問題があった時に、C++で即座に書き直して提出する力はやはり持っておきたいところです。
3. ライブラリを使いやすく整備した
まだ途中なので、整備した、と言い切るには抵抗がありますが……まぁ良いでしょう。
5月頃からJavaに切り替えた際、ライブラリも競プロ用ではなくどこでも使えるものとして書き直しています。
標準ライブラリに匹敵する使い勝手を確保しようと、ちゃんとJavaDocコメントを書いたり、コードの内部にも適切にコメントを残すことで実装が見て分かるようになっていたり、抽象化、例えばセグメント木にモノイドが載る(実際は圏が載りますが)ということでMonoidインターフェースを継承したものを載せられるようにしたりとあちこちで使いやすい工夫を施しています。
これは高速化という点でも実は貢献しており、例えば今PrimeModIntegerはPrimeクラスをコンストラクタに渡すことで生成できるのですが、素数という限定化をしたことで割り算が場合分けをせずに素直に定義できるようになったりと結果的にメリットにつながる場面も多く出てきています。
適切でない引数にはちゃんとコンパイルエラーあるいは早期のランタイムエラーが出るので、変なバグを掴まされることが減るのも良い点です。
重いアルゴリズムだけでなくごく簡単なアルゴリズムもライブラリ化することで、むしろ使い勝手が上がるかもしれません。(C++だとstd::algorithmみたいなの)
ライブラリは可視化できる最も効果的な精進方法なので、みんなもやってみましょう！
他のブログでよく見るので、私が持っている知識・ライブラリも列挙してみます。
- ライブラリを持っている
BFS, DFS, 二分探索, 尺取り法, 累積和, セグメント木, 相対セグメント木, 遅延セグメント木, 座標圧縮, UnionFind, ポテンシャル付きUnionFind, スライド最小値, ModInteger, AVL木
- ライブラリを持っている(他の人が持って無さそうな変なの)
FastIO(Javaerなら必須), 整数関連の便利演算(gcdなど), 配列関連の便利演算(nextPermutationとかPrimitive→Object変換とか), 距離演算関数, 素数管理, 循環配列, multiset, multimap
- 知識として使い方を知っている(書ける)
最短経路三点セット(Floyd-Warshall, Bellman-Ford/SPFA, Dijkstra)、最小全域木, ローリングハッシュ
- 知識として使い方を知っている(すぐに書けないが貼るだけなら……)
オイラーツアー, 高速フーリエ変換及び剰余環版, ラグランジュ補間, 最小共通祖先, ダブリング, 全方位木DP, LinkCutTree, EulerTourTree, 最大流, 最小費用流, 最大マッチング, LowLink, Li Chao Tree, Trie木, Aho-Corasick, 接尾辞配列, 最長共通接頭辞, 最長回文, 行列, 有理数
こんなところでしょうか？
まだまだ作りたいライブラリは沢山あり、少なくとも今年中に100個以上は生成するつもりです。
ファイル数だと、今見積もっていますが1500個を超える予定です(ヤバい)。
ライブラリを作るのは時間がかかりますが、知識を整理するという点では良いアウトプットになると思います。
AtCoder橙色を目指すためにやること
1. ライブラリ作り
はい
2. 自分用のまとめWikiを作って公開する
ライブラリは勿論貼ればいいのですが、例えば包除原理など有名な知識ですがライブラリにできないものも存在します。
そういった知識の使い方や使う場面などを纏めたホームページが欲しいと思っていて、それを作る予定です。
3. このブログを更新する
まだグラフ関連と行列関連のライブラリが弱いので先にそっちを整備しますが、それが終わればこのブログを再開したいと思います。
ブログで解法を上げるのを止めてしまった理由、綺麗なコードを書こうとして時間が無限に取られたのが原因なのですよね。
長くなる部分を全てライブラリに任せることができれば、また復活できると思います！
