Daily AtCoder # 27 in Python

Introduction

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 ismin(Do not use shortcuts, use shortcuts)Think about it. If you don't use shortcutsj-iWill be. When using|y-j|+|x-i|+1Will be. In the first term j-Distance between Y, X in the second term-Find the distance between i and add the shortcut distance 1.

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.

Summary

It was easier than I thought it was a graph. see you. good night

Recommended Posts

Daily AtCoder # 36 in Python
Daily AtCoder # 2 in Python
Daily AtCoder # 32 in Python
Daily AtCoder # 6 in Python
Daily AtCoder # 18 in Python
Daily AtCoder # 53 in Python
Daily AtCoder # 33 in Python
Daily AtCoder # 7 in Python
Daily AtCoder # 24 in Python
Daily AtCoder # 37 in Python
Daily AtCoder # 8 in Python
Daily AtCoder # 42 in Python
Daily AtCoder # 21 in Python
Daily AtCoder # 17 in Python
Daily AtCoder # 38 in Python
Daily AtCoder # 54 in Python
Daily AtCoder # 15 in Python
Daily AtCoder # 47 in Python
Daily AtCoder # 13 in Python
Daily AtCoder # 45 in Python
Daily AtCoder # 30 in Python
Daily AtCoder # 40 in Python
Daily AtCoder # 5 in Python
Daily AtCoder # 28 in Python
Daily AtCoder # 39 in Python
Daily AtCoder # 20 in Python
Daily AtCoder # 19 in Python
Daily AtCoder # 52 in Python
Daily AtCoder # 3 in Python
Daily AtCoder # 14 in Python
Daily AtCoder # 50 in Python
Daily AtCoder # 43 in Python
Daily AtCoder # 22 in Python
Daily AtCoder # 49 in Python
Daily AtCoder # 27 in Python
Daily AtCoder # 1 in Python
Daily AtCoder # 25 in Python
Daily AtCoder # 16 in Python
Daily AtCoder # 12 in Python
Daily AtCoder # 48 in Python
Daily AtCoder # 23 in Python
Daily AtCoder # 34 in Python
Daily AtCoder # 51 in Python
Daily AtCoder # 31 in Python
Daily AtCoder # 46 in Python
Daily AtCoder # 35 in Python
Daily AtCoder # 9 in Python
Daily AtCoder # 44 in Python
Daily AtCoder # 41 in Python
Atcoder ABC164 A-C in Python
atCoder 173 Python
Atcoder ABC167 A-D in Python
Atcoder ABC165 A-D in Python
Atcoder ABC166 A-E in Python
Atcoder ABC169 A-E in Python
AtCoder ABC177 A-D in python
[Python] Basic knowledge used in AtCoder
Quadtree in Python --2
Python in optimization
CURL in python
Metaprogramming in Python