ARC041 A - Table Tennis Training
備忘録
問題
回答
import sys import os import math import bisect import itertools import collections import heapq import queue import array import time # 時々使う # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # from decimal import Decimal # 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 INF = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N, A, B = il() if abs(A-B) % 2 == 0: print(abs(A-B)//2) else: print(min(A-1, N-B) + 1 + abs(A-B)//2) if __name__ == '__main__': main()
考え方
まず、どのような移動が最適か考えます。
お互いに試合をするためには、同じ台に移動する必要があります。
そのため、お互いに近づくように、常にA
はB
の方向へ、B
はA
の方向へ移動することが最速です。
しかし、A
とB
の距離が奇数の場合、どこかですれ違いが発生するため、
距離を偶数にしてから互いに近づく必要があります。
互いの距離を変えるためには、どちらかが同じ位置にとどまる必要があります。
位置を変えずにとどまるためには、卓1で勝つか卓Nで負ける必要があります。
そのため、「A
が勝ち続けるまたはB
が負け続ける(min(A-1, N-B)
)」あとに「一度その場でとどまり(+ 1
)」、
最後に「お互いに近づく(abs(A-B)//2)
)」必要があります。