ひらめの日常

プログラミングと読書と

AtCoder: ABC164-D Multiple of 2019 (400)

問題はこちら

atcoder.jp

1から9までの数字からのみなる、文字列 S が与えられる。
次の条件を満たす整数の組  (i, j)(1 \leq i \leq j \leq|S|) の総数を求めよ。

条件:  S i 文字目から  j 文字目までを10進法の整数としてみると、この整数は2019の倍数である。
制約:  1 \leq|S| \leq 200000

考え方

はじめに

 i, j を二重ループで全ての通り試して、その数が2019で割り切れるかを試す方法が真っ先に思い浮かぶが、計算量が  O(n ^ {2} ) となり今回は間に合わない。

桁を増やしながら何か数えることができれば、計算量が減りそうだと考える。そこで、桁を一つ増やすごとにどのように状態が変わるかに注目してみる。

簡便化のために、 S の長さを  n S の右から  i 番目の数を  a_i とし、 Sを次のように表す。
 a _ {n} a _ {n-1} \cdots a _ {2} a _ {1}

着目点

今回、「2019という数は10と互いに素な数になっている。なので、 10 ^ {x} n が2019の倍数の時、  n も2019の倍数になっている」ことがポイント。

例えば4038000(=2019*2*1000) を考えると、これが2019の倍数の時、4038が2019の倍数になっているということ。当たり前のように感じるが次のように役立つ。

  • 4038333のような数が出てきた時、4038333 - 333 = 4038000 が2019の倍数だったならば、4038は2019の倍数となり、題意をみたす。
  • 右からどこまでを0にするか?に注目しそうである(右からどこまでを引き算して0にしまうか?)
  • 4038333 - 333 % 2019 == 0
  • 4038333 % 2019 == 333 % 2019
  • 余りの等しい連続する部分列のペアを取ってくれば良い!

言い換え

このことから、次のように言い換えることができる。

  1.  a _ {l} a _ {l-1} \cdots a _ {r+1} a _ {r} が2019の倍数である。
  2.  10 ^ {l - 1} a _ {l} + \cdots + 10 ^ {r -1} a _ {r} が2019の倍数である。(これを  X _ {l, r} とおく。)
  3.   X _ {l, 0} - X _ {r - 1, 0} が2019の倍数である。(→累積和と似たような考え方になる。)
  4.  (X _ {l, 0}  - X _ {r-1, 0})\%2019=0
  5.  X _ {l, 0} \%2019=X _ {r-1, 0} \%2019

同じ余りとなる  l, (r-1) のペアを探せば、題意を満たす整数の組になるということがわかる。

これは右の桁から順に数字を見ていき、2019で割った余りを  m とすると、map[m]++するなどして管理し、最後に各余りについて、二つ取る組み合わせを計算して足し上げれば良い。注意として、余りが0の数の場合、他の数とペアにしなくてもその数だけで題意を満たすため、map[0]=1 と初期化しておくことで他の場合と同じように計算ができる。

計算量は、 O(Nlog(2019))となり、間に合う。(unordered_mapを使うとlogが取れる。)

この一連の求め方は、A - Zero-Sum Ranges でも同じような流れを踏むので見ておくと良いかもしれない。また、E - Divisible Substringでも似たような問題だったらしいがまだ解いていない。

解答

文字列だと右側から見ていく必要があるために、最初に文字列をreverseしてindexを扱いやすくしている。

また、桁数が非常に大きいため、桁数については別途modを取るようにしている。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define each(i, mp) for(auto& i:mp)

int main() {
    string s;
    cin >> s;
    map<ll, ll> mp;
    mp[0] = 1;
    reverse(s.begin(), s.end());
    ll now = 0, ten = 1;
    each(e, s) {
        now = (now + (e - '0') * ten) % 2019;
        ten *= 10;
        ten %= 2019;
        mp[now]++;
    }
    ll ans = 0;
    each(e, mp) {
        ans += e.second * (e.second - 1) / 2;
    }
    cout << ans << '\n';
    return 0;
}

Submission #12407239 - AtCoder Beginner Contest 164