| 第９回日本情報オリンピック 予選６ |
|
|
2009年12月17日
情報オリンピック日本委員会
|
既にプレゼントを置いた家の上を通らず何通りの経路を通ることができるかという問題であり，古くから存在する碁石拾いというパズルに少々制限を加え逆向きの(拾うのではなく置いていく)問題にしたものである．
プレゼントを置くことができる経路というのは，その置いた順を逆から見ると
という条件下でプレゼントを拾うことができる．このように問題を置き換えると，どのような状況でも上下左右向きに真っ直ぐ行き突き当たる家のみを調べれば良いので探索空間(調べなければならない手の数)が大幅に減る．
解法１
現在すでに拾ったプレゼントの組み合わせと最後にプレゼントを拾った家の組み合わせを状態とし，各々について考える． すでに拾ったプレゼントの組み合わせは家が最大 23 個あることから 2^23 通り，そして最後にプレゼントを拾った家(または拾っていない状態)は 24 通りあるので，その 2 つの組み合わせると約 200,000,000 (=2億) 通りの状態がある． 各々の状態は遷移可能な次の状態が最大で 4 通りあるので多めに見積もっても約 800,000,000 (=8億) 通りである． ただし，プレゼントを拾った組み合わせのうちの多くは実現不可能な組み合わせであり，また遷移可能な状態も 4 通りより少ないことが多々あるので，実際に計算しなければならない状態遷移の数ははるかに小さい．
まず一つもプレゼントを拾っておらず，教会にいる状態を 1 通りとし開始状態する． これ以降，逆方向の遷移はない(プレゼントを増える一方である)ので，プレゼントの少ない状態から順に値を決めていけば最終状態の数がわかる．
解法２
すべての実現可能な道順を拾う方向ですべて探索すると，検索しなければならない移動方法は最大で 4^23 通りであるが，これもまた実際に計算しなければならない数は小さいので，計算時間をかければ計算することができる．
解法３
問題に書かれているように置いていく方向ですべて探索すると，検索しなければならない数は最大で 23 の階乗通りある．これも同様に実際に計算しなければならない数は小さいが，この方法では最悪ケースの場合は計算することは容易ではない．