ABC105-D:Candy Distribution

問題

https://beta.atcoder.jp/contests/abc105/tasks/abc105_d

数列 A が与えられる。閉区間  [A_l + A_{l+1} + ... + A_r ] の和が M の倍数になる区間の個数を求めよ。

考え方

 [A_l + A_{l+1} + ... + A_r ] の累積和を  B_r - B_{l-1} とする。これが M の倍数になる時 B_rB_{l-1}M の倍数でなければなりません。よって A の累積和をとり、M であまりをとったときに、同じ値の数から 2 つ選ぶときの組み合わせの個数が解になります。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            long m = in.nextLong();
            long[] a = new long[n+1];
            long[] sum = new long[n+1];
            Map<Long, Long> map = new HashMap<>();
            for (int i = 1; i < n+1; i++) {
                a[i] = in.nextLong();
                sum[i] = sum[i-1] + a[i];
                sum[i] %= m;
            }
            for (long l : sum) {
                map.merge(l, 1L, Long::sum);
            }

            long ans = 0;
            for (long l : map.keySet()) {
                long v = map.get(l);
                if (v >= 2) {
                    ans += v * (v-1) / 2;
                }
            }
            out.println(ans);
        }

ポイント

  • いくつかの値の和や差の倍数判定はあまりに着目する
  • 連続する区間の和 ⇔ 累積和の配列上の2点

類題

A - Zero-Sum Ranges

D - Five, Five Everywhere

雑記

本番中はひとめしゃくとりかな?と思っていろいろ考えてみたのですが違いました。一旦愚直解 O(N^2) で考えてみたときに A の累積和をとって M のあまりをとったときの数列を眺めていたら解放をエスパーできたのでよかったです。