C++の練習を兼ねて, AtCoder Regular Contest 156 の 問題A (Non-Adjacent Flip) ～ 問題B (Mex on Blackboard) を解いてみた.
■感想.
1. 問題B は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 計算できる点が, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 156 解説 の 各リンク を ご覧下さい.
■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 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; #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 int main(){ // 1. 入力情報. int T; scanf("%d", &T); // 2. テストケース. rep(i, T){ // 2-1. 各テストケース. int N; scanf("%d", &N); char c[N + 1]; scanf("%s", c); string s(c); // 2-2. 1 の 個数. vi v; rep(j, N) if(s[j] == '1') v.pb(j); // 2-3. 1 が 奇数個. int n = v.size(); if(n & 1){ puts("-1"); continue; } // 2-4. 1 が 0個 or 4個以上. if(n == 0 || n >= 4){ printf("%d\n", n / 2); continue; } // 2-5. 1 が 2個(隣接していない). if(v[0] + 1 != v[1]){ printf("%d\n", n / 2); continue; } // 2-6. 1 が 2個(隣接している). // N が 3. if(N == 3){ puts("-1"); continue; } // N が 3 より大きい(110...00, または, 00...011). if((v[0] == 0 && v[1] == 1) || (v[0] == N - 2 && v[1] == N - 1)){ puts("2"); continue; } // N が 4(0110). if(N == 4){ puts("3"); continue; } // N が 4 より大きい(00...0110...00). puts("2"); } 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 |
[入力例] 5 3 101 6 101101 5 11111 6 000000 30 111011100110101100101000000111 [出力例] 1 2 -1 0 8 ※AtCoderのテストケースより [入力例] 24 3 000 3 001 3 010 3 011 3 100 3 101 3 110 3 111 4 0000 4 0001 4 0010 4 0011 4 0100 4 0101 4 0110 4 0111 4 1000 4 1001 4 1010 4 1011 4 1100 4 1101 4 1110 4 1111 [出力例] 0 -1 -1 -1 -1 1 -1 -1 0 -1 -1 2 -1 1 3 -1 -1 1 1 -1 2 -1 -1 2 [入力例] 7 5 10111 10 1011010010 15 100111000011010 20 00000000011000000000 30 011011100101110110011101100011 50 10110001111001100000000010001010011110011000000011 100 1010000110110000010110100111101011100011000100001101010110110011101010000101001010101101111001010111 [出力例] 2 -1 -1 2 9 10 25 |
■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 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 |
// 解き直し. // https://atcoder.jp/contests/arc156/editorial/5718 // 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--) const LL MOD = 998244353; const int LIMIT = 404040; LL FAC[LIMIT], INV[LIMIT]; int a[LIMIT], M[LIMIT], memo[LIMIT]; // Fermat's little theorem から, 大きな冪乗の計算を行う. // @param a: べき乗したい正整数. // @param b: 指数. // @return: べき乗した計算結果(mod版). LL mPow(LL a, LL b){ LL t = 1; while(b){ if(b & 1) t = (t * a) % MOD; a = a * a % MOD; b >>= 1; } return t; } // 組み合わせ(nCk)計算用(mod版). // ※配列FAC, INV は, 事前に計算済のものを使う. // @param n: 対象となる要素の個数. // @param k: 選択する要素の個数. // @return: 組み合わせ(nCk)の計算結果(mod版). LL combination(LL n, LL k){ if(n < 0 || k < 0 || k > n) return 0LL; if(n == k || k == 0LL) return 1LL; LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD; return ret; } int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); rep(i, N){ int p; scanf("%d", &p); a[p] = 1; } // 2. 事前準備. FAC[0] = INV[0] = 1; repx(i, 1, LIMIT){ FAC[i] = (LL)i * FAC[i - 1] % MOD; INV[i] = mPow(FAC[i], MOD - 2); } // 3. M の 計算. int mMax = 0; rep(i, N + K + 1){ if(i) M[i] = M[i - 1]; if(a[i] == 0) M[i] = ++mMax; } // 4. 集計. // // ex. // 8 5 // 1 2 0 2 0 5 6 9 // (K - M) が 等しい場合は, 操作で書く最大値 x の中で, 最も大きい部分だけ, 加算する. // ※重複して数えることを防止するため. // // x = 12 K - M = -2 combination = 0 // x = 11 K - M = -1 combination = 0 // x = 10 K - M = 0 combination = 1 <- 加算対象. // x = 9 K - M = 1 combination = 10 <- 加算対象. // x = 8 K - M = 1 combination = 9 // x = 7 K - M = 2 combination = 36 <- 加算対象. // x = 6 K - M = 3 combination = 84 <- 加算対象. // x = 5 K - M = 3 combination = 56 // x = 4 K - M = 3 combination = 35 // x = 3 K - M = 4 combination = 35 <- 加算対象. // x = 2 K - M = 5 combination = 21 <- 加算対象. // x = 1 K - M = 5 combination = 6 // x = 0 K - M = 5 combination = 1 // -> 加算対象を集計すると, 1 + 10 + 36 + 84 + 35 + 21 = 187 を 得る. LL ans = 0; repr(x, N + K - 1, 0){ int km = K - M[x]; if(km < 0 || memo[km]) continue; // 加算. ans = (ans + combination(K - M[x] + x, x)) % MOD; // 加算済. ++memo[km]; } // 5. 出力. 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 |
[入力例] 3 1 0 1 3 [出力例] 3 ※AtCoderのテストケースより [入力例] 2 1 0 0 [出力例] 2 ※AtCoderのテストケースより [入力例] 5 10 3 1 4 1 5 [出力例] 7109 ※AtCoderのテストケースより [入力例] 8 5 1 2 0 2 0 5 6 9 [出力例] 187 [入力例] 20 10 0 5 7 7 2 1 5 6 6 4 9 0 1 5 3 2 8 6 0 6 [出力例] 354522 |
■参照サイト
AtCoder Regular Contest 156