Ringo's Favorite Numbers 2 [京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200） C]

https://atcoder.jp/contests/abc200/tasks/abc200_c

解説

https://atcoder.jp/contests/abc200/submissions/22436968

これは類題を解いたことがないと最初の発想が難しいかもしれない。
i,jの全列挙はN²通りくらいになるので、10¹⁰でこれは間に合わない。
右側であるjを全列挙していき、条件を満たす左側iを高速に取得していくことで計算を高速化していく。

jを全列挙

jを1から順番に列挙していく過程で「iに関する情報を適切に計算して保持しておく」ことで計算の高速化を目指す。
jを固定したときに条件を満たすiの条件は、そのまま書くと「A[i]-A[j]が200の倍数」ということになるが、

A[i] - A[j] = 0 (mod 200)
A[i] = A[j] (mod 200)

このように考えると、200で割った余りがA[j]と等しいA[i]の個数が分かればいいことになる。
ここで「iに関する情報を適切に計算して保持しておく」ことを考えると、以下の配列を作りながら列挙していけばいいことになる。

cnt[x] := A[i]=xを満たすiの個数

jを1から順に列挙していく過程で、

1. 今までのcntを使って個数計算
2. A[j]をcntに追加する

という流れを取れば、操作1をしている段階では1～j-1までの情報が入ったcntが用意されていて、
ちょうどこれはiの探索範囲と同一になる。
なので、ここで取ってきた結果は、条件を満たす個数となっている。
これを順次計算して、総和して答える。

int N, A[201010];
int cnt[202];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    ll ans = 0;
    rep(i, 0, N) {
        int mo = A[i] % 200;
        ans += cnt[mo];
        cnt[mo]++;
    }
    cout << ans << endl;
}