AtCoder Beginner Contest 062 C - 今日から始める競プロ日記
はじめに
chokudaiさんの今日の一問を解いてみた。
AtCoder Beginner Contest 062 C 。
とりあえず解き方を自分なりにまとめておく。
今日の問題は、ABC062より、Chocolate Bar！
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) August 24, 2019
自分が個人的に解けてほしい問題を選んでるのが分かりやすいチョイスかなーと思うけど、これも緑くらいあったら解けてほしい問題。400点だけどね＞＜#chokudai今日の一問
C - Chocolate Bar https://t.co/nWB7rNyyuM
C - Chocolate Bar
縦Hブロック、横Wブロックのチョコレートをできるだけ均等に3分割したい。
3つのブロックの最大面積をSmax、
最小面積をSminとするとき、
Smax - Sminを最小化せよ。
解いた方針
公式の解説を参考にしながらまとめてみる。
https://img.atcoder.jp/arc074/editorial.pdf
全通りの切り方を試そうとするとTLEするから、 工夫する必要がある。
そこで考えてみると、 三分割する方法は4通りしかない。
- 1 : (1) 横に切ってから、(2) 横に切る
- 2 : (1) 横に切ってから、(2) 縦に切る
- 3 : (1) 縦に切ってから、(2) 横に切る
- 4 : (1) 縦に切ってから、(2) 縦に切る
(1) では切る場所を全通り試すO(N^5)。
(2) では、(1) で切ったあとの残りのブロックを半分にすればいいので、
単純に真ん中を切ればいいO(1)。
「(1) 横に切ってから、(2) 縦に切る」を図に表すとこんな感じ。
まず、0 < h < H で横に切る場所 h を全て試すfor文を回す (1)。
そのfor文の中で、横に切った後の残りのブロックを半分にする (2)。
そうすると、三分割ができるので、Smax - Smin を求められる。
その中で最も小さい Smax - Smin を見つければよい。
自分のコード
解説を読んでから書いたので、 たぶん解説寄りなコードになっているはず。
#include <iostream>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int main()
{
ll H, W; cin >> H >> W;
ll ans = INF;
for(int h = 1; h < H; h++) {
ll h2 = (H - h) / 2;
if(h2 > 0) {
ll S1 = W * h;
ll S2 = W * h2;
ll S3 = W * (H - h - h2);
ll Smax = max(S1, max(S2, S3));
ll Smin = min(S1, min(S2, S3));
ans = min(ans, Smax-Smin);
}
ll w2 = W / 2;
if(w2 > 0) {
ll S1 = W * h;
ll S2 = (H-h) * w2;
ll S3 = (H-h) * (W - w2);
ll Smax = max(S1, max(S2, S3));
ll Smin = min(S1, min(S2, S3));
ans = min(ans, Smax-Smin);
}
}
for(int w = 0; w < W; w++) {
ll w2 = (W - w) / 2;
if(w2 > 0) {
ll S1 = H * w;
ll S2 = H * w2;
ll S3 = H * (W - w - w2);
ll Smax = max(S1, max(S2, S3));
ll Smin = min(S1, min(S2, S3));
ans = min(ans, Smax-Smin);
}
ll h2 = H / 2;
if(h2 > 0) {
ll S1 = H * w;
ll S2 = (W-w) * h2;
ll S3 = (W-w) * (H - h2);
ll Smax = max(S1, max(S2, S3));
ll Smin = min(S1, min(S2, S3));
ans = min(ans, Smax-Smin);
}
}
cout << ans << endl;
return 0;
}
おわりに
そこそこ時間がかかってしまった。
もっとシンプルに問題を考えられるように精進していきたい。
