AtCoder AGC 004 A - Divide a Cuboid (茶色, 200 点)

割と難しい気がする。数学センスが少し必要な感じ

問題へのリンク

問題概要

のブロックが の直方体状に並んでいます。 高橋君は各ブロックを赤色または青色で塗ろうとしています。 このとき、次の条件が成り立つようにします。

• 赤いブロックも青いブロックもそれぞれ 1 個以上ある
• 赤いブロック全体が 1 つの直方体状になっている
• 青いブロック全体が 1 つの直方体状になっている。

高橋君は、赤いブロックの個数と青いブロックの個数の差をできるだけ小さくしたいと思っています。 赤いブロックの個数と青いブロックの個数の差の最小値を求めてください。

制約

• 

考えたこと

まず、問題の意味を一瞬で把握するためには、それなりの数学慣れが必要な気がする。一瞬何を問われてるのかわからなくなってしまった方も多い気がする。

「赤いブロックが全体で 1 つの長方形状」で「青いブロックが全体で 1 つの長方形状」というのは、要するにこういう状態

この 3 パターンがありうる。つまり、

• とわけて、 と というパターン
• とわけて、 と というパターン
• とわけて、 と というパターン

とがある。ここまで整理できれば、後は見えて来る。この 3 パターンについて「赤と青の体積差の最小値」を求めて、そのうちの最小値をとればよいということになる。

簡単のため、1 番目の場合を考える。

• が偶数のとき、 にできるので体積差の最小値は 0
• が奇数のとき、 と の差を 1 にするのが最小で体積差の最小値は

ということになる。これを 2 番目と 3 番目についてもやればよい。

さらに

さらに整理すると、こうなる

• のいずれかが偶数なら答えは 0
• のすべてが奇数なら、 のうち一番小さいものが答え

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    long long A, B, C; cin >> A >> B >> C;
    if (A % 2 == 0 || B % 2 == 0 || C % 2 == 0) cout << 0 << endl;
    else cout << min({A*B, B*C, C*A}) << endl;
}