TODO

参考 †

↑

Topcoder †

  • div2 Hard は難易度的には div1 medium より簡単なイメージ
↑

Topcoder環境設定 †

  • codeprocessorで何故か必要な部分がカットされちゃう
    • 変なことがあったら、一旦Removeしてもう一回設定しないと変更が反映されない
  • Options -> Setup User Preferences -> Editors -> Default Language
↑

問題の見方 †

  1. google翻訳に問題文を突っ込む
  2. 原始的順像
    1. 具体的な簡単な問題を自分の手で解こうと試みる。問題の概要を把握する。
    2. 明らかな条件を列挙し、覚えておく。自明な条件をコーナーケースとして把握する。
    3. その他、貪欲でいけるかなど、発想重視で色々考える。
  3. 求められる情報量の確認
    • yes-noか、max-minか、numかなど。
  4. 特性関数の作りやすさ
    • この答え（以上・以下）は問いの答えたりえるか？という質問に簡単に答えられるかを確認する。
  5. 計算量
    • アルゴリズムに要求される計算量のキツさを確認する。
  6. 頑張って実装
  7. テスト
    • 時間最大セットと、メモリ最大セットと、コーナーケースで通るかを確認する。
↑

Challenge †

  • vectorのチャレンジの仕方 
    hoge,foo,test
  • とすると、vector[3]={hoge, foo, test};となる。
  • 変なスペースはつけてはならない。
  • 最後にカンマをつけてはならない。
↑

虎本まとめ †

  • 探索
    • n次元の全探索
    • グラフの幅優先、深さ優先の全探索
      • しかし、格子状の道の最小ステップ経路の場合の数などでは、h*wの格子について$2^{h+w}$の探索をすることになる→メモリを使ってメモ化することで余分な探索を省く
    • 幅・深さ優先のメモ化可能性
      • まず、指数関数計算量の探索方法を考えることが重要。その後、複数のルートから同じ計算を行なっていないか（グラフ上で合流する部分はないか）をチェックする。
      • 返り値がある形でないとメモ化できない
      • 「それ以降に得られる〜」をメモ化する
    • メモ化からの漸化式構築＝動的計画法
      • 「これまでに得られる〜」をメモ化する
      • 幅・深さ優先探索のメモ化のときに保存した状態と、ここで計算するテーブルの状態変数は一致する
      • 「ありえない組み合わせ」というものが存在する
  • DPは指数計算量探索の合流である
    • 探索の「状態」と「合流法則」を抽出したものがDPとなる
    • まず指数計算量探索を図示してみる
    • 丸の中に状態（＝添字や重さや価値）を書いたグラフを書いてみる
    • すると、合流を見つけることができる。合流のルール（＝その上流すべての情報の集め方）を抽出する
    • 状態と合流から自動的にDPが計算できる
グラフ分析メモ化探索DP
状態ノード引数DPテーブル添字
値ノードに付属する値返り値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はどこでしても同じ3-5 行列累乗, SRM 502 Div2 Hard
集合を、整数型のビット演算を用いてDPの状態に組み込む3-5 ビットDP
DPは適切なデータ構造を用いると高速化3-5 データ構造を用いて高速化
問題を同値な数学に置き換える牛が云々とかいう状態で考えたくないSRM 502 Div2 Hard
DPのデータ型のパターンはいっぱいある6次元配列だろうが何だろうがビビらないSRM551 Div2 Hard
一つ前にしか依存しないDPテーブルは2テーブルを使いまわすint prev=i%2,next=prev^1;dpdp[next][(x+i)%N][y-1] += dpdp[prev][x][y];SRM 502 Div2 Hard
最小手数といえば幅優先探索SRM 509 Div2 Hard
↑

講評 †

  • 簡潔に。
問題どんな問題か理解度
SRM 502 Div2 Hard簡単な動的計画法。メモリ節約法。分かるが通ってない（解答）
SRM 502 Div2 Hard基本の動的計画法。分かるが通ってない(解答)
SRM 509 Div2 Hard簡単め動的計画法、幅探索。分かってない。ダイクストラとDPと幅探索と幅探索でいけるっぽい
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS