コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 1818 (記事作成時点)

供養

解法

操作を次のように考える
1. $x$ を $x + a$ にする、ここで $a \in \lbrace 0, 1 \rbrace$ である
2. $y$ を $y + b$ にする、ここで $b \in \lbrace 0, 1 \rbrace$ である
3. $x$ を $x + y$ にする
4. $y$ を $x + y$ にする
上記からなる操作列を $1 \to 2 \to 4 \to 3 \to 1 \to \dots$ と繰り返すことを考える
$n$ 回目の $1 \to 2 \to 4 \to 3$ を実行したときに操作 $1$ もしくは $2$ で増加した数を $a_{n}, b_{n}$ とすると、各ループが終わった時の $(x, y)$ の値は
- $(2a_{1} + b_{1}, a_{1} + b_{1})$
- $(5a_{1} + 3b_{1} + 2a_{2} + b_{2}, 3a_{1} + 2b_{1} + a_{2} + b_{2})$
- $\dots$
よって、$n$ 回目のループ終了時の $x$ の値に関する一般項 $x_{n}$ は $x_{n} = \sum_{i = 1}^{n}(f_{2i + 1}a_{i} + f_{2i}b_{i})$
- ここで $f_{k}$ はフィボナッチ数列の第 $k$ 項を意味する
$N$ を表現するために十分な数の $n$ を用意して、$f_{k}$ の降順にgreedyに $a_{i}, b_{i}$ を決めていけばよい
- $n$ を $f_{2k + 1} + f_{2k} \ge N$ となる最小の $k$ とした場合、$n = 43$ で十分であることがわかる
以下のように操作列 $S$ を作成できる
- $f_{2i + 1} \le N$ ならば $1$ を $S$ に加えて $N = N - f_{2i + 1}$
- $f_{2i} \le N$ ならば $2$ を $S$ に加えて $N = N - f_{2i}$
- $4, 3$ を $S$ に加える
この方法だと $N = 679891637638612257$ のとき $|S| = 129$ となるのがおそらく最長
- greedyに選ぶと $b_{i}, a_{i - 1}$ や $a_{i - 1}, b_{i - 1}$ が連続して $1$ になることはない
  - それぞれ $a_{i}, b_{i}$ で選択してしまうため
- そのため、$|S|$ は高々 $3n$ 程度で抑えられる
- $n$ を用意するときに $\sum_{i = 1}^{k}f_{k} \ge N$ となる最小の $k$ で止めてしまうと、すべてのループですべての操作をする可能性があり、最大で $4n$ くらいになってしまう
  - この場合 $n = 42, |S| = 168$ くらいになってしまう