C++の練習を兼ねて, AtCoder Regular Contest 054 の 問題C (鯛焼き) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考にして, AC版に到達できたと思う.
2. 行列の掃き出し法について復習出来たので, 非常に良かったと思う..
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 054 解説 を ご覧下さい.
■C++版プログラム(問題C／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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
// 解き直し. // https://img.atcoder.jp/data/arc/054/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vs = vector<string>; #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--) #define pb push_back #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N; scanf("%d", &N); vs matrix; rep(i, N){ char c[222]; scanf("%s", c); string s(c); matrix.pb(s); } // puts("--- Matrix before update ---"); // rep(i, N) printf("%s\n", matrix[i].c_str()); // 2. 掃き出し法(mod2版). // https://ja.wikipedia.org/wiki/ガウスの消去法 // // ex. // [変更前行列] // 011001 // 001001 // 101011 // 010110 // 001100 // // [変更後行列] // 100001 // 010000 // 001001 // 000101 // 000011 // auto gauss = [&](vs &m, int N, int M) -> vs { // 2-1. 戻り値設定. vs ret = m; // 2-2. 各行を順次確認. rep(i, N){ // 降順sort. sort(all(ret)); reverse(all(ret)); // 最初に, '1' となる位置. int at = M; rep(j, M){ if(ret[i][j] == '1'){ at = j; break; } } // 見つからなった場合. if(at == M) continue; // i行目以外(j行目)と比較して, 前項で求めた位置(列)に, '1' が 有れば, 掃き出す. rep(j, N){ if(i != j && ret[j][at] == '1'){ // 操作対象を設定. string o = ret[i]; // i行目. string n = ret[j]; // j行目. // j行目の掃き出し. rep(k, M) n[k] = '0' + ((n[k] - '0') ^ (o[k] - '0')); // j行目更新. ret[j] = n; } } } // 2-3. 返却. return ret; }; vs gMatrix = gauss(matrix, N, N); // puts("--- Matrix after update ---"); // rep(i, N) printf("%s\n", gMatrix[i].c_str()); // 3. 行列式. int ans = 1; rep(i, N) ans *= gMatrix[i][i] - '0'; // 4. 出力. printf("%s\n", ans ? "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 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
[入力例] 3 110 101 011 [出力例] Even ※AtCoderのテストケースより [入力例] 3 110 111 011 [出力例] Odd ※AtCoderのテストケースより [入力例] 2 00 00 [出力例] Even ※AtCoderのテストケースより [入力例] 12 000000100000 011111111111 000000100000 000111111100 100100000100 100111111100 100100000100 100111111100 100100000100 100111111100 100000000000 111111111111 [出力例] Even ※AtCoderのテストケースより [入力例] 5 10001 01010 00100 10100 01001 [出力例] Odd [入力例] 7 0010100 1010001 0010110 0110100 0011101 1110100 0110110 [出力例] Even [入力例] 20 10101011001000001011 01101000100000101010 00101010100110101101 01100001100101001011 10111100110110111011 00111001101011001010 01100100100101001101 01101101001010010001 00011011011101011100 01100001111010010011 01001000111001101101 00100101010111100001 01010101101111000000 11011100011101001001 00101101000111100100 01100001110011100111 01000110110011011101 01101000110000100110 10100011100101001010 11001010110101010111 [出力例] Odd [入力例] 30 111000000000000000000000000000 010000000000000000000000000000 001001000000000100000000000000 000100000000000000000100000000 001010000000000100000000000000 000001000000000000000000000000 010000100000000000000000000000 000000010000000100000000000000 000100001000000000000100000000 001000000100000000000000000000 000001000010000000000000000000 000100000001000000000000000000 000000000000100000000000000000 001000000000010000000100000000 000000000000001000000000000000 000100000000000100000000000000 000001000000000010000000000000 000000000000000001000000000000 000100000000000000100000000000 000000000000000100010000000000 000000000000000000001000000000 000001000000000000000100000000 000000000000000000000010000000 000000000000000000000001000000 000000000000000000000000100000 000000000000000100000100010000 000000000000000000000000001000 000000000000000000000000000100 000000000000000100000100000010 000000000000000000000000000001 [出力例] Odd |
■参照サイト
AtCoder Regular Contest 054