C++の練習を兼ねて, 競プロ典型 90 問 の 問題057 (Flip Flap) を解いてみた.
■感想.
1. 問題057は, 方針が見えなかったので, (問題057 (Flip Flap) 解説) を参考に実装したところ, AC版に到達出来た.
2. 行列の掃き出し法について学習出来たので, 非常に良かったと思う..
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題057 を ご覧下さい.
■C++版プログラム(問題057／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 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 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 |
// 解き直し. // https://github.com/E869120/kyopro_educational_90/blob/main/editorial/057.jpg // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vs = vector<string>; 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--) #define pb push_back #define all(x) x.begin(), x.end() const LL MOD = 998244353; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); string z(M, '0'); vs matrix; rep(i, N){ matrix.pb(z); int t; scanf("%d", &t); rep(j, t){ int a; scanf("%d", &a); a--; matrix[i][a] = '1'; } } string S; rep(i, M){ int c; scanf("%d", &c); S.pb(c + '0'); } // puts("--- Matrix before update ---"); // rep(i, N) printf("%s\n", matrix[i].c_str()); // puts("--- Target string ---"); // printf("%s\n", S.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 = 0; rep(j, M){ if(ret[i][j] == '1'){ at = j; break; } } // 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, M); // puts("--- Matrix after update ---"); // rep(i, N) printf("%s\n", gMatrix[i].c_str()); // 3. 1行目のスイッチから, 希望通りのパネルのパターンになるかチェック. int index = 0; while(index < N){ // 文字列 S で, 最初に, '1' となる位置. int at = -1; rep(j, M){ if(S[j] == '1'){ at = j; break; } } // 文字列 S に, '1' が 含まれなかった場合. if(at == -1) break; // 更新後の行列で, 前項で求めた位置に, '1' が 来るものがあるか？ while(gMatrix[index][at] != '1'){ index++; if(index >= N) break; } // 見つからなかった場合は, 終了. if(index >= N) break; // 見つかった場合, 文字列 S を 更新. rep(k, M) S[k] = '0' + ((S[k] - '0') ^ (gMatrix[index][k] - '0')); // 次行へ. index++; } // 4. 希望通りのパネルのパターンを実現出来なかったら終了. if(S != z){ puts("0"); return 0; } // 5. 希望通りのパネルのパターンを実現できる場合. int zCount = 0; rep(i, N) if(gMatrix[i] == z) zCount++; // 6. ボタンの押し方の場合の数を計算. LL ans = 1; rep(i, zCount) ans <<= 1, ans %= MOD; // 7. 出力. 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 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 134 135 136 |
[入力例] 2 3 2 1 2 2 2 3 1 0 1 [出力例] 1 ※AtCoderテストケースより [入力例] 2 3 1 1 1 2 0 1 1 [出力例] 0 ※AtCoderテストケースより [入力例] 3 2 1 1 1 2 1 2 1 0 [出力例] 2 ※AtCoderテストケースより [入力例] 13 6 3 1 3 5 3 1 4 5 4 3 4 5 6 2 2 5 4 1 2 3 5 3 3 4 6 3 4 5 6 6 1 2 3 4 5 6 4 1 3 5 6 3 1 2 4 3 1 5 6 4 1 2 3 4 1 5 1 0 0 1 0 0 [出力例] 128 ※AtCoderテストケースより [入力例] 5 6 3 2 3 6 2 3 6 4 1 3 5 6 3 2 4 5 2 3 4 1 0 1 1 0 1 [出力例] 1 [入力例] 7 10 6 2 3 5 6 8 9 5 2 4 6 7 8 6 3 4 5 6 7 8 5 1 2 3 5 8 3 4 5 6 8 1 3 4 5 6 7 8 9 5 5 7 8 9 10 1 0 1 0 1 1 0 0 0 1 [出力例] 1 [入力例] 10 15 3 4 6 12 2 9 13 3 4 6 13 5 3 9 11 12 13 3 4 6 13 3 4 6 13 2 9 13 3 1 2 4 3 3 7 8 3 4 6 12 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 [出力例] 16 |