備忘録
問題
回答
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))
よくわからん。。。