4問まで減ったけど後半は結局縁がないんだよな～

結果

o(2)--- 97:26 209位

Perf:2286 2027->2056 (+29)

A問題

https://atcoder.jp/contests/agc073/submissions/69711954

良さそうな言い換えを頑張って探す。そのために「弦の集合 $S$ を用いたとき黒い領域はいくつできるか？」判定問題を解こうとすると、 $A _i$ の小さい方から順に走査して「終点が $\lbrack A_i+1,A_i+K-1 \rbrack$ に入る弦の個数」を $d$ としたとき $\lfloor d/2 \rfloor +1$ 足す操作を繰り返して得られる合計がその問題の答えになることがわかる。

ある区間の寄与について考える。上の問題の $d$ を用いると、寄与は $2^ {n-d-1} \sum \binom{n}{i} \lfloor i/2+i \rfloor$ みたいなことになる。あとはこれを高速に求めればよいことになり、式変形はAIに任せてもできるし実験エスパーでもできる。（AGCなので、堂々とAIを使える）結局、

$(d-1)2^ {d-2}+2^ d$

みたいな式が出てくることになる。

B問題

N=2ですらよくわかんない......

感想

パフォーマンス2200ありがとう......