CodeIQ:マヨイドーロ問題を解く
CodeIQ のマヨイドーロ問題を解いていました。
解答が締め切られたので、その振り返りをしようと思います。
マヨイドーロ問題
こちらをご覧下さい。
CodeIQの問題に挑戦しよう！
アルゴリズム
いちいちどんなルートがあるのか虱潰しに列挙するのは枚挙に暇がないのでスマートではないですね。
そこで私は以下の様に考えました。
N回反転した時の各マヨイor出口までのルートのパターン数を数えて、反転数0〜N回の時のYまでのルートのパターン数の総和を取ればよくね？
…これもこれで、スマートとは言いがたいような。
というわけで、0〜N回反転した時の、全地点までのルートパターン数を数えていきます。
ただし、Bから反転した時に、Aに辿り着くパターン(Zの方を向いていた時)と、Cに辿り着くパターン(Yの方を向いていた時)があるので、両者を区別するために、前者をBz、後者をByとします。
Bz・Byを加えた各地点で前進or反転したときの状態遷移図は次のようになります。
n回反転した時の各地点までのルートパターン数を、N+1×全地点数の2次元配列dpを用意して数え上げていきます。
| n | Z | C | Bz | By | A | Y |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 | 0 | 0 |
| … | … | … | … | … | … | … |
(0で初期化)
N=0
反転できないので、ゴールまでのルートは、Bz→C→Zの1パターンのみです。
これを配列dpに反映するとこうなります。
| n | Z | C | Bz | By | A | Y |
|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 | 0 | 0 |
| … | … | … | … | … | … | … |
N=1
N=0のときの各マヨイまでのルート情報から、各マヨイにて反転した時のルート情報をdp[1][*]に追加します。
- A → Bz : dp[1][Bz] = dp[0][Bz] + dp[0][A]
- By → C : dp[1][C] = dp[0][C] + dp[0][By]
- Bz → A : dp[1][A] = dp[0][A] + dp[0][Bz]
- C → By : dp[1][By] = dp[0][By] + dp[0][C]
| n | Z | C | Bz | By | A | Y |
|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 |
| 2 | 0 | 0 | 0 | 0 | 0 | 0 |
| … | … | … | … | … | … | … |
また、Aへは1Byから直進してもいけるので、d[1][A]までのルートのパターン数にd[1][By]を加算します。
| n | Z | C | Bz | By | A | Y |
|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 2 | 0 |
| 2 | 0 | 0 | 0 | 0 | 0 | 0 |
| … | … | … | … | … | … | … |
同様に、A → Y。
| n | Z | C | Bz | By | A | Y |
|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 2 | 2 |
| 2 | 0 | 0 | 0 | 0 | 0 | 0 |
| … | … | … | … | … | … | … |
(省略しますが、Bz→C、C→Zでも同様の処理をします)
N回反転した時ではなくて、0〜N回反転した時のゴールまでのルートのパターンを知りたいので、n回反転したときのルートのパターン数に、n-1回反転した時のものを加算します。
- dp[1][Y] = dp[1][Y] + dp[0][Y]
- dp[1][Z] = dp[1][Z] + dp[0][Z]
| n | Z | C | Bz | By | A | Y |
|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 2 | 2 |
| 2 | 0 | 0 | 0 | 0 | 0 | 0 |
| … | … | … | … | … | … | … |
以下、n=Nとなるまで繰り返して、dp[N][Y]が最終的な解答となります。
個人的な結果
以上のアルゴリズムを C++・Python・Java で実装して提出したのですが、C++はNが大きくなるとオーバーフローしてしまって最後まで解けませんでした(unsigned long long intでも間に合わず、boost/multiprecision/cpp_int.hpp はCodeIQではインクルードできなかった)。
JavaはBigInteger型があるし、Pythonはオーバーフローしそうになったら自動的に多倍長整数になるので上限がないのは便利ですね。
