階段の登り方は？
競技プログラミングが広まって欲しいので
数学的に面白いなと思った問題を試験的に紹介。
(人の頭では、数学的な解き方は分かっても実際に計算するのは不可能だけど)
問題文
段の階段があります。高橋君は現在、上り口( 段目)にいます。 高橋君は一歩で 段か 段上ることができます。
ただし、いくつかの段の床は壊れており、その段に足を踏み入れることは危険です。
壊れている床を踏まないようにしながら、最上段( 段目)にたどりつくまでの移動方法は何通りあるでしょうか？
(AtCoder Beginner Contest 129を一部改変)
例えば、6段までの階段の内、3段目が壊れている場合は、
の4通りになる。
以下、私が一般解を求めるプログラムをつくるまでの思考を書いていくので、
ヒントにしたり、ヒントなしで考えてみて欲しいな。
思考1
移動が出来ない(=0通り)になる場合を考えました。
これはすぐ分かる通り、連続で階段が壊れていた場合です。この場合は例外処理しました。
思考2
階段が壊れていた場合に、前後の移動が単純(1通り)になることに気づきました。
例えばn段目が壊れている場合、n-1段目に着き、1段飛ばしてn＋1段に行く必要がある。
思考3
階段が壊れていない場合に、何通りになるのかを考えました。
問題を単純化し、少ない段数で考えはじめました。
1段の場合：
...1通り
2段の場合：
3段の場合：
0 → 2 → 3
0 → 1 → 3 ...
4段の場合：
0 → 1 → 2 → 3 → 4
0 → 2 → 3 → 4
0 → 1 → 3 → 4
0 → 1 → 2 → 4
0 → 2 → 4 ...5通り
ここら辺で法則性に気づきました。あとはこれまでの思考を合わせて、解き方を求めました。
ということで
解法
階段が壊れていない、n段目までの通り数は、n-1段目又は、n-2段目から、移動するしかなので、f(n)をn段目までの通り数とするとf(n) = f(n-1) + f(n-2)で求まる。(フィボナッチ数列と同じ方法) また、壊れた段の前後の動き方は固定化されるので、
N段目までの通り数A(初期値1)は、
壊れている直前までの段数を数え、フィボナッチ数列と同様に、その段までの通り数Bを求め、A＝A×Bとする。壊れた段を飛び越える。
という操作を目的の段まで繰り返すことで求まる。
ちなみにn段目が壊れていないときは、
f(n) = f(n-1) + f(n-2) で良いんですけど
n段目が壊れているときは、f(n)=0にすると、わざわざ前後を考えなくても、綺麗に求まります。
x-1段が壊れているとすると f(x)=f(x-2)となるので、
(なんなら2段連続壊れている場合にも対応している)
解法はこんな感じでした。多分しっかり考えれば、分かる程度に色々書いたと思うので、是非考えて欲しい。
最後に当時私が書いた、前者の解法のプログラムと、後者の綺麗なプログラム載せて終わります。(言語はPython3)
私のやつ
一応、フィボナッチ数列を作成することで高速化を図ってる…
模範解答(恐らく)
inの判定はリストだと遅いので、セットにしないと駄目
以上です。お疲れ様でした。
