Last time Yesterday's ABC161 was +65. Next, it will turn brown in about 1200 parfaits.
#27
Problem 843diff
1TLE。
** Thoughts **
It was a problem that I couldn't solve in production. If I thought it was a graph, I could solve it without thinking like a graph.
$ (i, j) (i, j \ in Z, 1 \ leq i <j \ leq N) It is a problem to find the number of the shortest distances of $ i, j $ when considering the point.
That's easy, but in this case X-There is an edge that can be moved at a distance of 1 between Y. So the shortest distance is
n, x, y = map(int,input().split())
ans = [0]*(n-1)
for i in range(1,n+1):
for j in range(i+1,n+1):
ans[min(j-i,abs(x-i)+1+abs(y-j))-1] += 1
for k in range(n-1):
print(ans[k])
At first, I append to ans and count at the end, but if it is count, it becomes O (N) and the amount of calculation increases and TLE occurs. Therefore, we add +1 to ans [distance] and output it at the end.
It was easier than I thought it was a graph. see you. good night
Recommended Posts