読者です 読者をやめる 読者になる 読者になる

たぶん週刊「今週の進捗」

1週間に勉強したことや実装したことをネタに、週に1回(主に土日に)更新していく予定です。「多分」なので、臨時休刊があってもご海容ください。

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++PythonJava で実装して提出したのですが、C++はNが大きくなるとオーバーフローしてしまって最後まで解けませんでした(unsigned long long intでも間に合わず、boost/multiprecision/cpp_int.hpp はCodeIQではインクルードできなかった)。
JavaはBigInteger型があるし、Pythonはオーバーフローしそうになったら自動的に多倍長整数になるので上限がないのは便利ですね。

反省

結城浩の「マヨイドーロ問題」解説|CodeIQ MAGAZINE

  • なんか解き方が全然違う… フィボナッチ数が顔を覗かせるのは気づいたけど、再帰で解こうなんて思いもかけなかった。
  • 数学的構造を活かして解くこともなかったし、多倍長整数演算はC++でできなかったらすぐに違う言語に手を出したし、高速化はほとんど必要なかった。まぁ動的計画法っぽいアルゴリズムを考えるのは楽しかったしいいや。
  • 文字列を使った多倍長整数!そういうのもあるのか
  • メモ化はあとで調べておこう。

メモ

多倍長整数 - boostjp

今回の反転可能回数のような数を num_○○ とすると、○○に固有に割り当てられた番号と捉えられないか不安になるのだが、もっと適切な名前はないだろうか。