marocasの競プロ精進日記

競技プログラミングの精進日記です

AtCoder青色になりました

こんにちは、marocasと申します。このブログの初投稿です。

少し時間が経ってしまいましたが、この度2020/10/31のARC107にてAtCoder青色になることができました！

f:id:love_language:20201122101216p:plain

青入りを決めたARC107の順位表

水色になってから5ヶ月かかりましたが(入水は5月)、その間は大きな壁に直面し、試行錯誤の日々でした。

そのため、青色になれた嬉しさは一入でした！

 

 

f:id:love_language:20201120094211p:plain

レーティング遷移

書きたいことがたくさんあるのですが、より一般的で役に立ちそうな話を書いていきます。

青になるまでにやったこと

とりあえず、データを貼っておきます。青になってから少し経ってますが、最近精進してないのであまり変わってません（おい）

f:id:love_language:20201123013742p:plain

Rating Histroyより

 

f:id:love_language:20201123013836p:plain

Difficulty Pies

精進の方針

まずは、精進の方針です。他の方の色変記事を読んでいると精進に関しては、

  1. 上限を上げる（≒高難易度力を鍛える）精進
  2. 下限を上げる（≒早解き力を鍛える）精進

の二つに分類されているのをよく見かけます。

私もこの分類に賛成で、「上限を上げる精進」をさらに二つに分け、以下の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.知識精進になります。

 

大枠は以上です。知識と考察力は切っても切り離せない関係ですが、水色時代の後半は特に知識精進をかなり重視して取り組んでいました。理由は以下です。

  1. 7月にやっていたバチャで知識不足を痛感したから
  2. 競プロをやる大きな目的の一つがアルゴリズムに詳しくなることだから
  3. 受験数学で鍛えた考察力にある程度自信があり、知識さえあれば何とかなると思っているから

知識精進には大きな特徴があり、それについて過去にツイートしています。

つまり、知識が増えてもすぐにはレーティングに反映されません。ですが、定期的に復習をして忘れないようにしていれば、長い目で見たときに確実に効果が出る精進であることも確かです。実際、8月~10月上旬にかけて頑張った分の効果が11月になった今になって出ていると強く感じています。

 

各精進の詳細

分野別　初中級者が解くべき過去問精選100問(入水まで)・150問(8月~9月)

E869120さんによる色変するための問題集で、量がちょうど良く埋めやすいです。

水色までに100問を7割、青色までに150問を7割埋めました。

qiita.com

AtCoder版蟻本(4月~10月)

けんちょんさんによる、蟻本の例題に対応するAtCoderの問題がまとめられた記事です。精選に比べると問題量が多いですが、その分網羅性が高いので併用がおすすめです。量が多く、そもそも蟻本がかなり前に書かれていて現代における難易度順と少しずれているため、前から順に埋めようとせず、必要を感じた順に埋めていくと良いと思います。

こちらは現段階でまだ初級編が半分程度、中級編は3割程度しか埋められていません。

難易度評価が低い方にずれがちなのは注意です...

qiita.com

AtCoderTags

知識精進をしていて、精選150問とAtCoder版蟻本だけでは物足りない、もっと類題を解きたいと思った場合に活用しました。このサイトは、ユーザーによるタグ付けを基に分野別に問題にアクセスすることができます。貪欲埋めをする際にも使いました。

atcoder-tags.herokuapp.com

EDPC(4月、7月~9月)

おなじみのEducational DP Contest、いろんなDPの詰め合わせです。

以前はDPが苦手だったのですが、これを埋めたことによってDPで遅れを取ることはなくなりました。全競プロerにお勧めできます。

前から解けるところまで解いて、分からなくなったら解説記事などを検索して読んでいました。まだ26問中22問しか埋まっていないので、あと4問頑張ります。

atcoder.jp

ACLPC(9月~10月)

 AtCoder LibraryというC++用のAtCoder公式ライブラリをverifyするための問題集ですが、アルゴリズム習得に活用しました。まずpythonで1周し、C++を学んでからはAtCoder Libraryを使ってもう1周しました。

atcoder.jp

令和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回ぐらいは出ています。

以下のようにまだ特徴を掴み切れていないのですが、数学問題が少ない分より純粋なアルゴリズム力を測れて良いな、と思ったりしています。

yukicoder・その他大学コンテストなど

yukicoderは有志によるコンテストサイトで、毎週金曜日にコンテストが開催されていています。コンテストの特徴として数え上げや数学問題が多い、考察典型を習得できる問題が多いと感じています。私は数え上げが得意分野なのですが、青diffレベルまで確実に解けるようになったのはyukicoderに鍛えられたおかげです。

考察典型はアルゴリズムやデータ構造に焦点を当てる私の知識精進のやり方では漏れやすい要素なので、実力向上に大変役立っています。

その他大学コンテスト等もできるだけ参加していました。面白い問題が多く、コンテスト時間が長くてコンテスト中に新しくアルゴリズムを学んでACするなど知識精進にもなり、とても楽しかったです。

そのうち作問もしてみたいなと思っています。

 

プログラミング言語の問題 

私は競プロを始めてからずっとpythonだけを使ってきたのですが、pythonistaとして避けては通れないのが言語の問題です。

詳しくは書きませんが、一般的に競プロにおいてpythonという言語は、低難易度の問題にはかなり強みを発揮できるが、高難易度には弱いという傾向があります。緑・水色ぐらいになって高難易度(水diff以上)の問題も解くようになると、この問題に直面し出します。

pythonで橙・赤になられている方もいらっしゃいますし、最近では青・黄コーダーもかなり増えていたのでpython・pypyだけで上位に行けないということはありません。ですが、個人的には相性の問題があると思っていて、自分の場合はpythonで数々直面するデータ構造や定数倍高速化の問題が原因でコンテストで失敗することが多くなったので、C++と併用することに決めました。

C++を使い始める前にnumba, Cythonなどpython系の高速化手段に色々手を出したのですが、情報量の少なさや汎用性の点などを考慮するとやはりC++が良いと判断した次第です。

C++を使い始めたのは水色時代の終盤(10月頃)なので、青になる上で直接効果があったかは分かりません。ですが、pythonだとTL厳しいなっと思った時に迷わずC++で実装を始められることによって、少なからず時間を短縮できたりTLEするリスクを減らせているのではないかと思います。

やったことは以下です。

  1. APG4b
  2. あさかつやunratedコンテストの本番をC++縛りで解く
  3. ratedコンテストの終了後にpythonでACした全問題をC++で解き直す

これらを徹底してやっていたら本番でもなんとか使えるレベルになりました。

f:id:love_language:20201122100710p:plain

10月頃C++精進を始めて、先日100ACしました

 

精進指針の決め方と分析の重要性

続いて、精進方針をどうやって決めたら良いのか？というより一般的なテーマに挑戦してみます。

最初に断っておくと、精進方針はこうやって決めるべき！という主張をしたいわけではありません。精進の具体的方法を示すよりも一段階メタ的な視点で、精進方法の決め方の一例を示すという程度の意図ということで、ご理解ください。

そもそも何のために精進をするのかということなのですが、少なくとも以下の２つの目的があると思います。

競プロをやっている目的は何で自分は何を楽しいと思うのかをよく考えて、その欲求を満たしかつ実力向上に結びつく精進指針を定めていくのが良いと思っています。

色変記事には必ずといって良いほど「この精進の方針は自分に合っているだけなので、自分で合っている精進を自分で見つけてやりましょう」みたいなことが書いてあります。

ですが、自分に合う精進ってどうやって見つけるのでしょうか？

その答えは分析だと私は考えています。

分析といっても細かい数値とにらめっこするところから始まるわけではなく、まずは直感からです。コンテストに何回も参加していると、自分は早解きが苦手だなとか、DPが苦手だなとか、色々と気づくことがあるでしょう。そのように自分の弱点に気づいたら、その弱点に対して効果的な精進方法を他人の方法なども参考にしながら考え、実行し、効果が出ているか検証することを繰り返します。さほど苦労せずにどんどん強くなっているように見える人というのは、このプロセスを自然と実行できているはずです。

 しかし、どうにも伸びないが直感では何が悪いのか分からないという場合もあります。そのような場合、一つの選択肢としてコンテスト結果を詳細に分析するのがおすすめです。

以下は、8月初めに私が行った分析に関するツイートです。

 

 

8月に貪欲埋め、7~9月にEDPCに取り組んだのは、この時の分析がきっかけです。EDPCに関しては分析の前から始めていましたが、よりモチベーションが上がりました。これらは直感では気づいていなかった部分だったので、詳細に分析した甲斐がありましたし、結果としてその後この二つの分野が足を引っ張るケースは少なくなったと感じています。

分析をきちんとするメリットとして、メンタルが安定します。なぜなら

  • 失敗しても何が原因だったかが分かるので、次何をすれば良いか明確になる。成長のためのヒントを得たと思えるから
  • 成功した場合でも何が成功の要因だったか分かるので、今後もその要因を外さなければ成功し続けられると自信を持てるから

 です。後者については、もちろん実際には新たに失敗要因が出現するので成功がいつまでも続くということはないのですが、そういう場合もその都度失敗要因を潰せば良いだけなので、特に心配することはありません。

このようにきちんと分析をすることがメンタルの安定に寄与し、努力し続けることができます。

 

ここまでやるのはやりすぎじゃないかと自分でも思うのですが、このような感じで早解きが苦手だと思えば自分の実力と同じか一つ下程度のdiffをタイムを意識して解いていくのが有効でしょうし、コンテスト形式での練習が不足していると感じるならバチャをやるのが良いでしょう。

 

何にせよその人なりの感性とロジックで、そのときやりたい、やるべきと思う精進をしていくのが一番なのですが、ここではそのロジックの一例を示してみました。どなたかの参考になれば幸いです。

今後の精進の方針

とりあえず当面は余裕がないのでコンテストの参加と復習のみを着実にこなしていき、その都度出現した弱点を潰していきます。予想としてはこのまま行くとAtCoderではレーティング1800前後(青の真ん中)、CodeForcesでは2000前後(紫の真ん中)で停滞するでしょう。

修論が終わったら少し余裕ができると思うので、そうなったらこれまで同様知識精進に注力しつつ、青・黄diff埋めを進めて考察力向上・考察典型の習得にも取り組むつもりです。

さらに、レベルが上がるに連れて早解き力の不足を感じるタイミングが遅かれ早かれ訪れるはずなので（過去にも茶色のときと水色のときにそれぞれ訪れました）、そうなった段階で対処をしていきます。

ここまでやればAtCoderで黄色になれると思っています。目標は来年の3月までです。

思い通りに行かない場合はバチャを取り入れるなり、状況に応じて対処をしていきます。

さいごに

いつもTwitterでフォローしているみなさんのツイートから有益で面白い情報を吸収させていただいてとても感謝しています。普段絡んでくださっている方は特に、これからもよろしくお願いします。 

一応これで完結なのですが、まだ書きたいことはあるので余裕があったら2記事目を書きます。ここまで長文をお読みいただきありがとうございました！