ABC473 E - K-Divisible Subarrays
Kの倍数区間
考え方
自由に区切って、条件を満たす区間の個数がなるべく多いようにする。
これは、互いに重ならないように条件を満たす区間を可能な限りたくさん選ぶと言い換えてもよい。
つまりこれは、区間スケジューリング問題である。
ということは、右端 $r$ が小さい順に見て、採用可能なら採用する貪欲法でよい。
すなわち、以下を実行すればよい。
- 先頭から $1$ つずつ探索範囲を広げて、条件を満たす区間が取れるか調べる
- 条件を満たす区間が取れるとなったら、直ちにそれを採用する
- 採用したら、今までの数列を全てみなかったことにして、次の数が先頭と思って再び調査を始める
問題は「条件を満たす区間が取れるか調べる」のやり方。
これは累積和を用いることで高速に処理できる。
最初に、空の数列の和である $0$ を set か何かに記録しておく。
そこから $1$ つずつ進めながら累積和を計算し、出現した累積和を $K$ で割った余りを全て記録していく。
同じ余りが $2$ 回出現した場合、それが出現した $2$ ヶ所の間が条件を満たす区間である。
計算量は $O(N\log N)$ である。
入力例1での動作
入力を受け取る。
n: 6
k: 10
a: {6, 8, 2, 2, 6, 4}最初に、空の数列の累積和の余り $0$ を set に入れておく。
先頭から順に累積和を計算し、その $10$ で割った余りを調べる。
| 値 | 累積和の余り | 出現済みか | 処理 | 処理後の出現済の余り |
|---|---|---|---|---|
| $6$ | $6$ | いいえ | $6$ を記録する | {0,6} |
| $8$ | $4$ | いいえ | $4$ を記録する | {0,4,6} |
| $2$ | $6$ | はい | 区間を $1$ つ採用し、状態をリセットする | {0} |
| $2$ | $2$ | いいえ | $2$ を記録する | {0,2} |
| $6$ | $8$ | いいえ | $8$ を記録する | {0,2,8} |
| $4$ | $2$ | はい | 区間を $1$ つ採用し、状態をリセットする | {0} |
最初の重複した余り $6$ は、$8+2=10$ となる区間に対応する。
次の重複した余り $2$ は、$6+4=10$ となる区間に対応する。
よって、条件を満たす区間を $2$ 個採用でき、答えは $2$ となる。
注意点
特になし。
別解
特になし。