tips私が2年間競プロをして1理解した諸々の言語化を試みたものです。異論反論は期待しています2。Sourceも便利WA時のペナルティ等を確認しておく賞金等の条件もついでに過去問を解く場合は、以下も確認しておくとよい。解法を探索する前に、とりあえずの前処理以下を行う。50$だから$O(2^N)$な方向で考えてたら実は$O(1)$でよかった、とかもあるので油断しないように愚直解を考える明らかに間に合わないものでよい例:候補数が全体で$N$、ひとつあたりの判定に$N$だから、全体で$O(N^2)$かければ答えはでる考えないといけないのがどの部分か分かる以上をして残った困難がその問題の核となる部分である。方針を探索する方針が立つまで、以下を繰り返す。十分な回数繰り返し、変化がなくなった場合も終了する。部分木の大きさ/部分木の高さ/辺や頂点の重み/$\dots$$\dots$情報を整理する図を書く具体例を作る現在得られている仮定とそのゴールを書き出す基本的に行なっているのは証明4の作製に近い5と思っています。そもそも全てはしらみつぶしな探索だと思っています。空中から解法を取り出しているような挙動をする人間はよく見られますが、諸々を(本人の意識にものぼらない程に)高速に実行しているだけであるはずです。解けないと思ったらなぜ解けないのか考える。問題文の読み直し(可能なら)仲間への相談なぜ解けないのかの説明を試みる(どうしても自力で解きたいなら)時間をおくをする。それでもだめなら諦めよう。十分な時間(初心者であれば$30$分程度か)考えても分からないならその後数日考えても分からないだろう、ということはよく言われる。復習は大事なので、諦めたら解説を見て実装して提出してACを貰うところまできっちりやっておくべきである。方針が立ったと思ったら、確認その方針で本当によいのかを確認する。ICPCなどで仲間と相談ができるなら、一緒に確認するとよい。得意不得意なにか勘違いをしていないか非自明なケースをいくつか作って試すまた、ある方針でよいことが確認できても、追加の考察により実装量が減ることはある。可能だからといってすぐに実装を開始しないようにしよう。以下のようなことを考える。+2$を全部試して最も良いものを選ぶことでごまかす似たような計算部分をまとめて処理できないか例えば、各数に$-1$を掛けるなどでいい感じにする例えば、事前にsortすることで場合分けを消す$\dots$実装する決めた通り丁寧に書くだけ。チームで解いていて、実装が重かったり計算機の台数に強い制限があるなら、ペアプロをしよう。書けばいいかにつまるのなら、問題や解法に対する理解が足りていない可能性が高い。editorを閉じて紙の上に戻ったほうがよいことは多い。oneのあたりは実装しながら考えればよいと思うが、それでもあまり複雑になるようならこれも一度紙の上で整理するべきだろう。提出する前に、本当に解けているのか確認する。サンプルケースは全て試して確認する。サンプルケースに漏れがあるなら、追加で試す。コーナーケース非自明なケース手で試した出力と合うことを見る最大ケース本当に間に合うのか確認するこのあたりのテストは自動化すべき。以下のようなツールも利用することができる。https://github.com/kmyk/online-judge-toolshttps://github.com/nodchip/OnlineJudgeHelperhttps://github.com/shivawu/topcoder-greedその後に、提出する。提出したがpretestなどで落ちてしまった時。Errorに変わるか否かで追加の情報を得るテクがある。撃墜ケースを探すどのようなケースで落ちているのか考える。複雑なケースで落ちているのでなければ、以下のいずれかで具体的に撃墜ケースが得られる。ichyo.jpあたりを眺めるのもよい。修正する実装を後から修正するのはとてもバグを埋めやすいので注意するまとめ基本は全探索を丁寧かついい感じにやるだけ。真に新しいものを生み出せる人間なんてめったに存在しませんし、そこらのコンテストでそのような所業が要求されるはずがないです。解法とは無から新しく生み出すものではなくて、過去の問題で見た解法を切り貼りして構成するものであるはずです。「ひらめき6」だとかのような存在しないものを追い求めるのではなくて、積極的にパターン化を目指すべきだと思います。一度触ってみると、何かが得られるかもしれないし、得られないかもしれない。