C++の練習を兼ねて, AtCoder Beginner Contest 124 の 問題C (Coloring Colorfully) ～ 問題D (Handstand) を解いてみた.
■感想.
1. 問題D は, 解答方針が全く見えなかったので, 解き直しすることになった.
本家のサイトABC 124解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; int main() { // 1. 入力情報取得. string S; cin >> S; // 2. 塗り替えるタイルの枚数の最小値は？ // 2-1. 1 -> 0 -> 1 -> ... パターン. int a1 = 0; char f1 = '1', f2 = '0'; for(int i = 0; i < S.size(); i++){ if(S[i] != f1) S[i] = f2, a1++; swap(f1, f2); } // 2-2. 0 -> 1 -> 0 -> ... パターン. int a2 = 0; f1 = '0', f2 = '1'; for(int i = 0; i < S.size(); i++){ if(S[i] != f1) S[i] = f2, a2++; swap(f1, f2); } // 3. 後処理. int ans = min(a1, a2); cout << ans << endl; return 0; } |
■C++版プログラム(問題D／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 |
// 解き直し. // ABC 124解説. // https://img.atcoder.jp/abc124/editorial.pdf #include <bits/stdc++.h> using namespace std; int main() { // 1. 入力情報取得. int N, K; string S; cin >> N >> K >> S; // 2. 解説通り. // 連続する '0' or '1' の開始位置 i1, i2, i3, ... , ir を 取得. vector<int> v; // 前回出現文字. char bef = 'b'; for(int i = 0; i < N; i++){ // 今回出現文字. char cur = S[i]; // 前回文字と異なる場合は, 文字位置を保存. if(bef != cur) v.push_back(i); // 前回出現文字更新. bef = cur; } v.push_back(N); // for(auto &p : v) cout << p << " "; // 3. S(ik) の 値 に応じて, 逆立ちした人を連続で最大何人並ばせることが出来るか計算. // S(ik) = '0' なら, X(ik) = i(k + 2 * K) - i(k) // S(ik) = '1' なら, X(ik) = i(k + 2 * K + 1) - i(k) int ans = 0; int r = v.size(); for(int k = 1; k < r; k++){ if(S[v[k - 1]] == '0'){ int u = min(r, k + 2 * K); ans = max(ans, v[u - 1] - v[k - 1]); } if(S[v[k - 1]] == '1'){ int u = min(r, k + 2 * K + 1); ans = max(ans, v[u - 1] - v[k - 1]); } } // 4. 後処理. cout << ans << endl; 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 |
[入力例] 5 1 00010 [出力例] 4 ※AtCoderテストケースより [入力例] 8 1 01100100 [出力例] 5 [入力例] 14 2 11101010110011 [出力例] 8 ※AtCoderテストケースより [入力例] 1 1 1 [出力例] 1 ※AtCoderテストケースより [入力例] 32 3 11100100000101101000110000000000 [出力例] 19 |
■参照サイト
AtCoder Beginner Contest 124