C++の練習を兼ねて, AtCoder Beginner Contest 146 の 問題E (E – Rem of Sum is Num) を解いてみた.
■感想.
1. 方針が見えなかったので, 解説を参考に実装した.
2. 解説上では, 読み取れなかったが, おそらく, 1 <= j <= N でなく, 0 <= j <= N にする必要があると推測した.
本家のサイトABC 146解説をご覧下さい.
■C++版プログラム(問題E/AC版).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
// 解き直し. // ABC 146解説. // https://img.atcoder.jp/abc146/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; #define repex(i, a, b, c) for(LL i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define a first #define b second const int MAX = 202020; LL A[MAX], CUM[MAX]; int main(){ // 1. 入力情報. LL N, K; scanf("%lld %lld", &N, &K); rep(i, N) scanf("%lld", A + i), CUM[i + 1] = CUM[i] + A[i]; // 2. 条件を満たす連続部分列をカウント(TLE版). // (N + 1) * N / 2 の 計算量があるはず. LL ans = 0; // rep(i, N){ // repx(j, i, N){ // if((CUM[j + 1] - CUM[i]) % K == j - i + 1) ans++, printf("i=%d j=%d\n", i, j); // } // } // 3. 解説通り. // (CUM[j] - j) % K == (CUM[i] - i) % K かつ j - i < K となるものを集計. // -> 1 <= j <= N で, (CUM[j] - j) % K == (CUM[i] - i) % K を 満たす // j - K < i < j となる iの個数を調べるとのこと. // ex. // [入力例] // 10 7 // 14 15 92 65 35 89 79 32 38 46 // index 0 1 2 3 4 5 6 7 8 9 10 // S[i] 0 14 29 121 186 221 310 389 421 459 505 // S[i] - i 0 13 27 118 182 216 304 382 413 450 495 // mod K 0 6 6 6 0 6 3 4 0 2 5 // // [計算メモ] // j j - K < i < j S[j] - j 個数 マップ // 0 -7 < i < 0 0 0 {0:1} // 1 -6 < i < 1 6 0 {0:1}, {6:1} // 2 -5 < i < 2 6 1 {0:1}, {6:2} // 3 -4 < i < 3 6 2 {0:1}, {6:3} // 4 -3 < i < 4 0 1 {0:2}, {6:3} // 5 -2 < i < 5 6 3 {0:2}, {6:4} // 6 -1 < i < 6 3 0 {0:2}, {3:1}, {6:4} // 7 0 < i < 7 4 0 {0:1}, {3:1}, {4:1}, {6:4} // 8 1 < i < 8 0 1 {0:2}, {3:1}, {4:1}, {6:3} // 9 2 < i < 9 2 0 {0:2}, {2:1}, {3:1}, {4:1}, {6:2} // 10 3 < i < 10 5 0 {0:2}, {2:1}, {3:1}, {4:1}, {5:1}, {6:1} // ----------------------------------------------------------------------------- // 合計 8 map<LL, LL> m; LL cur = 0, bef = 0; rep(i, N + 1){ cur = (CUM[i] - i) % K; m[cur]++; if(i - K >= 0){ bef = (CUM[i - K] - (i - K)) % K; m[bef]--; } ans += m[cur] - 1; // printf("cur=%lld bef=%lld\n", cur, bef); // for(auto &p : m) printf("{%lld:%lld}, ", p.a, p.b); // printf("\n"); } // 4. 出力. printf("%lld\n", ans); return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
[入力例] 5 4 1 4 2 3 5 [出力例] 4 ※AtCoderテストケースより [入力例] 8 4 4 2 4 2 4 2 4 2 [出力例] 7 ※AtCoderテストケースより [入力例] 10 7 14 15 92 65 35 89 79 32 38 46 [出力例] 8 ※AtCoderテストケースより [入力例] 5 10 1 1 1 1 1 [出力例] 15 [入力例] 9 7 123456789 234567891 345678912 456789123 567891234 678912345 789123456 891234567 912345678 [出力例] 7 [入力例] 100 123 111111111 111111112 111111113 111111114 111111115 111111116 111111117 111111118 111111119 111111120 111111121 111111122 111111123 111111124 111111125 111111126 111111127 111111128 111111129 111111130 111111131 111111132 111111133 111111134 111111135 111111136 111111137 111111138 111111139 111111140 111111141 111111142 111111143 111111144 111111145 111111146 111111147 111111148 111111149 111111150 111111151 111111152 111111153 111111154 111111155 111111156 111111157 111111158 111111159 111111160 111111161 111111162 111111163 111111164 111111165 111111166 111111167 111111168 111111169 111111170 111111171 111111172 111111173 111111174 111111175 111111176 111111177 111111178 111111179 111111180 111111181 111111182 111111183 111111184 111111185 111111186 111111187 111111188 111111189 111111190 111111191 111111192 111111193 111111194 111111195 111111196 111111197 111111198 111111199 111111200 111111201 111111202 111111203 111111204 111111205 111111206 111111207 111111208 111111209 111111210 [出力例] 90 |
■参照サイト
AtCoder Beginner Contest 146