AOJ 0557 A First Grader 解説

OkNCT-ICT 2013 春合宿 Day 6 (らしい) に解説したもの.

Transcript

1. AOJ 0557 A First Grader 解説 @kagamiz
2. www.company.com 問題概要 • 長さがn の数列が与えられます. • 途中計算が0 以上20 以下になり, 最後がa[n] と等しく なるように間に+ か – を入れてください. • n ≦ 100, 0 ≦ a[i] ≦ 20
3. www.company.com 入力例の解析 • n = 11 数列 = {8　3　2　4　8　7　2　4　0　8　8} • 8+3-2-4+8-7-2-4-0+8=8 • 8+3-2-4+8-7-2-4+0+8=8 • 8+3+2+4-8-7+2-4-0+8=8 • 8+3+2+4-8-7+2-4+0+8=8 • 8+3-2-4+8-7+2+4-0-8=8 • 8+3-2-4+8-7+2+4+0-8=8 • 8-3+2+4-8+7+2+4-0-8=8 • 8-3+2+4-8+7+2+4+0-8=8 • 8-3+2-4+8+7+2-4-0-8=8 • 8-3+2-4+8+7+2-4+0-8=8 • …の10 個
4. www.company.com 入力例の解析 • n = 40 数列 = {1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1} • もうなんかヤバそう • 全探索お姉さんなら数え上げ兼ねないけど... (http://www.youtube.com/watch?v=Q4gTV4r0zRs) • どうやら7069052760 個あるらしい. JOI くんマジキチ. • ちなみにint 型には入りません. ザンネン.
5. www.company.com O(2^n) 解法 • がんばって再帰で+と-を入れていく. • どうやるのが楽？ → 引数に(今の項数, 今の和)を持つ と行けそう. • 擬似コード function getNum(int index, int sum){ if (index + 1 == N) return (sum == a[index + 1]); return (getNum(index + 1, sum a[index + 1]) + – getNum(index + 1, sum + a[index + 1]); }
6. www.company.com O(2^n) 解法 • 例外処理がたくさん • 最初の項は必ず+ だったり • 負になるところとか20 を越える所を排除したり • 満点解法を思いつくには, この(今の項数, 今の和) のよ うな状態を思いつくことがとても大事.
7. www.company.com O(ns) 解法 • さっきまでのプログラムの何が無駄だったか？ • 同じ状態を何度も遷移すること. • これってどうすれば解消出来たっけ？ → Dynamic Programming, しよう(提案)
8. www.company.com O(ns) 解法 – (1) メモ化 • さっきまでのプログラムの何が無駄だったか？ • 同じ状態を何度も遷移すること. • メモ化することで同じ状態にこないようにしよう. • 引数の状態は高々(100, 21) = 2100 通り. いける.
9. www.company.com O(ns) 解法 – (1) メモ化 • メモ化することで同じ状態にこないようにしよう. • 引数の状態は高々(100, 21) = 2100 通り. いける. • メモ化配列memo[100][21] を用意すると簡単. • 擬似コード int memo[100][21]; function getNum(int index, int sum){ if (~memo[index][sum]) then return (memo[index][sum]); if (index + 1 == N) return (sum == a[index + 1]); return (memo[index][sum] = getNum(index + 1, sum a[index + – 1]) + getNum(index + 1, sum + a[index + 1]); }
10. www.company.com O(ns) 解法 – (1) メモ化 • 通例メモ化配列は-1 で初期化することが多い • メモされていない状態, ということを指す • 初期条件をあまり意識しなくて良いので楽と言う人が 結構居る • @kyuridenamida さんとか
11. www.company.com O(ns) 解法 – (2) for 文 • さっきの配列を考えると, dp[1][a[1]] は明らかに1. • この”明らか” を拡張していく事を考える. • 1 から順番に, 前の値を利用していくと自然とn 番目に ついての答えも求まる. • ちなみに, 答えはn – 1番目までの項で, 和がa[n] となっ ているものなので, dp[n – 1][a[n]] となる.
12. www.company.com O(ns) 解法 – (2) for 文 dp[1][seq[1]] = 1; for (i = 2; i <= n; i++){ for (j = 0; j <= 20; j++){ if (j + seq[i] <= 20){ dp[i][j + seq[i]] += dp[i - 1][j]; } if (j - seq[i] >= 0){ dp[i][j - seq[i]] += dp[i - 1][j]; } } }
13. www.company.com O(ns) 解法 – (2) for 文 • こういう風に, 計算した値を後の方に再利用するDP を 配るDP と言う. • 今着目している値に操作するDP を貰うDP を言う.
14. www.company.com DP について • DP は “習うより慣れろ” が鉄則です. • こういう記事とか, 蟻本の練習問題をたくさん解きま しょう. • DP の練習として良いやつ http://d.hatena.ne.jp/kyuridenamida/20111009/1318091499 • 「DP・メモ化再帰」はこんなに簡単だった http://www.itmedia.co.jp/enterprise/articles/1003/06/news002.html • 動的計画法を学ぶリソース・練習問題まとめ http://d.hatena.ne.jp/cou929_la/20100708/1278600922