AtCoder ABC 062 C - Chocolate Bar (ARC 074 C) (緑色, 400 点)

最適解の形を丁寧に場合分けして考える系

問題へのリンク

問題概要

の板チョコレートを 3 つの長方形に割りたい。そのときの 3 つの長方形の面積の最大値と最小値の差の最小値を求めよ。

制約

• 

考えたこと

まず思ったのは、 のうちの少なくとも一方が 3 の倍数であったら三等分できて 0 になる。

そうでない場合、とりあえず一つ言えるのは、3 つの長方形のうちの 1 つは、「」か「」の形になる。このくらいは全探索できる。

そして残る長方形については、どうあっても差が最小になるようにすればよい。

• 2 辺のうちの少なくとも一方が偶数だったら綺麗に二等分
• そうでない場合は、辺の長さが小さい方の辺に沿って割る

とすれば OK。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using pll = pair<long long, long long>;
pll sub(long long h, long long w) {
    if (h % 2 == 0 || w % 2 == 0) return {h*w/2, h*w/2};
    if (h > w) swap(h, w);
    return {h * (w+1)/2, h * (w-1)/2};
}

int main() {
    long long H, W;
    cin >> H >> W;
    long long res = H * W;

    for (long long h = 1; h < H; ++h) {
        vector<long long> a(3);
        a[0] = h * W;
        auto p = sub(H-h, W);
        a[1] = p.first, a[2] = p.second;
        sort(a.begin(), a.end());
        chmin(res, a.back() - a[0]);
    }
    for (long long w = 1; w < W; ++w) {
        vector<long long> a(3);
        a[0] = H * w;
        auto p = sub(H, W-w);
        a[1] = p.first, a[2] = p.second;
        sort(a.begin(), a.end());
        chmin(res, a.back() - a[0]);
    }
    cout << res << endl;
}