Problem:


Score : 400 points

Problem Statement

We have an undirected graph G with N vertices numbered 1 to N and N edges as follows:

For each i=1,2,...,N-1, there is an edge between Vertex i and Vertex i+1.

There is an edge between Vertex X and Vertex Y.

For each k=1,2,...,N-1, solve the problem below:

Find the number of pairs of integers (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j in G is k.

Constraints

3 \leq N \leq 2 \times 10^3

1 \leq X,Y \leq N

X+1 < Y

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X Y

Output

For each k=1, 2, ..., N-1 in this order, print a line containing the answer to the problem.

Sample Input 1

5 2 4

Sample Output 1

5
4
1
0

The graph in this input is as follows:

There are five pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 1: (1,2)\,,(2,3)\,,(2,4)\,,(3,4)\,,(4,5).

There are four pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 2: (1,3)\,,(1,4)\,,(2,5)\,,(3,5).

There is one pair (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 3: (1,5).

There are no pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 4.

Sample Input 2

3 1 3

Sample Output 2

3
0

The graph in this input is as follows:

Sample Input 3

7 3 7

Sample Output 3

7
8
4
2
0
0

Sample Input 4

10 4 8

Sample Output 4

10
12
10
8
4
1
0
0
0



Sample input:
5 2 4


Sample output:
5
4
1
0

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,X,Y = inputMap()
	g2 = Graph()

	for i in range(N):
		if i == 0:
			continue

		g2.add_edge(i-1, i, 1)
		if i >= X:
			g2.add_edge(i, i-1, 1)

	g2.add_edge(X-1, Y-1, 1)
	#g2.add_edge(Y-1, X-1, 1)

	ans2 = 0
	ans = []
	ansans = [0 for i in range(N)]
	for ii in range(N):
		d2 = Dijkstra(g2, ii)
		for jj in range(N):
			if ii >= jj:
				continue
			tmp2 = d2.shortest_distance(jj)

			if (jj,ii) in ans:
				continue
			#print("{} {}".format(ii+1,jj+1))
			ansans[tmp2] += 1
			ans.append((ii,jj))

	#print(ansans)
	for i in range(1,N):
		print(ansans[i])




#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

def int_sqrt2(n):
    def f(prev):
        while True:
            m = (prev + n / prev) / 2
            if m >= prev:
                return prev
            prev = m

    return f(int(math.sqrt(n) * (1 + 1e-10)))

# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split())
dic = [[0 for i in range(n)]for j in range(n)]
for i in range(n):
    for j in range(i,n):
        dic[i][j] = abs(i-j)
        if i < x and y-1 <= j :
            dic[i][j] = dic[i][x-1]+1+(j-y+1)
        elif i < x and y-1 > j :
            dic[i][j] = min(abs(i-j),(abs(i-(x-1))+1+abs(y-1-j)))
        elif x <= i :
            dic[i][j] = min(abs(i-j),(abs(i-(x-1))+1+abs(y-1-j)))

ans = [0 for i in range(n)]
for i in range(n):
    for j in range(i,n):
        ans[dic[i][j]] += 1
for i in range(1,n):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    n,x,y = map(int,input().split())
    cnt = [0]*(n)
    res = []
    for i in range(n):
        d = [float('inf')]*n
        que = deque([(i, 0)])
        while que:
            idx, c = que.popleft()
            if d[idx]!=float('inf'):
                d[idx] = min(d[idx], c)
                continue
            else:
                d[idx] = min(d[idx], c)
                if idx!=0:
                    que.append((idx-1, c+1))
                if idx!=n-1:
                    que.append((idx+1, c+1))
                if idx==x-1:
                    que.append((y-1, c+1))
                if idx==y-1:
                    que.append((x-1, c+1))
        res.append(d)
    
    for r in res:
        for i in range(n-1):
            cnt[i] += r.count(i)
    for c in cnt[1:]:
        print(c//2)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
# グラフの作成 数字が小さい方から大きい方への有向グラフ
g = [[i-1, i+1] for i in range(N)]
g[0].remove(-1)
g[N-1].remove(N)
g[X-1].append(Y-1)
g[Y-1].append(X-1)
#print(g)

ans_list = [0] * N
# 各頂点からの最短経路長を計算
for i in range(N):
    queue = g[i]
    seen = [False] * N
    length = 0
    while queue:
        length += 1
        #print("now length:", length, queue)
        add = []
        for qi in queue:
            if seen[qi] == False:
                if i < qi:
                    ans_list[length] += 1
                seen[qi] = True
                add += g[qi]
                #print("add,", g[qi])
        queue = list(set(add))
        #print(queue)

# 答えの出力
for k in range(1, N):
    print(ans_list[k])

Submission status: Time Limit Exceeded

Solution code:
N,X,Y=map(int,input().split())
l=[]
for i in range(1,N):
  if i<(X+Y)//2:
    for j in range(i+1,N+1):
      if abs(X-i)+1+abs(Y-j)>j-i:
        l.append(j-i)
      else:
        l.append(abs(X-i)+1+abs(Y-j))
  if i>=(X+Y)//2:
    for j in range(i+1,N+1):
      l.append(j-i)
for i in range(1,N):
  print(l.count(i))

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())

result = []
for i in range(1, N+1):
    for j in range(i, N+1):
        if j<=X:
            result.append(j-i)
        else:
            jy = abs(Y-j)
            ix = abs(X-i)
            if (j-i)<=(jy+ix+1):
                result.append(j-i)
            else:
                result.append(jy+ix+1)
            
for i in range(N-1):
    print(result.count(i+1))

Submission status: Time Limit Exceeded

Solution code:
import queue
n, x, y = map(int, input().split())

lst = [0 for i in range(n)]

for i in range(n-1):
    xx = x-1
    yy = y-1
    q = queue.Queue()
    po = [0 for i in range(n)]
    q.put((i, 0))
    while not q.empty():
        num, leng = q.get()
        if po[num] == 0:
            po[num] = leng
            if i < num and leng < len(lst):
                lst[leng] += 1
            if num < n-1 and po[num+1] == 0:
                q.put((num+1, leng+1))
            if num > xx and po[num-1] == 0:
                q.put((num-1, leng+1))
            if xx == num:
                q.put((yy, leng+1))
for i in range(len(lst)-1):
    print(lst[i+1])

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split())
edge = [[] for _ in range(n+1)]
dist = [[abs(i-j) for i in range(n+1)] for j in range(n+1)]
counter = [0 for i in range(n)]
for i in range(1, n):
    edge[i].append(i+1)
    edge[i+1].append(i)
edge[x].append(y)
edge[y].append(x)
for i in range(y+1):
    for j in range(x, n+1):
        new_dist = abs(x-i)+abs(y-j)+1
        if new_dist < dist[i][j]:
            dist[i][j] = new_dist
            dist[j][i] = new_dist

for i in range(1, n+1):
    for num in dist[i][1:]:
        counter[num] += 1
# print(dist)

for num in counter[1:]:
    print(num//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush
input = sys.stdin.readline
# int(input()) # 入力が1つ
n, x, y = map(int, input().split()) # 入力が複数
graph = [[] for _ in range(n)]

for i in range(n - 1):
    graph[i].append((1, i + 1))
    graph[i + 1].append((1, i))
graph[x - 1].append((1, y - 1))
graph[y - 1].append((1, x - 1))

def dijkstra(graph, n, start):
    inf = float('inf')
    visited = [inf] * n
    visited[start] = 0
    heap = [(0, start)] #(cost, vertex)
    while heap:
        _, vertex = heappop(heap)
        for c, v in graph[vertex]:
            cost = visited[vertex] + c
            if visited[v] > cost:
                visited[v] = cost
                heappush(heap, (cost, v))
    return visited

path = []
for i in range(n):
    visited = dijkstra(graph, n, i)
    path.append(visited)
    
for k in range(1, n):
    ans = 0
    for i in range(len(path)):
        visited = path[i]
        for j in range(i, len(visited)):
            if visited[j] - visited[i] == k:
                ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
import sys
def main():
	input = sys.stdin.readline

	n,x,y = map(int,input().split())

	route = [[0 for _ in range(n)]for _ in range(n)]
	for i in range(n-1):
		route[i][i+1] = 1

	route[x-1][y-1] = 1
	route[y-1][x-1] = 1
	route = tuple(route)
	#res = shortest_path(route, unweighted=False,directed=False)
	res = dijkstra(route, directed=False)

	ans = [0 for _ in range(n)]
	for i in range(n):
		for j in range(i,n):
			ans[int(res[i][j])] += 1

	for i in range(1,n):
		print(ans[i])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from scipy.sparse.csgraph import dijkstra
import numpy as np

NXY = input().split()
N = int(NXY[0])
X = int(NXY[1])
Y = int(NXY[2])

adj_matrix = np.zeros((N,N))
for i in range(N-1):
    adj_matrix[i,i+1] = 1
    adj_matrix[i+1,i] = 1

adj_matrix[X-1,Y-1] = 1
adj_matrix[Y-1,X-1] = 1
result = dijkstra(adj_matrix)
for i in range(1,N):
    print(int(np.count_nonzero(result == i)/2))

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
graph = [set() for _ in range(N)]
graph[X - 1].add(Y - 1)
graph[Y - 1].add(X - 1)
for i in range(N - 1):
    graph[i].add(i + 1)
    graph[i + 1].add(i)


dist = [[10 ** 9] * N for _ in range(N)]
for i in range(N):
    queue = [i]
    seen = {i}
    dist[i][i] = 0
    while queue:
        new = []
        for cur in queue:
            for nei in graph[cur]:
                dist[i][nei] = min(dist[i][nei], dist[i][cur] + 1)
                if nei not in seen:
                    new.append(nei)
                    seen.add(nei)
        queue = new
count = [0] * N
for i in range(N):
    for j in range(i + 1, N):
        count[dist[i][j]] += 1

for c in count[1:]:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

n, x, y = map(int, input().split())

for k in range(1, n):
    cnt = 0
    for i in range(1, n+1-k):
        for j in range(i+k, n+1):
            if i <= x and y <= j:
                d = j - i - (y - x - 1)
            else:
                d = min(j - i, abs(x - i) + 1 + abs(y - j))
            if d == k:
                cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())

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

for i in range(1,N):
    checking = i

    #まずスタート地点から幅優先探索を実装
    queue = [[i,0]]
    # checked = list(range(1,i+1)) #マス、距離
    # checked = [i]

    if i <= X:
        checked = list(range(1,i+1))
    else:
        checked = list(range(1,X))
        checked.append(i)

    while(True):
        now = queue[0]

        #ショートカット確認
        if now[0] == X:
            if Y not in checked:
                queue.append([Y,now[1]+1])
                checked.append(Y)
                if not(checking > Y):
                    ans[now[1]+1] += 1
                    # print(now[0],Y,now[1]+1)

        if now[0] == Y:
            if X not in checked:
                queue.append([X,now[1]+1])
                checked.append(X)
                if not(checking > X):
                    ans[now[1]+1] += 1
                    # print(now[0],X,now[1]+1)

        #左
        if now[0]-1 >= 1 and now[0]-1 not in checked:
            queue.append([now[0]-1,now[1]+1])
            checked.append(now[0]-1)
            if not(checking > now[0]-1):
                ans[now[1]+1] += 1
                # print(now[0],now[0]-1,now[1]+1)

        #右
        if now[0]+1 <= N and now[0]+1 not in checked:
            queue.append([now[0]+1,now[1]+1])
            checked.append(now[0]+1)
            if not(checking > now[0]+1):
                ans[now[1]+1] += 1
                # print(now[0],now[0]+1,now[1]+1)

        queue.pop(0)

        if len(checked) == N or len(queue) == 0:
            break

#回答を出力
for i in range(1,N):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import heapq
def main():
    N, X, Y = map(int, input().split())
    dp = [[float("inf") for i in range(N)] for j in range(N)]
    heap = []
    heapq.heapify(heap)
    for i in range(N - 1):
        dp[i][i + 1] = 1
        dp[i + 1][i] = 1
        heapq.heappush(heap, (1, i, i + 1))
    dp[X - 1][Y - 1] = 1
    dp[Y - 1][X - 1] = 1
    heapq.heappush(heap, (1, X - 1, Y - 1))
    while True:
        if len(heap) == 0:
            break
        else:
            cost, a, b = heapq.heappop(heap)
            # xを動かす
            for i in [-1, 1]:
                if (a + i) < 0 or (a + i) >= N or (a + i) == b:
                    continue
                if dp[a+i][b] != float("inf"):
                    continue

                dp[a + i][b] = (cost + dp[a][a + i])
                dp[b][a + i] = (cost + dp[a][a + i])
                heapq.heappush(heap, (dp[a + i][b], a + i, b))
            for i in [-1, 1]:
                if (b + i) < 0 or (b + i) >= N or (b + i) == a:
                    continue
                if dp[a][b + i] != float("inf"):
                    continue
                dp[a][b + i] = (cost + dp[b][b + i])
                dp[b + i][a] = (cost + dp[b][b + i])
                heapq.heappush(heap, (dp[b + i][a], a, b + i))

    ans = [0 for i in range(N - 1)]
    for i in range(N):
        for j in range(N):
            if dp[i][j] == float("inf"):
                pass
            else:
                ans[dp[i][j] - 1] += 1
    for i in range(N - 1):
        print(ans[i] // 2)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N,X,Y = map(int,input().split())
ToltN=N*(N-1)/2
Dist=[[0 for i in range(N)] for i in range(N)]
for i in range(N):
    for j in range(i,N):
        Dist[i][j] = j-i
for i in range(N):
    for j in range(i,N):
        MyDist=abs(i-(X-1))+abs(j-(Y-1))+1

        if MyDist<Dist[i][j]:
            Dist[i][j]=MyDist
for j in range(N-1):
    ans=0
    for i in range(N):
        ans+=Dist[i].count(j+1)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
data = [[3000]*N for _ in range(N)]
for i in range(N-1):
  data[i][i+1] = 1
  data[i+1][i] = 1
  data[i][i] = 0
data[0][0] = 0
data[X-1][Y-1] = 1
data[Y-1][X-1] = 1
for k in range(N):
  for i in range(N):
    for j in range(N):
      data[i][j] = min(data[i][j],data[i][k]+data[k][j])
for i in range(N-1):
  counter = 0
  for j in range(N):
    counter += data[j].count(i+1)
  print(int(counter//2))

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split())
w = n

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(n-1):
    cost[i][i+1] = 1
    cost[i+1][i] = 1
    
cost[x-1][y-1] = 1
cost[y-1][x-1] = 1

print(n)
for dis in range(2,n) :
  ans = 0
  for s in range(n) :
    ans += dijkstra(s,n,w,cost).count(dis)
  print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())

distance = [[abs(i-j) for j in range(N)] for i in range(N)]
ans = [0] * N

X -= 1
Y -= 1
for i in range(N):
    for j in range(i+1, N):
        # X Y i j
        if Y <= i:
            pass
        # i j X Y
        elif j <= X:
            pass
        # X i Y j
        elif X <= i < Y <= j:
            dis = (i-X) + 1 + (j-Y)
            distance[i][j] = min(distance[i][j], dis)
        # i X j Y
        elif i <= X < j <= Y:
            dis = (X-i) + 1 + (Y-j)
            distance[i][j] = min(distance[i][j], dis)
        # i X Y j
        elif i <= X < Y <= j:
            dis = (X-i) + 1 + (j-Y)
            distance[i][j] = min(distance[i][j], dis)
        # X i j Y
        elif X <= i < j <= Y:
            dis = (i-X) + 1 + (Y-j)
            distance[i][j] = min(distance[i][j], dis)

        ans[distance[i][j]] += 1

for k in range(1, N):
    print(ans[k])

Submission status: Time Limit Exceeded

Solution code:
import sys


n, x, y = map(int, sys.stdin.readline().split())
dist = []
for i in range(n):
    dist.append([])
    for j in range(n):
        dist[i].append(abs(j - i))

dist[x-1][y-1] = 1
def get_dist(a,b):
    if a < b:
        return dist[a][b]
    else:
        return dist[b][a]
x -= 1
y -= 1
# update the x
# first, range (x,y) 
for i in range(x+2, y):
    dist[x][i] = min(dist[x][i], dist[i][y] + 1)
# them, range(y,n)
for i in range(y+1, n):
    dist[x][i] = dist[y][i] + 1
# range[0,x) 
for i in range(x):
    # to (x, y)
    for j in range(x+1, y):
        dist[i][j] = min(dist[i][j], dist[j][y] + dist[i][x] + 1)
    # to [y, n)
    for j in range(y,n):
        dist[i][j] = dist[i][x] + 1 + dist[y][j]

# range(x, y)
for i in range(x+1, y):
    # to (i,y)
    for j in range(i+1, y):
        dist[i][j] = min(dist[i][j], dist[x][i] + dist[j][y] + 1)

    # to [y, n)
    for j in range(y, n):
        dist[i][j] = min(dist[i][j], dist[x][i] + dist[y][j] + 1)
final = [0]*(n-1)
for i in range(n-1):
    for j in range(i+1, n):
        final[dist[i][j]-1] += 1
 
for one in final:
    print(one)

Submission status: Time Limit Exceeded

Solution code:
import pprint
import itertools
import collections
n, x, y = (int(each) for each in input().split(' '))

table1 = [[0] * n for i in range(n)]
table2 = [[0] * n for i in range(n)]
table_shortest = [[0] * n for i in range(n)]
cntr = {}

# 点iから点jまでの距離をテーブルにする

# 抜け道を通らないルートの場合
for i in range(n):
    for j in range(n):
        if j-i > 0:
            table1[i][j] = j-i

# 抜け道を通るルートの場合
for i in range(n):
    for j in range(n):
        if j-i > 0:
            table2[i][j] = abs(j-y+1)+abs(i-x+1)+1

# どちらか近いほうのルートが最短距離
for i in range(n):
    for j in range(n):
        if j-i > 0:
            table_shortest[i][j] = min(table1[i][j], table2[i][j])

# テーブルをflattenして数をかぞえる
cntr = collections.Counter(list(itertools.chain.from_iterable(table_shortest)))

cntr = dict(cntr)
for each in range(1,n):
    print(cntr.get(each, 0))

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())

D = [0] * (N - 1)

for i in range(1, N):
    for j in range(i + 1, N+1):
        K = j - i
        M = abs(X - i) + 1 + abs(Y - j)
        J = abs(Y - i) + 1 + abs(X - j)
        R = min(K, M, J)
        D[R - 1] += 1

for d in D:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

def func(mat, d, n):
    def plus(i, j, d, count):
        if mat[i][j] == 0:
            mat[i][j] = d + 1
            count += 1
        return count

    count = 0
    for i in range(1, n+1-d):
        for j in range(i-1+d, n+1):
            if mat[i][j] == d:
                count = plus(i, j-1, d, count)
                count = plus(i, j+1, d, count)
                count = plus(i-1, j, d, count)
                count = plus(i+1, j, d, count)

    return(count)


def main():
    n, x, y = map(int, input().split())
    mat = [[0 for i in range(n+1)] for j in range(n + 1)]
    for i in range(n+1):
        mat[0][i] = -1
        mat[i][n] = -1
    for i in range(1, n+1):
        mat[i][i-1] = -1
    for i in range(1, n):
        mat[i][i] = 1
    mat[x][y-1] = 1

    print(n)
    for d in range(1, n-1):
        print(func(mat, d, n))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split())
ans = [0] * (n - 1)
x -= 1
y -= 1
for i in range(n-1):
    for j in range(i+1, n):
        d = min(abs(y-i)+abs(y-j), abs(x-i)+abs(x-j), abs(i-j),
                abs(y-i)+abs(x-j)+1, abs(x-i)+abs(y-j)+1) - 1
        if i == x and j == y:
            d = 0
        # print(i, j, d)
        ans[d] += 1
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from scipy.sparse.csgraph import shortest_path
import numpy as np

NXY = input().split()
N = int(NXY[0])
X = int(NXY[1])
Y = int(NXY[2])

adj_matrix = np.zeros((N,N))
for i in range(N-1):
    adj_matrix[i,i+1] = 1
    adj_matrix[i+1,i] = 1

adj_matrix[X-1,Y-1] = 1
adj_matrix[Y-1,X-1] = 1
result = shortest_path(adj_matrix)
for i in range(1,N):
    print(int(np.count_nonzero(result == i)/2))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path

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

l1 = np.linspace(1,1,N-1)
l = np.diag(l1,k=1) + np.diag(l1,k=-1)

l[X-1,Y-1] = 1
l[Y-1,X-1] = 1

spath = shortest_path(l)

for i in range(N-1):
    ans = int(np.count_nonzero(spath==i+1)/2)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split())

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
graph = np.zeros((n,n))
for i in range(n-1):
    graph[i][i+1] = 1
graph[x-1][y-1] = 1
s = floyd_warshall(graph,directed=False)
dst = {}
for i in range(n-1):
    for j in range(i+1,n):
        if not s[i][j] in dst.keys():
            dst[s[i][j]] = int(1)
        else:
            dst[s[i][j]] += int(1)
for i in range(1,n):
    if not i in dst.keys():
        print(0)
    else:
        print(dst[i])

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
import sys
def main():
	input = sys.stdin.readline

	n,x,y = map(int,input().split())

	route = [[0 for _ in range(n)]for _ in range(n)]
	for i in range(n-1):
		route[i][i+1] = 1

	route[x-1][y-1] = 1
	route[y-1][x-1] = 1

	#res = shortest_path(route, unweighted=False,directed=False)
	res = dijkstra(route, directed=False)


	ans = [0 for _ in range(n)]
	for i in range(n):
		for j in range(i,n):
			ans[int(res[i][j])] += 1

	for i in range(1,n):
		print(ans[i])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    #return d
a , b , c = map(int,input().split())

n = a
w = a #n:頂点数　w:辺の数

d = [[float("inf")]*n for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(n-1):
    x = i
    y = i+1
    d[x][y] = 1
    d[y][x] = 1
d[b-1][c-1] = 1
d[c-1][b-1] = 1

for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
    
warshall_floyd(d)

for i in range(1,n):
    ans = 0
    for j in range(n):
        ans += d[j].count(i)
    print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N,X,Y = map(int,input().split())
  d = [[float('inf') for _ in range(N)] for _ in range(N)]
  for i in range(N-1):
    d[i][i+1] = 1
    d[i+1][i] = 1
  d[X-1][Y-1] = 1
  d[Y-1][X-1] = 1
  for i in range(N):
    d[i][i] = 0
  
  for k in range(N):
    for i in range(N):
      for j in range(N):
        d[i][j] = min(d[i][k]+d[k][j],d[i][j])
  #print(d)
  ans = [0 for _ in range(N-1)]
  for i in range(N-1):
    for j in range(i,N):
      if 0 < d[i][j] < N:
        ans[d[i][j]-1] += 1
  for i in range(N-1):
    print(ans[i])

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import deque
    n,x,y = map(int,input().split())
    ans = [0]*(n)
    E = [[] for i in range(n)]
    E[0].append(1)
    E[n-1].append(n-2)
    for i in range(1,n-1):
        E[i].append(i-1)
        E[i].append(i+1)
    E[x-1].append(y-1)
    E[y-1].append(x-1)
    ans = [0]*(n)
    def search(x):
        d = [float("INF")]*n
        d[x] = 0
        q = deque([])
        q.append((x,0))
        while q:
            bef,l = q.pop()

            for nex in E[bef]:
                if d[nex] > l+1:
                    d[nex] = l+1
                    q.append((nex,l+1))
        
        d = d[x:]
        for j in range(n):
            ans[j] += d.count(j)
    for i in range(n-1):
        search(i)

    for i in ans[1:]:
        print(i)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split(' '))

dct = {X : Y}
short = Y - X - 1

dist_list = []

for i in range(1,N):
    for j in range(i+1,N+1):
        if i <= X and j >= Y:
            dist = j - i - short
        elif i <= X and j >= X and j <= Y:
            d1 = X - i + 1 + Y - j
            d2 = j - i
            dist = min(d1,d2)
        elif i >= X and i <= Y and j >= Y:
            d1 = i - X + 1 + j - Y
            d2 = j - i
            dist = min(d1,d2)
        elif i >= X and j <= Y:
            d1 = i - X + 1 + Y - j 
            d2 = j - i
            dist = min(d1,d2)
        else:
            dist = j - i
        dist_list.append(dist)

for k in range(1,N):
    print(dist_list.count(k))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
from collections import Counter

n,x,y=map(int,input().split())

fr,to,w=[],[],[]

for i in range(n-1):
  fr.append(i)
  to.append(i+1)
  w.append(1)

fr.append(x-1)
to.append(y-1)
w.append(1)

g=csr_matrix((w, (fr, to)), shape=(n, n))

ans_l=[]
for i in range(n):
  d=dijkstra(g,indices=i,directed=False)
  for i in d:
    if 1<=i<=10**5:
      ans_l.append(i)


c=Counter(ans_l)
for i in sorted(c.keys()):
  print(c[i]//2)
for i in range(n-1-len(c.keys())):
  print(0)