World Tour Finals 2019 C1: Triangular Lamps Easy

まず，問題を言い換えて状況を整理する． $(X, 0)$ のランプに加え，最初から $N$ 個のランプも点灯しているとみなし，うまい操作によって全てのランプを消灯させられるような $X$ を求めればよい．

ここで，「点灯しているランプのうち最大のy座標」が小さくなるように操作を繰り返すことを考える．

考察として，初期状態で点灯しているランプが1つだけの場合（簡単のため座標 $(0, 0)$ とする）を検討する．手を動かして実験すれば，ちょうど $y=-l$ より上側のランプを全部消灯し終えた時点で， $0 \leq x \leq l, y = -l$ のランプの点灯・消灯が ${}_l C_x \; {\rm mod} \; 2$ に対応していることがわかる．この値はLucasの定理を用いて非常に簡単に求められて，特に $l$ が(2のべき乗)-1のときは全ての値が1になる（伏線）．

任意個のランプが点灯している場合も，線形性より，各ランプからの寄与を計算してxorをとれば， $y=-l$ より上側のランプを全て消し終えた段階での $y=-l$ でのランプの点灯状況がわかる．具体的には、初期状態で $N$ 個のランプ $(x _ i, y _ i) \; (i = 1, \ldots, N)$ が光っていたとして、y座標が $l$ より大きいランプが全て消えている状態になるまでの操作をちょうど終えた段階で、 $(k, l)$ における点灯状況は $f(k, l) = \sum_{i = 1} ^ N {} _ {y _ i - l} C _ {k - x _ i} \; ({\rm mod} \; 2)$ で表される．

$(X, 0)$ のランプを加えた $N+1$ 個のランプに対して点灯しているランプのy座標の最大値を減らしていく操作を続ければ，いずれ全てのランプが消灯するはずであるから， $N$ 個のランプに対して操作を繰り返した時の点灯状況は $(X, 0)$ のランプに対して操作を繰り返した際のそれと一致しなければならない（mod 2で考えているため）．

ここで，Lucasの定理より，十分小さいy座標として例えば $l = -2 ^ {60}+1$ をとると， $N$ 個のランプに対して計算した $f(k, l)$ は $X \leq k \leq X + 2 ^ {60} - 1$ をみたす任意の $k$ に関して $f(k, l) = 1$ , 他の任意の $k$ に関して $f(k, l) = 0$ になる．直線 $y=l$ 上で， $f(k, l)$ の値が0から1へ変わる地点 $k$ を二分探索で求めれば，これが求めたい $X$ である．

実装

atcoder.jp