結城浩の「マヨイドーロ問題」

競技プログラミング

※このエントリは競プロで圧倒的成長 Advent Calendar 2015の17日目のエントリです．

問題

※ 出題が終わってしまったため上記のURLから問題が見られません．「マヨイドーロ問題」で検索すると出題pdfが見られます．(pdfへの直リンクは禁止らしいのでここに貼っていません．)

問題概要

  • Xから入ってY, Zから出ることのできる「マヨイドーロ」がある
    X
    　＼
    YーーーーZ
  • マヨイドーロはZ付近 (A)，Y付近 (C)，Xから道ZYへの合流地点 (B)で折り返すことができる
  • N回まで折り返すことができる時，N回以内の折り返しでYから出るパターンの数Pを求める

解法

  • N=nの時のPをPnとする
  • 奇数回折り返すと左へ，偶数回折り返すと右へ行く
  • Yから出るためには奇数回折り返さなければない
  • Pnをいきなり求めるのは難しいので，丁度n回折り返してY or Zから出るパターン数，Qnを考える
    • A，Cから折り返してきた時，次はB, CもしくはB, Aで折り返すことができる
    • Bから折り返してきた時，次はCもしくはBで折り返すことができる
    • 1回目の折り返しはAで折り返してきたと考えることができる
    • 従ってn=1の時，Bで折り返す，Cで折り返すの2通りの行動が取れるため，Qn=2
    • 続いてn=2の時，Bから折り返してきた時，Cで折り返すの1通り，Cから折り返してきた時，B, Cで折り返すの2通りで，Qn=3
    • 同様に求めていくとQ1=2, Q2=3, Q3 = 5, Q4 = 8となり，Qnはフィボナッチ数列のn+2項目であることがわかる
  • Pnは丁度k回折り返してYから出るパターン数をk<=Nの場合に足し合わせたものである
    • nが偶数の時は丁度n回折り返してYから出ることはできない
    • 従ってnが奇数の時のQnを足しあわせたものが答えである

Nの制約条件が書かれていないため何も考えずに，フィボナッチ数列を一般項を使って求めたらオーバーフローした．
多倍長を使って，整数のみで求めて無事正解．
数学的な証明はできなかったので賢い人の解説待ち．