アルゴリズムを考えること
アルゴリズムを考えるアプローチ初動
最初に素朴に考えられるデータの種類を確認する(数値(int, float, decimal), 文字列, グラフ, 木, など)
小さい入力で必要条件や傾向を得る
逐次実行や探索で擬似コードを書く
似た問題を探す
簡単な問題
一般化された問題
特殊な条件が追加された問題
アルゴリズム改善
使えてない情報や特徴を探す
貪欲法で済んでしまったりする
データ構造の利用
出力を埋め込む
ソートを2分探索木への逐次挿入で対処するなど
重複した処理を高速化
分割統治で対応できないか検討する
メモ化
動的計画法
無駄な処理をしていないか探す
分枝限定法
対称性を使って探索空間を減らす
事前に条件分岐で対処
最悪時の入力に対応する
ランダマイゼーション
計算困難問題な最適化問題について対処するアプローチ
計算困難問題な最適化問題について対処するアプローチは2つ。
最適: 指数関数的に計算量が増えるのであれば指数の底を小さくする
動的計画法(状態をまとめて管理して探索範囲を狭める)
分枝限定法(理論的な期待値の上限を使って探索範囲を狭める)
線形緩和
最適(Optimal)を諦めて良い解を求める
近似アルゴリズム
ヒューリスティック
アニーリング
ビームサーチ
アルゴリズムの検討事項
提示された条件を使っているか?
反例探し
小さく考える
網羅する
弱点を考える
特殊なケースがないか検討する
同点に持ち込む
極端な例を考える
証明
帰納法
書ききる前に確認すること
出力形式が間違い (全滅しがち)
オーバーフロー注意 (サンプル通るけどテスト失敗でよくある)
int32: 2^31-1(2147483647: 10^10くらい)
int64: 2^64-1(9223372036854775807: 10^18ちょっと) を超えないか?
小数は正しいか? (サンプル通るけどテスト失敗でよくある)
場合によっては有理数型を定義して利用する
添字確認
コーナーケースを扱っているか? (サンプル通るけどテスト失敗でよくある)
0の扱い, 負数の扱い
グラフに循環あり, グラフが非連結, グラフのサイズが1/0, エッジなし
ループの初回, 最終回は適切に扱っているか? (サンプル通るけどテスト失敗でよくある)
入力値は受け取れているか? (全滅しがち)
スレッドセーフじゃないコードで入力を扱ってないか? (全滅しがち)
テストケースの入力順を変更して別のテストケースを作る
資料