C++の練習を兼ねて, AtCoder Regular Contest 127 の 問題C (Binary Strings) を解いてみた.
■感想.
1. 問題C は, 方針が見えなかったので, 解説を参考に実装したところ AC版に到達できた.
2. 個人的には, 解説のロジックが, 不思議な感じがするとともに, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 127 解説 の 各リンク を ご覧下さい.
■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 101 102 103 104 105 106 107 |
// 解き直し. // https://atcoder.jp/contests/arc127/editorial/2688 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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 N; char c[1010101]; scanf("%d %s", &N, c); string s(c); // 2. (X - 1)作成. // ex. // N = 7, X = 1010 -> X - 1 = 0001001 を 作成. int l = s.size(); int n = N - l; int x[N]; int at = -1; repr(i, l - 1, 0){ if(s[i] == '1'){ at = i; break; } } rep(i, n) x[i] = 0; repx(i, n, n + at) x[i] = s[i - n] - '0'; x[n + at] = 0; repx(i, n + at + 1, N) x[i] = 1; // rep(i, N) printf("%d", x[i]); // puts(""); // 3. 文字列作成. // ex. // N = 5 // X = 10110 // -> X - 1 は, 10101. // N = 5. // B 10000 // X 10101 // -> 1 (X - 10000 を 計算) // // N = 4 // B 01000 // X 00101 // -> 10 (X - 00001 を 計算) // // N = 3 // B 00100 // X 00100 // -> 101 (X - 00100 を 計算) // // N = 2 // B 00010 // X 00000 // -> X が 0 となったので終了. // -> 1 + 101 = 1101 が出力されると理解. string ans = ""; rep(i, N){ // X[i] が 1. if(x[i]){ x[i] = 0; ans.pb('1'); continue; } // X[i] が 0. // 一番後ろの 1 の場所は？ int cur = -1; repr(j, N - 1, 0){ if(x[j]){ cur = j; break; } } // X が 0(終了). if(cur == -1) break; // X[N - 1] が 1. if(cur == N - 1) x[N - 1] = 0; // X[N - 1] が 0. if(cur < N - 1){ x[cur] = 0; repr(j, N - 1, cur + 1) x[j] = 1; } // '0' を 追加. ans.pb('0'); } // 4. 先頭に, '1' を 追加. ans = "1" + ans; // 5. 出力. printf("%s\n", ans.c_str()); 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 |
[入力例] 3 101 [出力例] 11 ※AtCoderのテストケースより [入力例] 10 10100011 [出力例] 1001001111 ※AtCoderのテストケースより [入力例] 1000000 11111 [出力例] 1000000000000000000000000000000 ※AtCoderのテストケースより [入力例] 4 1010 [出力例] 110 [入力例] 4 101 [出力例] 1001 [入力例] 5 10110 [出力例] 1101 [入力例] 31 11000111010010101001100101111 [出力例] 100110001110100101010011001 [入力例] 200 1100010111011011011111101001111010010111100001010001010110110110011110110000011010101101010000010001010000100100010101101010000111111101011111101000001100110000100001000011101100101110100000011011010 [出力例] 1011000101110110110111111010011110100101111000010100010101101101100111101100000110101011010100000100010100001001000101011010100001111111010111111010000011001100001000010000111011001011101000000011101 [入力例] 2021 1010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100011010010000100101111110100110001110010011110001000010111110100001011100101000011111011111111110100100010001100100000011110010011101110001010010001000110010000011010111100001101011011100101001010011000110100100001001011111101001100011100100111100010000101111101000010111001010000111110111111111101001000100011001000000111100100111011100010100100010001100100000110101111000011010110111001010010100110001101001000010010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100011010010000100101111110100110001110010011110001000010111110100001011100101000011111011111111110100100010001100100000011110010011101110001010010001000110010000011010111100001101011011100101001010011000110100100001 [出力例] 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000101011111101001100011100100111100010000101111101000010111001010000111110111111111101001000100011001000000111100100111011100010100100010001100100000110101111000011010110111001010010100110001101001000010010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100011010010000100101111110100110001110010011110001000010111110100001011100101000011111011111111110100100010001100100000011110010011101110001010010001000110010000011010111100001101011011100101001010011000110100100001001011111101001100011100100111100010000101111101000010111001010000111110111111111101001000100011001000000111100100111011100010100100010001100100000110101111000011010110111001010010100110001101001000010010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100001110010001 |
■参照サイト
AtCoder Regular Contest 127