Atcoderを解くときに意識しておくことを箇条書きでまとめています。
問題の理解
- 問題文をよく読む
- 問題文が理解できなくても入力例を読む
- 複雑な問題は簡単な部分問題に分割する
- 簡単な例を挙げてみる
解法の検討
- 数式で表すことができるか考える
- 知っているアルゴリズムを適用できないか考える
- 規則性がないか考える
- 偶数と奇数で分けて考える
- コーナーケースの有無を考える
- 集合で考える(包除原理)
- 境界や端について考える
- N=A+B+Cの形はN-C＝A＋BでAとBの全探索
- 2つの内どちらかを選ぶのがN通りある→bit全探索
- 最小値、最大値を求めるときはループ変数に現在の値を代入して探索回数を減らす
実装上の注意
- 実装に取り掛かる前にコメントアウトを使って処理を日本語で書く
- 必要な変数はなるべく初めに固めておく
- 自作関数は初めに固めておく
- なるべく添え字は使わない(例：list[i])
- 浮動小数点型の計算は誤差が発生することがあるため、整数での計算を考える
- リストを使うときは計算量に注意
- for節で、リスト内の変数や文字列の存在チェックはTLEの可能性が高まる
- for節内でリスト内の全要素に対して操作を行うとTLEの可能性が高まる
コメント