C++の練習を兼ねて, AtCoder Beginner Contest 112 の 問題C（Pyramid), 問題D（Partition) を解いてみた.
■感想.
1. 問題D は, 時間内で, テストケース C030_scrambled を除いて, 通過したが, ロジック修正を, 自力で出来なかったため, コンテスト終了後, 解説を見て, ロジック修正した.
2. 問題C は, 時間内で, 外枠だけコーディングしたが, 問題の意図を理解できなかったので, コンテスト終了後, 再度解き直した.
3. 問題C は, テストケース in04.txt, in06.txt, in20.txt の Wrong Answer を, 解説見ても, 自力で修正できなかったので, 正解者 の コーディングを参照したところ, N個 の ピラミッド情報 で, ピラミッド高度 に 関する 降順 sort が, 必要なことが分かった(※初回取得で, 高度 0 を取得させないようにするため)ので, ロジック修正した.
4. 個人的には, ここ最近, ABCコンテストの難易度が, かなり上昇気味に感じた, 復習がかなり大変となっている模様(汗).
本家のサイトABC 112 解説をご覧下さい.
■C++版プログラム(問題C).
|
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 |
// 解き直し. // ABC 112 解説. // https://img.atcoder.jp/abc112/editorial.pdf #include <bits/stdc++.h> using namespace std; typedef long long LL; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) struct pyramid { int x; // ピラミッドのx座標. int y; // ピラミッドのy座標. LL h; // ピラミッドの高度. }; int main() { // 1. 入力情報取得. int N; cin >> N; vector<pyramid> v; FOR(i, 0, N) { pyramid p; cin >> p.x >> p.y >> p.h; v.push_back(p); } // 2. ピラミッドの高度に関して, 降順sort の ロジック追加. // テストケース in04.txt, in06.txt, in20.txt の Wrong Answer を, 自力で修正できなかったので, // 正解者 の コーディングを参照したところ, 下記 3-1. の ロジックで, // ピラミッドの高度 が 0 より大きいものが取れている必要があるとの情報が得られたため. sort(v.begin(), v.end(), [](const pyramid& x, const pyramid& y) {return x.h > y.h;}); // 3. ピラミッド中心座標を計算. // 中心が, (pCx, pCy) だったとして, 全部調査してみる. int cx = 0; int cy = 0; LL h = 0LL; FOR(pCx, 0, 101) { FOR(pCy, 0, 101) { bool isCenter = true; LL lh = -1LL; for (auto &p : v) { // 3-1. とりあえず, 高さを抽出. if(lh == -1LL) { lh = p.h + abs(p.x - pCx) + abs(p.y - pCy); continue; } // 3-2. 抽出した高さが, 条件を満たすかを確認. // -> ピラミッド中心座標が確定すれば, (p.x, p.y) によらず, 高さが一定になるはず. LL lh2 = max(lh - abs(p.x - pCx) - abs(p.y - pCy), 0LL); if(p.h != lh2) { isCenter = false; break; } } // 3-3. 確定したピラミッド中心座標, 高度を保存. if(isCenter) { cx = pCx; cy = pCy; h = lh; break; } } } // 4. 出力 ～ 後処理. cout << cx << " " << cy << " " << h << endl; return 0; } |
■C++版プログラム(問題D).
|
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 |
// 解き直し. // ABC 112 解説. // https://img.atcoder.jp/abc112/editorial.pdf #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, M; cin >> N >> M; // 2. 最大公約数を計算. LL ans = 1; if(M % N == 0) ans = M / N; if(M % N != 0) { LL LGCD = 1; // C030_scrambled が通過できなかった. // FOR(i, 2, 100001) { LL LIMIT = M / N; FOR(i, 2, LIMIT) { if(M % i == 0) LGCD = i; if(LGCD * N <= M) ans = max(ans, LGCD); } } // 3. 出力 ～ 後処理. cout << ans << endl; return 0; } |
■参照サイト
AtCoder Beginner Contest 112