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
余りの等しい連続する部分列のペアを取ってくれば良い！

言い換え

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

$a _ {l} a _ {l-1} \cdots a _ {r+1} a _ {r}$ が2019の倍数である。
$10 ^ {l - 1} a _ {l} + \cdots + 10 ^ {r -1} a _ {r}$ が2019の倍数である。（これを $X _ {l, r}$ とおく。）
$X _ {l, 0} - X _ {r - 1, 0}$ が2019の倍数である。（→累積和と似たような考え方になる。）
$(X _ {l, 0} - X _ {r-1, 0})\%2019=0$
$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

ひらめの日常

日常のメモをつらつらと

AtCoder: ABC164-D Multiple of 2019 (400)

問題はこちら

考え方

はじめに

着目点

言い換え

解答