AtCoder Beginner Contest 378 の解説＆攻略記事です。
コンテストの解説を見ても「なんでこんなの思いつくねん！」と思わず叫んでしまうことが多いので、どう考えてそうなったのかをできるだけ細かく書いていきます。
コンテストURL
今回の問題のポイントは4つです。
数式系の問題は式変形してみる
今回の問題の数式を見てみましょう。
なお、インデックスはすべて0-indexedで表記しています。
$$ \sum_{0 \le l \le r \lt N} \Bigg( \Big( \sum_{k=l}^r A_k \Big) \ mod \ M \Bigg) $$
こういうシグマが入った数式系の問題は、具体的に計算せずともガチャガチャ式変形をしているといい感じになる場合があります。modなどが入っているときは特に。
今回の問題も「式変形でいけるとこまでいったるぞ」という強い気持ちを持つことが大切です。
さっそく式変形していきましょう！
連続する部分和は累積和をつかう
問題の式を眺めると、
$$ \sum_{k=l}^r A_k $$
という部分があります。ここはもう手癖のように式変形したいところですね。
そう、みんな大好き累積和です。
S_k = \sum_{i=0}^{k-1} A_i
と前計算しておけば、
$$ \sum_{k=l}^r A_k = S_{r+1}-S_l $$
とできます。
求めたい値は
$$ \sum_{l=0}^{N-1} \sum_{r=l}^{N-1} \Big( (S_{r+1}-S_l) \ mod \ M \Big) $$
となります。
なんだかスッキリしましたね。
計算量も$ O(N^3) $から$ O(N^2) $に落ちていますし、式もスッキリしているし、おまけに累積和はバクらせにくいので一石三鳥の気分です。累積和マジかんしゃ。
次は式変形でmodを消していきます。
modは式変形で消せる場合がある
ポイントは、$ a,b \ (0 \le a,b < M)$に対して$ a-b > -M $となることです。
$ a-b $がマイナスになってしまっても、ちょうど1回$M$を足せばプラスにできるのです。
つまり、
(a-b) \ mod \ M = a-b+\left\{ \begin{array}{ll} 0 & (a \ge b) \\ M & (a < b) \end{array} \right.
とすれば$mod$を消すことができます！
$a-b \ mod \ M$のかたちを見たらこれもパッと思い出せるようになりたいです。
$ mod $の引き出しの真ん中くらいに入れておくといい知識だと思います。
さて、この変形を使って$ mod $を消していきましょう。
$$ SM_i=S_i \ mod \ M $$
とすると、求めたい値は
$$ \sum_{l=0}^{N-1} \sum_{r=l}^{N-1} \Big( (SM_{r+1}-SM_l) \ mod \ M \Big) $$
となります。
先ほどの式変形を使えば、求めたい式は
\displaylines{
\sum_{l=0}^{N-1} \sum_{r=l}^{N-1} \Bigg( SM_{r+1}-SM_l +
\left \{
\begin{array}{ll}
M & ( \ SM_{r+1}-SM_l < 0 \ ) \\
0 & else
\end{array}
\right.
\Bigg) \\
= \sum_{l=0}^{N-1} \Bigg( \sum_{r=l}^{N-1}SM_{r+1}-\sum_{r=l}^{N-1}SM_l + \sum_{r=l}^{N-1}
\left \{
\begin{array}{ll}
M & ( \ SM_{r+1}-SM_l < 0 \ ) \\
0 & else
\end{array}
\right.
\Bigg)
}
です。
式変形した結果ふくざつになってしまった感じがしますが、よくよく見てみるとかなりいい形になっています。ゴールはそう遠くありません。
カッコの中の3つのシグマを解きほぐしていきましょう。
と言ってもうち2つはすでに解かれたようなものです。
まずはこの部分。
\sum_{r=l}^{N-1}SM_{r+1}
これはもう大丈夫ですね。みんな大好き累積和です。
$ SM^{'} $を$ SM $の累積和とすると、
\sum_{r=l}^{N-1}SM_{r+1} = SM^{'}_{N+1}-SM^{'}_{l+1}
です。
累積和の累積和をとるってなんだかおもしろいですね。
次はこの部分。
\sum_{r=l}^{N-1}SM_l
ここはよくみると、$r$が変化しても$SM_l$には何の影響もありません。
つまりただ$SM_l$を$N-l$回足しているだけなので、
\sum_{r=l}^{N-1}SM_l = (N-l)SM_l
となります。スッキリ。
さて、ラストは
\sum_{r=l}^{N-1}
\left \{
\begin{array}{ll}
M & ( \ SM_{r+1}-SM_l < 0 \ ) \\
0 & else
\end{array}
\right.
です。
これはすなわち、「($l < r \le N$の中で$SM_r<SM_l$を満たす$r$の個数)$\times M$」です。
条件を満たす$r$の個数を$X_l$と表すことにすると、
\sum_{r=l}^{N-1}
\left \{
\begin{array}{ll}
M & ( \ SM_{r+1}-SM_l < 0 \ ) \\
0 & else
\end{array}
\right.
=X_l \times M
です。
一旦整理しましょう。
求めたい式はこれです。
\sum_{l=0}^{N-1}\big( SM^{'}_{N+1}-SM^{'}_{l+1}-(N-l)SM_l + X_l\times M \big)
ついに$O(N)$まで計算量が落ちていますね！
これで完成系は見えました。あとは$ X_l $を爆速で求める方法があればOKです。
区間はだんだんひろげると吉
$X_l$を爆速で求めることを考えます。言い換えると、$SM_l$より後ろにあって、$SM_l$より小さいものの個数を求めればいいです。
これは$SM_l$より後ろの中で、
(0の出現回数)+(1の出現回数)+(2の出現回数)+ \cdots + (SM_l-1の出現回数)
を爆速で求めればいいです。
このように区間に対して何か求めるときは、区間をだんだん狭めたり広げたりする方法がしばしば有効です。ある種DP的な考え方ですね。
今回は後ろから更新するとうまくいきます。
具体的には、$0 \le l < N$に対して後ろから以下の操作を繰り返します。
- $0 \sim SM_l-1$までの出現回数の合計を取りそれをX_lとする
- $SM_l$の出現回数を1増やす
区間和&一点更新なので、つよつよデータ構造のセグ木で万事解決です！！
解決！
以上でABC378-Eは攻略できたと言ってもいいでしょう！！
お疲れ様でした。
同じような問題が出たときの対策もバッチリです。
ちなみに偉そうに解説してきましたが、僕は本番でこの問題を通せてません。（本番で解ける人すげぇ〜）
5完安定して解けるようになりたいな〜。
それでは、良い競プロライフを！