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, i-1, 1)
		g2.add_edge(i-1, i, 1)

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

	for i in range(1,N):
		if i == 1:
			print(N)
			continue
		if i == N-1:
			print(0)
			continue

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

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





#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# 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())

_list=[]

for i in range(1,n):
    for j in range(i+1,n+1):
        if j<=x:
            tmp=j-i
            
        elif x<i and j<y:
            tmp=min(j-i,(i-x)+1+(y-j))
            
        elif y<=i:
            tmp=j-i

        elif i<=x and y<=j:
            tmp=j-i -(y-x-1)

        elif i<=x and x<j and j<y:
            tmp=min(j-i,(x-i)+1+(y-j))
        elif x<i and i<y and y<=j:
            tmp=min(j-i,(i-x)+1+(j-y))

        _list.append(tmp)

for k in range(1,n):
    print(_list.count(k))

Submission status: Time Limit Exceeded

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall

N, X, Y = input_int()

null_value = 10**4
edge = []
for i in range(N):
    temp = [float("inf") for j in range(N)]  
    
    #あれば一つ次
    if i+1 < N :
        temp[i+1]=1
    
    #あれば一つ前
    if i-1 >= 0:
        temp[i-1]=1
    
    if i==X-1:
        temp[Y-1]=1
    elif i==Y-1:
        temp[X-1]=1
    edge.append(temp)
G = csgraph_from_dense(edge, null_value=null_value)

edge_q = floyd_warshall(G)


dicts = {i:0 for i in range(N)}

for i in range(N):
    for j in range(i+1,N):
        if edge_q[i][j]<N:
            dicts[int(edge_q[i][j])] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

d = {i:set() for i in range(N)}
for i in range(0,N):
  if i-1>=0:
    d[i-1].add(i)
  if i+1<=N-1:
    d[i+1].add(i)
  if i==X:
    d[Y].add(X)
    d[X].add(Y)

ans = {i+1:0 for i in range(N-1)}


for i in range(0,N):
  dist = [-1]*N
  q = deque([i])
  dist[i] = 0
  while q:
    v = q.popleft()
    for j in d[v]:
      if dist[v] + 1 < dist[j] or dist[j]==-1:
        dist[j] = dist[v] + 1
        q.appendleft(j)
  for k in dist:
    if k in ans:
      ans[k] += 1

for l in ans.values():
  print(l//2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import itertools
n,x,y = map(int,input().split())
dist = [[0 for i in range(n)] for i in range(n)]
for i in range(n):
  if i == 0:
    dist[i][i+1] = 1
  elif i == n - 1:
    dist[i][n-1] = 1
  else:
    dist[i][i+1] = 1
    dist[i][i - 1] = 1
dist[x-1][y-1] = 1
dist[y - 1][x-1] = 1
dist = np.array(dist)
kyori = shortest_path(dist,directed = False)
kyori = kyori.tolist()
kyori = list(itertools.chain.from_iterable(kyori))
kyori = list(map(int, kyori))

for i in range(1,n):
  print(kyori.count(i)//2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

n,x,y = map(int,input().split())
graph = [[0 for i in range(n)]for j in range(n)]

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

ans = shortest_path(np.array(graph))
u= np.unique(ans)

for i in range(1,n):
    if i in u:
        print(int(np.count_nonzero(ans == i)/2))
    else:print(0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def solve(n,x,y):
  matrix = np.full((n,n), -1)
  x = x-1
  y = y-1
  for i in range(n):
    for j in range(i+1, n):
      if j >= x:
        matrix[i][j] = min(j-i, np.abs(j-y)+np.abs(x-i)+1)
      else:
        matrix[i][j] = j-i

  for i in range(1,n):
    print(np.count_nonzero(matrix==i))

if __name__ == "__main__":
  _n, _x, _y = map(int, input().split())
  solve(_n,_x,_y)

Submission status: Time Limit Exceeded

Solution code:
def all_pair(W):
    n = len(W)
    res = [[0] * n for i in range(n)]
    for i in range(n):
        for j in range(i,n):
            if i == j:
                val = 0
            elif W[i][j]:
                val = W[i][j]
            else:
                val = 10**10
            res[i][j] = res[j][i] = val
    for k in range(n):
        for u in range(n):
            for v in range(n):
                res[u][v] = min(res[u][v], res[u][k] + res[k][v])
    return res


n,x,y=map(int, input().split(' '))
W = [[0]*n for i in range(n)]
W[x-1][y-1] = W[y-1][x-1] = 1
for i in range(n-1):
    W[i][i+1] = 1
my_graph = all_pair(W)
for i in range(1, n):
    res = 0
    for j in my_graph:
        res += j.count(i)
    print(res//2)

Submission status: Time Limit Exceeded

Solution code:
#import numpy

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

L=[[i+1 for i in range(j+1)][::-1]+[0]*(N-1-j) for j in range(N-1)]
#print(L)

for i in range(len(L)):
    L[i]=[0]+L[i]+[0]
L.append([0]*(N+2))
L.insert(0,[0]*(N+2))
L.insert(0,[0]*(N+2))

#print(L)

H=[i+1 for i in range(N-1)][::-1]
#print(L)
#print(H)

L[Y][X]=1
task=[(Y,X,1)]
while len(task)>0:
    P=task.pop()
    y,x,c=P[0],P[1],P[2]
    if y<0 or x<0 or y>N or x>N:
        continue
    if L[y+1][x]>=c+1:
        L[y+1][x]=c+1
        task.append((y+1,x,c+1))
    if L[y-1][x]>=c+1:
        L[y-1][x]=c+1
        task.append((y-1,x,c+1))
    if L[y][x+1]>=c+1:
        L[y][x+1]=c+1
        task.append((y,x+1,c+1))
    if L[y][x-1]>=c+1:
        L[y][x-1]=c+1
        task.append((y,x-1,c+1))
    #print(y,x,c)
    #print(numpy.array(L))

LL=[]
for i in range(len(L)):
    LL+=L[i]
#LL.sort()
#print(LL)

import collections
D=collections.Counter(LL)
d=list(D.values())
d.pop(0)
d+=[0]*(max(N-len(d)-1,0))

for i in d:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n,x,y = (int(x) for x in input().split())
x-=1
y-=1
middle=(y+x)/2
list=[[0 for i in range(n)]for j in range(n)]
for i in range(n-1):
    for j in range(i+1,n):
        if i<=x and j<=x:
            list[i][j] = j-i
        elif j==middle:
            list[i][j] = j-i
        elif i==middle:
            list[i][j] = j-i
        elif i<=x and j>=x and j<=middle:
            list[i][j] = j-i
        elif i<=x and j>=middle and j<=y:
            list[i][j] = (x-i) + 1 + (y-j)
        elif i<=x and j>=middle and j>=y:
            list[i][j] = (x-i) + 1 + (j-y)
        elif i>=x and i<=middle and j<=middle:
            list[i][j] = j-i
        elif i>=x and i<=middle and j>=middle and j<=y:
            list[i][j] = min(j-i, i-x+y-j+1)
        elif i>=x and i<=middle and j>=y:
            list[i][j] = i-x + j-y + 1
        elif i>=middle and j<=y:
            list[i][j] = j-i
        elif i>=middle and j>=y:
            list[i][j] = j-i
        elif i>=y and j>=y:
            list[i][j] = j-i
dic={}
for i in range(n-1):
    for j in range(i+1,n):
        if list[i][j] not in dic:
            dic[list[i][j]]=1
        else:
            dic[list[i][j]]+=1
for i in range(1,n):
    if i not in dic:
        print(0)
    else:
        print(dic[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

graph = [[] for _ in range(N)]

for i in range(N - 1):
    graph[i].append(i + 1)
    graph[i + 1].append(i)

graph[X - 1].append(Y - 1)
graph[Y - 1].append(X - 1)

# print(graph)


def bfs(s):
    q = deque([])
    q.append(s)
    dist[s][s] = 0

    while q:
        x = q.popleft()

        for nx in graph[x]:
            if dist[s][nx] != 0:
                continue
            else:
                dist[s][nx] = dist[s][x] + 1
                q.append(nx)


inf = 10 ** 9

dist = [[0] * N for _ in range(N)]

dist_lis = [0] * N

for i in range(N):
    bfs(i)

for i in range(N):
    for j in range(i + 1, N):
        dist_lis[dist[i][j]] += 1

# print(dist)
# print(dist_lis)

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

Submission status: Time Limit Exceeded

Solution code:
def distanced_nodes(neighbor, start_node, depth_limit):
    visited = [start_node]
    next_nodes = neighbor[start_node]
    depth = 1
    while len(next_nodes) > 0 and depth < depth_limit:
        depth += 1
        queue = next_nodes[:]
        visited += next_nodes
        next_nodes = []
        for q in queue:
            for node in neighbor[q]:
                if node in visited:
                    continue
                else:
                    next_nodes.append(node)
        next_nodes = list(set(next_nodes))
    return next_nodes

N, X, Y = list(map(int, input().split()))
neighbor = { i+1: [] for i in range(N) }
for i in range(1,N):
    neighbor[i].append(i+1)
    neighbor[N-i+1].append(N-i)
neighbor[X].append(Y)
neighbor[Y].append(X)

for i in range(1,N):
    pairs = set()
    for j in range(1,N+1):
        for node in distanced_nodes(neighbor, j, i):
            if node > j:
                pairs.add((j, node))
            else:
                pairs.add((node, j))
    print(len(pairs))

Submission status: Time Limit Exceeded

Solution code:
#n=int(input())
n,x,y=map(int,input().split())
#l=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

adjl=[[0 for i in range(n)] for j in range(n)]

dic={}

for i in range(n):
    for j in range(i,n):
        #if i>=j:
        #    continue
        dis=j-i
        maybe=abs(x-(i+1))+1+abs(y-(j+1))
        dis=min(dis,maybe)
        adjl[i][j]=dis

for i in range(n):
    for j in range(i,n):
        #if i>=j:
        #    continue
        dis=adjl[i][j]
        dic[dis]=dic.get(dis,0)+1
for k in range(1,n):
    print(dic.get(k,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, i-1, 1)
		g2.add_edge(i-1, i, 1)

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

	for i in range(1,N):
		if i == 1:
			print(N)
			continue
		if i == N-1:
			print(0)
			continue

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

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





#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# 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:
# D
import numpy as np
N, X, Y = map(int, input().split())

X = X - 1
Y = Y - 1

x = np.zeros((N,N))
for i in range(N):
    x[i,i:] = np.array(range(N-i))
y = np.zeros((N,N))
for i in range(0, N):
    for j in range(i+1, N):
        y[i, j] = abs(i-X) + abs(j-Y) + 1

ans = np.minimum(x, y)

for i in range(1,N):
    print(np.sum(ans==i))

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import numpy as np
    from scipy.sparse.csgraph import shortest_path
    from scipy.sparse import csr_matrix
    n, x, y = map(int, input().split())
    netw = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if abs(j-i) == 1:
                netw[i][j] = 1
    netw[x-1][y-1] = 1
    netw[y-1][x-1] = 1
    netw = np.array(netw)
    ans = {}
    a = shortest_path(netw)
    for i in range(n-1):
        for j in range(i+1, n):
            if a[i][j] in ans:
                ans[a[i][j]] += 1
            else:
                ans[a[i][j]] = 1
    for i in range(1, n):
        if i in ans:
            continue
        else:
            ans[i] =0
    for i in range(1, n):
        print(ans[i])
resolve()

Submission status: Time Limit Exceeded

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

list_in = list(map(int, input().split()))
N = list_in[0]
X = list_in[1]
Y = list_in[2]

graph_arr = np.zeros((N,N), dtype=np.int)

for i in range(N-1):
    graph_arr[i, i + 1] = 1
    graph_arr[i+1, i ] = 1

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

result = np.triu(shortest_path(graph_arr))
for i in range(1, N):
    num_path = np.count_nonzero(result == i)
    print(num_path)

Submission status: Time Limit Exceeded

Solution code:
N,X,Y=map(int,input().split())
Es=[(i,i+1) for i in range(N-1)]
Es.append((X-1,Y-1)) 
for i in range(len(Es)):
    aa,bb=Es[i]
    Es.append((bb,aa))
#print(Es)
c=[[N+1 for _ in range(N)]for _ in range(N)]
#print(c)
for each in Es:
    f,t=each
    c[f][t]=1

COST=tuple(c)
D=tuple([N+1 for _ in range(N)])
USED=tuple([False for _ in range(N)])
ans=[]
for i in range(N):
    cost= list(COST)
    d=list(D)
    used=list(USED)
    d[i]=0
    while True:
        v=-1
        for u in range(N):
            if not used[u] and ( v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(N):
            d[u] = min(d[u],d[v]+cost[v][u])
    #print(d)
    ans+=d[i:]
#print(ans)
for i in range(N-1):
    print(ans.count(i+1))

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
l=[]
r_append = l.append
for i in range(n-1):
  for k in range (i+1,n):
    if k<x-1 or i>y-1:
      r_append(k-i)
    else:
      r_append(min(abs(x-1-i)+abs(y-1-k)+1,k-i))
for i in range(1,n):
  print(l.count(i))

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, i-1, 1)
		g2.add_edge(i-1, i, 1)

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

	for i in range(1,N):
		if i == 1:
			print(N)
			continue

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

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





#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# 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()