AtCoder Regular Contest 088

今回から余裕があれば自分の解法とか感想とかを書いていこうかと思う。
思考の過程を整理したり、解法を一度文章にまとめたりすることで競プロ強くなんないかなと淡い期待。

結果はCDEの3完で101位でした。

C - Multiple Gift

必要条件を徐々に広げていく感じで考察していくと、

の漸化式で、 $A_n\leq Y$ となるような最大の $n$ まで生成した数列が、条件を満たす長さが最大となる数列の一つだとわかる。よってこの $n$ が解。
愚直に1つ1つ計算して長さを求めると $O(\log\frac{Y}{X})$ で通る。

$N:=|S|$ とする。また、添字は0-basedとする。

制約から想定解法は $O(N\log N)$ っぽいし、問題中で「最大の整数 $K$ を求めてください。」とあったので、二分探索をまず疑った。

ので、 $K$ を固定してそのときにすべて $0$ になるような数列にできるかを考えた。

の順でだったら区間でフリップ。
- この操作で $S_0, S_1, \cdots, S_{\min(K-1, N-K)}$ は $0$ になる。
がすべてになれば、もとの数列は条件を満たす。
- $\because$ $S_i=1\land i\geq K$ ならば、「区間 $[0, i+1)$ でフリップ→区間 $[0, i)$ でフリップ」をすることで $S_i$ のみの反転が可能で $S_i=0$ にすることができるから。
逆にのうちが存在すれば、もとの数列は条件を満たさない。
- $\because$ このとき、 $S_0=S_1= \cdots =S_{i-1}=0\land S_i=1$ となる $i\in \{N-K+1, N-K+2, \cdots ,K-1\}$ が存在する。 $S_{i-1}$ と $S_{i}$ を同じ数字にするためには少なくとも1回は区間 $[s, i)$ （ただし $s\in\{0, \cdots, i-1\}$ ）または区間 $[i, t)$ （ただし $t\in\{i+1, \cdots, N\}$ ）でフリップする必要がある。しかし、 $\max (i-0, N-i) \leq K-1 \lt K$ より、そのようなフリップはできない。
- （コンテスト中では直感で正しそうだったので、ちゃんと証明せずにコードを書いた）