AtCoder Beginner Contest 160 D – Line++ をPython3で解く

# AtCoder Beginner Contest 160 D - Line++
# https://atcoder.jp/contests/abc160/tasks/abc160_d
# tag: グラフ BFS 距離 最短距離 数え上げ

# 最初に思いついたのは、それぞれの開始地点から、BFSで全探索。
# 制約 (3 <= N <= 2000) で、O(N^2) なのでちゃんと間に合う。
# Pypyなら230msくらいで余裕。Python提出でも1300msくらい。
# あまり何も考えずに書けるので、まあこれでもいいのでは？……という感じ。

from collections import deque
def main():
    # 内部的には 0-indexed にしておく
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    # グラフ構築
    paths = [[] for _ in range(N)]
    for i in range(N-1):
        paths[i].append(i+1)
        paths[i+1].append(i)
    paths[X].append(Y)
    paths[Y].append(X)

    # 最短距離ごとの組み合わせ数を探索の際に数えていく
    # result[x]: 最短距離 x の組み合わせ数
    result = [0] * N

    # 開始地点 (1 ～ N) を全部試す
    for start in range(N):
        dist = [-1] * N
        dist[start] = 0
        queue = deque([start])

        # いつものBFS
        while queue:
            now = queue.popleft()
            for nxt in paths[now]:
                if dist[nxt] != -1:
                    continue
                dist[nxt] = dist[now] + 1
                queue.append(nxt)

                # 距離が確定した際、result で数えておく
                result[dist[nxt]] += 1

    # 往復で数えているので、2 で割って出力
    for r in result[1:]:
        print(r//2)

# main()

# 公式解説のやり方は、開始地点と終了地点を定めての全探索。
# 距離については、経路(X-Y) を通る場合と通らない場合で
# 分けてやると、O(1) で計算できる。
# さっきのやり方は往復で見てしまっている分無駄があるので、
# こちらのほうが速い。
# 実際に（最大効率で書けば）大体半分の実行時間になるのが、
# ちょっと面白い（当たり前ではあるが）。

def main2():
    N, X, Y = map(int, input().split())

    # ここでは、関数を分けて少し分かりやすく書いている
    def get_dist(a, b):
        # a -> b 直行
        d1 = abs(a - b)

        # a -> X -> Y -> b
        d2 = abs(a - X) + 1 + abs(b - Y)

        # a -> Y -> X -> b
        d3 = abs(a - Y) + 1 + abs(b - X)

        # 経路は上記のどれかになるので、最小のものを返す
        return min(d1, d2, d3)

    result = [0] * N

    for start in range(1, N):
        for goal in range(start+1, N+1):
            result[get_dist(start, goal)] += 1

    for r in result[1:]:
        print(r)

# main2()