In this article, we will answer AtCoder Beginners Selection 10 + 1 questions in Python (3.8).

AtCoder is a competitive programming service originating in Japan. For more information, see @ drken's and @ e869120's articles

-Tips about AtCoder Contest -Guidelines for improving AtCoder, a competition pro taught by Red Coder [Beginner: Let's start competition pro]

Please see. Especially @drken

The 10 past questions summarized in the above were later adopted by the AtCoder formula as AtCoder Beginners Selection as exercises for beginners.

There are already some Python answers for AtCoder Beginners Selection, but this article was especially helpful. Thank you very much. In this article, I will give you an answer that feels "good" for you. If you compare them, you can see that they have been improved in detail.

As an aside, I think that the "goodness" of the code depends on the purpose and situation and is not a concept that can be clearly defined, but mainly

--Human circumstances: Readability --Machine side: Time complexity, space complexity

There are two directions, and I think there is often a trade-off between these two directions. This trade-off also appeared at the time of language selection before writing the code, and as you can see by comparing the answer in Python like this article with the answer in C ++ by drken, it is written in Python compared to C ++. The choice seems to be in a position to prioritize readability at the expense of computational complexity.

Conciseness is often mentioned as the "goodness" of code, but unless it's disposable code, conciseness is only valuable when it contributes to readability, and if it's less readable, it's better not to shorten the code. I personally think.

- PracticeA - Welcome to AtCoder

```
a = int(input())
b, c = map(int, input().split())
s = input()
print(a+b+c, s)
```

- ABC086A - Product

```
a, b = map(int, input().split())
print("Odd" if a%2 and b%2 else "Even")
```

--ʻA% 2 and b% 2`may be`

(a * b)% 2` as per the problem statement

- ABC081A - Placing Marbles

```
print(input().count("1"))
```

- ABC081B - Shift only

```
_ = input()
A = [*map(int, input().split())]
count = 0
while not any(a%2 for a in A):
A = [a/2 for a in A]
count += 1
print(count)
```

―― ʻa% 2` can indicate whether ʻa`

is odd, and ʻany (a% 2 for a in A)`can indicate`

bool` whether ʻA`

contains odd numbers. Numbers other than 0 are interpreted as `True`

, so ʻany` may be`

sum`, and for some reason `

sum` was faster, but for readability I chose ʻany`

.
――Let's solve it according to the problem statement. There is also a method of counting how many times each number is divided by 2 by reading how many 0s continue to the right in binary notation.

- ABC087B - Coins

```
import itertools as it
A, B, C, X = map(int, [input() for _ in range(4)])
count = 0
for a, b, c in it.product(range(A+1), range(B+1), range(C+1)):
if 500*a + 100*b + 50*c == X:
count += 1
print(count)
```

--The computational complexity of the full search is $ O (50 ^ 3) $, and even if it is overestimated as $ O (100 ^ 3) = O (10 ^ 6) $, it is a guideline for the upper limit of the time complexity $ O (10 ^ 8). ) It's well below $, so a full search is okay
--I think it's easier to read the nesting of `for`

statements by rewriting it with ʻitertools.product`.

- ABC083B - Some Sums

```
N, A, B = map(int, input().split())
print(sum(i for i in range(N+1) if A <= sum(map(int,str(i))) <= B))
```

--For ʻi` of "

- ABC088B - Card Game for Two

```
_ = input()
a = sorted(map(int,input().split()), reverse=True)
print(sum(a[::2]) - sum(a[1::2]))
```

--Sort all the cards and subtract the odd sum from the even sum.

- ABC085B - Kagami Mochi

```
N = int(input())
print(len(set(input() for _ in range(N))))
```

- ABC085C - Otoshidama

```
N, Y = map(int, input().split())
for n_10k in range(N+1):
for n_5k in range(N-n_10k+1):
n_1k = N - n_10k - n_5k
if n_10k*10000 + n_5k*5000 + n_1k*1000 == Y:
print(n_10k, n_5k, n_1k)
exit()
print(-1, -1, -1)
```

--` n_10k`

,` n_5k`

, `n_1k`

represent the number of 10,000-yen bills, 5,000-yen bills, and 1,000-yen bills, respectively.
--Thanks to the constraint that the total value of these three variables is `N`

, the search can be effectively done with two variables. Since the amount of calculation is $ O (2000 ^ 2) = O (8 \ times 10 ^ 6) $, which is less than the guideline of the upper limit of the amount of calculation, $ O (10 ^ 8) $, the whole search is okay.
--When you want to end a nested `for`

loop in the middle, if you try to break it with` break`

, it will be a little tricky code, so I think that you may end the program with ʻexit ()` like this.

```
S = input()
while S:
for x in ["dream","dreamer","erase","eraser"]:
if S.endswith(x):
S = S[:-len(x)]
break
else:
print("NO")
break
else:
print("YES")
```

――Which prefix is not uniquely determined, but which suffix is uniquely determined
--` for ... else ...`

and `while ... else ...`

of ʻelse` works when`

for`and`

while` end normally, and ends abnormally with`

break`. Does not work if

- ABC086C - Traveling

```
t0, x0, y0 = 0, 0, 0
for _ in range(int(input())):
t, x, y = map(int, input().split())
margin = (t-t0) - abs(x-x0) - abs(y-y0)
if margin < 0 or margin%2 != 0:
print("No")
break
t0, x0, y0 = t, x, y
else:
print("Yes")
```

――First of all, if `margin`

is negative, you cannot reach the target point. In addition, you can't get to the point you want if the `margin`

is odd because you don't have the option to rest.
--Instead of the batch version of the code that receives all the `(t, x, y)`

and then batch-processes it, the online version of the code that processes each `(t, x, y)`

sequentially in this way. it can

Recommended Posts