C++の練習を兼ねて, AtCoder Grand Contest 004 の 問題A (Divide a Cuboid) ~ 問題B (Colorful Slimes) を解いてみた.
■感想.
1. 問題B は, 方針が見えなかったので, 解説を参照して実装したところ, 何とか, AC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトAGC 004 解説をご覧下さい.
■C++版プログラム(問題A/AC版).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <bits/stdc++.h> using namespace std; using LL = long long; int main(){ // 1. 入力情報. LL A, B, C; scanf("%lld %lld %lld", &A, &B, &C); // 2. 赤いブロックの個数と青いブロックの個数の差を小さくする. // 2-1. A, B, C の いずれかが偶数なら, 差は 0 のはず. LL ans = 0; if((A % 2) * (B % 2) * (C % 2) == 0) ans = 0; // 2-2. A, B, C が すべて奇数の場合は, A * B, B * C, C * A の 最小値. if((A % 2) * (B % 2) * (C % 2) == 1) ans = min({A * B, B * C, C * A}); // 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 |
[入力例] 3 3 3 [出力例] 9 ※AtCoderテストケースより [入力例] 2 2 4 [出力例] 0 ※AtCoderテストケースより [入力例] 5 3 5 [出力例] 15 ※AtCoderテストケースより [入力例] 14142135 6237309 5048801 [出力例] 31490931916509 |
■C++版プログラム(問題B/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 |
// 解き直し. // https://img.atcoder.jp/data/agc/004/editorial.pdf #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--) LL a[2020], b[2020][2020]; int main(){ // 1. 入力情報. int N; LL x; scanf("%d %lld", &N, &x); rep(i, N) scanf("%lld", &a[i]); rep(i, N) rep(j, N) b[i][j] = 2020202020202020; // 2. 事前計算. rep(i, N) rep(k, N) b[i][k] = min(b[i][(k - 1 + N) % N], a[(i - k + N) % N]); // 3. 魔法を唱える回数を固定し全探索. LL ans = 2020202020202020; rep(k, N){ LL t = k * x; rep(i, N) t += b[i][k]; ans = min(ans, t); } // 4. 出力. 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 |
[入力例] 2 10 1 100 [出力例] 12 ※AtCoderテストケースより [入力例] 3 10 100 1 100 [出力例] 23 ※AtCoderテストケースより [入力例] 4 10 1 2 3 4 [出力例] 10 ※AtCoderテストケースより [入力例] 7 11 7 9 2 5 13 8 17 [出力例] 50 |
■参照サイト
AtCoder Grand Contest 004