AtCoder Grand Contest 073 A問題メモ
ついにAGCでもChatGPTでそのまま解けたという例が現れたらしい。すごいねぇ(他人事)
A - Chords and Checkered
問題文
- 整数 $L,K$ 及び長さ $N$ の非負整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます.
- ここで,$2K \lt L$ 及び $0 \leq A_1 \lt A_2 \lt \cdots \lt A_N \lt L$ が保証されます.
- 周の長さが $L$ の円を考えます.
- この円の適当な点を基準点としてとり,そこから円周上を距離 $x$ だけ時計回りに進んだ場所を座標 $x$ の点と呼ぶことにします.
- また,各 $i$ ($1 \leq i \leq N$) について, 座標 $A_i$ の点と座標 $A_i+K$ の点を結ぶ弦を考え,これを弦 $i$ と呼ぶことにします.
- 弦の集合 $s$ に対して,以下の手順で スコアを定めます.
- $s$ に含まれる弦をすべて描く.描いた弦によって円がいくつかの領域に分かれるので,それらを白と黒で塗る.
- まず円の中心が含まれる領域を白く塗り,残りの領域は,(長さ正の線分で)隣接する領域の色が異なるように塗る.
- このような塗り方は常に一意に存在することが証明できる.
- ここで黒く塗られた領域の個数をスコアとする.
- $s$ としてあり得る集合は $2^N$ 通りあります.
- これらすべてに対するスコアの総和を $998244353$ で割ったあまりを求めてください.
制約
- $1 \leq K$
- $2K \lt L \leq 10^9$
- $1 \leq N \leq 250000$
- $0 \leq A_1 \lt A_2 \lt \cdots \lt A_N \lt L$
- 入力はすべて整数
解法
まず、各 $i=1,2,...,N$ について、$1~i-1$ の採用有無が決まっている状態で弦 $i$ を採用することの寄与(採用することで新たに増える黒の領域の個数)を考えてみる。
少し実験すると、弦 $i$ と「端以外の交点を持たない弦の採用可否」は関係せず、
「端以外の交点を持つ弦($A_j \lt A_i \lt A_j + K$ なる $j$)」の、特に「個数」のみが重要であることが分かる。
この個数を $x$ とする。$x$ は二分探索で簡単に分かる。
$x$ 個のうち採用したのが $y$ 個である状態に弦 $i$ を引くと、交点は必ず $y$ 個でき、弦 $i$ は $y+1$ 個の区間に分かれる。
これを、$A_i+K$ に近い方から順に区間 $1,2,...,y+1$ と名付ける。
問題の制約から、区間 $1$ が通る領域は弦 $i$ を引く前は必ず白であった。
その後は交互に白と黒を通過するので、区間 $1,3,5,...$ が白、$2,4,6,...$ が黒を通過することになる。
白の領域をぶった切ると、白と黒が1つずつになり、黒の領域の個数が1増える。
黒の領域をぶった切っても、白と黒が1つずつになるが、この時は黒の領域の個数は増えない。
よって、$\lceil \frac{y+1}{2} \rceil$ 個、黒が増えることになる。
$x$ 個中、$y$ 個を採用する方法の個数は二項係数を使って ${}_x \mathrm{C}_y$ である。
$\displaystyle f(x) = \sum_{y=0}^{x} {}_x \mathrm{C}_y \left\lceil \frac{y+1}{2} \right\rceil$ が求まればよい。
これは、二項係数の偶数番目と奇数番目の和が等しいことを利用すると、以下のように変形できる。
または、最初の方を愚直に求めてOEISで検索すると A045623 が見つかる。
- $f(0)=1$
- $f(x)=(x+3)2^{x-2}$($x \ge 1$)
ここに、交点を持たない弦 $N-x-1$ 本の採用の自由度 $2^{N-x-1}$ を乗じたものが、 弦 $i$ を採用したときの寄与となり、各 $i$ についての合計が答えとなる。
ただし、$A_i \lt K$ となる $i$ については、ループを考慮して1周前から来て交点を持つものも $x$ に含めておく必要がある。