C++の練習を兼ねて, AtCoder Regular Contest 115 の 問題A (Two Choices) ~ 問題B (Plus Matrix) を解いてみた.
■感想.
1. 規則性が抽出出来たので, 久しぶりに, 解答見る前に, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 115 解説 の 各リンク を ご覧下さい.
■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 |
// 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 N, M; LL odd = 0, even = 0; scanf("%d %d", &N, &M); rep(i, N){ int one = 0; char c[22]; scanf("%s", &c); rep(j, M) if(c[j] == '1') one++; if(one & 1) odd++; else even++; } // 2. 出力. printf("%lld\n", odd * even); 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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
[入力例] 3 2 00 01 10 [出力例] 2 ※AtCoderのテストケースより [入力例] 7 5 10101 00001 00110 11110 00100 11111 10000 [出力例] 10 ※AtCoderのテストケースより [入力例] 10 6 000110 001110 100111 011000 100110 100011 011001 001001 100010 101010 [出力例] 25 [入力例] 50 10 0001100101 0011101000 1001110111 0110001011 1001100011 1000110101 0110011100 0010011111 1000100000 1010101111 0101010000 0010110100 1100011010 0000101101 1010101110 0000010010 1110011001 1111001101 0000001011 0001011010 1001100011 1110110111 0101010001 0010110011 0001100001 0110100000 1101001100 1010010100 1110001100 1110100110 0100000000 0110110000 0011101110 0001101110 0101001111 0001101100 0101100111 1110001100 1011001000 1111111001 1011111010 0101111011 1010011011 1001010110 1010110011 0101111110 0000001111 0110001111 0101100110 0011111100 [出力例] 624 |
■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 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 |
// 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--) LL C[505][505], ka[505], kb[505], A[505], B[505]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) rep(j, N) scanf("%lld", &C[i][j]); // 2. 行方向. bool rOk = true; rep(i, N - 1){ // (i + 1)行目 マイナス i行目. LL a = C[i + 1][0] - C[i][0]; repx(j, 1, N) if(a != C[i + 1][j] - C[i][j]) rOk = false; // 条件を満たす場合は, 保存. if(rOk) ka[i] = a; else break; } // 3. 列方向. bool cOk = true; rep(j, N - 1){ // (j + 1)列目 マイナス j列目. LL b = C[0][j + 1] - C[0][j]; repx(i, 1, N) if(b != C[i][j + 1] - C[i][j]) cOk = false; // 条件を満たす場合は, 保存. if(cOk) kb[j] = b; else break; } // 4. 条件を満たさない場合は, 終了. if(!rOk || !cOk){ puts("No"); return 0; } // 5. 条件を満たす場合. // 5-1. A を 計算. LL minA = A[0]; rep(i, N - 1) A[i + 1] = A[i] + ka[i], minA = min(minA, A[i + 1]); // 5-2. minA が マイナスの場合, 加算. if(minA < 0) rep(i, N) A[i] -= minA; // 5-3. B を 計算. LL minB = B[0]; rep(i, N - 1) B[i + 1] = B[i] + kb[i], minB = min(minB, B[i + 1]); // 5-4. minB が マイナスの場合, 加算. if(minB < 0) rep(i, N) B[i] -= minB; // 5-5. C[0][0] と 比較し, 差分 を 加算. LL kc = C[0][0] - A[0] - B[0]; if(kc > 0) rep(i, N) B[i] += kc; // 6. 出力. puts("Yes"); rep(i, N){ printf("%lld", A[i]); printf("%s", (i < N - 1) ? " " : "\n"); } rep(i, N){ printf("%lld", B[i]); printf("%s", (i < N - 1) ? " " : "\n"); } 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 |
[入力例] 3 4 3 5 2 1 3 3 2 4 [出力例] Yes 2 0 1 2 1 3 ※AtCoderのテストケースより [入力例] 3 4 3 5 2 2 3 3 2 4 [出力例] No ※AtCoderのテストケースより [入力例] 5 6 12 5 8 11 13 19 12 15 18 10 16 9 12 15 8 14 7 10 13 5 11 4 7 10 [出力例] Yes 1 8 5 3 0 5 11 4 7 10 |
■参照サイト
AtCoder Regular Contest 115