ABC 401-500/ABC419E - Subarray Sum Divisibility - 競技プログラミング用 知識集積所【8/17更新】

---

問題

ABC419E

必要知識

B以下レベルの内容は省略

• sliding window法（考察のみ）
• 動的計画法

考え方

各区間の和をsliding window法で考えることを想像すると、結局問題はこういうことである。

• 先頭L個の総和がMの倍数
• L個離れた位置の数は、Mで割った余りが等しい

ということで、まずは「L個離れた位置の数は、Mで割った余りが等しい」を整えるのに必要な回数を求める。
これはもちろんいくつに統一するかによって必要回数は違うので、全部個別に出す。
ということで、「位置をlで割ったらi余るところにある数全てをmで割った余りがjであるようにするのに最低何回操作が必要か」を各i各jについて二次元で求めておく。
これは、aの各値に1からm-1までを順に足してみながら、それぞれmで割った余りと位置を考えながら適切な集計をしていけばよい。

それが出来たら、あとは動的計画法を行うだけ。
dp.at(i).at(j)は、

• 先頭のi個の合計をmで割った余りがjである
• 位置をlで割った余りがi以下であるものは、全て余りが適切になっている

という状態にする手数。
配るDPで書いた方がやや楽か。

解答例

解答例

注意点

別解

余り揃えの手数集計に階差数列※を使う

O(MN)じゃなくてO(M+N)で表を埋められる……けど、O(MN)でも余裕なのであんまり関係なかった。
解答例