AtCoder Grand Contest 073 A問題メモ

AtCoder Grand Contest 073

ついに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$ に含めておく必要がある。

Python3

programming_algorithm/contest_history/atcoder/2025/0928_agc073.txt · 最終更新: by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0