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:
from collections import Counter, deque

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

E = [[] for i in range(N)]
for i in range(N):
    if i-1 >= 0: E[i].append(i-1)
    if i+1 < N: E[i].append(i+1)
    
E[X-1].append(Y-1)
E[Y-1].append(X-1)

cnt = Counter()

for i in range(N):
    visited = [False] * N
    q = deque([(i, 0)])
    cn = [0] * N
    
    while q:
        v, c = q.popleft()
        
        if visited[v]: continue
        visited[v] = True
        cn[v] = c
        
        for u in E[v]:
            if not visited[u]: q.append((u, c+1))
    for j in cn[i:]:
        cnt[j] += 1
    
for i in range(1, N):
    print(cnt[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs(v):
    todo = deque()
    todo.append(v)
    seen[v] = 0
    while len(todo) > 0:
        v = todo.popleft()
        d = seen[v]
        for w in graph[v]:
            if seen[w] != -1:
                continue
            seen[w] = d + 1
            todo.append(w)


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)

cnt = [0 for _ in range(N)]
for i in range(N-1):
    seen = [-1 for _ in range(N)]
    bfs(i)
    for j in range(i+1, N):
        cnt[seen[j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, x, y = map(int, input().split())
eage = [[] for _ in range(n)]

for i in range(n-1):
  eage[i].append( i+1 )
  eage[i+1].append( i )

x -= 1
y -= 1

eage[x].append( y )
eage[y].append( x )

visited = [[-1] * n for _ in range(n)]

counter = [0] * n
for start_point in range(n):
  visited[start_point][start_point] = 0
  # [0] とか [0, 2, 3] とか [1, 3]
  q = deque([start_point])
  while q:
    v = q.popleft()
    for j in eage[v]:
      # 未訪問
      if visited[start_point][j] == -1:
        # v が start_point の切り替え役
        visited[start_point][j] = visited[start_point][v] + 1
        q.append( j )
  for c in visited[start_point]:
    counter[c] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, x, y = map(int, input().split())
eage = [[] for _ in range(n)]

for i in range(n-1):
  eage[i].append( i+1 )
  eage[i+1].append( i )

x -= 1
y -= 1

eage[x].append( y )
eage[y].append( x )

visited = [[-1] * n for _ in range(n)]

for start_point in range(n):
  visited[start_point][start_point] = 0
  # [0] とか [0, 2, 3] とか [1, 3]
  q = deque([start_point])
  while q:
    v = q.popleft()
    for j in eage[v]:
      # 未訪問
      if visited[start_point][j] == -1:
        # v が start_point の切り替え役
        visited[start_point][j] = visited[start_point][v] + 1
        q.append( j )

from itertools import chain

counter = [0] * n

for v in list(chain.from_iterable(visited)):
  counter[v] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import collections
def main():
    N,X,Y = map(int, input().split())
    # 扱いやすいようにX,Yはインデックス表記にしておく
    X -= 1
    Y -= 1
    # i<jを満たす(i,j)について6通りの場合分けして全最短距離を求められる
    shortest = [[-1]*N for _ in range(N)]
    for i in range(N):
        k1 = abs(X-i)
        for j in range(i+1,N):
            k2 = abs(j-Y)
            shortest[i][j] = min(j-i, k1+1+k2)

    coll = [collections.Counter(s) for s in shortest]
    for i in range(1,N):
        count = 0
        for j in range(N):
            count += coll[j].get(i,0)
        print(count)
main()

Submission status: Time Limit Exceeded

Solution code:
import collections
def main():
    N,X,Y = map(int, input().split())
    # 扱いやすいようにX,Yはインデックス表記にしておく
    X -= 1
    Y -= 1
    # i<jを満たす(i,j)について6通りの場合分けして全最短距離を求められる
    shortest = [[-1]*N for _ in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            shortest[i][j] = min(j-i, abs(X-i)+1+abs(j-Y))

    coll = [collections.Counter(s) for s in shortest]
    for i in range(1,N):
        count = 0
        for j in range(N):
            count += coll[j].get(i,0)
        print(count)
main()

Submission status: Time Limit Exceeded

Solution code:
import collections
def main():
    N,X,Y = map(int, input().split())
    # 扱いやすいようにX,Yはインデックス表記にしておく
    X -= 1
    Y -= 1
    # i<jを満たす(i,j)について6通りの場合分けして全最短距離を求められる
    shortest = [[-1]*N for _ in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            # i<=X,Y<=j
            if i<=X and Y<=j:
                shortest[i][j] = min(j-i, X-i+1+j-Y)
            # j<=X
            elif j<=X:
                shortest[i][j] = j-i
            # i<=X<j<=Y
            elif i<=X and X<=j and j<=Y:
                shortest[i][j] = min(j-i, X-i+1+Y-j)
            # X<=i,j<=Y
            elif X<=i and j<=Y:
                shortest[i][j] = min(j-i, i-X+1+Y-j)
            # X<=i<=Y<=j
            elif X<=i and i<=Y and Y<=j:
                shortest[i][j] = min(j-i, i-X+1+j-Y)
            # Y<=i
            else:
                shortest[i][j] = j-i

    coll = [collections.Counter(s) for s in shortest]
    for i in range(1,N):
        count = 0
        for j in range(N):
            count += coll[j].get(i,0)
        print(count)
main()

Submission status: Time Limit Exceeded

Solution code:
import collections
def main():
    N,X,Y = map(int, input().split())
    # 扱いやすいようにX,Yはインデックス表記にしておく
    X -= 1
    Y -= 1
    # i<jを満たす(i,j)について6通りの場合分けして全最短距離を求められる
    shortest = [[-1]*N for _ in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            # i<=X,Y<=j
            if i<=X and Y<=j:
                shortest[i][j] = min(j-i, X-i+1+j-Y)
            # j<=X
            elif j<=X:
                shortest[i][j] = j-i
            # i<=X<j<=Y
            elif i<=X and X<=j and j<=Y:
                shortest[i][j] = min(j-i, X-i+1+Y-j)
            # X<=i,j<=Y
            elif X<=i and j<=Y:
                shortest[i][j] = min(j-i, i-X+1+Y-j)
            # X<=i<=Y<=j
            elif X<=i and i<=Y and Y<=j:
                shortest[i][j] = min(j-i, i-X+1+j-Y)
            # Y<=i
            else:
                shortest[i][j] = j-i

    for i in range(1,N):
        count = 0
        for j in range(N):
            coll = collections.Counter(shortest[j])
            count += coll.get(i,0)
        print(count)
main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush

def dijkstra(s):
    used = [1] * n
    dp = [INF] * n
    dp[s] = 0
    hq = []
    used[s] = 0
    for i in cost[s]:
        heappush(hq, i)

    while hq:
        minv = heappop(hq)
        if used[minv[1]] == 0:
            continue
        v = minv[1]
        dp[v] = minv[0]
        used[v] = 0
        for i in cost[v]:
            if used[i[1]]:
                heappush(hq, [i[0] + dp[v], i[1]])
    return dp

INF = 10 ** 18
n, x, y = map(int, input().split())
cost = [[] for _ in range(n)]

for i in range(n - 1):
    a = i
    b = i + 1
    cost[a].append([1, b])
    cost[b].append([1, a])
cost[x - 1].append([1, y - 1])
cost[y - 1].append([1, x - 1])
ans = [0] * n
for i in range(n - 1):
    dp1 = dijkstra(i)
    for j in dp1[i:]:
        ans[j] += 1

for i in ans[1:]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
n, x, y = map(int, input().split())
g = [[] for _ in range(n)]

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

g[x-1].append((y-1, 1))
g[y-1].append((x-1, 1))


def dijkstra(s, n, g):
    # g[i][j] : the cost of i→j  or g[i] = [(target, cost), ...]
    # must import heapq
    # sys.stdin.readline is recommended
    prev = [-1]*n
    d = [10**18] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in g[u]:  # 'in g[u]' if g is an adj list.
            if d[v] > dist_u + c:
                prev[v] = u
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d, prev


ans = [0]*(n-1)

for i in range(n):
    d, prev = dijkstra(i, n, g)
    for j in range(n-1):
        ans[j] += d.count(j+1)

for x in ans:
    print(x//2)

Submission status: Time Limit Exceeded

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

mn_ln = [[0 for _ in range(n-1)] for _ in range(n)]

dic = {}
x = x-1
y = y-1
for i in range(n):
    for j in range(n):
        if(i == j):
            break

        nm = abs(j - i)
        if(abs(x-i) > abs(y-i)):
            lp = abs(y-i) + abs(x-j) + 1
        else:
            lp = abs(x-i) + abs(y-j) + 1
        
        k = min(nm,lp)
        if(k in dic):
            dic[k] += 1
        else:
            dic[k] = 1
#print(dic[2])


for i in range(1,n):
    if not (i in dic):
        print(0)
    else:
        print(dic[i])

Submission status: Time Limit Exceeded

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

dis=[['NONE']*n for i in range(n)]
d = deque()
for i in range(n):
    d.append((i,0))
    c=0
    while d:
        p,j=d.popleft()
        if p==x and c==0:
            d.append((y,j+1))
            c=1
        if p==y and c==0:
            d.append((x,j+1))
            c=1
        if dis[i][p]=='NONE':
            dis[i][p]=j
            if p+1<n:
                if dis[i][p+1]=='NONE':
                    d.append((p+1,j+1))
            if p-1>=0:
                if dis[i][p-1]=='NONE':
                    d.append((p-1,j+1))
s=[]
for i in dis:
    s+=i
c=Counter(s)
for i in range(1,n):
    print(c[i]//2)

Submission status: Time Limit Exceeded

Solution code:
def warshal_floyd(m, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                c_ij = m[i][j]
                c_ikj = m[i][k] + m[k][j]
                m[i][j] = min(c_ij, c_ikj)
    return m


def main():
    from collections import Counter
    n, x, y = map(int, input().split())
    m = [[float("Inf")] * n for _ in range(n)]
    for i in range(n):
        m[i][i] = 0
    for i in range(n - 1):
        m[i][i + 1] = 1
        m[i + 1][i] = 1

    m[x - 1][y - 1] = 1
    m[y - 1][x - 1] = 1

    wm = warshal_floyd(m, n)

    mm = sum(m, [])
    c = Counter(mm)
    ans = ''
    for i in range(1, n):
        d = c.get(i)
        if d is None:
            ans += "0\n"
        else:
            ans += str(d // 2) + '\n'
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
l=[[] for i in range(n+1)]
ans=[0]*(n+1)
for i in range(n+1):
	for j in range(n+1):
		l[i].append(0)
for i in range(1,n+1):
	for j in range(1,n+1):
		l[i][j]=abs(i-j)

for i in range(1,n+1):
	for j in range(1,n+1):
		l[i][j]=min(l[i][j],l[i][x]+l[y][j]+1)
for i in range(1,n+1):
	for j in range(i+1,n+1):
		if l[i][j]<=n:
			ans[l[i][j]]+=1
for i in range(1,n):
	print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

ni = lambda: int(input())
nm = lambda: map(int, input().split())
# nl = lambda: list(map(int, input().split()))

n,x,y=nm()

class Node:
  def __init__(self,x):
    self.val = x
    self.left=[]
    self.right=[]

nodes = [Node(i) for i in range(n)]
for i in range(n-1):
  nodes[i].right.append(nodes[i+1])
  nodes[i+1].left.append(nodes[i])

nodes[x-1].right.append(nodes[y-1])
nodes[y-1].left.append(nodes[x-1])

gl_dist = [0]*n


for i in range(n):
  dist = [-1]*n
  dist[i]=0
  q = deque()
  q.append(nodes[i])
  while len(q) > 0:
    node = q.popleft()
    nv = node.val
    nl = node.left
    nr = node.right

    for nli in nl:
      if dist[nli.val] == -1:
        dist[nli.val] = dist[nv]+1
        q.append(nli)
    for nri in nr:
      if dist[nri.val] == -1:
        dist[nri.val] = dist[nv]+1
        q.append(nri)

  for j in range(i+1,n):
    # print("{} to {} is {}".format(i,j,dist[j]))
    if dist[j] != -1:
      gl_dist[dist[j]]+=1

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

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split())
dp = [[0 for _ in range(n)] for _ in range(n)]
ans = [0 for _ in range(n-1)]
for i in range(1, n):
  for j in range(i+1, n+1):
    a = min(j-i, abs(x-i)+abs(y-j)+1, abs(x-j)+abs(y-i)+1)
    ans[a-1] += 1
for i in range(n-1):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split())
cnt_l = [0 for i in range(0,n)]
from collections import deque
def bfs(start):
    queue = deque()
    queue.append([start,0])
    isNotSearched = [False]*(n+1)
    
    while(len(queue)>0):
        i,cnt = queue.popleft()
        
        if(isNotSearched[i]):
            continue
        
        isNotSearched[i]=True
        cnt_l[cnt]+=1
        pre = (i-1)
        nex = (i+1)
        if(i==x):
            queue.append([y,cnt+1])
        if(i==y):
            queue.append([x,cnt+1])
        if(pre>=1):
            queue.append([pre,cnt+1])
        if(nex<=n):
            queue.append([nex,cnt+1])
            
        

        
for i in range(1,n+1):
    bfs(i)


for i in range(1,n):
    print(cnt_l[i]//2)

Submission status: Time Limit Exceeded

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

def bfs(start):
    queue = [[start,0]]
    isNotSearched = [False]*(n+1)
    
    while(len(queue)>0):
        i,cnt = queue.pop(0)
        
        if(isNotSearched[i]):
            continue
        
        isNotSearched[i]=True
        cnt_l[cnt]+=1
        pre = (i-1)
        nex = (i+1)
        if(i==x):
            queue.append([y,cnt+1])
        if(i==y):
            queue.append([x,cnt+1])
        if(pre>=1):
            queue.append([pre,cnt+1])
        if(nex<=n):
            queue.append([nex,cnt+1])
            
        

        
for i in range(1,n+1):
    bfs(i)


for i in range(1,n):
    print(cnt_l[i]//2)

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split())
cnt_l = [0 for i in range(0,n)]
searched = [[False]*(n+1) for i in range(n+1)]

def bfs(start):
    queue = [[start,0]]
    isNotSearched = [False]*(n+1)
    
    while(len(queue)>0):
        i,cnt = queue.pop(0)
        
        if(isNotSearched[i]):
            continue
        
        isNotSearched[i]=True
        
        cnt_l[cnt]+=1
        pre = (i-1)
        nex = (i+1)
        if(i==x):
            queue.append([y,cnt+1])
        if(i==y):
            queue.append([x,cnt+1])
        if(pre>=1):
            queue.append([pre,cnt+1])
        if(nex<=n):
            queue.append([nex,cnt+1])
            
        

        
for i in range(1,n+1):
    bfs(i)


for i in range(1,n):
    print(cnt_l[i]//2)

Submission status: Time Limit Exceeded

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

# 入力はstringで入る．
# intにしたければ int(input())
# floatで受け取ると 1.0 になる．

import numpy as np

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

L = np.zeros((N,N))

for i in range(N-1):
    L[i,i+1] = 1
L[X-1,Y-1] = 1

for k in range(1,N):
    ind_k = np.where(L == k)

    for ind in range(0,len(ind_k[0])):
        i = ind_k[0][ind]
        j = ind_k[1][ind]

        if i+1 <= N-1:
            if L[i+1,j] == 0:
                L[i+1,j] = k+1

        if j-1 >= 0:
            if L[i,j-1] == 0:
                L[i,j-1] = k+1

        if i-1 >= 0:
            if L[i-1,j] == 0:
                L[i-1,j] = k+1

        if j+1 <= N-1:
            if L[i,j+1] == 0:
                L[i,j+1] = k+1




for k in range(1,N):
    cnt = 0

    for i in range(0,N-1):
        for j in range(i+1,N):
            if L[i,j] == k:
                cnt += 1
    
    print(cnt)

Submission status: Time Limit Exceeded

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

# 入力はstringで入る．
# intにしたければ int(input())
# floatで受け取ると 1.0 になる．

import numpy as np

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

L = np.zeros((N,N))

for i in range(N-1):
    L[i,i+1] = 1
L[X-1,Y-1] = 1

for k in range(1,N-1):
    for i in range(0,N-k-1):
        for j in range(i+1,N):
            if L[i,j] == k:
                
                if L[i+1,j] == 0:
                    L[i+1,j] = k+1
                if L[i,j-1] == 0:
                    L[i,j-1] = k+1

                if i-1 >= 0:
                    if L[i-1,j] == 0:
                        L[i-1,j] = k+1
                if j+1 <= N-1:
                    if L[i,j+1] == 0:
                        L[i,j+1] = k+1


for k in range(1,N):
    cnt = 0

    for i in range(0,N-1):
        for j in range(i+1,N):
            if L[i,j] == k:
                cnt += 1
    
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

ans = [0] * N
comb = list(itertools.combinations(range(1,N+1),2))


for i in range(len(comb)):
    if comb[i][0] <= X and comb[i][1] >= Y:
        k = comb[i][1] - Y + X - comb[i][0]  + 1
        ans[k] += 1
    elif comb[i][0] <= X:
        k = X - comb[i][0] + min(comb[i][1] - X, Y - comb[i][1]+1)
        ans[k] += 1
    elif comb[i][1] >= Y:
        k = comb[i][1] - Y + min(Y - comb[i][0], comb[i][0] - X + 1)
        ans[k] += 1
    else:
        k = min(comb[i][1] - comb[i][0], comb[i][0] - X + Y - comb[i][1] + 1)
        ans[k] += 1
for i in range(1,N):
    print(ans[i])

Submission status: Time Limit Exceeded

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

# 入力はstringで入る．
# intにしたければ int(input())
# floatで受け取ると 1.0 になる．

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

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

# スパース行列の作成
data = [1]*N

row = [int(x) for x in range(N-1)]
row.append(X-1)

col = [int(x+1) for x in range(N-1)]
col.append(Y-1)

S_Mat = csr_matrix((data, (row, col)), shape=(N,N)).toarray()
S_Mat += S_Mat.T

# 最短経路行列の取得
SP_Mat = dijkstra(S_Mat, directed=False, unweighted=True)

for k in range(N-1):
    print(int(np.sum(SP_Mat == k+1)/2))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import Counter
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
ans = np.zeros([N, N])
for i in range(N):
  for j in range(i, N):
    ans[i][j] = min(abs(j-i), abs(j-X)+1+abs(Y-i), abs(i-X)+1+abs(j-Y))
c = Counter(ans.reshape(-1))
for k in range(1, N):
  print(c[k])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n, x, y = map(int, input().split())
ans = []
for i in range(1, n+1):
    for j in range(1, n+1):
        ans.append(min(abs(j - i),
                       abs(x - i)+1+abs(j - y),
                       abs(y - i)+1+abs(j - x)))
ans_cnt = Counter(ans)
for i in range(1, n):
    print(ans_cnt[i] // 2)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int, input().split())
dst = [[0]*n]*n
ans = [0]*n

for i in range(n):
    for j in range(1,n-i):
        dst[i][j] = min(j, abs(x-1-i)+abs(y-1-(i+j))+1, abs(x-1-(i+j))+abs(y-1-i)+1)
        ans[dst[i][j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int, input().split())
dst = [[0]*n]*n
ans = [0]*n

for i in range(n):
    for j in range(n):
        dst[i][j] = min(abs(i-j), abs(x-1-i)+abs(y-1-j)+1, abs(x-1-j)+abs(y-1-i)+1)
        ans[dst[i][j]] += 1

for m in range(1,n):
    print(ans[m]//2)

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int, input().split())
dst = [[0 for j in range(n)] for i in range(n)]
ans = [0]*n

for i in range(n):
    for j in range(n):
        dst[i][j] = min(abs(i-j), abs(x-1-i)+abs(y-1-j)+1, abs(x-1-j)+abs(y-1-i)+1)
        ans[dst[i][j]] += 1

for m in range(1,n):
    print(ans[m]//2)

Submission status: Time Limit Exceeded

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

for i in range(n):
    for j in range(n):
        dst[i][j] = min(abs(i-j), abs(x-1-i)+abs(y-1-j)+1, abs(x-1-j)+abs(y-1-i)+1)

ans = [0]*n
for k in range(n):
    for l in range(n):
        ans[k] += dst[l].count(k)


for m in range(1,n):
    print(ans[m]//2)

Submission status: Time Limit Exceeded

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

dp = [[0]*N for _ in range(N)]
for i in range(N):
    for j in range(i+1, N):
        dp[i][j] = j-i
        dp[j][i] = j-i
dp[X-1][Y-1] = 1
dp[Y-1][X-1] = 1
for i in range(N):
    for j in range(N):
        if dp[i][j] > dp[i][X-1] + dp[X-1][j]:
            dp[i][j] = dp[i][X-1] + dp[X-1][j]
            dp[j][i] = dp[i][X-1] + dp[X-1][j]
        if dp[i][j] > dp[i][Y-1] + dp[Y-1][j]:
            dp[i][j] = dp[i][Y-1] + dp[Y-1][j]
            dp[j][i] = dp[i][Y-1] + dp[Y-1][j]

n_map = {}
for i in range(N):
    for j in range(i+1,N):
        if dp[i][j] not in n_map:
            n_map[dp[i][j]] = 1
        else:
            n_map[dp[i][j]] += 1
for i in range(1, N):
    if i not in n_map:
        print(0)
    else:
        print(n_map[i])

Submission status: Time Limit Exceeded

Solution code:
N,X,Y=map(int,input().split())
def dist(i,j):
  return min([j-i,abs(X-1-i)+1+abs(Y-1-j),abs(Y-1-i)+1+abs(X-1-j)])
dists = []
for i in range(N-1):
  for j in range(i+1,N):
    dists.append(dist(i,j))
for i in range(1,N):
  print(len([str(v) for v in dists if v == i]))

Submission status: Time Limit Exceeded

Solution code:
import queue

n,x,y = map(int,input().split())
l = [0] * n
for z in range(n):
    q = queue.Queue()
    q.put(z)
    d = [-1] * n
    d[z] = 0
    while(not q.empty()):
        i = q.get()
        if(d[i] > 0 and i > z):l[d[i]] += 1
        j = i + 1
        if(j < n):
            if(d[j] == -1):
                d[j] = d[i] + 1
                q.put(j)
        j = i - 1
        if(j >= 0):
            if(d[j] == -1):
                d[j] = d[i] + 1
                q.put(j)
        if(i == x - 1):
            j = y - 1
            if(d[j] == -1):
                d[j] = d[i] + 1
                q.put(j)
for i in range(1,n):print(l[i])

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,X,Y = map(int,input().split())
n = list(range(1,N+1))
l = []
for v in itertools.combinations(n,2):
  l.append(min(abs(Y-v[1]) + abs(X-v[0]) + 1,abs(X-v[1]) + abs(Y-v[0]) + 1,v[1] - v[0]))
for k in range(1,N):
  print(l.count(k))

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,X,Y = map(int,input().split())
n = list(range(1,N+1))
l = []
for v in itertools.combinations(n,2):
  if v[1] - v[0] > abs(Y-v[1]) + abs(X-v[0]) + 1:
    l.append(abs(Y-v[1]) + abs(X-v[0]) + 1)
  else:
    l.append(v[1] - v[0])
    
for k in range(1,N):
  print(l.count(k))

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,X,Y = map(int,input().split())
n = list(range(1,N+1))
m = []
l = []
for v in itertools.combinations(n,2):
  m.append(v)
for u in range((N*(N-1))//2):
  if m[u][1] - m[u][0] > abs(Y-m[u][1]) + abs(X-m[u][0]) + 1:
    l.append(abs(Y-m[u][1]) + abs(X-m[u][0]) + 1)
  else:
    l.append(m[u][1] - m[u][0])
    
for k in range(1,N):
  print(l.count(k))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,x,y = map(int, input().split())
dist = []
for v in itertools.combinations(range(1,n+1),2):  # sorted
    mins = min(v[1]-v[0], abs(x-v[0])+1+abs(v[1]-y))
    dist.append(min(mins, abs(y-v[0])+1+abs(v[1]-y)))
for i in range(1, n):
    print(dist.count(i))

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import deque,Counter
n,x,y = map(int,input().split())
route=[[10**10]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
  q=deque([i])
  j=i
  route[i][j]=0
  while q:
    j=q.pop()
    if j == y:
      if route[i][j]+1 < route[i][x]:
        route[i][x]=route[i][j]+1
        q.append(x)
    if j == x:
      if route[i][j]+1 < route[i][y]:
        route[i][y]=route[i][j]+1
        q.append(y)
    if 1 < j:#-1
      if route[i][j]+1 < route[i][j-1]:
        route[i][j-1]=route[i][j]+1
        q.append(j-1)
    if j < n:#+1
      if route[i][j]+1 < route[i][j+1]:
        route[i][j+1]=route[i][j]+1
        q.append(j+1)

ans=Counter(list(itertools.chain.from_iterable(route)))
for i in range(1,n):
  print(ans[i]//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,x,y = map(int,input().split())
route=[[10**10]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
  q=deque([i])
  j=i
  route[i][j]=0
  while q:
    j=q.pop()
    if j == y:
      if route[i][j]+1 < route[i][x]:
        route[i][x]=route[i][j]+1
        q.append(x)
    if j == x:
      if route[i][j]+1 < route[i][y]:
        route[i][y]=route[i][j]+1
        q.append(y)
    if 1 < j:#-1
      if route[i][j]+1 < route[i][j-1]:
        route[i][j-1]=route[i][j]+1
        q.append(j-1)
    if j < n:#+1
      if route[i][j]+1 < route[i][j+1]:
        route[i][j+1]=route[i][j]+1
        q.append(j+1)
ans=[0]*(n+1)
for i in range(1,n+1):
  for j in range(i+1,n+1):
    ans[route[i][j]]+=1
for i in range(1,n):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import heapq
# 単一始点最短経路。2地点間ではなく、始点が一つで各点へのコストを計算する
# eは隣接リストでe[v] = [(u1,cost1), (u2,cost2)]みたいな形を想定
# 辺の重みは正である必要がある
# O(ElogV)
def dijkstra(e,n,s):
    inf = 10**18
    d = [inf]*n
    d[s] = 0

    q = [(d[s],s)] # priority queueのソートキーが第一要素
    heapq.heapify([q])
    while len(q)>0:
        _,v = heapq.heappop(q)
        for u,c in e[v]:
            if d[v]+c>=d[u]:
                continue
            d[u] = d[v] + c
            heapq.heappush(q, (d[u],u))
    return d

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

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

res = [0]*n
for i in range(n):
    d = dijkstra(g,n,i)
    for j in range(i+1,n):
        res[d[j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

INF = float('inf')

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heappop(h)
        if dist[v] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for b, cost in G[v]:
            if dist[b] > dist[v] + cost:
                dist[b] = dist[v] + cost
                heappush(h, (dist[b], b))
    return dist

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

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

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

g[x-1].append((y-1, 1))
g[y-1].append((x-1, 1))

ans = [0] * n

for i in range(n):
    for d in dijkstra(n, g, i):
        ans[d] += 1

for item in ans[1:]:
    print(item // 2)

Submission status: Time Limit Exceeded

Solution code:
import heapq

INF = float('inf')

class Edge():
    def __init__(self, a, b, cost):
        self.a = a
        self.b = b
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.a, self.b, self.cost)

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heapq.heappop(h)
        if dist[v] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for e in G[v]:
            if dist[e.b] > dist[v] + e.cost:
                dist[e.b] = dist[v] + e.cost
                heapq.heappush(h, (dist[e.b], e.b))
    return dist

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

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

for i in range(n-1):
    g[i].append(Edge(i, i+1, 1))
    g[i+1].append(Edge(i+1, i, 1))

g[x-1].append(Edge(x-1, y-1, 1))
g[y-1].append(Edge(y-1, x-1, 1))

ans = [0] * n

for i in range(n):
    for d in dijkstra(n, g, i):
        ans[d] += 1

for item in ans[1:]:
    print(item // 2)

Submission status: Time Limit Exceeded

Solution code:
N,X,Y=list(map(int,input().split()))
G=[]
for i in range(1,N):
    G.append([i,i+1])
G.append([X,Y])
graph=[[] for i in range(N+1)]
for i in range(N):
    u,*v=G[i]
    v.sort()
    for j in v:
        graph[u].append(j)
        graph[j].append(u)
counter=[[] for i in range(N+1)]
for j in range(1,N+1):
    stack=[j]
    visited=[-1 for i in range(N+1)]
    visited[j]=0
    while stack:
        n=stack.pop(0)
        for i in graph[n]:
            n_n=i
            if visited[n_n]<0:
                visited[n_n]=visited[n]+1
                stack.append(n_n)
    for i,value in enumerate(visited):
        for k in range(1,N):
            if value==k:
                counter[k].append([j,i])
for i,value in enumerate(counter):
    if not (i==0 or i==N):
        print(int(len(value)/2))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter
N, X, Y = map(int, input().split())
G = [[0]*N for _ in range(N)]
for i in range(N-1):
    G[i][i+1] = 1
    G[i+1][i] = 1
G[X-1][Y-1] = 1
G[Y-1][X-1] = 1

def bfs():
    C = Counter([i+1 for i in range(N)])
    for i in range(N):
        color = ['W']*N
        D = [10**5]*N
        D[i] = 0
        color[i] = 'B'
        Q = deque([])
        Q.append(i)
        idx = 1
        while Q:
            q = Q.popleft()
            for j in range(N):
                if q == j:
                    continue
                if G[q][j] == 1 and color[j] != 'B':
                    color[j] = 'G'
                    D[j] = min(D[q]+1, D[j])
                    Q.append(j)
                color[q] = 'B'
        for d in D:
            C[d] += 1
    return C

C = bfs()

for k in range(1, N):
    ans = C[k]//2
    print(ans)