AtCoder青色になるまでにしたこと

Jan 2, 2020 20:16 compro

こんにちは。お久しぶりです。ますぐれです。 さて、タイトルの通り AtCoder 青色になりました。

レートの推移

大学を卒業するまでに青色を達成するのが目標だったので、3カ月ほど早い達成となります。一時期伸び悩んでいて間に合うか微妙なくらいだったのですが、最近調子が良くてとんとん拍子で上がっていきました。

というわけで、色が変わったのでそれまでにしてきたことをブログにしたいと思います。恒例の奴です。

灰色～緑

過去問とかは特にやらず、時々コンテストに出ていたら緑にはなっていました。地力がここらへんだと思います。

能力的には、数学的思考力はこのレベル帯では十分、実装力は普通くらい、アルゴリズムは何もわからんという感じでした。 受験数学をある程度ちゃんとやっていて、大学入ってからプログラミングを始めた典型的な理系大学生という感じだと思います。

アルゴリズムが分からんのレベルですが、所謂全探索系の問題すら通せませんでした。解の候補を全部列挙して調べる、みたいな処理が苦手だったのを覚えています。また、計算量に関する知見もなかったので、とにかくfor2重ループを避けるみたいな謎のことをしていました。もちろんDPやグラフ系の問題なんて全く無理です。

昔の AtCoder はそれでも緑くらいにはなれる、というのが今だと信じられないかもしれませんね。個人的な気持ちですが、今はこのレベルだとまず無理な気がします。多分茶色になれるかなれないかくらいじゃないでしょうか。

緑から水色になるまで

さて、競プロに目覚めたのは大体2019年の1月です。この頃から蟻本を買って真面目に競技プログラミングを始めました。この時期に始めた理由は、「水色になっておけば就活で数学的思考能力をアピールするのに便利そう」という気持ちがあったからです。従って水色になったらさっとやめるつもりだったんですが、なんか普通に面白くてそのままずぶずぶとハマっていった感じです。

前述のとおり自分の弱点はアルゴリズムです。このことには当時から気づいていたので、まずはアルゴリズムの勉強をしました。基本戦略としては、コンテスト中に解けなかった問題のうち最も簡単なものを解説読みながらしっかり通すということをしていました。基本的には平成ABC-Dレベルです。解説が最初少し行間が広くて読みづらいかもと思ったのですが、雰囲気に慣れたらスラスラ読めるようになりました。

あと外せないこととしては、標準ライブラリの使い方をちゃんと勉強しました。標準ライブラリというのは頭のいい人が実装したバグっていないコードなわけで、使わない手はないわけです。たくさん助けられました。

そんな感じの勉強を積み重ねて、データ構造とかを使わないといけない問題とかを通せるようになってきたあたりで水色になりました。水色になるまでに勉強したこととしては

  • 全探索
  • DFS/BFS
  • bit全探索
  • 累積和
  • 優先度付きキュー
  • グラフのデータの持ち方(隣接リスト)
  • UnionFind

辺りが挙げられます。グラフの問題をさばけるようになったらなんか競技プログラミングしているぞ！　って気分になれて楽しかったです。

上にDPやにぶたんがないんですが、学校の講義で少しかじってはいたので存在は知っていました。めっちゃ自明なDP問とかはたぶんこの頃から通せましたが、習熟していたとは言い難いので外しています。

水色から青になるまで

さて、水色になってすぐABCが令和ABCになったのでratedコンテストの数はあまり変わりませんでした。いいタイミングで昇格したと思っています。

水色からも基本的な戦略は変わらないですが、それに加えて日常的に過去問を解くようになりました。

序盤

水色になったのですが、この頃はまだ300が安定しているとは言えない状況だったので、簡単目な問題に多く取り組んでいました。

具体的にはAtCoder版！蟻本(初級編)の問題のうち、ある程度習熟しているテーマの過去問に取り組んだりしました。これは類題を見ることで頭の中の問題マップを育てる目的でやったと思います。

そうこうしているうちに300はかなり安定するようになり、8月あたりに大当たりを2回引いてhighest 1463を記録します。大当たりを引いた理由はあまりよく分かりません。確か、AGCの嘘解法をさっと通して伸びた気もしています(オイ)

中盤

大当たり直後に激冷えを2回引いてレートを100近く溶かしました。

激冷え回はABCとAGCでそれぞれ一回ずつあるんですが、どちらも冷静になれば通せるはずの問題を落とす、という形で経験しました。これが非常に悔しかったです。

地力を上げればこういう事故は減らせるのかなと思って、difficultyが水色の問題を中心に電車の中で考察をして思いついたら実装をするみたいなことを始めました。最初の頃はよく嘘解法を錬成していたのですが、時間がたつにつれてだんだんとピントの合った考察ができるようになっていきました。

その努力が実る回はかなりいいパフォーマンスを発揮できるようになってきたのですが、それでも大爆発が頻繁に発生していました。このことから、地力を上げるという戦略は爆発力は増せど、レートの安定には寄与しなさそうということが推察されます。

戦略を立て直すためにこのタイミングでもう一度なんでレートが下がったのかを考えてみると、時々激冷えするのは時間を気にしすぎて考えがまとまらないままコーディングに走っているからという結論に至りました。

コンテスト中というのは結構緊張しているのに、普段の練習でしないようなコーディングスタイルを焦りながら始めたらバグを埋め込まないわけがありません。さらに、考察不足のまま突っ込んでWAが出ると、実装のミスなのか考察のミスなのかの切り分けがかなり難しくなります。そして何もわからなくなって焦ってそのまま自爆……みたいな結果を招きます。

これを直すために、今は紙の上で疑似コードレベル(添え字を合わせるとか)になるまでちゃんと考察してから実装に移るようにしています。これはmaspyさんの橙昇格記事を読んで、自分に足りない部分を補ってくれるなあと思って取り入れたフローです。

競技プログラミング用のツイッターアカウントを見ている方はご存知かもしれませんが、ぼくは問題を解いたときに考察に何分、実装に何分かかったのかを記録しています。記録することで疑似的にコンテストの状況を作れ、雑な考察をすると実装で時間が解けるということを体感できます。一石二鳥です。

↑をするために、適正レベルの問題は電車ではなくその場で時間を作って考察するようにし、電車では青上位～黄色レベルの考察をするようにしました。また、コンテスト中もほぼ同様のスタイルで問題を解くようにしました。練習は本番のように、本番は練習のように……という奴です

水色終盤

このスタイルの練習に加えて、DPやにぶたんといった典型的な問題をAtCoder版蟻本やEDPCでさらいました。その結果、本番でやべえやらかしをすることがほぼなくなり、水後半～青パフォが安定しました。

あとこの頃からコンテスト中に順位表のお気に入り表示をコンテスト中はしないようにしました。友達や後輩が通していて自分だけ通せてないみたいな状況を見るのは好奇心を満たす以外のメリットはありません。メンタルが弱い自分みたいな人間にとってはデメリットしかありません。順位表で全参加者のうち何人がどの問題を解いているのかということ以外をチェックするのは時間の無駄です。レートを上げたいなら即刻やめたほうが良い行動だと思います(気になるのはめっちゃ分かるんですけどね……)

適正レベルの問題を時間を計って解く、スタイルを固定する、というのが自分に結構あっていたようで、これのおかげでABC-Eまではほぼコンテスト内に食らいつけるようになってきました。最近は難しいFを通せるように頑張っています。

こんな調子でやっていたら、簡単なときのABCで全完して初の黄パフォを出したりして青色になりました。

水色のまとめ

水色ではアルゴリズム、というよりは500-600レベルの問題の考え方やコンテストへの向き合い方といった部分をちゃんとすることでレートを伸ばしていった気がします。

実際水色になってちゃんと勉強したアルゴリズム・データ構造は

  • dijkstra等の最短経路アルゴリズム
  • 二分探索 (三分探索も少し)
  • DP(基本的なもの)
  • セグ木
  • imos法
  • 最小全域木(クラスカル法だけ)

くらいだと思います。最小全域木とimos法、三分探索は多分コンテスト中に使ったことないです。逆にセグ木は想定解じゃなくても使えると思ったら張りまくっています。めっちゃ便利ですよね。

そして、これを見るとやはり蟻本は初級編+中級編の一部だけでもかなりいい範囲をカバーしているように思います。まだ通読はしていないので、卒論終わった後の暇な時間で読みたいなあと思っています。

水色初期と比較して一番強くなった点としては、問題を見てから解法を紙で作るまでの時間がかなり短くなった点が挙げられます。あとコーナーケースの発見速度も上がりました。これは考察と実装を切り分けたことで脳内リソースが整理された結果なんじゃないかと思っています。

今後

黄色パフォも一回出すことに成功しましたが、正直アレを連続で出せる気がしません。まずは水落ちしないくらいにレートを安定させて、使える手札を増やしつつ難しめの問題にチャレンジしていくという風にやっていきたいです。

黄色になるためには恐らく+1問解けるようになることが要求されていると思うので、今までよりも考察に比重を寄せた練習をしていきたいかなと考えています。