|
uchinyan |
|
はい，こんにちは。さて，今回の問題は．．．
この手の問題は比較的よく見るので，知っていれば簡単ですが，初見では立体だし面食らうかも知れませんね。 各回の各頂点に来る場合の数は，その頂点とつながっている隣の頂点のその一つ前の回の場合の数の和にないます。 ただし，一度 Q に来るとそこで動けなくなってしまうので，Q から来ることはありません。 また，5 回目に Q に来るものを求めるので，それ以前に Q に来たものは無視することになります。 つまり，5 回目よりも前に Q に来た場合の数は 0 としていいことになります。 以上のことに注意して各回の頂点に来る場合の数を書き出していくと．．． 最初 1 <--- P 0 0 0 0 0 0 0 0 0 0 0 -> 0 <--- Q 1 回目 0 <--- P 1 1 1 1 1 0 0 0 0 0 0 -> 0 <--- Q 2 回目 5 <--- P 2 2 2 2 2 2 2 2 2 2 0 -> 0 <--- Q 3 回目 10 <--- P 13 13 13 13 13 08 08 08 08 08 10 -> 00 <--- Q 4 回目 65 <--- P 52 52 52 52 52 42 42 42 42 42 40 -> 00 <--- Q 5 回目 260 <--- P 253 253 253 253 253 188 188 188 188 188 210 <--- Q したがって，答えは 210 通り，になります。 実際の計算は，対称性なども考慮できるので，暗算でできますね。 |
|
ネコの住む家
3月15日（木） 10:29:42
MAIL:uchi@sco.bekkoame.ne.jp 39114 |