ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 2372 - IkaNumber

問題

提出コード
自力でなんとか解けました!時間は4時間くらいかかりました…
くコ:彡 くコ:彡 くコ:彡 くコ:彡

解法

問題を読んだだけではかなり自由度が高いので、一つ一つ見ていくことにします。
まず、Taroの家の位置を固定します。
Taroの家、にんじん、Hanakoの家の3つすべてを好きな場所に置くことができますが、Taroの家とにんじん、にんじんとHanakoの家の距離がすべて同じだった場合はイカ数が必ず等しくなります。なので、わかりやすくするためにTaroの家を原点に固定します。
次に、小さなケースで実験をしていきます。
(にんじんの座標,Hanakoの家の座標)としたとき、(1,2),(1,3),(2,3),(1,4),(2,4),(3,4)...というパターンが考えられるので、その場合のイカ数をそれぞれ計算していくと、1,1,1,2,1,2...となっています。
この実験をするとわかるのが、

  • にんじんの前後のマスは必ず止まらないといけない

ということです。
にんじんの2マス前に止まったとき、1マスすすむことはできますが、2マスすすむとにんじんのマスに止まってしまうので、にんじんの1マス前に止まることしかできません(それ以上前のマスの場合もにんじんを超えた先に行くことはできません)。同様に、にんじんの1マス前に止まったとき、1マスすすむとにんじんのマスに止まってしまうので、にんじんの1マス先に止まることしかできません。よって、にんじんの前後のマスには必ず止まることになります。
そこで、イカ数は次のように書き換えることができます。
(原点からにんじんの1マス前にいく場合の数)×(にんじんの1マス先からHanakoの家にいく場合の数)
こうすることで、単純な場合の数を書き出していけば見通しがたつようになります。

では、原点から座標xにいくような場合の数を考えます。
これも1~6あたりまで実験をすると、法則性が見えてきます。
実は、以下の式のようになっています。
{ \displaystyle \sum{_{i=0}^{x/2}}  _{(x-i)}C_i}
そしてこの数式をx=0から列挙してみると、
1,1,2,3,5,8,13,21,34,55,89...
となっていて、実はフィボナッチ数列になっています。
i番目のフィボナッチ数をf[i]としたとき、問題の答えは以下のように言い換えることができます。

  • f[i]×f[j]のなかでk番目に小さいもの

ここで、被っているものを排除するため、i=1のときはf[i]=1i=2のときはf[i]=2とします。 それ以降はいつものフィボナッチ数列になります。
あとは、kを入力したときに、ijが何かがわかれば、答えを求めることができます。
ここも実験をしてみます。
ijを探索してひたすら試します。
プログラムを組み、ijの範囲を1~15あたりにして実験すると見えてきます。
まず、以下のことがわかります。

  • i \neq a,j \neq bのとき、f[i]×f[j] = f[a]×f[b]となるのはi=bかつj=aの場合のみ

つまり、被りが存在しないということです。

そして、肝心の順番はこうなっています。

  1. f[i]×f[j]は、i+jが小さい順に並んでいる。

  2. i+jが等しい中では、 i \leqq jとしたときに、i:1,3,5,7,9...8,6,4,2という順番で出てくる。

例えば、 10 \leqq k \leqq 12のとき、i+j=7になっているのですが、
順番に(i,j)= (1,6),(3,4),(2,5)と並んでいます。
あとは、この法則をうまくプログラムに落とし込み、計算をします。
i+jは二分探索で調べます。 210^{9}ぐらいまでの範囲をとっていれば十分です。
(i+j) \leqq \frac{p}{2}×\frac{(p+1)}{2}
を満たすような最小のpi+jの答えになります。
次に、iの数字を特定します。これができれば、j=p-ijも求めることができます。
i+j=pのときのiのパターン数は、\frac{p}{2}となっています。また、それまでの総和が

\frac{(p-1)}{2}×\frac{p}{2}なので、i+j=p\{k - \frac{(p-1)}{2}×\frac{p}{2}\}番目が求めるものになります。長いので、これをqと置きます。
q\frac{p}{2}の半分を超えているかどうかでiの偶奇を判定します。超えていなければ奇数、超えていれば偶数になります。
奇数のときは、そのままi=2×q - 1とすれば完了です。
偶数のときは、i=2×(\frac{p}{2}-q+1)となります。
iが求まったので、j=p-ijを求めます。あとは、
 f[i]×f[j]10^{9}+7で割って余りを求めれば完了です。
これを求めるのは行列式を活用します。

{\displaystyle 
  \begin{pmatrix} 
f[n]\\
f[n-1]
\end{pmatrix}
=
    \begin{pmatrix}
      1 & 1   \\
      1  &0
    \end{pmatrix}
  \begin{pmatrix} 
f[n-1]\\
f[n-2]
\end{pmatrix}
}

ですので、

{\displaystyle 
    \begin{pmatrix}
      1 & 1   \\
      1  &0
    \end{pmatrix}
^{2×n}
}

これを先に求めていき、そこからi乗とj乗を求めていけば、高速に求めることができます。
あとは計算をして答えを出力すれば完了になります。