第９回日本情報オリンピック予選 問題６

[みけCAT]

学校に提出するレポートとして、情報オリンピックの問題を複数の方法で解き、
実行速度を比較するということをしています。
今第９回日本情報オリンピック予選
http://www.ioi-jp.org/joi/2009/2010-yo- ... index.html
の問題６をやっています。
解説の解法２と解法３のプログラムは書けたのですが、解法１がわからなくて困っています。
とくに「プレゼントの少ない状態から順に値を決めていけば最終状態の数がわかる．」
というところがわかりません。
解説できる人がいたらお願いします。

解法２と解法３のプログラムを添付しておきます。
標準入力から読み込み、標準出力に出力します。
2009-yo-t6-1.cが解法３、2009-yo-t6-2.cが解法２です。

[ookami]

興味深い問題ですね。

でも読んでいるうちに頭がモヨモヨしてきたため、
以下、わけのわからないことを書くかもしれません。よろ☆しくｗ

--

> 現在すでに拾ったプレゼントの組み合わせと最後にプレゼントを拾った家の組み合わせを状態とし

というのを、「入力１」の場合で考えて見ます。

4 4
1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 2

4 * 4の広さで、教会[2]が右下にあって、それぞれ上下左右の辺に家[1]があり、残りは空き地[0]ですね。
便宜上、家に 1 2 3 ... 9 A B と番号を振ります。

1 2 3 4
5 6
7 8
9 A B

教会からスタートして、最初に考えられるのは、

B(last:B) / 8(last:8)

の2通り。次の状態は、Bからは A or 3 に　、　8からは 7 or 6 にいけるので、

B A(last:A) / B 3(last:3) / 8 7(last:7) / 8 6(last:6)

の4通り。次の状態は...

--

みたいに考えるんじゃないですかね。
「プレゼントの少ない状態から順」にもしっくり来る気がします。