C++の練習を兼ねて, AtCoder Beginner Contest 115 の 問題C（Christmas Eve) ～ 問題D (Christmas) を解いてみた.
■感想.
1. 問題D は, Level k Burger が, どのように含まれるか考えた後, 苦労して実装したが, ゴリゴリ書く羽目になってしまった.
かなり実装方針で悩んだが, 解説でも, 数列の考え方を使っていたので, アプローチとしては, 大きく外れて無かったと思う.
本家のサイトABC 115 解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; #define FOR(i, a, b) for(LL i = (a); i < (b); ++i) int main() { // 1. 入力情報取得. LL N, K; cin >> N >> K; LL h[N] = {}; FOR(i, 0, N) cin >> h[i]; // 2. 昇順sort. sort(h, h + N); // 3. 出来るだけ近い高さの木に飾り付ける. LL ans = 1000000000; FOR(i, 0, N - K + 1) ans = min(ans, h[i + K - 1] - h[i]); // 4. 後処理. cout << ans << endl; return 0; } |
■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 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 |
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(LL i = (a); i < (b); ++i) #define FORR(i, a, b) for(LL i = (a); i >= (b); --i) typedef long long LL; int main() { // 1. 入力情報取得. LL N, X; cin >> N >> X; // 2. Level k Burger の 枚数, Level k Burger の Patty の 枚数 を確認. // Level k Burger, Patty, Bun の 枚数は, それぞれ以下の内容と理解できる. // L(k) = 2 の (k + 2)乗 - 3 枚 // P(k) = 2 の (k + 1)乗 - 1 枚 // B(k) = 2 の (k + 1)乗 - 2 枚 // ex. // L(2) = 13, P(2) = 7, B(2) = 6 LL Burger[N + 1] = {}; Burger[0] = 1; FOR(i, 1, N + 1) Burger[i] = 2 * (Burger[i - 1] + 3) - 3; // FOR(i, 0, N + 1) cout << Burger[i] << endl; LL Patty[N + 1] = {}; Patty[0] = 1; FOR(i, 1, N + 1) Patty[i] = 2 * (Patty[i - 1] + 1) - 1; // 2-1. X が N 以下なら, 0 を出力して, 終了. LL ans = 0LL; if(X <= N) { cout << ans << endl; return 0; } // 2-2. Level k Burger を どのように含むかチェック. // Level k Burger の Level を 保存. vector<LL> Levels; // 前回チェックした Burger の Level. LL bef = N; while(1) { // X以下 で 最大の Level を見つけたら, 保存. FORR(cur, bef, 0) { LL subX = bef - cur + Burger[cur]; // cout << "subX=" << subX << " bef=" << bef << " cur=" << cur << " Burger[cur]=" << Burger[cur] << endl; if(subX <= X) { X -= subX; Levels.push_back(cur); bef = cur; break; } } // X が, 0 より大きい場合は, Level 0 Burger 追加. if(X > 0) { Levels.push_back(0); X--; } // cout << "X=" << X << endl; // X が, (5 + bef)以下 になったら, 以下の処理を行い, 処理を抜ける. if(X <= 5 + bef) { if(X >= 1 + bef) Levels.push_back(0); if(X >= 2 + bef) Levels.push_back(0); if(X >= 3 + bef) Levels.push_back(0); break; } } // for(auto &l : Levels) cout << l << endl; // 2-3. Patty の 枚数 を 数える. for(auto &l : Levels) ans += Patty[l]; // 3. 出力 ～ 後処理. cout << ans << endl; 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 |
[入力例] 5 5 [出力例] 0 BBBBB に, 'P' が 0個 含まれている. [入力例] 5 35 [出力例] 16 BBBBBPPPBPBPPPBBPBBPPPBPBPPPBBBPBBB に, 'P' が 16個 含まれている. [入力例] 5 50 [出力例] 25 BBBBBPPPBPBPPPBBPBBPPPBPBPPPBBBPBBBPPPBPBPPPBBPBBP に, 'P' が 25個 含まれている. [入力例] 5 75 [出力例] 38 BBBBBPPPBPBPPPBBPBBPPPBPBPPPBBBPBBBPPPBPBPPPBBPBBPPPBPBPPPBBBBPBBBBPPPBPBPP に, 'P' が 38個 含まれている. [入力例] 5 125 [出力例] 63 BBBBBPPPBPBPPPBBPBBPPPBPBPPPBBBPBBBPPPBPBPPPBBPBBPPPBPBPPPBBBBPBBBBPPPBPBPPPBBPBBPPPBPBPPPBBBPBBBPPPBPBPPPBBPBBPPPBPBPPPBBBBB に, 'P' が 63個 含まれている. [入力例] 50 4321098765432109 [出力例] 2160549382716056 ※AtCoderテストケースより |
■参照サイト
AtCoder Beginner Contest 115