ABC200のC問題 Ringo's Favorite Numbers 2 を工夫して解く - 競技プログラミング悪戦苦闘日記

ABC200のC問題を解説します。

問題

200 という整数が大好きなりんごさんのために、次の問題を解いてください。
N 個の正整数からなる数列 A が与えられるので、以下の条件をすべて満たす整数の組 (i, j) の個数を求めてください。
$1\leq i \lt j \leq N$
$A_i − A_j$ は 200 の倍数である。

難しいポイント

Nの個数が最大で $2\times10^5$ なので、単純な全探索ではタイムオーバーします。
200の倍数というところから計算量を減らす方法に気づけるかどうかがポイントかと思います。

解き方の方針

ポイントになるのは $A_i − A_j$ は 200 の倍数という条件なので、余りだけに着目すれば良いことになります。
余りだと数字の範囲は0から199の範囲になります。
数列Aを全部200で割った余りに変換します。

引き算して200の倍数になるのはどういう余りの組み合わせになるか考えます。
例えば、余り1の数字があったときに、そこから0から199の間でどういう余りの数字を引けば200の倍数になるでしょうか。
そういうことを考えると余り1の数字から余り1の数字を引くしかないことがわかります。他の余りの数字を引いても200の倍数にはなりません。
なのでそれぞれの余りについて、同じ余りの数字から2つ選ぶ組み合わせの数を足した数が答えになります。

実装

実装は特別難しいことはしていません。

N = int(input())
a_arr = list(map(int, input().split()))
amari = [0 for i in range(200)]
for a in a_arr:
    amari[a % 200] += 1

ans = 0
for i in range(200):
    ans += (amari[i] * (amari[i] - 1)) // 2

print(ans)