![叉秉盞2
¢ 豚棋､箸い┐??
★ 侘來!!
¢ 箔めるものは
?????E[?Σ(iタ`ン朕に誼られるスコア)?]
?????=?Σ?E[(iタ`ン朕に誼られるスコア)]](https://image.slidesharecdn.com/cards-121024094945-phpapp01/85/Cards-7-320.jpg)
![叉秉盞2
¢ E[?(iタ`ン朕に誼られるスコア)?]?を箔めたい。
¢ ?iタ`ン朕にj旦朕のカ`ドを燕にひっくり卦す_楕
を p[i,?j]とする。
¢ _楕の各來より、 p[i,?j]?=?1?/?n
¢ したがって、
?E[?(iタ`ン朕に誼られるスコア)?]
???=?Σ?p[i,?j]?*?X[j]?
???=?Σ?1/n?*?X[j]?
???=?1/n?*?Σ?X[j]?=?(カ`ドの方の峠譲)](https://image.slidesharecdn.com/cards-121024094945-phpapp01/85/Cards-8-320.jpg)
![叉秉盞2
¢ 參貧をまとめると、
???E[?Σ(iタ`ン朕に誼られるスコア)?]
?????=?Σ?E[(iタ`ン朕に誼られるスコア)]
?????=?Σ?(カ`ドの方の峠譲)
?????=?(カ`ドの方の峠譲)?*?(n?C?1)
¢ 峠譲､鯒鵑瓩襪世韻任茲い里如⊂侘rg!
¢ ビットDPよりg廾もg!](https://image.slidesharecdn.com/cards-121024094945-phpapp01/85/Cards-9-320.jpg)
Cards
- 1. Cards 圻宛komiya 盾基komiya, uwi
- 2. }古勣 ¢ N旦のカ`ドが燕鬚にKんでいる。 ¢ 燕になっているカ`ドを2旦xんでY卦す。 ¢ Yになっているカ`ドを1旦xんでY卦し、かれ ている方忖の蛍だけスコアを誼る。 ¢ 燕になっているカ`ドが1旦しかなければK阻。 ¢ 誼られるスコアの豚棋､鯒鵑瓩茵 ¢ N?Q?20
- 3. 何蛍泣盾隈 ¢ ＾タ`ン_兵rに燕になっているカ`ドの鹿栽￣を 彜BにとってビットDPする。 ¢ 彜B方:?2^n,?彜B阿林麻楚:?n^3 ¢ 畠悶でO(2^n?*?n^3)
- 4. 叉秉盞1 ¢ 圭:?ビットDPを互堀晒する。 ¢ さっきのやり圭では、彜B阿O(n^3)な何蛍が嶷 すぎた。 ¢ 彜B方をやすことによって麻楚を鯛とせる。
- 5. 叉秉盞1 ¢ ?1.?Yのカ`ドをまだ1旦もxんでないr泣 ?2.?Yのカ`ドから1旦だけxんでY卦したr泣 ?3.?Yのカ`ドを屡に2旦ともY卦したr泣 ¢ それぞれのr泣について、燕になっているカ`ドの 鹿栽を彜Bとする。
- 6. 叉秉盞1 ¢ こうやって彜Bをやすと、光彜Bgのw卞が O(n)しかない。 ¢ 彜B方:?3?*?2^n?、彜B阿林麻楚:?O(n) なので、畠悶の麻楚はO(2^n?*?n)まで鯛ちる。 ¢ なお、O(2^n?*?n^2)でも宥る庁。
- 7. 叉秉盞2 ¢ 豚棋､箸い┐?? ★ 侘來!! ¢ 箔めるものは ?????E[?Σ(iタ`ン朕に誼られるスコア)?] ?????=?Σ?E[(iタ`ン朕に誼られるスコア)]
- 8. 叉秉盞2 ¢ E[?(iタ`ン朕に誼られるスコア)?]?を箔めたい。 ¢ ?iタ`ン朕にj旦朕のカ`ドを燕にひっくり卦す_楕 を p[i,?j]とする。 ¢ _楕の各來より、 p[i,?j]?=?1?/?n ¢ したがって、 ?E[?(iタ`ン朕に誼られるスコア)?] ???=?Σ?p[i,?j]?*?X[j]? ???=?Σ?1/n?*?X[j]? ???=?1/n?*?Σ?X[j]?=?(カ`ドの方の峠譲)
- 9. 叉秉盞2 ¢ 參貧をまとめると、 ???E[?Σ(iタ`ン朕に誼られるスコア)?] ?????=?Σ?E[(iタ`ン朕に誼られるスコア)] ?????=?Σ?(カ`ドの方の峠譲) ?????=?(カ`ドの方の峠譲)?*?(n?C?1) ¢ 峠譲､鯒鵑瓩襪世韻任茲い里如⊂侘rg! ¢ ビットDPよりg廾もg!