![2015/09/23 会津大学競技プロ合宿 day3 B 10
探索のメモ化は必要？
? memo[磯野左][磯野右][中島左][中島右]のように
メモ化すればO（5^4）を達成できる
? しかし、『あれ』は最悪でも9手で終了し、探索の分
岐もあまり多くならないため、メモ化の必要はない
? 指が増えたらメモ化しよう](https://image.slidesharecdn.com/bmatchpeaswar-160416092535/85/2015Day3-B-10-320.jpg)
More Related Content
Viewers also liked (11)
More from HCPC: 北海道大学競技プログラミングサークル (20)
Recently uploaded (11)
会津合宿2015顿补测3：叠问题
- 1. 2015/09/23 会津大学競技プロ合宿 day3 B 1 B:Match Peas War ～中島、あれやろうぜ！～ 原案：田中 解答：井上?鈴木?田中 解説スライド：鈴木
- 2. 2015/09/23 会津大学競技プロ合宿 day3 B 2 問題概要 ? 磯野君と中島君が「あれ」で勝負する ? 先手後手があり、先手は磯野君である ? 互いに最適な行動を選択する ? 与えられた初期状態において、勝者はどちらか
- 3. 2015/09/23 会津大学競技プロ合宿 day3 B 3 「あれ」 ? マッチ?グリーンピース?戦争（と呼ぶらしい）
- 4. 2015/09/23 会津大学競技プロ合宿 day3 B 4 「あれ」のルール：初期状態 1 1 ※各手において立っている指の本数を書いています 1 1 赤：磯野君 vs 青：中島 君 両プレイヤーとも 両手に1本ずつ 指を立てた状態 からスタート
- 5. 2015/09/23 会津大学競技プロ合宿 day3 B 5 「あれ」のルール：攻撃 1 1 1 1?2 赤：磯野君 vs 青：中島 君 先手から順に、 一方の手を使っ て、相手の一方 の手を攻撃 攻撃された手は、立 っている指の本数が 足される
- 6. 2015/09/23 会津大学競技プロ合宿 day3 B 6 「あれ」のルール：退場 4 1 2?6 2 赤：磯野君 vs 青：中島 君 立つべき指の本数 が5以上になった 手は退場し、ゲー ムに参加できなくな る 退場！ 相手の両手を退場させたプレイヤーが勝ち！
- 7. 2015/09/23 会津大学競技プロ合宿 day3 B 7 磯野君たちのローカルルール 4 1 3 2 赤：磯野君 vs 青：中島 君 初期状態が1本 から4本の間で自 由
- 8. 2015/09/23 会津大学競技プロ合宿 day3 B 8 想定解法 ? ゲーム木探索 ? あり得るゲーム進行を深さ優先探索した結果を利用する (2, 3) (2, 3) (2, 3) (4, 3) (2, 3) (2, -) (-, 3) (4, 3) (2, -) (4, 3) (4, 3) (2, -) (2, -) (2, -) (-, 3) (-, 3) (-, 3) (4, -) (2, -) (4, -) (2, -) (-, 3) (4, 3) (-, -) (2, -) (4, -) (-, -) (4, -) (-, -) (4, -) (-, -) (-, 3) (-, -) (4, -) (-, -) (-, 3) (磯野) (中島) (2, 3) (-, 3) (-, 3) (-, 3) (2, -) (-, 3) (-, 3) (-, -) (2, -) (-, -) こんな感じの木ができる！
- 9. 2015/09/23 会津大学競技プロ合宿 day3 B 9 想定解法 ? DFSの帰りがけに、勝者を持ち上げる 各プレイヤーは自分が勝てる分岐があるならばそれを選ぶ (2, 3) (2, 3) (2, 3) (4, 3) (2, 3) (2, -) (-, 3) (4, 3) (2, -) (4, 3) (4, 3) (2, -) (2, -) (2, -) (-, 3) (-, 3) (-, 3) (4, -) (2, -) (4, -) (2, -) (-, 3) (4, 3) (-, -) (2, -) (4, -) (-, -) (4, -) (-, -) (4, -) (-, -) (-, 3) (-, -) (4, -) (-, -) (-, 3) (磯野) (中島) (2, 3) (-, 3) (-, 3) (-, 3) (2, -) (-, 3) (-, 3) (-, -) (2, -) (-, -) 中 磯 中 中 中 中 中 中 中 中 中 磯 磯 磯 磯 磯 磯 中 中 中 中 中 勝者：磯野
- 10. 2015/09/23 会津大学競技プロ合宿 day3 B 10 探索のメモ化は必要？ ? memo[磯野左][磯野右][中島左][中島右]のように メモ化すればO（5^4）を達成できる ? しかし、『あれ』は最悪でも9手で終了し、探索の分 岐もあまり多くならないため、メモ化の必要はない ? 指が増えたらメモ化しよう
- 11. 2015/09/23 会津大学競技プロ合宿 day3 B 11 Writer解 ? 井上（C++）：22行 ? 鈴木（C++）：45行 ? 田中（Python）：27行