Mister雑記

競プロやります。

AGC004-A 「Divide a Cuboid」 (200)

問題リンク

概要

 1 \times 1 \times 1の立方体が A \times B \times Cの直方体状に並んでいる。 全てのブロックを赤と青の2色で、各色で塗られたブロック全体が直方体となるように塗り分けるとき。

このとき、赤ブロックと青ブロックの個数の差の最小値を求めよ。

概要

  •  1 \leq A, B, C \leq 10^9

解説

2色塗り分けの条件が少しややこしいが、要は「面と平行な平面で直方体を2つに切る」ことと同値である。

例えば B \times Cと平行な平面で2つに切ると、各直方体の体積は k \times B \times C (A - k) \times B \times Cとなる。 これらの差を最小にするにはできるだけ真ん中で切る、つまり k = \lceil A / 2 \rceilとすればいい。

あとはこれを各面でやればいいのだが、そのまま体積を出すとlong longでもオーバーフローしてしまう。そこでもう少しまとめてみる。

まず Aが偶数の場合、上の切断による体積差は0になる。つまり長さが偶数の辺があれば答えは常に0になる。

では全ての辺の長さが奇数の場合を考えよう。上の切断での体積差は計算すれば分かる通り B \times Cとなる。他の面でも同様である。 したがって A, B, Cの小さい方2つについて、その積が答えとなる。 これで全パターンの解が求まった。

実装例

#include <algorithm>
#include <iostream>
using namespace std;
using ll = long long;

int main() {
    ll edge[3];
    bool even = false;
    for (int i = 0; i < 3; ++i) {
        cin >> edge[i];
        if (edge[i] % 2 == 0) even = true;
    }
    sort(edge, edge + 3);
    cout << (even ? 0 : edge[0] * edge[1]) << endl;
    return 0;
}

感想