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の家にいく場合の数)
こうすることで、単純な場合の数を書き出していけば見通しがたつようになります。
では、原点から座標にいくような場合の数を考えます。
これも1~6あたりまで実験をすると、法則性が見えてきます。
実は、以下の式のようになっています。
そしてこの数式をから列挙してみると、
1,1,2,3,5,8,13,21,34,55,89...
となっていて、実はフィボナッチ数列になっています。
番目のフィボナッチ数をとしたとき、問題の答えは以下のように言い換えることができます。
- のなかで番目に小さいもの
ここで、被っているものを排除するため、のときは、のときはとします。 それ以降はいつものフィボナッチ数列になります。
あとは、を入力したときに、とが何かがわかれば、答えを求めることができます。
ここも実験をしてみます。
とを探索してひたすら試します。
プログラムを組み、との範囲を1~15あたりにして実験すると見えてきます。
まず、以下のことがわかります。
- のとき、となるのはかつの場合のみ
つまり、被りが存在しないということです。
そして、肝心の順番はこうなっています。
は、が小さい順に並んでいる。
が等しい中では、としたときに、という順番で出てくる。
例えば、のとき、になっているのですが、
順番にと並んでいます。
あとは、この法則をうまくプログラムに落とし込み、計算をします。
は二分探索で調べます。 ~ぐらいまでの範囲をとっていれば十分です。
を満たすような最小のがの答えになります。
次に、の数字を特定します。これができれば、でも求めることができます。
のときののパターン数は、となっています。また、それまでの総和が
なので、の番目が求めるものになります。長いので、これをと置きます。
がの半分を超えているかどうかでの偶奇を判定します。超えていなければ奇数、超えていれば偶数になります。
奇数のときは、そのままとすれば完了です。
偶数のときは、となります。
が求まったので、でを求めます。あとは、
をで割って余りを求めれば完了です。
これを求めるのは行列式を活用します。
ですので、
これを先に求めていき、そこから乗と乗を求めていけば、高速に求めることができます。
あとは計算をして答えを出力すれば完了になります。