筆者はレート800前後の茶～緑コーダ
ABC462のE問題を解いていく
実装コード
座標の符号と大小をそろえ、対称な経路をまとめて最小コストを計算する。
-
solveの先頭でA, BとX, Yをそれぞれ小さい順に並べ替える - これにより、座標の符号や軸の入れ替えによる対称なケースを共通の式で扱う
-
2 * A * Yは、安い移動を使って目的地へ向かう場合のコストを表す - もう一方の式では、両方の移動を使う部分と、残りの距離を進む部分に分けてコストを求める
-
solveではこの2通りの小さい方を返す -
X + Yが偶数なら、そのままsolve(A, B, X, Y)を答えにする - 奇数なら到達可能な偶奇に合わせるため、
XまたはYを1だけ減らした2通りを試し、最後の1移動分を足して最小値を出力する
main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)
def solve(A, B, X, Y):
if A > B:
A, B = B, A
if X > Y:
X, Y = Y, X
return min(2 * A * Y, A * (X + Y) + (B - A) * (Y - X) // 2)
def main():
T = rI()
for _ in range(T):
A, B, X, Y = rLI()
X, Y = abs(X), abs(Y)
if (X + Y) % 2 == 1:
ans = min(solve(A, B, X - 1, Y) + A, solve(A, B, X, Y - 1) + B)
else:
ans = solve(A, B, X, Y)
print(ans)
if __name__ == '__main__':
main()
感想
解の対称性を利用して場合分けを減らす考え方が参考になった。
座標の符号や大小を先にそろえると、式をかなり簡潔にできると感じた。