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:
#!/usr/bin/env python3
import sys


def solve(N: int, X: int, Y: int):
    cst = [0 for _ in range(N)]
    nodes = [Node(i, N, X, Y) for i in range(N)]
    for i in range(N):
        for n in nodes:
            n.done = False
            n.cost = -1
        # nodes = []
        # for j in range(N):
        #     nodes.append(Node(j, N, X, Y))
        # nodes = [Node(i, N, X, Y) for i in range(N)]
        nodes[i].cost = 0
        while True:
            doneNode = Node(N, N, X, Y)
            for n in nodes:
                if n.done or n.cost < 0:
                    pass
                elif doneNode.num == N or n.cost < doneNode.cost:
                    doneNode = n
            if doneNode.num == N:
                break
            
            doneNode.done = True
            for i in doneNode.edges:
                if nodes[i].cost < 0 or doneNode.cost + 1 < nodes[i].cost:
                    nodes[i].cost = doneNode.cost + 1
        
        for n in nodes:
            cst[n.cost] += 1
    
    for i in range(1, len(cst)):
        print(int(cst[i] / 2))
        



class Node:
    def __init__(self, i, N, X, Y):
        self.num = i
        self.edges = set()
        if i == 0:
            self.edges.add(i+1)
        elif i == N - 1:
            self.edges.add(i-1)
        else:
            self.edges.add(i+1)
            self.edges.add(i-1)
        if i == X - 1:
            self.edges.add(Y - 1)
        elif i == Y - 1:
            self.edges.add(X - 1)
        self.done = False
        self.cost = -1

            
            


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(N, X, Y)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:



def main():
    
    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 N for i in range(N)]
    
    # from pprint import pprint 
    # pprint(D)
    import numpy as np
    D =np.array(D)

    for k in range(N):
        # print(np.tile(D[:,k],(N,1)))
        # print(np.tile(D[k,:],(N,1)))
        tmp = np.tile(D[:,k],(N,1)) + np.tile(D[k,:],(N,1)).T
        # print(tmp)
        # print(D[:,k] + D[k,:])
        D = np.min([D, tmp], axis=0)
        # print(D)

    # for k in range(N):
    #     for i in range(N):
    #         if N == D[i][k]:
    #             continue
    #         for j in range(N):
    #             D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    # pprint(D)
    # print(D)
    # D=sum(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:
# -*- coding: utf-8 -*-
from collections import Counter
 
(N, X, Y) = (int(i) for i in input().split())
 
# まずは経路情報をd[N][N]の二次元配列に格納
# (i, j)がつながっていれば1, つながってなければ2*10^3
 
d = []
for i in range(N):
    d.append([2 * 10**3]*N)
 
for i in range(N - 1):
    d[i][i] = 0
    d[i][i+1] = 1
    d[i+1][i] = 1
 
d[X-1][Y-1] = 1
d[Y-1][X-1] = 1
#print(d)
 
# ワーシャル・フロイドで全点の最短経路を計算
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])
 
#print(d)

# dの全リストを連結してあとは0~N-1までカウントする
d_list = []
for i in range(N - 1):
    d_list += d[i][i+1:]

#print(d_list)
c = Counter(d_list)

for i in range(1, N):
    if i in c:
        print(c[i])
    else:
        print(0)

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

n,x,y = map(int,input().split()) #n:頂点数　w:辺の数

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

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 #自身のところに行くコストは０
k=0

for i in range(n):
    if i==0:
        continue
    for j in range(n):
        k=k+warshall_floyd(d)[j].count(i)
    print(k//2)
    k=0

Submission status: Time Limit Exceeded

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

ans = [0] * N

X -= 1
Y -= 1
for i in range(N):
    for j in range(i+1, N):
        distance = abs(i-j)
        # 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 = min(distance, dis)
        # i X j Y
        elif i <= X < j <= Y:
            dis = (X-i) + 1 + (Y-j)
            distance = min(distance, dis)
        # i X Y j
        elif i <= X < Y <= j:
            dis = (X-i) + 1 + (j-Y)
            distance = min(distance, dis)
        # X i j Y
        elif X <= i < j <= Y:
            dis = (i-X) + 1 + (Y-j)
            distance = min(distance, dis)

        ans[distance] += 1

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

Submission status: Time Limit Exceeded

Solution code:
n, x, y = input().split(" ")
n, x, y = int(n), int(x), int(y)
ans = [0] * (n - 1)
 
for i in range(n - 1):
    for j in range(i + 1, n):
        now = 0
        if (j <= x - 1):
            ans[j - i - 1] += 1
 
        elif(j > x - 1 and j <= y - 1 and i <= x - 1):
            now = now + x - 1 - i
            if (j - (x - 1) >= (y - 1) - j + 1):
                now = now + (y - 1) - j + 1
            else:
                now = now + j - (x - 1)
            ans[now - 1] += 1
 
        elif(j > x - 1 and j <= y - 1 and i > x - 1):
            if (j - i >= (i - (x - 1)) + ((y - 1) - j) + 1):
                now = (i - (x - 1)) + ((y - 1) - j) + 1
            else:
                now = j - i
            ans[now - 1] += 1
 
        elif(j > y - 1 and i <= x - 1):
            now = now + x - 1 - i
            now = now + j - (y - 1) + 1
            ans[now - 1] += 1
 
        elif(j > y - 1 and i > x - 1 and i < y - 1):
            if((y - 1) - i >= i - (x - 1) + 1):
                now = now + i - (x - 1) + 1
            else:
                now = now + (y - 1) - i
            now = now + j - (y - 1)
            ans[now - 1] += 1
 
        elif(i >= y - 1):
            ans[j - i - 1] += 1
 
print(*ans)

Submission status: Time Limit Exceeded

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

import heapq

class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        goal: オプション引数．終点のID
        出力
        goalを引数に持つ場合，startからgoalまでの最短経路を格納したリストを返す
        持たない場合は，startから各頂点までの最短距離を格納したリストを返す
        >>> d = Dijkstra()
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0)
        [0, 2, 4, 5, 8] # 例えば，始点0から頂点3までの最短距離は5となる
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0, goal=4)
        [0, 2, 4] # 頂点0から頂点4までの最短経路は0 -> 2 -> 4となる
        '''
        num = len(adj)          # グラフのノード数
        dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
        
        dist[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop
            
            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost # distの更新
                    heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                    prev[dest] = src                      # 前の頂点を記録
                    
        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))


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

graph = [[1 if j == i+1 or j+1 == i else float('inf') for j in range(1,N+1)] for i in range(1,N+1)]
graph[X-1][Y-1] = 1
graph[Y-1][X-1] = 1

dist = []

d = Dijkstra()

for i in range(N):
  for j in range(N):
    if i == j: continue
    dist.append(len(d.dijkstra(graph, i, j))-1)
    
for i in range(N-1):
  print((int)(dist.count(i+1)/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())
a = np.ones(N-1)
route_list = np.diag(a,k=1)
route_list[X-1][Y-1] = 1
route_list[Y-1][X-1] = 1

shortest = shortest_path(route_list,directed=False,method="D")

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

Submission status: Time Limit Exceeded

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


arr = [[10**4] * n for i in range(n)]
for i in range(n-1):
        arr[i][i+1] = 1
        arr[i+1][i] = 1
arr[x-1][y-1] = 1
arr[y-1][x-1] = 1

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

csr = csr_matrix(arr)
dist_m = shortest_path(csr, directed=False)

ans = [0] * (n-1)
for i in range(n):
    dist = dist_m[i].tolist()
    for j in range(len(dist)):
        ans[int(dist[j])] += 1

for i in range(1,len(ans)):
    print(ans[i] // 2)
print(0)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import itertools

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

n, x, y = map(int, input().split())
d = [[n]*n for i 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
warshall_floyd(d)
D = Counter(list(itertools.chain.from_iterable(d)))
for i in range(1, n):
    print(D[i]//2)

Submission status: Time Limit Exceeded

Solution code:
n, x, y = input().split(" ")
n, x, y = int(n), int(x), int(y)
ans = [0] * (n - 1)

for i in range(n - 1):
    for j in range(i + 1, n):
        now = 0
        if (j <= x - 1):
            ans[j - i - 1] += 1

        elif(j > x - 1 and j <= y - 1 and i <= x - 1):
            now = now + x - 1 - i
            if (j - (x - 1) >= (y - 1) - j + 1):
                now = now + (y - 1) - j + 1
            else:
                now = now + j - (x - 1)
            ans[now - 1] += 1

        elif(j > x - 1 and j <= y - 1 and i > x - 1):
            if (j - i >= (i - (x - 1)) + ((y - 1) - j) + 1):
                now = (i - (x - 1)) + ((y - 1) - j) + 1
            else:
                now = j - i
            ans[now - 1] += 1

        elif(j > y - 1 and i <= x - 1):
            now = now + x - 1 - i
            now = now + j - (y - 1) + 1
            ans[now - 1] += 1

        elif(j > y - 1 and i > x - 1 and i < y - 1):
            if((y - 1) - i >= i - (x - 1) + 1):
                now = now + i - (x - 1) + 1
            else:
                now = now + (y - 1) - i
            now = now + j - (y - 1)
            ans[now - 1] += 1

        elif(i >= y - 1):
            ans[j - i - 1] += 1

print(*ans,sep="\n")

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())
a = np.ones(N-1)
route_list = np.diag(a,k=1)
route_list[X-1][Y-1] = 1
route_list[Y-1][X-1] = 1

shortest = shortest_path(route_list,directed=False,method="J")

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

Submission status: Time Limit Exceeded

Solution code:
N, X, Y= map(int, input().split()) 
Count = []
for i in range(N-1):
  Count.append(0)
  
for k in range(1, N):
  for i in range(1, N):
    for j in range(i+1, N+1):
      if (j-i > k) & ((abs(i-X) +abs(j-Y) +1)>k) & ((abs(i-X) +abs(j+1-Y) +1 )>(abs(i-X) +abs(j-Y) +1)>k):
        break
      if j-i <= (abs(i-X) +abs(j-Y) +1):
        if j-i == k:
          Count[k-1] = Count[k-1]+1
      else:
        if (abs(i-X) +abs(j-Y) +1) == k:
          Count[k-1] = Count[k-1]+1

for i in range(N-1):
  print(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+1, 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)
print(N)
for i in range(1, N-1):
    print(result.count(i+1))

Submission status: Time Limit Exceeded

Solution code:
def main():
  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)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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


graph = {}

for i in range(n):
    if(i == 0):
        graph[i] = [1]
    elif(i == n-1):
        graph[i] = [n-2]
    else:
        graph[i] = [i-1,i+1]


#print(graph)

xx = graph[x-1]
xx.append(y-1)
graph[x-1] = xx

yy = graph[y-1]
yy.append(x-1)
graph[y-1] = yy

#print(graph)

def bfs(graph,st):
    q = deque()
    q.append(st)
    dist = [-1]*n
    dist[st] = 0
    
    while len(q) > 0:
    # キューの先頭（左端）からnodeを取り出す
        v = q.popleft()
        
        for i in graph[v]:
            if (dist[i] != -1):
                continue
            dist[i] = dist[v] + 1;
            q.append(i)
    
    return dist

res = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    res[i] = bfs(graph,i)

#print(res)

for k in range(1,n):
    ress = 0
    for i in range(n):
        ress += res[i].count(k)
    
    
    print(ress//2)

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]]

    if i >= Y:
        checked = list(range(1,i+1))
    elif 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:
# coding: utf-8

from copy import deepcopy

import sys
sys.setrecursionlimit(100000)

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

# from time import time
# start = time()

# neighbor = {}
# for i in range(1, N):
#     neighbor[i] = [i+1]
# for i in range(X+4, Y):
#     neighbor[i] = [i-1, i+1]
# neighbor[X] = [X+1, Y]
# neighbor[Y] = [Y-1, Y+1]
# neighbor[N] = [] if Y < N else [N-1] 
# print(neighbor)

neighbor = {}
for i in range(1, X):
    neighbor[i] = [i+1]
for i in range(Y+1, N):
    neighbor[i] = [i+1]
for i in range(X+1, Y):
    neighbor[i] = [i-1, i+1]
neighbor[X] = [X+1, Y]
neighbor[Y] = [Y-1, Y+1]
neighbor[N] = [] if Y < N else [N-1]
# print(neighbor)

# print(neighbor)

# neighbor = {i: [i-1, i+1] for i in range(2, N)}
# neighbor[1] = [2]
# neighbor[N] = [N-1]
# neighbor[X].append(Y)
# neighbor[Y].append(X)

# appeared_st = set([])
appeared_st = [set([]) for _ in range(N+1)]
# appeared_st[0] = 0
n_k = [0] * N
s_t_dist_dict = {}


# def rec(n, dist, s, k, appeared):
#     # print(appeared_st)
#     if dist == k:
#         # if k == 2:
#         #     input()
#         if s < n and n not in appeared_st[s]:
#             appeared_st[s].add(n)
#             appeared_st[0] += 1
#             # print(appeared_st)

#     toes = [node for node in neighbor[n] if node not in appeared]
#     for to in toes:
#         appeared_copy = deepcopy(appeared)
#         appeared_copy.add(to)
#         rec(to, dist+1, s, k, appeared_copy)


def rec(n, dist, s, limit, appeared, X, Y):
    if s < n:
        ke = "{}.{}".format(s, n)
        if ke in s_t_dist_dict:
            if dist < s_t_dist_dict[ke]:
                n_k[s_t_dist_dict[ke]] -= 1
                s_t_dist_dict[ke] = dist
                n_k[dist] += 1
        else:
            s_t_dist_dict[ke] = dist
            n_k[dist] += 1
            
    # if s < n and n not in appeared_st[s]:
    #     appeared_st[s].add(n)
    #     n_k[dist] += 1
    #     print(appeared_st)
    #     print(n_k)
    #     input()

    if dist == limit:
        return None
    
    if X < n < Y and n - X + 1 > limit - dist:
        return None

    toes = [node for node in neighbor[n] if node not in appeared]
    for to in toes:
        appeared_copy = deepcopy(appeared)
        appeared_copy.add(to)
        rec(to, dist+1, s, limit, appeared_copy, X, Y)


for s in range(1, N):
    rec(s, 0, s, N-1, {s}, X, Y)

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

# for k in range(1, N):
#     tmp = appeared_st[0]

#     for s in range(1, N+1):
#         rec(s, 0, s, k, {s})

    # print(appeared_st[0] - tmp)

# print(appeared_st)
# print(len(appeared_st))
            
# print(time() - start)

Submission status: Time Limit Exceeded

Solution code:
import pprint
from itertools import chain
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(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:
# -*- 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
        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:
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)
  ans_l+=list(d)

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

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
S = [list(reversed(list(range(1, i+1)))) + list(range(N-i)) for i in range(N)]

S[X-1][Y-1] = 1
S[Y-1][X-1] = 1

for i in range(N):
    for j in range(N):
        x, y = X-1, Y-1
        S[i][j] = min(S[i][j], S[i][x]+1+S[y][j])

#print(S)

dist = [0]*N

from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
)

for i, j in combinations(list(range(N)), 2):
    d = S[i][j]
    dist[d] += 1

#print(dist)

for i in range(1, len(dist)):
    print(dist[i])

Submission status: Time Limit Exceeded

Solution code:
#template
def inputlist(): return [int(j) for j in input().split()]
#template
#issueから始める
N,X,Y = inputlist()
graph = [[0]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        if i - j == 1 or j - i == 1:
            graph[i][j] = 1
            graph[j][i] = 1
        if i == X and j == Y or i == Y and j == X:
            graph[X][Y] = 1
            graph[Y][X] = 1
from scipy.sparse.csgraph import shortest_path
import numpy as np
c = np.array(graph)
path = shortest_path(c,'D')
ans = [0]*(N+1)
for i in range(1,N+1):
    for j in range(1,N+1):
        if path[i,j] != 0:
            ans[int(path[i,j])] +=1
for i in range(1,N):
    print(ans[i]//2)

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = list(map(int, input().split(' ')))
X -= 1
Y -= 1
dist_map = {}

def search(origin):
  dist = []
  # X, Yの辺がない場合
  for i in range(N):
    dist.append(abs(origin - i))
  # X, Yの辺がある場合
  if dist[X] < dist[Y]:
    dist[Y] = dist[X] + 1
  elif dist[Y] < dist[X]:
    dist[X] = dist[Y] + 1
  for i in range(X+1, Y):
    dist[i] = min(dist[i-1]+1, dist[i+1]+1, dist[i])
  for i in range(N):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  for i in reversed(range(N)):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  #print(*dist)
  return dist


for i in range(N):
  dist_map[i] = search(i)

#print(N)
count = [0 for i in range(N)]
for i in range(N):
  #print('i='+str(i))
  #dist = dist_map[i]
  #print(*dist)
  dist = dist_map[i]
  for dis in dist:
    count[dis] += 1
for i in range(1, N):
  print(count[i]//2)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import numpy as np

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)]
    mat = np.zeros((n+1, 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:
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())
cost = [[1 if j==i+1 or j==i-1 else float("inf") for j in range(n)] for i in range(n)]
cost[x-1][y-1] = 1
cost[y-1][x-1] = 1

b = [dijkstra(i,n,n,cost) for i in range(n)]
c = [int(b[i][j]) for i in range(n) for j in range(n) if j>i]
for i in range(1, n):
    print(c.count(i))