hogecoder

tsutaj 競技プログラミングの記録

競技プログラミングで黄色になるまでにやったこと

目標とか

先月末に、めでたく AtCoder 黄色になりました。

きのう、ふと「黄色になりました記事書いてないなぁ」と思って雑に呟いたら、書いてくれという圧力声援を感じたので、記していこうかなと思います。記事の特性上自分語りしかありませんが、それでも良い方はお読みいただければと思います。

自分の能力について

世の中には、プログラミングを始める前から数学が大得意で、 AtCoder を初めて半年くらいで黄色になるような「競技プログラミングをするために生まれてきた天才」*1も中にはいるのですが、そのような人はごく僅かだと思います。

自分は B3 のころ、つまり 2 年半ほど前*2に、 C++ もアルゴリズムも何も知らない状態 (プログラミング経験は講義で C 言語をやっただけで、おそらく灰〜茶程度の実力です) で競技プログラミングを初め、青になるまでに 1 年かかり、黄色になるまでに更に 1 年半かかりました。数学は得意なのかというと、おそらく苦手な方です。高校生の頃は模試で「図形と方程式」の単元が 0 点だったこともありますし、大学入試本番の数学に関しても点数は半分も取れていません。そんな人でも黄色になれるんだなあ、と思っていただければ幸いです。

ステップアップのために何をしてきたか、の部分が多分いちばん見たいところだと思うので、それを中心に書いていきたいと思います。

やったこと

灰から茶へ

自分が競技プログラミングをはじめてからしばらく経ったのち AtCoder のレート制度が始まったのもあり、AtCoder レートにはあまり反映されていないのですが、自分にも灰色や茶色の時代は確かにありました*3。

この頃はまず C++ が書けなかったので、何も見ずにある程度書けるように頑張りました。C++ に慣れるために適しているのは、やはり AtCoder Beginner Contest の A 問題・B 問題あたりかなと思います。始めたての人あるあるだと思うんですが、整数が与えられる問題ばっかり解いてて「そろそろ慣れてきたな〜」ってときに文字列の問題来ると入出力でつまづくので萎えますよね、少なくとも自分はそうでした。自分なりに苦闘しながら、だんだん慣れていきました。そんなこんなで気づいたら ABC の A と B は埋まっていました。

あと競プロを始めたと同時に蟻本を買いました。動的計画法も逆元も何もかもわからなくて大変でした。

茶から緑へ

言語に慣れてくると ABC の B くらいまでは自力で解けるようになってきますが、C 問題はそうもいきません。問題で問われていることを満たすようなアルゴリズムを自分で見つけてこなければなりません。これに対処するには、言語の慣れを鍛えるのではなくアルゴリズムを考える頭の方を鍛えるしかありません。というわけで ABC-C を埋め始めました。また、埋めるだけでは知識が足りないので、蟻本で補いました。 (どのへんをやっていたかはあまり覚えていませんが、初級編と中級の半分くらいはだいたいやったと思います、時間は無限にかかりました)

そうしていくうちに、遅いながらもだんだん C が解けるようになっていきました。

緑から水へ

水色になる前に ABC-C を埋め終わりました。2 〜 3 ヶ月くらいかかった気がします。

その 3 日後に水色になりました。なぜかわかりませんが不服そうですね

水色になるためには ABC の C までが解けると良い、というのは TL でもたまに見ますが、実際そうだと思います。このときはまだ ABC-D はほぼ埋めていません。

ここまで来るのに使った知識は、全探索・BFS・DFS・標準ライブラリなどが主だったと思います。もちろん上に上がるために、蟻本を読んだり ARC の A や B も埋めていたりしていましたが、知識がコンテスト本番中に考察と結びつかず苦しんだ覚えがあります。

水から青へ

水色から青に上がるためには、勉強した知識をコンテスト中に応用できるようになる必要があると感じています。実際、これができるまでにかなり時間がかかりました。どうやったら応用できるのか？という話になりますが、自分の場合はひたすら問題を埋めて対処しました。ツイートを振り返ってみると、水色のうちに ARC の A と B も全て埋めていたようです。ARC の B は結構タフな問題も混じっているので埋めてみると面白いと思います。

問題を埋めていると、だんだん自分が知っていることをコンテスト中に活かせるようになってきました。コンテスト中に DP や最短経路がまともに書けるようになってきたのもこの時期からです。やはり経験は大事なのかなあ、という気がします。

競プロをやっていて印象的だった出来事のひとつとして、自分が出たコンテストでたまたまフローが出題され、それが解けたことで水色から青に上がれたということがあります*4。青になるまでにフローが重要視されることはあまりありませんが、それでも知識を蓄えておくというのはときに役に立つんだなあと思いました。勉強はやっておいて損はないです。

青から黄へ

ここからしばらく停滞が続きました。実際、青から黄色になるまでに 1 年半ほどかかっています。

何をしていたかというと、ABC-D を全て埋めたり、ARC-E をほぼ全部埋めたり*5、TDPC をほぼ全部埋めたり*6、気晴らしに AOJ を埋めたりしていました。あとは、Topcoder の Div1 Easy 埋めが有効とも聞いたので、それをしていた時期もありました。また、確率 DP のスライドなどなど、スライドを積極的に作るのも青になってからのことでした。

こんな感じで基本的には埋めることをしていたのですが、だんだん解説を読まなくなっていきました。というのも、コンテスト中に解法が自力で浮かばないと意味がないので、時間がかかっても良いから自分で思いつけるようにいろいろやっていました。勿論、どれだけ考えてもわからない問題もあるのでその場合は解説を見ます。考察の時間は大体 1 〜 2 時間が目安でしょうか・・・ずっとその問題だけ考えていたら人生が破滅するので、問題を頭の片隅に入れておいて、何か別の作業中にちょっと考えるのが良いかなあと思います。埋めのペースは減っていきますが、だんだん自力で解ける問題の幅が増えていきました。

今年の 5 月に、急激にレートが上がった時期がありました。何が原因でこんなに上がったのかは明確にはわかりませんが、Div1 Easy 埋めや ARC-E 埋めなどを春休みにある程度頑張っていたので、それが結びついてきたのかなあと雑に推測しています。埋めることは即効性はないものの、あとあと大事になってくるのかもしれません。

5 月に入ってから黄色パフォが ARC でも AGC でも取れるようになっていき、先月に黄色の仲間入りができました。

最後に

長々と書き連ねていきましたが、結局やったことは端的に言うと次の通りです。

  • 蟻本を読む
  • AtCoder 中心に、問題を (1800 問くらい) 埋める
    • 特に、ABC は全部・ARC は E まで埋めると良いと思います
  • 数学が壊滅的なので適宜復習したり、自分なりにまとめる

ABC を全部埋める、というとかなりヤバそうに感じますが、AtCoder Problems で一面緑になった問題表を見ることを夢見て頑張ると達成できるかもしれません (とはいえ、自分も 2 年近くかかったので、まあつらいです・・・)

自分の場合は解かないと身につかなかったので実際に解いていましたが、埋めなくとも解法が思いつけば問題はないので、それ相当の考察力を身につけるのも手です。自分にあった方法で磨きをかけると良いのかなと思います。

かなり長くなってしまいましたが、ここまで読んで下さりありがとうございました！いつかオレンジになりました記事も書けるように、もうすこし頑張りたいと思います。

*1:競技プログラマの強い人には数オリ経験者が多そう、という幻想を抱いているんですが、どれくらい確からしいんでしょうか・・・？ちなみに自分は数オリ未経験者です。

*2:AtCoder を始めたのが 2016/5/19 です

*3:コンテストサイトが異なるので一概に比較はできませんが、 Topcoder に関しては始めて 4 ヶ月くらいは灰色でした https://www.topcoder.com/members/Tsutajiro/details/?track=DATA_SCIENCE&subTrack=SRM

*4:C と F で 2 完するという異常者をやっていました

*5:今でも埋まっていない問題が 4 問くらいあります・・・

*6:今でも埋まっていない問題が 3 問くらいあります・・・