C++の練習を兼ねて, AtCoder Beginner Contest 203 の 問題F (Weed) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 203 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F／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 |
// 解き直し. // https://atcoder.jp/contests/abc203/editorial/1964 // 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 a[202020], f[202020], dp[202020][31]; int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); rep(i, N) scanf("%d", &a[i + 1]); // 2. sort. sort(a, a + N + 1); // 3. f を 計算. int l = N, r = N; while(r){ // 3-1. 判定. while(a[r] < 2 * a[l]) --l; // 3-2. 設定, および, デクリメント. f[r--] = l; } // 4. dp更新. repx(i, 1, N + 1) dp[i][0] = i; repx(i, 1, N + 1) repx(j, 1, 31) dp[i][j] = min(dp[i - 1][j] + 1, dp[f[i]][j - 1]); // 5. 操作回数を取得. int ans1 = 0, ans2 = 0; repr(j, 30, 0) if(dp[N][j] <= K) ans1 = j, ans2 = dp[N][j]; // 6. 出力. printf("%d %d\n", ans1, ans2); 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 1 2 3 4 9 [出力例] 2 1 ※AtCoderテストケースより [入力例] 3 3 2 3 5 [出力例] 0 3 ※AtCoderテストケースより [入力例] 9 8 137 55 56 60 27 28 133 56 55 [出力例] 1 4 ※AtCoderテストケースより [入力例] 30 8 51 104 6 87 96 44 90 11 9 90 82 50 98 52 105 44 63 92 99 37 92 33 32 73 72 57 41 102 109 96 [出力例] 2 3 [入力例] 50 10 348 207 216 593 462 219 37 612 36 1191 149 496 1042 259 452 206 529 70 52 540 418 63 709 917 915 466 265 21 32 824 228 705 1129 835 101 59 1020 1087 300 431 1049 1153 1119 678 1069 839 1175 258 148 833 [出力例] 3 9 |