C++の練習を兼ねて, AtCoder Beginner Contest 180 の 問題D (Takahashi Unevolved) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説にあるように, カコモンジムへ通う回数を, 最大64回に固定して, シミュレーションしていく解法が, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 180 解説 の 各リンク を ご覧下さい.
■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 53 54 55 |
// 解き直し. // https://atcoder.jp/contests/abc180/editorial/219 // 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--) int main(){ // 1. 入力情報. LL X, Y, A, B; scanf("%lld %lld %lld %lld", &X, &Y, &A, &B); // 2. 経験値の最大値は? // -> 強さ, 経験値 を シュミレート. LL ans = 0; rep(i, 65){ // カコモンジムへ通う. LL s = X, e = 0; while(s < Y && e < i){ // オーバーフロー防止. if(Y / A <= s) break; // 強さ A倍. s *= A; // 経験値増加. ++e; }; // 強さが, Y以上になっているか? if(s >= Y){ // 強さ (1 / A)倍. s /= A; // 経験値減少. --e; } // AtCoderジムへ通う. e += max(0LL, Y - 1 - s) / B; // 最大値更新. ans = max(ans, e); } // 3. 出力. printf("%lld\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 |
[入力例] 4 20 2 10 [出力例] 2 ※AtCoderテストケースより [入力例] 1 1000000000000000000 10 1000000000 [出力例] 1000000007 ※AtCoderテストケースより [入力例] 3 1415926535 8 979 [出力例] 1446300 [入力例] 2022 20220610 2 123 [出力例] 164378 [入力例] 1732050 8075688 7 72935 [出力例] 86 [入力例] 22360 679774997896964091 7 36687312762 [出力例] 18528891 |
■参照サイト
AtCoder Beginner Contest 180