D - Line++

ABC160のD問題。

https://atcoder.jp/contests/abc160/tasks/abc160_d

これはしっかりしたbfsで問題を解ける。回答に乗っている方法はちょっとむずかしい。

最短経路問題と捉える事もできそう。

import collections


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

    inf = 10 ** 9
    # 配列の0つき初期化はこう書ける
    ans = [0]*N

    # bfsはだいたいこんなpushがある
    # vは次の頂点、dはその頂点までの距離、distは各頂点までの距離を入れる
    # qには次の頂点が入る
    # 操作中の頂点はコードにはない（陽に持たない）
    def push(v, d, dist, q):
        if dist[v] == inf:
            dist[v] = d
            q.append(v)

    for i in range(N):
        q = collections.deque()
        dist = [inf]*N
        push(i, 0, dist, q)

        while(len(q)):
            v = q.popleft()
            d = dist[v]
            if v < N-1:
                push(v+1, d+1, dist, q)
            if 0 < v:
                push(v-1, d+1, dist, q)
            if v == X-1:
                push(Y-1, d+1, dist, q)
            if v == Y-1:
                push(X-1, d+1, dist, q)

        for i in range(N):
            ans[dist[i]] += 1

    # 往復しているので半分にする
    for i in range(1, N):
        print(ans[i]//2)


if __name__ == "__main__":  
    solve()

Menu