C++の練習を兼ねて, AtCoder Beginner Contest 085 の 問題D (Katana Thrower) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説にあるロジック(投げ刀, 強い投げ刀, 振り刀に分けて考える)が, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 085 解説 を ご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/abc085/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; using vp = vector<P>; #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 a first #define b second #define pb push_back #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N, H; scanf("%d %d", &N, &H); vp v; int a, b, maxA = 0; rep(i, N){ scanf("%d %d", &a, &b); v.pb({a, 0}); // 振り刀. v.pb({b, 1}); // 投げ刀. maxA = max(maxA, a); // 攻撃力最大の振り刀. } // 2. sort. sort(all(v)); reverse(all(v)); // 3. 攻撃パターン 1. // 強い投げ刀を投げる. int ans = 0; rep(i, N * 2){ if(H > 0 && v[i].b && v[i].a >= maxA){ H -= v[i].a; ans++; } } // 4. 攻撃パターン 2. // 攻撃力最大の振り刀を振り続ける. if(H > 0) ans += (H + maxA - 1) / maxA; // 5. 出力. 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 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 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
[入力例] 1 10 3 5 [出力例] 3 ※AtCoderテストケースより [入力例] 2 10 3 5 2 6 [出力例] 2 ※AtCoderテストケースより [入力例] 4 1000000000 1 1 1 10000000 1 30000000 1 99999999 [出力例] 860000004 ※AtCoderテストケースより [入力例] 5 500 35 44 28 83 46 62 31 79 40 43 [出力例] 9 ※AtCoderテストケースより [入力例] 10 12345 100 222 72 194 108 211 76 172 85 144 28 51 40 126 8 50 19 120 26 84 [出力例] 111 [入力例] 30 20220210 941 9675 723 8610 873 9340 133 8728 286 9696 343 9739 369 9549 715 8992 665 9378 127 7592 313 9120 141 9167 69 8934 999 9174 985 9922 862 8752 455 9665 969 8218 705 7940 519 9332 859 9772 47 8968 333 9603 427 8878 710 7646 272 9973 145 8972 375 7253 45 9815 930 8493 [出力例] 20000 |
■参照サイト
AtCoder Beginner Contest 085