AtCoderで水色レートになるまでに心がけたこと
スポンサードリンク
こんにちは、ふぁんたです。
突然ですが、AtCoderという、競技プログラミングというジャンルに属するオンラインゲームがありまして。
そこで最近水色レート(けっこうすごい)が安定してきたので、記事を書きたいと思います。
辿ってきた軌跡
一昨年の10月頃に緑になってから、コツコツとコンテストに出続け、つい最近は緑と水色の境目を行ったり来たりしていましたが、今回のコンテストで大きく水色側に食い込んだため、
「今や！水色になるまでにしたこと、水色にいるうちに書いたろ！！」
みたいな邪な気持ちで書き始めたいと思います。
コンテスト外で心がけたこと
これに関しては、
1.なるべくコンテストに出ること
2.考え方だけでもいいので、知らないアルゴリズムに触れること
3.DPを練習すること
この3つだと思っています。
それぞれについて語ります。
なるべくコンテストに出ること
「配点が100-300-500-600… だから2問早解きだな、出るのやめとくか…」とか、思うこともあると思います（自分はありました。）
出ましょう。
自分が何ができないのか、というのが明らかになります。
ちょうど、模試を受けるのとおなじような理由になります。
また、値は可視化できませんが、コンテストに出ることで「プログラムを書く経験値」が増えます。
競技プログラミングやる前は、for文ひとつ書くのが辛かった記憶がありますが、
書いてるうちにfor文が書けるようになり、
書いてるうちにfor文の二重ループが頭で追えるようになり、
書いてるうちにcontinue,break挟んでてもわかるようになり、
書いてるうちにMain以外での関数定義が必要になっても抵抗なく書けるようになり
書いてるうちにintじゃ足りないな、long使おう、という頭が働くようになり
書いてるうちに構造体だけじゃなくてクラスを実装する労力もそこまでじゃないと感じるようになり
水色になれた今の自分があります。
とりあえず、出ましょう。
前のコンテストの復習が済んでいなくても、経験値が貯まるので。
一回のコンテストで冷えても、何回でも参加できるので、受験みたいにリミットもないので。
出ましょう。
知らないアルゴリズム・実装方法に触れること
これです。
例を挙げます。
ワーシャルフロイド法、ダイクストラ法、ベルマンフォード法、
書けますか？
僕はできません。
でも、これらすべてがグラフの経路を計算するためのアルゴリズムであり、
・3重ループを回す？のがワーシャルフロイド法、
・負の重みがある辺が出てきても大丈夫？なのが？ベルマンフォード法、
・正の辺だけで最短経路を求めるのがダイクストラ法だったな、ぐらいの
「撫でただけ」みたいな知識は持っています（書きながらベルマンフォード法ググったけど）。
こんなふうに、「問題を解くための取っ掛かり情報」としてのアルゴリズム知識を蓄えておくと、コンテスト中に突然
「この問題、（書けないけど）見たことあるやつだ！」
となるので大変におすすめです。
具体的なアルゴリズム・実装方法を挙げますと、
・しゃくとり法
・累積和
・幅 / 深さ優先探索（BFS,DFSとか呼ばれるやつ）（タスクをスタックに入れるかキューにいれるかで変わるやつ）
・UnionFind
・セグ木（Segmentation Tree)
ぐらいですかね。
…列挙してみたけどそんなになかったな。
あと、アルゴリズムではないですが、「どれだけ計算したらTLEになる」みたいな情報は知識として持っておいたほうがいいと思います。
DPを練習すること
DPです。ダイナミックプログラミング、動的計画法と呼ばれるやつです。
「前の計算結果を再利用できる構造の時、それを使い回す」ことにより、愚直にやって解けない問題を解くことができます。
DPに関しては、「D(問題)はDPのD」という言葉があるほど頻出で、解説記事もありますし、DPだけを集めたコンテストもあります。（1問目しか解けなかった）
このアルゴリズムに関しては、考え方を知るだけでなく、一回書いてみることをおすすめします。
漸化式を書いてDPテーブルを構築したり、小さい数字で中身を実際にシミュレートしてみるのもありです。
とりあえず、DPは大事。やりましょう。簡単なやつでいいので。
コンテストで心がけたこと
ここからは、コンテスト中に心がけている（今でも行っている）行動の解説になります。
主な内容は、２つあります。
書き出す
PCの前にいると、どうしても頭がぼんやりとしてきます。
一旦、画面の前で考えるのをやめて、考察を書き出しましょう。
自分なりのやり方ですが、コンテストのために小さいホワイトボードを買いました。
簡単に書いたり消したりできるので、問題の考察に使ったり、普段は備忘録的に使ったり、コンテスト直前に「ぞい！」って書いたりできて便利です。
もちろん、紙でも構いません。ペイントツールとかよりは紙がいいと思います。
コンテスト前に書くものと書かれるものを用意しておきましょう。
シャワーを浴びる
別にふざけているわけではありません。
あと、コンテストがないとシャワーを浴びないわけではありません。
何か思いつくタイプの問題・クイズなどを考えているときに、トイレの中やシャワーで思いついた経験、ありませんか？
これをコンテストに無理やり活かすことを考えました。
やり方としては、考察が必要な問題に出くわしたときに、「問題の内容」「入力の形式」「出力」「制約」を覚えて、おもむろに服を脱ぎます。
これが意外と効果的で、これを書いたタイミングでの前回のABCのE問題を通すことができました。
普段500点問題はなかなか通せないので、効果がある方法だと思っています。
流行って欲しいけど、効果あると思うので、相対的にレート下がってほしくないなあ。
自分の心がけていることをまとめました。どうでしょう。
計算量の詳しい話とか、ソートアルゴリズムとか、触れても良かったかもしれないけど触れなかった話とかあるんですが、結局の所、
「楽しみながら、遊びながら覚える」
っていうのが一番の近道だと思うので、オンラインゲームだと思って楽しんでください。
一緒に楽しみましょう。
レート下がるのは怖いけど。
追記
わからない問題、わからない実装などありましたら、ツイッターに投稿しましょう。
個人的には自分がわかる問題に関するわからないツイートを見かけたら、リプライで自分の分かる範囲で教えるように心がけています。
結構難しいことやってるはずなので、そういうところで新しい人の参加を促したいなと思ってます。
界隈全体がそういう空気になればなあという思いで、陰ながら応援しております。
スポンサードリンク