AtCoder 黄色になる方法のうちの一つ
ついに黄色になりました。嬉しいです。多分人生で一番嬉しい。
思えば、競プロ始めてから 4 年と 3 ヶ月が経過しており、青になってからも 2 年と 4 ヶ月が経過してました。 黄色になるまでの rated なコンテスト参加回数は、なんと 166 回です。
家族とハワイ旅行に行った時も、深夜に起きてコンテストに出場したのはいい思い出です(レートは落ちましたが)。 インターン先の人事の方に飲みに誘っていただいた時も、コンテストに出場するのでごめんなさいをしました。あの時はごめんなさい。
青になってから、幾度となく黄色チャレンジをしては心を折られる毎日でした。 見えない壁が存在して、毎回グラフが反射しています。黄色になれたのは、5 度目の正直といったところです。
黄色になるための方法のうちの一つ
多くの人が言及している通り、ABC で高度な考察を要する問題はほとんど出ません。 出題される問題のほとんどが、典型アルゴリズムの組み合わせで解ける問題です。
橙くらいの強い人が、コンテスト後に以下のようなツイートをしているのをよく見かけます。(これは特定のツイートを指すものではなく、蓄積された橙コーダーのツイートのイメージです。)
ABC◯◯◯お疲れ様でした。 A:うし B:たぷ C:にきあくん笑 D:一番難しい。D 問題に 998244353 difficulty の問題を出すのやめろ E:問題文答えが書いてある F:はるだけ
最初は初級者を煽っているのかと思っていましたが、そうではないことに最近気がつきました。おそらく、ABC レベルの典型アルゴリズムを習得した上級者にとって、D, E, F 問題の 難しさに差がない のだと思われます。
ABC は考察の難しさというより必要知識 / ライブラリのレベルで配点が決まってるっぽいので、その知識を持ってる人にとっては D〜E より F の方が楽なことが多々あるよね
— opt (@opt_cp) 2021年6月27日
例えばそのまま書くと「ABCは思考力0の問題が出題され、ARCから思考力が問われ始めます」みたいなことがあって、自分はその意図はわかるんだけど、それをそのまま発信すると明らかに正しく伝わらないので、頑張って翻訳をしないといけないところがあり……。
— chokudai(高橋 直大)🍆 (@chokudai) 2021年6月26日
これを翻訳すると、「ABCは、競技プログラミングにおける典型を把握し、論理的に突き詰めれば自然と引き出せる典型を選択する、という行為をマスターした上級者であれば、問題を読めば一瞬でわかる問題が出題されますが、ARC/AGCからは、上級者でも一瞬でわからない問題が出題されます」みたいな感じに
— chokudai(高橋 直大)🍆 (@chokudai) 2021年6月26日
ABC の E, F で出題されるレベルのアルゴリズムは難しいですが、時間をかけて理解をし、類題をたくさん解くことで、凡人でもコンテスト中に解けるようになります。 一方で、E, F 問題で出題されるアルゴリズムは事前に知っていないと ほぼ勝ち目がない です。(論文になるようなアルゴリズムを、コンテスト時間中に再発明できる人は稀です。)
僕は ABC までに出題される典型アルゴリズムをほぼすべて習得することで、黄色になれました。 典型をすべて抑えることが、黄色になる一つの方法だと思います。
賛否両論あるかと思いますが、新しいアルゴリズムを勉強した時は、関連する問題を集中して全部解くという精進方法を取ってました。 例えば、F2 線形代数を勉強したら、「F2 線形代数 競技プログラミング」と Google で検索し、hit した問題をすべて解いてました。 そのあと、信頼できる上位陣のコードを読み、ライブラリにできるところはどんどん盗みました。
この方法は、以下のような pros/cons があると思っています。
- メリット:出題パターンを網羅できる。短期集中で習得できる
- デメリット:ネタバレを受けた状態で問題を解くので、より高度な問題(AGC など)への応用力がつきにくい
もちろん、ARC/AGC で勝ちまくって黄色になる人もいると思います。そういう方法に関しては、僕にはできそうにないので、記事に書くことができません。
これから
競技プログラミングからは少し距離を置こうかと思います。 最近は、ABC で勝つためだけの精進をしてきたので、これからは高度な問題をじっくり考えるような精進をしていきます。 当面の目標は、大学同期の TAB (@_____TAB_____) | Twitter にレートで追いつくことです。