C++の練習を兼ねて, AtCoder Beginner Contest 299 の 問題C (Dango) ～ 問題D (Find by Query) を解いてみた.
■感想.
1. 問題C, D は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題D で, 二分探索 の 復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 299 解説 の 各リンク を ご覧下さい.
■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 |
// 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[202020]; scanf("%d %s", &N, c); // 2. カウント. // 2-1 左 -> 右. int ans = -1; string s; rep(i, N){ if(c[i] == '-'){ if(s.size() > 1) ans = max(ans, (int)s.size() - 1); s.clear(); s.pb(c[i]); continue; } if(s.size()) s.pb(c[i]); } if(s.size() > 1) ans = max(ans, (int)s.size() - 1); // 2-2. 右 -> 左. s.clear(); repr(i, N - 1, 0){ if(c[i] == '-'){ if(s.size() > 1) ans = max(ans, (int)s.size() - 1); s.clear(); s.pb(c[i]); continue; } if(s.size()) s.pb(c[i]); } if(s.size() > 1) ans = max(ans, (int)s.size() - 1); // 3. 出力. printf("%d\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 |
[入力例] 10 o-oooo---o [出力例] 4 ※AtCoderテストケースより [入力例] 1 - [出力例] -1 ※AtCoderテストケースより [入力例] 30 -o-o-oooo-oo-o-ooooooo--oooo-o [出力例] 7 ※AtCoderテストケースより [入力例] 5 ooooo [出力例] -1 [入力例] 12 -o-oo-o-o-o- [出力例] 2 [入力例] 50 o---o-o--oo-o--ooo-o-o---o--oo-o-ooooo-o-oo--ooo-o [出力例] 5 |
■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 |
// 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--) int main(){ // 1. 入力情報. int N; scanf("%d", &N); // 2. 評価関数. auto f = [&](int m) -> bool { // 2-1. 質問. printf("? %d\n", m); fflush(stdout); // 2-2. 応答. int s; scanf("%d", &s); // 2-3. 判定結果. return (s == 0); }; // 3. 二分探索で確認してみる. int l = 0, h = N; while(l + 1 < h){ int m = (h + l) >> 1; if(f(m)) l = m; else h = m; // printf("h=%d l=%d m=%d\n", h, l, m); } // 4. 出力. printf("! %d\n", l); 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 |
※インタラクティブな問題のため, 入出力は, デバッグ時に使用したものを記載している. [入力例(N = 7, S=0010011)] 7 1 0 0 [出力例] ? 3 ? 1 ? 2 ! 2 ※AtCoderテストケースより [入力例(N = 12, S=011010010011)] 12 0 0 0 1 [出力例] ? 6 ? 9 ? 10 ? 11 ! 10 [入力例(N = 15, S=011001001010011)] 15 0 1 1 0 [出力例] ? 7 ? 11 ? 9 ? 8 ! 8 [入力例(N = 25, S=0110010101101010100100101)] 25 0 0 0 1 0 [出力例] ? 12 ? 18 ? 21 ? 23 ? 22 ! 22 |