【競プロ】通学時間精進のすゝめ

この記事は新歓ブログリレー2024 19日目の記事です。

初めまして、アルゴリズム班所属のNzt3です。普段は競技プログラミングをやったり、競技プログラミング以外をやったりしています。

通学時間が長い！

通学時間って長いですよね。
共感できない方はこの記事の対象読者ではないので家で競技プログラミングをしていてください。
共感できた方は読めるところまで読み進めてください。

通学時間を有効活用しよう！

通学中とはいえ時間は時間です。うまく活用したいですね。

何ができる？

睡眠
- 電車内で立ったまま寝るの？~~寝れるけど~~
課題
- 机がないと厳しくないですか？
ゲーム
- ギリギリできそう
読書
- できる

できることがあまりない感じがしてきましたが、読書ができそうですね。皆さんは通学時に読書をしましょう！
ところで、読書ができるなら他の文章を読むことができるはずです。具体的には競技プログラミングの問題文などの文章が読めます。
通学時に競技プログラミングができそうですね！

競技プログラミングをやろう！

競技プログラミングとは

競技プログラミングは問題を解くプログラムを高速に作成する競技です。

解く問題はさまざまで、足し算をするだけでいいこともあれば、AliceがBobに勝つために出すべきカードを求める必要があることもあります。

日本では AtCoder が最大なのでまずはこれに登録して適当にABC(AtCoder Beginner Contest)のA問題を解いてみましょう。

精進しよう！

ここからは競技プログラミングをやっている人向けの内容になります。

問題を解こう

コンテストで上位に入るには「難しい問題」を「速く」解くことが必要です。
難しい問題を解けるようになるには難しい問題を解くと良いです。問題を解きまくりましょう！AtCoderには5,000以上の過去問があるらしいのでどんどん解いてもかなり長く楽しめそうですね。

Recommendationをやろう

どの問題を解けばいいでしょうか。
あまり簡単な問題を解いても得るものがないですし、難しい問題はそもそも解けません。
適切な難易度の問題を選んでくれるサービスが欲しいですね。
そのサービス、あります。
AtCoder Problemsです。

AtCoderのユーザーIDを入力すると、ユーザーのRatingに合わせた問題を沢山提案してくれます。
https://kenkoooo.com/atcoder#/user/Nzt3?userPageTab=Recommendation

Nzt3のRecommendationの問題

これらの問題は「コンテスト中に通せればRatingが上がる」くらいの難易度なので、「以前は解けなかったけど練習により解けるようになった」という状態になりやすいです。

Recommendation をどんどん解いて実力を上げていきましょう！

時間の不足

Recommendation はRatingに合わせた問題を提案してくれます。提案されるのは現在の実力では解けないこともある難しい問題ばかりです。
難しい問題は解くのに時間がかかります。順調にやっても、1問に30分から1時間はかかると思います。

さて、時間がかかるという話はさっき聞きましたね！
そう！！通学時間です！！！
通学時間にRecommendationの問題を解けば時間が有効に使えますね！！！！

通学時間精進をしよう

問題を読もう

AtCoderでは問題はそこまで複雑にはなりません。複雑なものでも閏年の決定方法くらいにしかならないので一度頭に入れておけば後は問題文を読まずに考えられます。

とりあえず問題を読んでおけば、考えるのは後でもできます。電車内でも問題を読むくらいはできるので、通学中に問題を読んでおきましょう。

考察を進めよう

難しい問題は考えないと解けません。通学中は時間があるのでどうすれば解けるか考えてみましょう。

通学中に紙と鉛筆を取り出すのは難しいですが、必要ありません。窓の外をぼんやりと眺めながら数列の性質を考え、木を分解し、順列を構築しましょう。

思いついたことはキーワードだけメモしても良いでしょう。「桁和ごとに桁DP」や「斜めに見て正方形との差分を計算」などと書いておけば実装前に思い出せます。

実験エスパーで通されまくっている問題だと推定された難易度の割に全く考察が進まなくて辛い気持ちになりますが、「実験すれば何かわかるかも？」となった時点で考察は一段階進んでいるので残りの時間は別の問題の考察に使いましょう。

実装を進めよう

通学中に実装まで済ませてしまいましょう。
実装をすると言っても、電車内でキーボードを取り出すのは難しいです。日本語で実装方針を固めて、PCでの実装時に詰まらないようにします。

実装時に詰まりやすい部分を特に詳細に考えておきます。例えば「適切なモノイドを作って、Segment Treeに載せるだけ」となったら「適切なモノイド」の設計を考え、「ソートしてSegmnet Tree上でDP」であればDPの漸化式の添字を考えます。

PCなしでの実装とチーム戦

ICPCのようなチーム戦では「PC1台のみ」や「同時コーディング禁止」という制限があることがあります。このような制限があると、ある問題を実装している間は他の問題に関係するプログラムを書けないという事象が発生します。
考察や実装方針立てなどPCなしでできることをPCなしでできるように訓練しておくとこのようなチーム戦に有利です。

「解けたと思ってPCを渡してもらったけど、実装しているうちに解けてないことに気付いた」とかが起こると辛い気持ちになるのでPCなしで実装できると嬉しいですね。

諦めて解説を読もう

Recommendation は勝率が高くない難易度の問題が選出されます。ABCだと「こういうアルゴリズムがあります」みたいな知識問題が出題されることもあるので解説を読んで身につけていきましょう。解説を読んでも実装して通せるかは別なので「解けた」というところまで持っていく実装力を鍛える意味もあります。

ACしても解説を読もう

自力で解けたとしても解説は読みましょう。「ただの実家DPですね〜」と言いながら通したその問題は貪欲法で $O (N)$ で解けたりするかもしれません。別解に「実は $O (N)$ で解けます」と書かれているかもしれません。得られる知識は全部得ちゃいましょう。

通学時以外にも競プロをやろう

春休みって通学しないんですよね。じゃあいつ競プロをやるかという話なんですが、PCが使えるなら普通に競プロができますね。競プロをしましょう。バーチャルコンテストがおすすめです。

PCが使えない環境で競プロをしたいなら「入浴時競プロ」もおすすめです。
問題を頭に入れて風呂に入ると、風呂から上がる頃には頭に実装が浮かんでいます。あとは牛乳でも飲みながら実装してACを得れば良いです。

おわりに

PCが使える時は競技プログラミングをやりましょう。
PCが使えない時でも競技プログラミングをやりましょう。

明日の担当は s9さんです。明日もお楽しみに。