AGC004 A - Divide a Cuboid

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import numpy as np
from numpy import linalg as LA

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    ABC = il()
    ABC.sort()
    if ABC[0] % 2 == 0 or ABC[1] % 2 == 0 or ABC[2] % 2 == 0:
        print(0)
    else:
        C = ABC[-1] - (ABC[-1] // 2)
        print(abs((C * ABC[0] * ABC[1]) - ((ABC[-1] // 2) * ABC[0] * ABC[1])))


if __name__ == '__main__':
    main()

考え方

まず、A, B, Cいずれかに偶数が存在している場合について考えます。
偶数が存在している場合には、偶数の1辺を等分して赤色と青色を塗ることで、青と赤を均等に同じ数だけ作ることが出来ます。

次に、A, B, Cすべてが奇数の場合について考えます。
A, B, Cの全てが奇数の場合には、最も大きい数の1辺を等分するのが最適です。
等分する1辺が小さければ小さいほど、他の辺が大きいため差が大きく開いてしまいます。
そのため、A, B, Cのうち最も大きい辺を等分したのち、等分した辺で面積の差分を求めることで回答できます。