アジの開きを閉じる。

競プロ(AtCoder)中心のブログ

【解説】 ABC164 D - Multiple of 2019

ABC 解説

※この解説はhamayanhamayanさんの解説と同じ内容です。自分の理解のためにまとめ直しました。

 

執筆時レート：水色

 

問題文→https://atcoder.jp/contests/abc164/tasks/abc164_d

公式解説→https://atcoder.jp/contests/abc164/tasks/abc164_d/editorial

 

目次

 

 

問題

1 から 9 までの数字のみからなる文字列 S が与えられる。

次の条件を満たす整数の組 ( i, j ) \, (1 \leq i \leq j \leq |S| ) の総数を求めよ。

条件： S の i 文字目から j 文字目までを 10 進法の整数としてみると，この整数は 2019 の倍数である。

 

制約

  • 1 \leq |S| \leq 2 \times 10 ^ {5}
  • S は 1 から 9 までの数字のみからなる文字列

 

解説

区間数え上げは片方を固定し、もう片方を高速に数え上げるのが定石。

例えば数え上げ方の一つに尺取法がある。尺取法が有効なのは，片方を固定したとき，もう片方について「ある条件を満たす/満たさない」の単調性が見られる場合である。満たす/満たさないの境界が分れば，満たす側の個数を計上すれば良い。

 

しかし，今回の問題で尺取法は使えない。というのも，一般に単調性がないためだ。

入力例1「 1817181712114 」を見てみる。

区間の左端を一番左に固定し右端を右に伸ばしていくと，「 1817 」までは 2019 の倍数でなく，次の「 18171 」で初めて 2019 の倍数になるが，その次の「 181718 」は 2019 の倍数でない。このように，右端を動かしたときに条件「 2019 の倍数である」を満たす/満たさないの境界がただ 1 つでない。だから尺取法は有効でない。

 

別の方法を考えてみる。

 

区間の考え方の一つに，「区間の引き算」がある。

例えば，区間 [ l, r ] は半開区間の引き算 [0,r+1) - [0,l) と表現することができる。累積和がその代表的な例の 1 つだ。

これを利用できないか考えてみる。

 

先ほどの例示では左端 0 を支点としていたが，今回の問題は(それでは上手くいかないので)右端を支点にしてみる。

 

説明のため，文字や表記を次のように定義する。 i,j は 0-indexed である。

  • N := |S|
  • S[i:j] := S の i 文字目から j 文字目までを 10 進法の整数としてみたときの整数。ただし， j=N-1 (末尾)の場合は S[i:] と略記する。
  • S[N:] := 0

 

問題文の条件を変形していく。

S[i:j] \equiv 0 \pmod {2019}

  \displaystyle \Leftrightarrow \frac{ S[i:] - S[j+1:] }{ 10 ^ {n-j} } \equiv 0 \pmod {2019}

\Leftrightarrow S[i:] - S[j+1:] \equiv 0 \pmod {2019}  ( 10 ^ {n-j} と 2019 は互いに素なので \Leftarrow も成り立つ)

\Leftrightarrow S[i:] \equiv S[j+1:] \pmod {2019}

 

つまり， i 文字目以降の部分を 2019 で割った余りと j + 1 文字目以降の部分を 2019 で割った余りが等しければ， i 文字目から j 文字目までの部分は 2019 の倍数になる，ということである。

 

よって， i 文字目以降の部分の余りを集計しつつ，右から i を走査をすれば良い。

S[i:] \pmod {2019} を計算し，それと同じ値のものがこれまでにあれば，その個数が j として取り得るものの個数である。

 

S[i:] \pmod {2019} は前の S[i+1:] \pmod {2019} を使い，

S[i:] \equiv S[i:i] \times 10 ^ {n-i} + S[i+1:] \pmod {2019}

という式で O(1) で求められる。

 

i を全探索し，各 i での処理は O(1) なので，全体の計算量は O(N) である。

 

実装

C++による実装例。コメント付き。

https://atcoder.jp/contests/abc164/submissions/39539547