C++の練習を兼ねて, AtCoder Regular Contest 078 の 問題E (Awkward Response) を解いてみた.
■感想.
1. 方針が見えなかったので, 解説を参考に, ようやくAC版となった.
2. 標準出力で投げる整数は, 1 ～ 1e18 の 範囲に限定されることについて, 問題文を読み落としていたので, バグに気付くまでに, 非常に苦労した.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトAtCoder Regular Contest 078 解説をご覧下さい.
■C++版プログラム(問題E／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 |
// 解き直し. // https://img.atcoder.jp/arc078/editorial.pdf // 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--) #define pb push_back int main(){ // 1. 10 の べき乗 を 保存. vector<LL> p10; p10.pb(1); repx(i, 1, 19) p10.pb(10 * p10[i - 1]); // rep(i, 19) printf("%lld\n", p10[i]); // 2. N の 桁数L を 計算. // 2-1. N が 10 の (L - 1)乗 でない場合. int L1 = 0; rep(k, 19){ printf("? %lld\n", p10[k]); fflush(stdout); char ans[11]; scanf("%s", ans); if(ans[0] == 'Y') L1 = k + 1; else break; } // 2-2. N が 10 の (L - 1)乗 である場合. int L2 = 0; if(L1 == 19){ // 21.txt - 30.txt で, WA判定となった原因. // -> 標準出力で投げる整数は, 1 ～ 1e18 の 範囲に限定されることに注意. // -> 2 * p10[k] で, k = 18 の 場合に, 条件を満たさくなっていた. // repr(k, 18, 0){ repr(k, 17, 0){ printf("? %lld\n", 2 * p10[k]); fflush(stdout); char ans[11]; scanf("%s", ans); if(ans[0] == 'Y') L2 = k + 1; else break; } } // 3. N が 10 の (L - 1)乗 である場合. if(L2){ printf("! %lld\n", p10[L2 - 1]); fflush(stdout); return 0; } // 4. N が 10 の (L - 1)乗 でない場合. // 二分探索で確認してみる. LL l = p10[L1 - 1], h = p10[L1], m; while(l + 1 < h){ m = (h + l) >> 1; printf("? %lld\n", 10 * m); fflush(stdout); char ans[11]; scanf("%s", ans); if(ans[0] == 'Y') h = m; else l = m; } printf("! %lld\n", h); fflush(stdout); return 0; } |
|
1 |
※インタラクティブな問題のため, 入出力は, 未記載としている. |
■参照サイト
AtCoder Regular Contest 078