AtCoder Beginner Contest 006 So let's start with 006 of AtCoder Beginner Contest! (Please keep in mind the feeling that you shouldn't start with 001 ...)

Problem-A

The number N is given. Output YES if N contains 3 or is divisible by 3, otherwise output NO.

`A.py`


N = int(input())
if N % 3 == 0:
    print("YES")
else:
    print("NO")

Is it a slightly simpler version of the FizzBuzz problem? Don't forget to insert a line break when answering.

Problem-B

There is a tribonacci sequence. This sequence is the sum of the numbers up to three. Strictly speaking

a_1=0, a_2=0, a_3=1 \\
a_n=a_{n-1}+a_{n−2}+a_{n−3}

Is defined as. Find the remainder of the nth term of this sequence, $ a_n $ divided by 10007.

`B.py`


n = int(input())
a, b, c = 0, 0, 1

for i in range(n-1):
    a, b, c = (b % 10007), (c % 10007), ((a+b+c) % 10007)
print(a)

I'm vulnerable to this kind of problem of dividing by a large number (such as 10 ^ 7) and displaying the remainder. Recently, I've been taking measures to calculate the final answer each time instead of dividing it by a large number. .. Another way of thinking about this problem is to branch to output 0 in the case of $ a_1 $ and $ a_2 $, and in other cases, turn a for statement with the number of loops set to n-3. .. (I'm going to upload it to git.)

Problem-C

"There are N humans in this city. There are three types of humans: adults, old people, and babies. The total number of legs of humans in this city is M, two adult legs, and old people. Assuming 3 legs and 4 baby legs, answer one possible combination of human beings. "

`C.py`


n, m = map(int, input().split())

for a in range(n+1):
  b = 4*n -2*a - m
  c = n -a -b
  if b >= 0 and c >= 0:
    print(a, " ", b, " ", c)
    break
else:
  print("-1 -1 -1")

There are various things written

a+b+c=N \\
2a+3b+4c=M

It is equivalent to solving the simultaneous equations of. I may use my knowledge of mathematics unexpectedly, so I want to be careful not to get it out of my head.

By the way, when I referred to the solution method, I saw an xrange function instead of a range function. I saw it for the first time, so I found an article like this when I looked it up.

Changes from Python 2 to Python 3.0

I see, it was abolished without your knowledge. I didn't know it at all as I used it from python3. It might be a good idea to take this opportunity to study iterators.

Problem-D

There are N cards with numbers written on them. The following operations can be performed on this bundle of cards (deck). Remove one card from the deck and insert it anywhere. From top to bottom of the deck, find the minimum number of operations required to sort the cards in ascending order.

`D.py`


import bisect

n = int(input())
cards = [int(input()) for i in range(n)]

sort_after_cards = [0]
for card in cards:
  if sort_after_cards[-1] < card:
    sort_after_cards.append(card)
  else:
    index = bisect.bisect_left(sort_after_cards, card)
    sort_after_cards[index] = card    
print(n - len(sort_after_cards) +1)

The image is like drawing one card on the deck to make another deck. And in order to make it in ascending order, a larger number than the original card must come under the deck, so if a smaller number comes, let's return it to the position of true love by binary search. Eventually, an ascending deck list will be created that excludes the exchanged cards. If you just want to sort in ascending order, you can use sort or sorted.

in conclusion

For the first time, I had a hard time understanding. In particular, I feel that C and D problems are required to reduce the amount of calculation and improve efficiency by making full use of mathematical thinking and algorithms. In recent contests, I'm in good shape and can only solve the C problem, so I'll practice a lot and try to come up with various ideas.

[PYTHON] At Coder (2020/09/08)

Problem-A

A.py