C++の練習を兼ねて, AtCoder Regular Contest 150 の 問題A (Continuous 1) ～ 問題B (Make Divisible) を解いてみた.
■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 150 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題A／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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #define repex(i, a, b, c) for(int 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 repr(i, a, b) for(int i = a; i >= b; i--) int main(){ // 1. 入力情報. int T; scanf("%d", &T); // 2. テストケース. rep(i, T){ // 2-1. 各テストケース. int N, K; scanf("%d %d", &N, &K); char c[N + 1]; scanf("%s", c); string s(c); // 2-2. 累積和. int oCum[N + 1], qCum[N + 1]; rep(j, N + 1) qCum[j] = oCum[j] = 0; rep(j, N){ oCum[j + 1] = oCum[j] + (s[j] == '1'); qCum[j + 1] = qCum[j] + (s[j] == '?'); } // 2-3. 条件を満たすものがあるか？ int cnt = 0; rep(j, N - K + 1){ // 左. bool ok = (oCum[j] == 0); // 中. ok &= ((oCum[j + K] - oCum[j]) + (qCum[j + K] - qCum[j]) == K); // 右. ok &= (oCum[N] - oCum[j + K] == 0); // 集計. if(ok) ++cnt; } // 2-4. 出力. printf("%s\n", (cnt == 1) ? "Yes" : "No"); } 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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
[入力例] 4 3 2 1?? 4 2 ?1?0 6 3 011?1? 10 5 00?1???10? [出力例] Yes No No Yes ※AtCoderのテストケースより [入力例] 5 5 1 ??000 5 2 0??10 5 5 11111 7 5 001?1?? 7 5 00101?? [出力例] No Yes Yes Yes No [入力例] 7 3 1 000 3 1 00? 3 1 0?1 3 1 1?1 5 3 1?100 10 5 00?11??110 13 7 0000?11??1?00 [出力例] No Yes Yes No Yes No Yes |
■C++版プログラム(問題B／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 |
// 解き直し. // https://atcoder.jp/contests/arc150/editorial/4864 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #define repex(i, a, b, c) for(int 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 repr(i, a, b) for(int i = a; i >= b; i--) int main(){ // 1. 入力情報. int T; scanf("%d", &T); // 2. テストケース. rep(i, T){ // 2-1. 各テストケース. LL A, B; scanf("%lld %lld", &A, &B); // 2-2. k が [1, sqrt(B - 1) + 1]. LL ans = 202020202020202020; repx(k, 1, (int)sqrt(B - 1) + 1){ LL q = (B - 1) / k; ans = min(ans, (k + 1) * max(0LL, q + 1 - A) + k * A - B); } // 2-3. k が [sqrt(B - 1) + 2, B]. rep(q, (int)sqrt(B - 1) + 1){ LL k = (B - 1) / (q + 1) + 1; ans = min(ans, (k + 1) * max(0LL, q + 1 - A) + k * A - B); } // 2-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 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 79 80 |
[入力例] 5 11 23 8 16 4394 993298361 95392025 569922442 8399283 10293 [出力例] 2 0 65 2429708 8388990 ※AtCoderのテストケースより [入力例] 30 30 53 869 1221 77 918 3358 2455 11064 9982 11500 390 8174 7609 4663 1829 67505 5630 54995 47547 6837 19968 12879 59160 30230 60342 46813 52697 98695 39214 62846 202020 27085 175622 369593 736366 748395 802632 303030 626363 6461788 12088026 11226373 406096 9616101 7777777 101900 12047210 4967027 7967424 7822686 268354 1730062 3281498 3629974 5738535 8019338 10092093 8256235 6467269 [出力例] 7 352 6 903 1082 11110 565 2834 61875 7448 543 1911 118 5884 59481 4494 2190 2820 54237 10153 835550 10820277 1838324 195 1966630 7554332 178626 1521413 2072755 1788966 |
■参照サイト
AtCoder Regular Contest 150