ふぁんたすてぃっくふぁんたすてぃっくゲームの話題と、プログラミングの話題を。itLinkedInPocketCopyスポンサードリンクこんにちは、ふぁんたです。AtCoderという、競技プログラミングというジャンルに属するオンラインゲームがありまして。そこで最近水色レート(けっこうすごい)が安定してきたので、記事を書きたいと思います。「今や!水色になるまでにしたこと、水色にいるうちに書いたろ!!」みたいな邪な気持ちで書き始めたいと思います。コンテスト外で心がけたことこれに関しては、1.なるべくコンテストに出ること2.考え方だけでもいいので、知らないアルゴリズムに触れること3.DPを練習することこの3つだと思っています。それぞれについて語ります。2問早解きだな、出るのやめとくか...」とか、思うこともあると思います(自分はありました。自分が何ができないのか、というのが明らかになります。模試を受けるのとおなじような理由になります。値は可視化できませんが、コンテストに出ることで「プログラムを書く経験値」が増えます。書いてるうちにMain以外での関数定義が必要になっても抵抗なく書けるようになり書いてるうちにintじゃ足りないな、long使おう、という頭が働くようになり書いてるうちに構造体だけじゃなくてクラスを実装する労力もそこまでじゃないと感じるようになり水色になれた今の自分があります。前のコンテストの復習が済んでいなくても、経験値が貯まるので。一回のコンテストで冷えても、何回でも参加できるので、受験みたいにリミットもないので。知らないアルゴリズム・実装方法に触れることこれです。書けますか?僕はできません。・正の辺だけで最短経路を求めるのがダイクストラ法だったな、ぐらいの「撫でただけ」みたいな知識は持っています(書きながらベルマンフォード法ググったけど)。「この問題、(書けないけど)見たことあるやつだ!」となるので大変におすすめです。Tree)ぐらいですかね。...列挙してみたけどそんなになかったな。あと、アルゴリズムではないですが、「どれだけ計算したらTLEになる」みたいな情報は知識として持っておいたほうがいいと思います。DPを練習することDPです。ダイナミックプログラミング、動的計画法と呼ばれるやつです。「前の計算結果を再利用できる構造の時、それを使い回す」ことにより、愚直にやって解けない問題を解くことができます。DPに関しては、「D(問題)はDPのD」という言葉があるほど頻出で、解説記事もありますし、DPだけを集めたコンテストもあります。(1問目しか解けなかった)このアルゴリズムに関しては、考え方を知るだけでなく、一回書いてみることをおすすめします。漸化式を書いてDPテーブルを構築したり、小さい数字で中身を実際にシミュレートしてみるのもありです。