👻

ABC256のF問題を変な解き方で通してしまった？

2023/10/18に公開

問題はこちら
正しいのかわかりませんが通ったので正義です

ちなみに提出はこれです

解法

公式解説とほぼ同じ。
式をいじいじすると

D_x = \sum_{i=1}^{x}\frac{(x-i+1)(x-i+2)}{2}A_i

となります。
公式解説はここから展開していますが今回はこのまま考えます。

まずはじめに初期状態での数列 $D$ を求めてしまいます $O(N)$

次に、 $A_x$ を $v$ に更新するクエリが来た直後に $D_y$ を出力するクエリが来た時を考えます。

$x>y$ のとき、 $D_y$ の値は最初に求めたものと変わらないのでそのまま出力します
$x\leq{y}$ のとき、一番上のシグマの式より $D_y$ から $\frac{(y-x+1)(y-x+2)}{2}A_x$ を引いて $\frac{(y-x+1)(y-x+2)}{2}v$ を足せばこのときの正しい $D_y$ の値が得られます。

上の操作自体は $O(1)$ です。

あとはクエリを貯めていって出力のたびに関係ある箇所 ( $x\leq{y}$ のとき) を計算して出力すればよいです。

例えば、更新クエリが100個来た後に出力クエリが来たら100個分のクエリ内容をチェックして今回の出力に関係あるところは計算していけばうまくいきます。更新クエリが同じ $x$ に対して2つ以上来ることがあるのでそれに注意してください

が、TLEします。(それはそう)

オーダーを計算すると $O(QN)$ になるので $10^{10}$ です。無理です。

ここからが今回の解法の主な部分です。
クエリが貯まるとそれに比例して出力の際計算が重くなることに着目してそれを解消すればいいのではと考えました。

具体的にはクエリを1000個貯めたら $A$ と $D$ を再構築し、溜まっているクエリが0になるような状態を作ります。
それまでのクエリで言われたとおりに $A$ をすべて更新し、それをもとに累積和を3回して現時点での $D$ として再構築します。

制約から、再構築が行われる回数は最大で200回、常にクエリを1000個貯めている状態で出力していたとしても $O(1000*Q)$ となるのでギリギリセーフになります(?)

これでTLEを回避し、AC！

解説を書いていて、クエリを先読みして出力クエリの直前で再構築するかどうかの判断をしたほうがいいと思った。
また、今回は1000という設定で通ったが300くらいがより良かったのではないかと思った。

"つよい"皆様、正しくない部分があったら教えてください