はてぃーぽったーの備忘録

某授業まとめ+競プロの感想記事

Atcoderで水色になるまでにやったこと

競プロ記事初投稿です.今回はAtCoderで入水するまでにやったことを時系列でまとめていきたいと思います.まずはレートの変遷と累計AC数のグラフを見てみましょう.

f:id:mkwamezaki1007:20191222233835p:plain

レートの変遷

f:id:mkwamezaki1007:20191222233606p:plain

AC数の変遷

僕が競プロを始めたのは1年と半年ほど前です.周りがやってて楽しそうだなーと思ったのが主ですが,コードを書く時間を確保するという側面もありました.大学の講義でコード書く時間はあまり多くないので.

始めた当初は当時の講義で使っていたJavaを使っていましたが,書くのに時間がかかるのとpython書くのにも慣れといたほうがいいのでは,とのことでpython3に乗り換えました.2018年の11月の末の方ですね.この辺りは割とトントン拍子にレートが伸びていきました.自分の周りの友人が早々に入水していったので,このまま自分もそれに続けるだろうと,漠然と思っていました.

 

それがとんでもない間違いだったのです。

 

自分のレートが停滞し始めたのは,令和ABCが始まって間もなくでした.レートの変遷を見ると,7月頃から伸び悩むどころかむしろ縮んでいる時期さえ見て取れます.コンテストに数回出て,パフォがだんだん落ちてくるのを感じました.自分の実力はあまり変わっていないことと参加者のレベルが爆発的に上昇していくことに危機感を覚え,この頃から本格的な精進を始めました.ここから自分がやったことを時系列で挙げていきます.

 

1. AtCoder Scoresを使って300点問題を埋めた + 使用言語をC++に変えた

自分には,精進量も考察力も実装力も何もかも足りていませんでした.とにかく考える時間を増やし,自分の考えをコードで再現する.その作業をひたすらに繰り返しました.

また,使用言語もC++に変えました.pythonだから通せなくてC++なら通せる,ということを経験したことは一度もありませんが,C++ユーザがかなりの割合を占めているという現状から,今後何かと都合のいいことが多いだろうと思い使用言語を変更しました.(なお.今でも小数が絡む問題にはpythonを使うことが多いです) 学んだアルゴリズムとして印象的なのはbit全探索ですかね.当時はまだ全探索が可能ならやる,という意識が無かったので自分の中ではとても革命的な発想でした.

 

それでもレートは上がりません.

 

2. Atcoder Problemsを使って緑difficultyの問題を埋めた

300点を埋め終わって400点問題に差し掛かったころ,AtCoder Problemsに非常に便利な機能が追加されました.それは過去の問題に対して推定難易度を付けるというもので,実際当時の自分には非常に歯応えがあり,かつ頑張れば解けるという問題を効率的に解くことが出来ました.友人の力も借りて,どうにか埋めることが出来たのは夏休みが明けて間もなくのことでした.だんだんと自分に考察力が付いていくのを感じました.この頃から組み合わせの問題を解く時にmod逆元を使い始めた気がします.けんちょんさんの記事を何度も読んで理解に努めました.

 

それでもレートは上がりません.

 

まあでもここまでで上がらないのは予想の範囲内でした.だって水difficultyが解けないのですから,本番で水パフォはなかなか出ません.この頃はまだ自分の停滞に対して楽観的でした.

 

3. Atcoder Problemsを使って水difficultyの問題を埋め始めた 

 この辺りの問題から,探索のコードを書くことが増え,自分の中での探索を始めとした種々のアルゴリズムの書き方が固まってきました.書くことが多かったのは再帰でのdfsとワーシャルフロイド,累積和,めぐる式二分探索(超重要)ですかね.特にdfsは自分の中で書き方をパターン化できるくらいには書いたと思います.あと累積和はStatic Sushiを解くときに,これが累積和を"使いこなす"ってことか…と実感しました.めぐる式にぶたんは言わずもがなと言ったところ.開区間のちからってすげー。

用いた特徴的なデータ構造として記憶に残っているのはUnion-Findぐらいでした.

 

それでもレートは上がりません.

 

4. 水difficultyの問題を埋める一環でデータ構造を履修し始めた + EDPCを始めた

このあたりでいい加減に逃げ続けてきたデータ構造に立ち向かおうということでセグ木を書いてみました.まだコンテストで使ったことはないですが,区間操作についての理解が多少深まりました.

また,dpに関して何も分からん状態だったのでEDPCを徐々に埋め始めました.なかなかdpは他の考察とは毛色が異なるので,集中的に鍛えるのにとても都合が良い教材でした.

 

それでもレートは上がりません.

 

5. コンテスト前にケーキを食べ始める

コンテストを迎えるコンディションに問題があるのでは,という考えに至りました.

とにかくメンタルの弱い私は,落ち着いてコンテストを受けるにはどうしたらいいかを考えました.開始直前にお風呂には入らない,部屋の温度を高くしすぎないなどありますが,特に効果がありそうだと思ったのはコンテスト前にケーキを食べることでした.ケーキを食べることで糖分を補給し,温かいお茶を飲んでリラックスする.もうこれしかないと思いました.

結果はよく分かりませんでした　結果的にこの試みは成功に終わりました.が,この試みを取り入れた後の2回は冷えてしまいました.そしてそのうちの1回(ABC147)で私は…

心が折れかけました.

正直,微増微減はあっても10以上冷えることは無いと思っていました.やることはやってきたと思っていたのですから.

しかし,ABC147の結果は遅解き3完(1155 -> 1141).コンテスト直後は完全にぽっきりいってました.

 

6. 時間に追われて問題を解く

最後にすがったのがこれでした.ABC148が開催されるまでの2週間,私は積極的にバーチャル参加機能を活用してまだ解いていない青diffの問題を含むセットを解いていきました.そこで初めて,自分が"コンテスト時間内に通す感覚"を忘れていたことに気付きました.

 

7. ABC148に参加・全完する

お風呂は30分前に済ませ,M-1を見ながら紅茶とケーキを嗜み,最高にリラックスした状態でコンテストに臨みました.

とにかく誤読には気を付けました.D問題を通した時点で自分の順位は2000位ほど.多少焦りましたが,それでも自分のペースを信じて確実に考察を紙にまとめ,実装していきました.焦るな,落ち着けば時間内に実装できる.二週間前にはそう自分に言い聞かせても無意味だったのでしょうが,バーチャル参加で時間内に解く感覚を思い出したことで落ち着いて考察し,実装のバグを取り除くことが出来ました.FのACの文字列を見た時は,高揚感と安堵,ここまで支えてくれた友人達への感謝など色々な気持ちが入り混じっていました.

 

 

で、結局何をやったんですか

技術面とメンタル面に分けますと,

技術面

bit全探索

mod逆元

dfs, bfs

Union-Find木

累積和

セグ木(まだ使ってないけど)

ワーシャルフロイド法・ダイクストラ法

EDPCを途中まで(執筆時点でKまで埋めている)

考察力を鍛える(考えが煮詰まるまでじっくり考える)

メンタル面

自分の脳がよく回るコンディション(自分の体調および周辺環境)を把握する

これまで時間内に通してきた感覚を頼りに問題を解く

誤読をしないために落ち着いて問題を読む

焦らない

落ち着く

ケーキを食べる

 

こんなところです.この記事を読んで,コンテスト前にケーキを食べる人が増えてくれたら嬉しい限りです. それでは今回はこの辺で.