feature image

2024年3月26日 | ブログ記事

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

この記事は新歓ブログリレー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ですね〜」と言いながら通したその問題は貪欲法でで解けたりするかもしれません。別解に「実はで解けます」と書かれているかもしれません。得られる知識は全部得ちゃいましょう。

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

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

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

おわりに

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

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

Nzt3 icon
この記事を書いた人
Nzt3

23B algo|CTF|SysAd 競プロer

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2024年3月22日
traPグラフィック班の活動紹介2024
haru10 icon haru10
2024年3月17日
⑨でもわかる8bitアレンジ講習会
vPhos icon vPhos
2024年3月11日
思想の強いゲーム制作をしよう!
Kirby0717 icon Kirby0717
2023年9月26日
traP コンペ 2023 夏 sponsored by ピクシブ株式会社 運営後記
abap34 icon abap34
2023年7月13日
アルゴリズム班はやとき王選手権「競(けい)プロ」を開催しました!
abap34 icon abap34
2022年10月11日
アルゴリズム班にKaggle部を設立し、初心者向けデータ分析体験会を開催しました!
abap34 icon abap34
記事一覧 タグ一覧 Google アナリティクスについて 特定商取引法に基づく表記