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 numpy as np
from scipy.sparse.csgraph import floyd_warshall
# from pprint import pprint
INF = 2 ** 63 - 1

N, X, Y = map(int, input().split(' '))
ad_table = []

for i in range(N):
    tmp = [INF for _ in range(N)]
    tmp[i] = 0
    if i != 0:
        tmp[i-1] = 1
    if i != N - 1:
        tmp[i+1] = 1
    ad_table.append(tmp)
ad_table[X-1][Y-1] = 1
ad_table[Y-1][X-1] = 1

cost_table = floyd_warshall(ad_table)
# pprint(ad_table)
# print(cost_table)
# print(cost_table == np.float64(i+1))

for i in range(N):
    if i+1 == N:
        break
    ans = 0
    for j in range(N):
        ans += sum(cost_table[j][j:] == np.float64(i+1))
    print(ans)

Submission status: Time Limit Exceeded

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

knum = [0]*(n-1);
d = [[0]*(n) for i in range(n)];

for i in range(n) :
    for j in range(i+1,n) :
        d[i][j] = j - i;
        d[j][i] = j - i;

d[x-1][y-1] = 1;
d[y-1][x-1] = 1;

for i in range(n) :
    for j in range(i+1,n) :
        mind = min(d[i][j],d[i][x-1]+1+d[y-1][j],d[i][y-1]+1+d[x-1][j]);
        d[i][j] = mind;
        d[j][i] = mind;

for i in range(n) :
    for j in range(i+1,n) :
        knum[d[i][j]-1] += 1;

for i in range(n-1) :
    print(knum[i]);

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

#隣接リストの整備
route_list = np.zeros((N,N))
route_list[0][1] = 1
for i in range(1,N-1):
    route_list[i][i-1] = 1
    route_list[i][i+1] = 1
route_list[-1][-2] = 1
route_list[X-1][Y-1] = 1
route_list[Y-1][X-1] = 1

shortest = shortest_path(route_list,directed=False)

for i in range(1,N):
    print(np.count_nonzero(shortest == i)//2)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix_2
# CreatedDate:  2020-02-21 20:39:32 +0900
# LastModified: 2020-03-28 22:16:59 +0900
#

from collections import Counter
import heapq
def flatten_2dim(array):
    return [item for sublist in array for item in sublist]
def initial_signal(i,adj,N):
    d = [float("inf") for _ in range(N)]
    d[i] = 0
    Q = [(0,i)]
    return d,Q

def relax(n_cost, u, v, adj,d,Q):
    if d[v] > d[u]+n_cost:
        d[v]=d[u]+n_cost
        heapq.heappush(Q,(d[v],v))



def dijkstra(i,adj,N):
    d,Q = initial_signal(i,adj,N)
    while Q:
        cost, u = heapq.heappop(Q)
        for n_cost, v in adj[u]:
            relax(n_cost, u, v, adj, d, Q)
        
    return d



def main():
    N, X, Y = map(int, input().split())
    adj = [[] for _ in range(N)]
    for i in range(1,N):
        adj[i].append((1,i-1))
        adj[i-1].append((1,i))
    adj[X-1].append((1,Y-1))
    adj[Y-1].append((1,X-1))
#    print(adj)
#    return 
    shortest = []
    for i in range(N):
        shortest.append(dijkstra(i,adj,N))
#    print(shortest)
#    return
    c = Counter(flatten_2dim(shortest))
#    print(c)
#    return 
    print(N)
    for i in range(2,N-1):
        print(c[i]//2)
    print(0)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:



def main():
    import numpy as np
    N, X, Y = map(int, input().split())

    path_len = Y-X
    G = [0]*N
    for i in range(N):
        if i == 0:
            G[0] = [1]
        elif i == N-1:
            G[N-1] = [N-2]
        else:
            G[i] = [i-1, i+1]
        if i+1 == X:
            G[i].append(Y-1)
        if i+1 == Y:
            G[i].append(X-1)
    # print(G)
    D =[0]*N
    for j,g in enumerate(G):
        D[j] = [1 if i in g else np.inf for i in range(N)]
    
    # from pprint import pprint 
    # pprint(D)
    D =np.array(D)

    # D=[[0]*N]*N
    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])
    # pprint(D)

    for i in range(1,N):
        tmp = (D==i).sum()
        if i ==2:
            tmp = tmp - N
        
        print(tmp//2)
    

if __name__ == '__main__':
    main()

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())
g = np.zeros((n,n))+float("inf")
for i in range(n-1):
  g[i,i] = 0
  g[i,i+1] = 1
  g[i+1,i] = 1
g[-1,-1] = 0
g[x-1,y-1] = 1
g[y-1,x-1] = 1
g = shortest_path(g)
g = np.tril(g)
g = g[g>0]
for i in range(1,n):
  print(np.count_nonzero(g==i))

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]

for k in range(n):
    for i in range(n-1):
        for j in range(i+1, n):
            dist[i][j] = min(dist[i][j], get_dist(i, k) + get_dist(k, j))

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:
n, x, y = list(map(int, input().split()))
d = [[] for _ in range(n)]
dt = [] 

for i in range(1, n):
    t = (i, i+1)
    d[1].append(t)
    dt.append(t)
d[1].append((x,y))
dt.append((x,y))

for k in range(2, n):
    for a in d[1]:
        for b in d[k-1]:
            if a == b: break
            if a[0] == b[0]:
                t = (a[1], b[1]) if a[1] < b[1] else (b[1], a[1])
            elif a[0] == b[1]:
                t = (a[1], b[0]) if a[1] < b[0] else (b[0], a[1])
            elif a[1] == b[0]:
                t = (a[0], b[1]) if a[0] < b[1] else (b[1], a[0])
            elif a[1] == b[1]:
                t = (a[0], b[0]) if a[0] < b[0] else (b[0], a[0])
            if t not in dt:
                d[k].append(t)
                dt.append(t)
for di in d[1:]:
    print(len(di))

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np

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

# print(n, x, y)

g = [[0] * n for i in range(n)]

# print(g)

for i in range(n):
  for j in range(i+1, n):
    if j != y-1:
      g[i][j] = g[i][j-1] + 1
    elif i < x:
      g[i][j] = g[i][x-1] + 1
    else: 
      g[i][j] = min((g[i][j-1] + 1), i+1-x + 1)

# print(g)

for i in range(n):
  for j in range(n-1, i+1, -1):
    if g[i][j] + 1 < g[i][j-1]:
      g[i][j-1] = g[i][j] + 1

# print(g)

gn = np.array(g)

# print(gn)

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

Submission status: Time Limit Exceeded

Solution code:
[N,X,Y] = [int(s) for s in input().rstrip().split(' ')]
L = [] #L[i][j]はi,j間の最短距離(i<=j)
for i in range(N):
  L.append([10**4 for j in range(N-i)])
for i in range(N):
  L[i][0] = 0
  if i < N-1:
    L[i][1] = 1
L[X-1][Y-X] = 1
for k in range(1,N):
  a = 0
  for i in range(N):
    for j in range(N-i):
      if L[i][j] == k:
        a += 1
      elif L[i][j] > k:
        for p in range(N):
          if p < i:
            if L[p][i-p] + L[p][i+j-p] < L[i][j]:
              L[i][j] = L[p][i-p] + L[p][i+j-p]
          elif p < i+j:
            if L[i][p-i] + L[p][i+j-p] < L[i][j]:
              L[i][j] = L[i][p-i] + L[p][i+j-p]
          else:
            if L[i][p-i] + L[i+j][p-i-j] < L[i][j]:
              L[i][j] = L[i][p-i] + L[i+j][p-i-j]
  print(a)

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split())
r = y-x+1
for k in range(1,n):
  ans = 0
  left=right=circle = 0
  for i in range(1,n+1):
    #left
    if i < x:
      if i + k <= x:#円に届かない
        left += 1
        continue
      elif r/2 == k- (x-i):
        left += 1
      elif r/2 > k - (x-i):
        left += 2
      if (x-i)+1 < k and k - (x-i)-1 - (n-y) <= 0:
        left += 1
  #right
    elif i >= y:
      if i + k <= n:
        right += 1
      if i == y:
        continue
      if r / 2 == k-(i-y):
        right += 1
      elif r / 2 > k-(i-y)>0:
      #if  k - (i- y)> 0 and (k-(i-y))< r//2:
        right += 2
  #circle
  if r /2 == k:
    circle = r//2
  elif r/2 > k:
    circle = r
  print(left+right+circle)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, deque

class BellmanFord():
    def __init__(self, N):
        self.N = N
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        :param s: 始点
        :return: d[i] 始点sから各点iまでの最短経路
        """
        d = [float('inf') for i in range(self.N)]
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_bool(self, start, numNodes):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = [float('inf') for i in range(self.N)]
        d[start] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i == numNodes-1:
                        return True, d
        return False, d
      
n, x, y = [int(i) for i in input().split()]

bf = BellmanFord(n)

for i in range(n-1):
  bf.add(i, i+1, 1)
bf.add(x-1, y-1, 1)

d = deque([])
for i in range(n):
  d += deque(bf.BellmanFord_search(i))

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

Submission status: Time Limit Exceeded

Solution code:
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

################################
n,x,y = map(int,input().split()) #n:頂点数　w:辺の数
w = n
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
di = []
ans = {1:n}
for i in range(2,n):
    ans[i]=0


for i in range(n):
    dij = dijkstra(i,n,w,cost)
    di.append(dij)
    for j in range(2,n):
        ans[j] += dij.count(j)




print(ans[1])
for k, v in ans.items():
    if k==1:continue
    print(v//2)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline

  N,X,Y = map(int,input().split())
  d = [[N 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:
n,x,y = list(map(int,input().split()));

knum = [0]*(n-1);
d = [[0]*(n) for i in range(n)];

for i in range(n) :
    for j in range(i+1,n) :
        d[i][j] = j - i;
        d[j][i] = j - i;

d[x-1][y-1] = 1;
d[y-1][x-1] = 1;

for i in range(n) :
    for j in range(i+1,n) :
        if (i < x and j < x) or (i > y and j > y) :
            continue;
        else :
            mind = min(d[i][j],d[i][x-1]+1+d[y-1][j],d[i][y-1]+1+d[x-1][j]);
            d[i][j] = mind;
            d[j][i] = mind;

for i in range(n) :
    for j in range(i+1,n) :
        knum[d[i][j]-1] += 1;

for i in range(n-1) :
    print(knum[i]);

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int,input().split())
X = X-1
Y = Y-1
NN = [[0 for i in range(N)] for j in range(N)]
NN2 = [[0 for i in range(N)] for j in range(N)]
 
  
for i in range(N):
  for j in range(i,N):
    NN[i][j] = j-i
for i in range(N):
  for j in range(i+1,N):
    NN2[i][j] = abs(i-X)+abs(j-Y)+1
CNT = [0]*(N)
for i in range(N):
  for j in range(i+1,N):
    if NN[i][j]>NN2[i][j]:
      CNT[NN2[i][j]] += 1
    else:
      CNT[NN[i][j]] += 1
for i in range(1,N):
  print(CNT[i])

Submission status: Time Limit Exceeded

Solution code:

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


import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix

l = [[0] * n for _ in range(n)]

for i in range(n-1):
    l[i][i+1] = 1
    l[i+1][i] = 1

l[x-1][y-1] = 1
l[y-1][x-1] = 1

#print(l)
l = np.array(l)
ans = shortest_path(l)

dic = {}
for i in range(n):
    dic[i] = 0


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

for i in range(1,n):
    print(dic[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter


def bfs(start, graph):
    q = deque([(start, 0)])
    visited = set()

    while q:
        curr, dist = q.popleft()
        if curr not in visited:
            yield start, curr, dist
            visited.add(curr)
            for neighbor in graph[curr]:
                q.append((neighbor, dist + 1))


if __name__ == '__main__':
    n, x, y = tuple([int(i) for i in input().split()])
    graph = {i: [] for i in range(1, n + 1)}

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

    dists = [0 for k in range(n)]
    distances = {}
    for i in range(1, n):
        for s, e, d in bfs(i, graph):
            if s != e:
                start = min(s, e)
                end = max(s, e)
                key = (start, end)
                if key in distances.keys():
                    distances[key] = min(distances[key], d)
                else:
                    distances[key] = d

    dists = Counter(distances.values())

    for k in range(1, n):
        print(dists[k] if k in dists.keys() else 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)

	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:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
from collections import Counter

x,y,z=list(map(int, input().split()))
a= [[0] * x for i in range(x)]

for i in range(x-1):
	a[i][i+1]=1
	a[i+1][i]=1

a[y-1][z-1]=1
a[z-1][y-1]=1

b = np.array(a)
c=shortest_path(b)
t=[0]*x

def flatten_2dim(array):
    return [item for sublist in array for item in sublist]
cnt = list(flatten_2dim(c))

for i in range(1,x):
	print(cnt.count(i)//2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, x, y = map(int, input().split())
g = np.zeros((n+1,n+1),dtype=np.int64)
ans = np.zeros((n+1),dtype=np.int64)
for i in range(1,n+1):
    for j in range(i+1,n+1):
        if j <= x:
            g[i][j] = g[i][j - 1] + 1
        elif j > x and j <= y:
            #print(i,j,g[i][x] + j - x , g[i][x] + y - j + 1)
            if i <= x:
                g[i][j] = min(g[i][x] + j - x , g[i][x] + y - j + 1)
            else:
                g[i][j] = min(g[i][j - 1] + 1 , i - x + 1 + y - j)
        else:
            g[i][j] = g[i][j - 1] + 1

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

for i in range(1,n):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(start):
    global count
    d = [float('inf') for i in range(N)]
    d[start] = 0
    que = deque()
    que.append(start)
    alr = [start]
    while que:
        q = que.popleft()
        for i in path[q]:
            if i not in alr:
                que.append(i)
                alr.append(i)
                d[i] = min(d[i],d[q]+1)
    for i in range(start+1,N):
        count[d[i]-1] += 1

N,X,Y = map(int,input().split())
path = [[] for i in range(N)]
path[0] = [1]
path[N-1] = [N-2]
for i in range(1,N-1):
    path[i] = [i-1,i+1]
path[X-1].append(Y-1)
path[Y-1].append(X-1)

count = [0 for i in range(N-1)]
for i in range(N-1):
    bfs(i)
for i in range(N-1):
    print(count[i])

Submission status: Time Limit Exceeded

Solution code:
import collections
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
lst=[]
for i in range(n):
    lst+=dijkstra(i,n,w,cost)        
Lst=list(collections.Counter(lst).items())
Key=list(collections.Counter(lst).keys())
m=max(Key)
for i in range(1,m+1):
    print(Lst[i][1]//2)
for i in range(m+1,n):
    print(0)

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,method = "D",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
import collections


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

route = np.array([[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)

tmp = []
for i in range(n):
	tmp.append(collections.Counter(res[i][i:]))


ans = [0 for _ in range(n)]
for i in range(n):
	for k in range(1,n):
		ans[k] += tmp[i][k]

for i in range(1,n):
	print(ans[i])

Submission status: Time Limit Exceeded

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


def Warshall_Floyd(N):
    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


d = [[float("inf")] * N for i in range(N)]

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

for i in range(N):
    d[i][i] = 0

d[X-1][Y-1] = 1
d[Y-1][X-1] = 1

d = Warshall_Floyd(N)


for i in range(N):
    for j in range(N):
        if dic.get(d[i][j]) is None:
            dic[d[i][j]] = 1
        else:
            dic[d[i][j]] += 1

for i in range(1, N):
    if dic.get(i) is None:
        print(0)
    else:
        print(dic[i]//2)

Submission status: Time Limit Exceeded

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

dist = [[0 for i in range(N)] for j in range(N)]
for i in range(1,N):
    for j in range(i):
        dist[i][j]=i-j
dist[Y-1][X-1]=1

for i in range(N):
    y1 = min(Y-1+i,N-1)
    y2 = max(Y-1-i,0)
    for j in range(N):
        x1 = min(X-1+j,N-1)
        x2 = max(X-1-j,0)
        dist[min(y1+1,N-1)][x1] = min(dist[y1][x1]+1,dist[min(y1+1,N-1)][x1])
        dist[min(y1+1,N-1)][x2] = min(dist[y1][x2]+1,dist[min(y1+1,N-1)][x2])
        dist[max(y2-1,0)][x1] = min(dist[y2][x1]+1,dist[max(y2-1,0)][x1])
        dist[max(y2-1,0)][x2] = min(dist[y2][x2]+1,dist[max(y2-1,0)][x2])
        dist[y1][min(x1+1,N-1)] = min(dist[y1][x1]+1,dist[y1][min(x1+1,N-1)])
        dist[y2][min(x1+1,N-1)] = min(dist[y2][x1]+1,dist[y2][min(x1+1,N-1)])
        dist[y1][max(x2-1,0)] = min(dist[y1][x2]+1,dist[y1][max(x2-1,0)])
        dist[y2][max(x2-1,0)] = min(dist[y2][x2]+1,dist[y2][max(x2-1,0)])

ans = [0]*(N-1)

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

for i in ans:
    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)]
dic={}
for i in range(n-1):
    for j in range(i+1,n):
        if i<=x and j<=x:
            k = j-i
            if k not in dic:
            	dic[k]=1
            else:
            	dic[k]+=1
        elif j==middle:
            k = j-i
            if k not in dic:
            	dic[k]=1
            else:
            	dic[k]+=1
        elif i==middle:
            k = j-i
            if k not in dic:
            	dic[k]=1
            else:
            	dic[k]+=1
        elif i<=x and j>=x and j<=middle:
            k = j-i
            if k not in dic:
            	dic[k]=1
            else:
            	dic[k]+=1
        elif i<=x and j>=middle and j<=y:
            k = (x-i) + 1 + (y-j)
            if k not in dic:
            	dic[k]=1
            else:
            	dic[k]+=1
        elif i<=x and j>=middle and j>=y:
            k = (x-i) + 1 + (j-y)
            if k not in dic:
            	dic[k]=1
            else:
            	dic[k]+=1
        elif i>=x and i<=middle and j<=middle:
            k = j-i
            if k not in dic:
            	dic[k]=1
            else:
            	dic[k]+=1
        elif i>=x and i<=middle and j>=middle and j<=y:
            k = min(j-i, i-x+y-j+1)
            if k not in dic:
            	dic[k]=1
            else:
            	dic[k]+=1
        elif i>=x and i<=middle and j>=y:
            k = i-x + j-y + 1
            if k not in dic:
            	dic[k]=1
            else:
            	dic[k]+=1
        elif i>=middle and j<=y:
            k = j-i
            if k not in dic:
            	dic[k]=1
            else:
            	dic[k]+=1
        elif i>=middle and j>=y:
            k = j-i
            if k not in dic:
            	dic[k]=1
            else:
            	dic[k]+=1
        elif i>=y and j>=y:
            k = j-i
            if k not in dic:
            	dic[k]=1
            else:
            	dic[k]+=1
for i in range(1,n):
    if i not in dic:
        print(0)
    else:
        print(dic[i])