コラッツ写像

2 secs 1024 MB

この問題を愚直に解こうとすると

の $O(S2^N)$ 通りを試す必要があります。

実行時間制限の $2$ 秒では $10^9$ 回程度の演算しかできないため、 $S\times2^N \approx 10^{18}\times2^{14} \approx 10^{22}$ 回の演算は TLE となります。

そのため、工夫して時間計算量を削減しましょう。

具体例として入力例 $1$ の操作列を考えます。

$(3, 5) \xrightarrow{i = 1} (10, 5) \xrightarrow{i = 2} (10, 16) \xrightarrow{i = 1} (5, 16)$

$i = 1$ を選んだ操作と $i = 2$ を選んだ操作は独立です。つまり、 $i = 1$ を選んだ操作と $i = 2$ を選んだ操作の順番を入れ替えても最終的な値は変わりません。

よって、入力例 $1$ の操作列は次のように並び替えられます。

$(3, 5) \xrightarrow{i = 1} (10, 5) \xrightarrow{i = 1} (5, 5) \xrightarrow{i = 2} (5, 16)$

なので、 $i = 1$ を選んだ操作をしたあとに $i = 2$ を選んだ操作をするとして良いです。

さらに計算量を削減するため、入力で与えられる $(Y_1, Y_2)$ から $X_1 + X_2 = S$ となるような $(X_1, X_2)$ を探す方法を考えます。

整数 $A$ に対して整数 $B$ を次のように定義します。

この $B$ は $A = X_i$ のときに、操作手順 $2$ を行った後の $X_i$ の値です。

$A$ を $B$ を用いて表します。

よって $B$ となりうるのは $A = 2B$ と $A = (B - 1) / 3$ に限られることがわかります。

したがって、 $(Y_1, Y_2)$ から逆操作を $N$ 回繰り返して、 $X_1 + X_2 = S$ となるような $(X_1, X_2)$ のペアがあるかを調べれば良いです。

以上の考察を元にすると、

の計 $O(N2^N)$ 通りについて、それぞれ $N$ 回の逆操作を実際に行って $X_1 + X_2 = S$ となるかを判定することにより、 $O(N^22^N)$ で解くことができます。

これは再帰関数や bit 全探索によって実装できます。