プログラミングの基礎力向上のためにAtCoderを始めてみました。コンテストではABCのC問題のAC率が半々くらいのレベルなので、今は過去問を解く等して問題に慣れることをしています。その中で、いくつか気づきがあったのでまとめます。
- メモ化出来るなら必ずメモ化する事
メモ化出来そうでもついつい手抜きをしてしまうと、容赦なくTLEになります。
小手先で計算量を最適化(ループ途中でbreak等)をしても計算量が変わるわけではないのであれば、素直にメモ化したほうが良さそうです。
公式の解説も、メモ化を前提に計算量が書かれていると思いました。 - 境界値の判定はしっかり確認
基本的な事かと思いますが、何回かやらかしたので戒めで書いておきます。
テストケースでは境界値判定が不十分な事があるので(それを前提に自分でテストするべきだと思うので)、テストケースが全て通っても、境界値判定は自分でテストケースを作成してしっかり確認するべきだと思いました。 - 最大値がどうなるかの精査
仮に入力値が32bitで収まるような場合でも、総和を取ったら32bitでは足りない事も多くあるので、少しでもオーバーフローしそうなら、素直に64bitの型を使用した方が良いと思いました。 - ループ内で条件一致を確認する場合は、元の値を書き換えない
これも基本的な事かと思いますが、戒めです。
変数の値を書き換えて条件一致するか判定する時、ついつい元の値を書き換えたまま次のループの処理を行ってしまい、「どうして一致する条件が見つからないんだろう……」で30分位はまりました。基本的な事であるが故に見落としがちなので、コーディング中は意識をしておくようにします。 - 諦めない/面倒くさがらない
これをすると諦め癖がつくので。15分位考えて、それでも出来ない時は解説を見る。解説を見て理解できない時は、他の方のコードを参考にする。その上で、自分で白紙からコーディング出来るまで理解をする、という事を徹底したいです。
ただし背伸びした問題は解かないようにします。実力の少し上の問題を解いていきます。
また問題を解いていて気づきがあれば更新します。