C++の練習を兼ねて, AtCoder Beginner Contest 083 の 問題C（Multiple Gift) ～ 問題D (Wide Flip) を解いてみた.
■感想.
1. 問題D は, 解答方針が見えなかったので, 解説を参照して確認した.
本家のサイトARC 088/ABC 083 解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; int main() { // 1. 入力情報取得. LL X, Y; cin >> X >> Y; // 2. 条件を満たす数列を計算. LL curA = X; // 今回の計算結果保存用. LL befA = curA; // 前回の計算結果保存用. LL ans = 1; // 数列の長さ. while(true) { curA = 2 * befA; befA = curA; ans++; if(curA > Y) { ans--; break; } } // 3. 後処理. 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 |
// 解き直し. // ARC 088/ABC 083 解説. // https://img.atcoder.jp/arc088/editorial.pdf #include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) int main() { // 1. 入力情報取得. string S; cin >> S; // 2. 解説通り. // S の k文字目 と k + 1文字目が, 異なる箇所で, max(k, n - k) の最小値をT(S). int L = S.size(); // 文字列長. int ans = S.size(); // T(S). char cur = S[0]; // 今回出現する文字. char bef = S[0]; // 前回出現した文字. FOR(k, 1, L + 1) { // 今回出現する文字を設定. cur = S[k - 1]; // k文字目 と k + 1 文字目を比較. if(cur != bef) ans = min(ans, max(k - 1, L - k + 1)); // 前回出現文字を更新. bef = cur; } // 3. 後処理. 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 38 39 |
[入力例] 010 [出力例] 2 ※AtCoderテストケースより [入力例] 100000000 [出力例] 8 ※AtCoderテストケースより [入力例] 100010001 [出力例] 5 ※例えば, 以下のような変換が考えられる. (10001)0001 -> (01110)0001 (1文字目 ～ 5文字目までの5文字を変換) 0111(00001) -> 0111(11110) (5文字目 ～ 9文字目までの5文字を変換) 0(1111111)0 -> 0(0000000)0 (2文字目 ～ 8文字目までの7文字を変換) -> K = 5 と分かる. [入力例] 100010001100010001 [出力例] 10 ※例えば, 以下のような変換が考えられる. (1000100011)00010001 -> (0111011100)00010001 (1文字目 ～ 10文字目までの10文字を変換) 0(111011100000)10001 -> 0(000100011111)10001 (2文字目 ～ 13文字目までの12文字を変換) 0000(10001111110001) -> 0000(01110000001110) (5文字目 ～ 18文字目までの14文字を変換) 00000(111000000111)0 -> 00000(000111111000)0 (6文字目 ～ 17文字目までの12文字を変換) 00000000(1111110000) -> 00000000(0000001111) (9文字目 ～ 18文字目までの10文字を変換) (00000000000000)1111 -> (11111111111111)1111 (1文字目 ～ 14文字目までの14文字を変換) (111111111111111111) -> (000000000000000000) (1文字目 ～ 18文字目までの18文字を変換) -> K = 10 と分かる. |
■参照サイト
AtCoder Beginner Contest 083