Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

ARC074-C 「Chocolate Bar」 (400)

舐めてかかると苦い目を見る。

問題リンク

概要

 H \times Wのグリッド状をした板チョコがある。これを切れ目に沿って長方形に3分割したとき、(最大のピースの面積)-(最小のピースの面積)の最小値を求めよ。

制約

  •  2 \leq H, W \leq 10^5

解説

要はチョコを一般的な割り方でできるだけ3等分にしろという問題。

いかにも数学っぽい問題だが、実は数学で解こうとするとパターンが多くて相当苦戦する。というわけでプログラムの力でゴリ押すのが吉となる。

まず最初に、下から hの所で折ってしまうことにする。こうすれば後は (H - h) \times Wの板チョコをできるだけ2等分する問題へ帰着される。2等分になってしまえば問題は簡単で、ほぼ真ん中の位置で縦と横両方で割ってみればいい。

f:id:misteer:20180917091535p:plain

これを全ての hについて全探索すればいいので、計算量は O(H + W)。とても無駄がありそうな計算方法だが、間に合えばそれでいいのだ。 あと板チョコを90度回すのを忘れずに。

実装例

#include <algorithm>
#include <iostream>

using namespace std;
using ll = long long;

int main() {
    ll H, W;
    cin >> H >> W;

    ll ans = H * W;
    ll s[3];
    for (int i = 0; i < 2; ++i) {
        for (ll h = 1; h < H; ++h) {
            // まずは縦割り
            s[0] = h * W;
            s[1] = (H - h) * (W / 2);
            s[2] = H * W - (s[0] + s[1]);
            sort(s, s + 3);
            ans = min(ans, s[2] - s[0]);

            // 次いで横割り
            s[0] = h * W;
            s[1] = ((H - h) / 2) * W;
            s[2] = H * W - (s[0] + s[1]);
            sort(s, s + 3);
            ans = min(ans, s[2] - s[0]);
        }
        // 板チョコを90度回す
        swap(H, W);
    }
    cout << ans << endl;
    return 0;
}

感想

  • いかに数学的思考を捨てられるかが鍵になる。
    • そういう点では制約を見るのも大事。
  •  O(1)解法、いかにもありそうですけどね。