ABC160 D - Line++

AtCoder Python3

備忘録

問題

atcoder.jp

回答

import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, 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()
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]


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

    N, X, Y = il()
    ret = [0] * (N - 1)
    X -= 1
    Y -= 1
    for i in range(N - 1):
        for j in range(i + 1, N):
            k = min(abs(i - j), abs(X - i) + abs(Y - j) + 1, abs(Y - i) + abs(X - j) + 1)
            ret[k - 1] += 1

    print(*ret, sep="\n")


if __name__ == '__main__':
    main()

考え方

全通りのi, jに対して、

  • 愚直に iからjまで進むパターン（abs(i - j)）
  • X, Yを経由して、iからjまで進むパターン
    （abs(X - i) + abs(Y - j) + 1, abs(Y - i) + abs(X - j) + 1)

を試して、最短距離で到達できる方を採用する。

愚直にiからjまで進むパターンでは、
1ずつ加算される整数列からiおよびjを選択する。
そのため、単純な引き算(abs(i-j))が2点の距離となる。

X, Yを経由するパターンでは、

  • iとXまでの距離(abs(X-i))
  • jとYまでの距離(abs(Y-j))
  • XとYの距離(1)

をすべて足すことで求めることが出来る。