AGC020 B - Ice Rink Game

初めに

atcoder.jp 解けなかったので

敗因

例えば A_K は必ず 2 でないといけなくて, A_{K-1} は 2, 3 でないといけなくてみたいなこと( -1 のときはどうなるのかを)を考えていました. ( -1 になるときを中心に考察を進めても難しいので) K = 10^5 から線形にできる方法を考えるべきでした.

解法

各ラウンド直後の最小, 最大をもっておけばそのひとつ前が計算できます. O(K) です. 具体的には, L_i, R_i を i ラウンド後の最小 / 最大値としたときに,

L_{i-1} = \left \lceil \frac{L_i}{A_i} \right \rceil \cdot A_i

R_{i-1} = \left \lfloor \frac{L_i}{A_i} \right \rfloor \cdot A_i + ( A_i - 1 )

が成り立ちます. atcoder.jp

別解

( log がつくけど)二分探索でも通ります. 「広義単調増加関数同士の合成関数もまた広義単調増加関数になる」そうです(知りませんでした, これって自明ですか? よく考える余地があるかも?). そうすると Editorial での g が広義単調増加関数になるので二分探索ができます, と. なるほど... 最小最大で分けて二分探索をして逆転してしまえば -1 . 賢いですね. atcoder.jp

終わりに

よくかんがえれば dp なのか, むずかしい...