AtCoder ABC 105 D

python に慣れるため久しぶりにプロコンをやってみた。今の AtCoder になってから初だと思う。

D: Candy Distribution - AtCoder Beginner Contest 105 | AtCoder

code

from collections import defaultdict

N, M = map(int, input().split())
A = list(map(int, input().split()))

Amod = defaultdict(int)
sum_mod = 0
for v in A:
    sum_mod = (sum_mod + v) % M
    Amod[sum_mod] += 1

sum_mod = 0
ans = 0
for v in A:
    ans += Amod[sum_mod]
    sum_mod = (sum_mod + v) % M
    Amod[sum_mod] -= 1

print(ans)

解き方、感想

0 .. r (r = 0 .. N) の範囲の和の mod を hash に覚えておく。
0 .. l で l を動かして、0 .. r の和のmodから 0..l の 和の mod を引いて、mod が 0 になるようなもの (hash[ 0..l の和のmod] で個数がすぐに出せる)を足していく感じ。

python は慣れてないけど、defaultdict ないと面倒くさそう。
他の人のコードみて勉強せな。

• AtCoder は気軽に他の人のコード見れない？topcoder は見れるから勉強しやすい。

• AtCoder の解説は結構あっさりしてて、わかる人向けの解説って感じがする(解いたけど解説読んでもよくわからない…)。動画を見ればいいのかな。