ABC062 C - Chocolate Bar

備忘録

問題

atcoder.jp

回答

import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

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

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

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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

    H, W = il()
    if W % 3 == 0:
        print(0)
    elif H % 3 == 0:
        print(0)
    else:
        ret = MAX
        for h in range(1, H):
            # 横, 横, 横 分割パターン
            hh = (H - h) // 2
            hmin = min(hh * W, (H - h - hh) * W, h * W)
            hmax = max(hh * W, (H - h - hh) * W, h * W)

            # 横, 縦, 縦 分割パターン
            ww = W // 2
            wmin = min((H - h) * (W - ww), (H - h) * ww, h * W)
            wmax = max((H - h) * (W - ww), (H - h) * ww, h * W)

            ret = min(ret, abs(hmax - hmin), abs(wmax - wmin))

        for w in range(1, W):
            # 縦, 縦, 縦 分割パターン
            ww = (W - w) // 2
            wmin = min(w * H, (W - w - ww) * H, ww * H)
            wmax = max(w * H, (W - w - ww) * H, ww * H)

            # 縦, 横, 横 分割パターン
            hh = H // 2
            hmin = min(w * H, hh * (W - w), (H - hh) * (W - w))
            hmax = max(w * H, hh * (W - w), (H - hh) * (W - w))

            ret = min(ret, abs(hmax - hmin), abs(wmax - wmin))

        print(ret)


if __name__ == '__main__':
    main()

考え方

1つの面積を3分割し、最大と最小の差を求める問題。
単純に起こり得る分割を全探索し、回答した。

まず、WまたはHが3の倍数の時は、
均等に3分割できるため、差分は0となる。
そのため、それ以外のパターンを考える。

均等に3分割できないときの分割方法は4パターン起こり得る。
高さを基準にしたときは、
縦に2本線を入れて3分割するパターン、縦に1本線を入れ、残りを横に分割するパターンの2つ。
横を基準にしたときは、
横に2本線を入れて3分割するパターン、横に1本線を入れてから、残りを縦に分割するパターンの2つ。
それぞれ、全てのパターンを全探索し、回答した。
計算量はO(W * H)で最大10^5 * 2


他の方で提出しているO(1)の回答

h,w=map(int,input().split())
pattern=[h//2+w//3+1,h//3+w//2+1,h,w]
if h%3==0 or w%3==0:
    pattern+=[0]
if h%2==0:
    pattern+=[h//2]
if w%2==0:
    pattern+=[w//2]
print(min(pattern))

よくわからん。。。