AtCoder青色になりました
こんにちは、marocasと申します。このブログの初投稿です。
少し時間が経ってしまいましたが、この度2020/10/31のARC107にてAtCoder青色になることができました!
水色になってから5ヶ月かかりましたが(入水は5月)、その間は大きな壁に直面し、試行錯誤の日々でした。
そのため、青色になれた嬉しさは一入でした!
ついに青になれました
— marocas@デバッグ入力はランダム生成 (@marroncastle917) October 31, 2020
感無量です😂
marroncastle917さんのAtCoder Regular Contest 107での成績:189位
パフォーマンス:2286相当
レーティング:1502→1610 (+108) :)
Highestを更新し、2 級になりました!#AtCoder #ARC107 https://t.co/bdufWgxUxR
書きたいことがたくさんあるのですが、より一般的で役に立ちそうな話を書いていきます。
青になるまでにやったこと
とりあえず、データを貼っておきます。青になってから少し経ってますが、最近精進してないのであまり変わってません(おい)
精進の方針
まずは、精進の方針です。他の方の色変記事を読んでいると精進に関しては、
- 上限を上げる(≒高難易度力を鍛える)精進
- 下限を上げる(≒早解き力を鍛える)精進
の二つに分類されているのをよく見かけます。
私もこの分類に賛成で、「上限を上げる精進」をさらに二つに分け、以下の3つに分類しています。
A. 知識を増やす精進
B. 考察力を鍛える精進
C. 早解き力を鍛える精進
この3つを自分の状況に合わせてバランスよく組み合わせ、さらに効果を意識しながらやっていくことがレーティング上昇につながると考えています。
筋トレでも効果のある部位を意識しながらやった方が効果が出るという話をよく聞きますが、競プロでもそれは同じです。
これらを踏まえて、水色になってから青になるまでにやったことを、それぞれ上記A,B,Cのどれに当てはまるのかという観点で分類すると以下のようになります。
各精進の詳細は後ほど説明します。
1. 精選150問・AtCoder版蟻本・AtCoderTags・EDPC・ACLPC 埋め
これらは自分の中で「A. 知識を増やす精進」と位置付けています。
特に水色時代の後半はこれらを最重要視していました。
知識を使いこなせるよう演習もするので「B. 考察力を鍛える精進」にもなります。
2. 令和ABC埋め・貪欲埋め
これらは、知識・考察・早解きの全てに効果のある精進です。
上記の知識精進で漏れる部分を補う意図がありました。
3. あさかつ・くじかつ
おなじみのバチャ(バーチャルコンテスト)です。バチャは知識・考察・早解きの全てに効果のある優れた精進方法ですが、自分の中では精進方針・モチベがない時期に状況を脱却するためにやる位置付けです。C++の特訓にも使いました。
4. コンテスト参加(AtCoder・CodeForces・yukicoder・その他大学コンテスト等)
コンテストは本番であると同時に、B. 考察力・C. 早解き力を鍛える貴重な機会という位置付けです。終了後にはしっかり復習をして足りなかったA. 知識を補います。
5. C++練習
競プロを始めてからずっとpythonを使ってきたのですが、最近C++を併用し始めました。これはちょっと別枠なのですが、あえて分類するとA.知識精進になります。
大枠は以上です。知識と考察力は切っても切り離せない関係ですが、水色時代の後半は特に知識精進をかなり重視して取り組んでいました。理由は以下です。
- 7月にやっていたバチャで知識不足を痛感したから
- 競プロをやる大きな目的の一つがアルゴリズムに詳しくなることだから
- 受験数学で鍛えた考察力にある程度自信があり、知識さえあれば何とかなると思っているから
知識精進には大きな特徴があり、それについて過去にツイートしています。
あるアルゴリズムを学んだら、それがコンテスト本番で出題されるまではレートに直接影響しないけど出題された途端に影響するので完全にセグ木の遅延評価と同じだな
— marocas@デバッグ入力はランダム生成 (@marroncastle917) November 23, 2020
つまり、知識が増えてもすぐにはレーティングに反映されません。ですが、定期的に復習をして忘れないようにしていれば、長い目で見たときに確実に効果が出る精進であることも確かです。実際、8月~10月上旬にかけて頑張った分の効果が11月になった今になって出ていると強く感じています。
各精進の詳細
分野別 初中級者が解くべき過去問精選100問(入水まで)・150問(8月~9月)
E869120さんによる色変するための問題集で、量がちょうど良く埋めやすいです。
水色までに100問を7割、青色までに150問を7割埋めました。
AtCoder版蟻本(4月~10月)
けんちょんさんによる、蟻本の例題に対応するAtCoderの問題がまとめられた記事です。精選に比べると問題量が多いですが、その分網羅性が高いので併用がおすすめです。量が多く、そもそも蟻本がかなり前に書かれていて現代における難易度順と少しずれているため、前から順に埋めようとせず、必要を感じた順に埋めていくと良いと思います。
こちらは現段階でまだ初級編が半分程度、中級編は3割程度しか埋められていません。
難易度評価が低い方にずれがちなのは注意です...
AtCoderTags
知識精進をしていて、精選150問とAtCoder版蟻本だけでは物足りない、もっと類題を解きたいと思った場合に活用しました。このサイトは、ユーザーによるタグ付けを基に分野別に問題にアクセスすることができます。貪欲埋めをする際にも使いました。
EDPC(4月、7月~9月)
おなじみのEducational DP Contest、いろんなDPの詰め合わせです。
以前はDPが苦手だったのですが、これを埋めたことによってDPで遅れを取ることはなくなりました。全競プロerにお勧めできます。
前から解けるところまで解いて、分からなくなったら解説記事などを検索して読んでいました。まだ26問中22問しか埋まっていないので、あと4問頑張ります。
ACLPC(9月~10月)
AtCoder LibraryというC++用のAtCoder公式ライブラリをverifyするための問題集ですが、アルゴリズム習得に活用しました。まずpythonで1周し、C++を学んでからはAtCoder Libraryを使ってもう1周しました。
令和ABC水・青diff埋め(9月~10月上旬)
個人的にはあまり難易度別の「全埋め」にはこだわりがないのですが、それでも令和ABC(6問になってからのABC)だけは埋めました。なぜなら、解いている人が多く競プロerの中で共有知識となっており、扱われたテーマが再出題された場合に解いていないと明らかに不利だからです。それだけ問題の質が高く、全競プロerにお勧めできます。水・青diffを全埋めしました。
貪欲埋め(8月)
コンテスト結果を分析していたら茶diffぐらいの貪欲問題が苦手であることが分かったので、AtCoderTagsを利用してそこら辺の問題を徹底的に解きました。結果的に灰diffから青diffまで数日間で50問程度解きました。貪欲って知識としてまとめづらい分野なので、知識精進しかしていないと漏れてしまう分野であることから個別に対処した、という側面があります。
あさかつ・くじかつ(7~8月)
青以下の色変記事ではおなじみのバチャ(バーチャルコンテスト)です。水色になるまでは結構やっていて、水色になってからも7月頃は毎日やっていました。水色になってすぐの6~7月はかなり精進モチベが下がっていましたが、これで回復しました。
CodeForces(8月~)
ロシアのコンテストサイトです。8月からratedの3回に1回ぐらいは出ています。
以下のようにまだ特徴を掴み切れていないのですが、数学問題が少ない分より純粋なアルゴリズム力を測れて良いな、と思ったりしています。
各人のAtCoderとコドフォに対する相性がどう決まるのか未だに言語化できてない。
— marocas@デバッグ入力はランダム生成 (@marroncastle917) November 21, 2020
AtCoderの方が数学問題が多い、コドフォは数列操作がやたらと多いのは確かだと思うけど他にも要因がありそう
yukicoder・その他大学コンテストなど
yukicoderは有志によるコンテストサイトで、毎週金曜日にコンテストが開催されていています。コンテストの特徴として数え上げや数学問題が多い、考察典型を習得できる問題が多いと感じています。私は数え上げが得意分野なのですが、青diffレベルまで確実に解けるようになったのはyukicoderに鍛えられたおかげです。
考察典型はアルゴリズムやデータ構造に焦点を当てる私の知識精進のやり方では漏れやすい要素なので、実力向上に大変役立っています。
その他大学コンテスト等もできるだけ参加していました。面白い問題が多く、コンテスト時間が長くてコンテスト中に新しくアルゴリズムを学んでACするなど知識精進にもなり、とても楽しかったです。
一連のUPCでたくさん新しいこと学んだのでまとめます
— marocas@デバッグ入力はランダム生成 (@marroncastle917) September 21, 2020
WUPC : 約数系包除・全方位木DP
HUPC day2 : ダブリング(その場履修AC)
AUPC day2 : pythonでDP通らなかったのでC++本番初AC
AUPC day3 : 強連結成分分解(その場履修AC)
そのうち作問もしてみたいなと思っています。
プログラミング言語の問題
私は競プロを始めてからずっとpythonだけを使ってきたのですが、pythonistaとして避けては通れないのが言語の問題です。
詳しくは書きませんが、一般的に競プロにおいてpythonという言語は、低難易度の問題にはかなり強みを発揮できるが、高難易度には弱いという傾向があります。緑・水色ぐらいになって高難易度(水diff以上)の問題も解くようになると、この問題に直面し出します。
pythonで橙・赤になられている方もいらっしゃいますし、最近では青・黄コーダーもかなり増えていたのでpython・pypyだけで上位に行けないということはありません。ですが、個人的には相性の問題があると思っていて、自分の場合はpythonで数々直面するデータ構造や定数倍高速化の問題が原因でコンテストで失敗することが多くなったので、C++と併用することに決めました。
C++を使い始める前にnumba, Cythonなどpython系の高速化手段に色々手を出したのですが、情報量の少なさや汎用性の点などを考慮するとやはりC++が良いと判断した次第です。
C++を使い始めたのは水色時代の終盤(10月頃)なので、青になる上で直接効果があったかは分かりません。ですが、pythonだとTL厳しいなっと思った時に迷わずC++で実装を始められることによって、少なからず時間を短縮できたりTLEするリスクを減らせているのではないかと思います。
やったことは以下です。
これらを徹底してやっていたら本番でもなんとか使えるレベルになりました。
精進指針の決め方と分析の重要性
続いて、精進方針をどうやって決めたら良いのか?というより一般的なテーマに挑戦してみます。
最初に断っておくと、精進方針はこうやって決めるべき!という主張をしたいわけではありません。精進の具体的方法を示すよりも一段階メタ的な視点で、精進方法の決め方の一例を示すという程度の意図ということで、ご理解ください。
そもそも何のために精進をするのかということなのですが、少なくとも以下の2つの目的があると思います。
- 競技プログラミングの実力向上
- 精進自体を楽しむ
競プロをやっている目的は何で自分は何を楽しいと思うのかをよく考えて、その欲求を満たしかつ実力向上に結びつく精進指針を定めていくのが良いと思っています。
色変記事には必ずといって良いほど「この精進の方針は自分に合っているだけなので、自分で合っている精進を自分で見つけてやりましょう」みたいなことが書いてあります。
ですが、自分に合う精進ってどうやって見つけるのでしょうか?
その答えは分析だと私は考えています。
分析といっても細かい数値とにらめっこするところから始まるわけではなく、まずは直感からです。コンテストに何回も参加していると、自分は早解きが苦手だなとか、DPが苦手だなとか、色々と気づくことがあるでしょう。そのように自分の弱点に気づいたら、その弱点に対して効果的な精進方法を他人の方法なども参考にしながら考え、実行し、効果が出ているか検証することを繰り返します。さほど苦労せずにどんどん強くなっているように見える人というのは、このプロセスを自然と実行できているはずです。
しかし、どうにも伸びないが直感では何が悪いのか分からないという場合もあります。そのような場合、一つの選択肢としてコンテスト結果を詳細に分析するのがおすすめです。
以下は、8月初めに私が行った分析に関するツイートです。
過去15回分のABC級コンテストのC~Fについて問題の特徴と自分の結果を徹底分析してみたところ、
— marocas@デバッグ入力はランダム生成 (@marroncastle917) August 2, 2020
・数学、数え上げ、探索が得意
・貪欲、DPを用いる最大最小問題がめちゃくちゃ苦手(ほぼ全敗)
なことが分かった。
最近調子が悪いのは苦手な分野からの出題が多いからであることが明白になった。 pic.twitter.com/tIYOruzvmg
8月に貪欲埋め、7~9月にEDPCに取り組んだのは、この時の分析がきっかけです。EDPCに関しては分析の前から始めていましたが、よりモチベーションが上がりました。これらは直感では気づいていなかった部分だったので、詳細に分析した甲斐がありましたし、結果としてその後この二つの分野が足を引っ張るケースは少なくなったと感じています。
分析をきちんとするメリットとして、メンタルが安定します。なぜなら
- 失敗しても何が原因だったかが分かるので、次何をすれば良いか明確になる。成長のためのヒントを得たと思えるから
- 成功した場合でも何が成功の要因だったか分かるので、今後もその要因を外さなければ成功し続けられると自信を持てるから
です。後者については、もちろん実際には新たに失敗要因が出現するので成功がいつまでも続くということはないのですが、そういう場合もその都度失敗要因を潰せば良いだけなので、特に心配することはありません。
このようにきちんと分析をすることがメンタルの安定に寄与し、努力し続けることができます。
ここまでやるのはやりすぎじゃないかと自分でも思うのですが、このような感じで早解きが苦手だと思えば自分の実力と同じか一つ下程度のdiffをタイムを意識して解いていくのが有効でしょうし、コンテスト形式での練習が不足していると感じるならバチャをやるのが良いでしょう。
何にせよその人なりの感性とロジックで、そのときやりたい、やるべきと思う精進をしていくのが一番なのですが、ここではそのロジックの一例を示してみました。どなたかの参考になれば幸いです。
今後の精進の方針
とりあえず当面は余裕がないのでコンテストの参加と復習のみを着実にこなしていき、その都度出現した弱点を潰していきます。予想としてはこのまま行くとAtCoderではレーティング1800前後(青の真ん中)、CodeForcesでは2000前後(紫の真ん中)で停滞するでしょう。
修論が終わったら少し余裕ができると思うので、そうなったらこれまで同様知識精進に注力しつつ、青・黄diff埋めを進めて考察力向上・考察典型の習得にも取り組むつもりです。
さらに、レベルが上がるに連れて早解き力の不足を感じるタイミングが遅かれ早かれ訪れるはずなので(過去にも茶色のときと水色のときにそれぞれ訪れました)、そうなった段階で対処をしていきます。
ここまでやればAtCoderで黄色になれると思っています。目標は来年の3月までです。
思い通りに行かない場合はバチャを取り入れるなり、状況に応じて対処をしていきます。
さいごに
いつもTwitterでフォローしているみなさんのツイートから有益で面白い情報を吸収させていただいてとても感謝しています。普段絡んでくださっている方は特に、これからもよろしくお願いします。
一応これで完結なのですが、まだ書きたいことはあるので余裕があったら2記事目を書きます。ここまで長文をお読みいただきありがとうございました!