Educational Codeforces Round 52 G. Fibonacci Suffix

Problem - G - Codeforces

面白い問題を自力で通せたので記録。

問題概要

文字列の列 $F(i)$ を、漸化式

$F(0) =$ "0" $, F(1) =$ "1" $, F(i) = F(i-2) + F(i-1)$

で定義する。この $+$ は文字列の結合を示す。

整数 $n, m, k$ が与えられる。 $F(n)$ の接尾辞を辞書順に並べた時、 $k$ 番目に該当する文字列の先頭 $m$ 文字を求めよ。（ただし、その文字列の長さが $m$ 未満の場合は文字列全体を出力せよ。）

制約

$1 \le n, m \le 200$
$1 \le k \le 10^{18}$
$k$ は $F(n)$ の長さを超えない

考察・解法

方針を考える

タイトルにもあるように漸化式がフィボナッチ数列のようになっていて、 $F(i)$ の長さは通常の意味でのフィボナッチ数となる。 $n=200$ のときを計算してみると $|F(n)| \simeq 4.54\times 10^{41}$ となり非常に大きい数となる。

注目すべきは $m \le 200$ であり、要求されているのは高々200文字なので、接尾辞のうち201文字目以降は区別する必要がない。そのため「先頭200文字が○○○になるような接尾辞はいくつあるか？」という分布のようなものを計算できれば、それを辞書順で前から加算し、累積 $k$ 個以上になった時点での文字列が答えである。

接尾辞を効率的に数える

01 で構成される200文字の文字列は最悪 $2^{200}$ 通りあるが、 $F(i)$ には同じ文字列が繰り返し含まれているため、パターン数はぐっと少なくなる。

具体的には、 $i$ を適当に決めて $A = F(i-1), B = F(i)$ とすると、 $F(i)$ 以降の文字列は全て $A, B$ を並べたものになる。そのため以下のような方針で、接尾辞の先頭200文字の分布を求めることができる。

$A = F(i-1), B = F(i)$ がおよそ200文字になるように $i$ を適当に決める。
それ以降の $F(i)$ で、文字列の連結も含めて $A, B$ の組み合わせとして登場し得るパターンを列挙する。
それぞれのパターンで登場する200文字以内の部分文字列と、その登場回数を計算し、全て合計する。

$A, B$ として固定するものとしては、 $|F(11)| = 144, |F(12)| = 233$ なのでこれを使う。

$F(n)$ 内に存在する「200文字以内の部分文字列」の登場パターンとして考慮すべきは、以下のものである。

文字列の最後に存在する $B$ の接尾辞1～199文字
$B$ の200文字の部分文字列
$BA$ の200文字の部分文字列のうち、前の $B$ を199文字以下含むもの
$BB$ の200文字の部分文字列のうち、前の $B$ を1～199文字含むもの
$ABA$ の200文字の部分文字列のうち、最初の $A$ を1文字以上含むもの

漏れとダブリがないよう、そのパターンが $F(n)$ にいくつ登場するかの回数も含めて計算していく。各パターンの登場回数はフィボナッチ数に似た漸化式で表せるので前計算しておく。

これで、接尾辞の先頭200文字としてあり得るものについて、それが $F(n)$ にいくつ登場するかが数えられる。実際にやってみると登場する文字列はちょうど400種類になった（！？）。十分扱えそうな個数である。

「 $k$ 番目」を求める

分布が求められたので、実際に $k$ 番目を求めていく。…といっても、高々200文字の文字列が400個なので、辞書順でソートして前から見ていけば十分間に合う。

最初はTrie木を使うと速いかなと思ってそっちを使ったが、mapに順序関係を保ってもらった状態で個数をカウントし、前から見ていったほうが実行時間も短かった。

ACコード

map Submission #44541587 - Codeforces
Trie木 Submission #44495360 - Codeforces

実装上の注意点としては、

$A = F(11), B = F(12)$ として $A, B$ の組み合わせだけで考えた場合、 $n \le 11$ のときはこのやり方では答えが出ない。ただその場合は接尾辞の総数が少ないので、普通に全列挙＆ソートして直接 $k$ 番目を取ってしまえばよい。
数え上げた結果がものすごく大きな数になり得るので注意。 $10^{18}$ を超える個数は数えても無意味なので、個数を足し算するごとに「結果が $10^{18}$ を超えていたら $10^{18}$ にする」などの処理をしておけばOK。