TODO
Topcoder †
- codeprocessorで何故か必要な部分がカットされちゃう
- 変なことがあったら、一旦Removeしてもう一回設定しないと変更が反映されない
- Options -> Setup User Preferences -> Editors -> Default Language
問題の見方 †
- google翻訳に問題文を突っ込む
- 原始的順像
- 具体的な簡単な問題を自分の手で解こうと試みる。問題の概要を把握する。
- 明らかな条件を列挙し、覚えておく。自明な条件をコーナーケースとして把握する。
- その他、貪欲でいけるかなど、発想重視で色々考える。
- 求められる情報量の確認
- 特性関数の作りやすさ
- この答え（以上・以下）は問いの答えたりえるか？という質問に簡単に答えられるかを確認する。
- 計算量
- アルゴリズムに要求される計算量のキツさを確認する。
- 頑張って実装
- テスト
- 時間最大セットと、メモリ最大セットと、コーナーケースで通るかを確認する。
Challenge †
- vectorのチャレンジの仕方
hoge,foo,test
- とすると、vector[3]={hoge, foo, test};となる。
- 変なスペースはつけてはならない。
- 最後にカンマをつけてはならない。
虎本まとめ †
- 探索
- n次元の全探索
- グラフの幅優先、深さ優先の全探索
- しかし、格子状の道の最小ステップ経路の場合の数などでは、h*wの格子について
 の探索をすることになる→メモリを使ってメモ化することで余分な探索を省く
- 幅・深さ優先のメモ化可能性
- まず、指数関数計算量の探索方法を考えることが重要。その後、複数のルートから同じ計算を行なっていないか（グラフ上で合流する部分はないか）をチェックする。
- 返り値がある形でないとメモ化できない
- 「それ以降に得られる〜」をメモ化する
- メモ化からの漸化式構築＝動的計画法
- 「これまでに得られる〜」をメモ化する
- 幅・深さ優先探索のメモ化のときに保存した状態と、ここで計算するテーブルの状態変数は一致する
- 「ありえない組み合わせ」というものが存在する
- DPは指数計算量探索の合流である
- 探索の「状態」と「合流法則」を抽出したものがDPとなる
- まず指数計算量探索を図示してみる
- 丸の中に状態（＝添字や重さや価値）を書いたグラフを書いてみる
- すると、合流を見つけることができる。合流のルール（＝その上流すべての情報の集め方）を抽出する
- 状態と合流から自動的にDPが計算できる
蟻本まとめ †
- DPテーブルを書いてみて、混み合っている場合は無駄な計算がないか考える (2-3 漸化式を工夫する, 個数制限なしナップザック問題)
- boolのDPは非効率 (2-3 漸化式を工夫する, 個数制限付き部分和問題)
- DPの双対性
- 「状態に対して評価値がどうなるか」⇔「固定された評価値（＝ここでの状態）に対して、最も良い状態（＝ここでの評価値）は何か」
- (2-3 漸化式を工夫する, 01ナップサック問題その2, 最長部分増加部分列問題）
- 「fの最大化」を、「命題C(x)=『fがx以上である』が判定可能ならば、xの探索的最大化」と置き換える(3-2 平均最大化)
- n回の掛け算はO(log n)で計算可能(3-1 べき乗を高速に計算する)
- 漸化式は行列演算に変換可能(3-5 行列累乗)
- modはどこでmodしても同じ (3-5 行列累乗)
- 集合を整数型のビット演算を用いて、DPの状態に組み込む（3-5 ビットDP）
- DPは適切なデータ構造を用いると高速化できる（3-5 データ構造を用いて高速化）
|
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
