[PYTHON] AtCoderBeginnerContest161 Review & Summary (second half)

AtCoder ABC161 This is a summary of the AtCoder Beginner Contest 161 questions that were held on 2020-04-04 (Sat), starting with question A and taking into consideration the considerations. The second half deals with the DEF problem. Click here for the first half. The problem is quoted, but please check the contest page for details. Click here for the contest page Official commentary PDF

D problem Lunlun Number

Problem statement When the positive integer $ X $ meets the following conditions, $ X $ is said to be a run-run number. ・ When $ X $ is expressed in decimal notation (without leading zero), the absolute value of the difference is 1 or less for the values of any two adjacent digits. For example, 1234, 1, 334 are run-run numbers, but 31415, 119, 13579 are not run-run numbers. A positive integer $ K $ is given. Find the K-th run-run number from the smallest.

It was $ 1 \ leq K \ leq 10 ^ 5 $, so I thought it would be enough to count the run-run numbers from the smallest one with a recursive function, and I was very happy to solve it when I wrote the program. When I solved it, it was run-run, but when I saw the problem, it didn't run at all. I will post the submitted code as it is.

abc161d.py

def check(mae, keta, count, k):
    if keta == 0:
        count += 1
        if count == k:
            ans = mae
        else:
            ans = -1
        return count, ans
    if mae == 0:
        count, ans = check(0, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
        count, ans = check(1, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
    elif mae == 9:
        count, ans = check(8, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
        count, ans = check(9, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
    else:
        for i in [-1, 0, 1]:
            count, ans = check(mae + i, keta - 1, count, k)
            if ans >= 0:
                ans += mae * 10 ** keta
                return count, ans
    return count, ans

k = int(input())
if k < 10:
    print(k)
else:
    count = 9
    flag = 0
    for keta in range(2, 1000):
        for sento in range(1, 10):
            count, ans = check(sento, keta - 1, count, k)
            if ans >= 0:
                print(ans)
                flag = 1
                break
        if flag == 1:
            break

When I wrote the program, I came up with a recursive function because I thought that if I wanted to make a run-run number with $ m $ digits, I could make it by deciding the number from the highest position on the tree diagram. For example, the 3-digit run-run number 1 ** starting from 1 can be obtained as shown in the figure below. It should be noted that there are two types of branches at 0 and 9, and if you can pay attention to that, you can enter the variable for counting and the information on what digit you are currently thinking about in the function. If you greedily search for it, you can find the answer in time.

E problem Yutori

Problem statement Takahashi decided to work on $ K $ of the $ N $ days starting tomorrow. Given the integer $ C $ and the string $ S $, choose a working day that meets the following two conditions. ・ If you work one day, you will not work for the $ C $ day immediately after that. ・ When the $ i $ character of $ S $ is $ x $, it will not work after $ i $ days from today. Please be sure to ask for all the days when Takahashi works.

I was in a hurry at the time of the contest, so I couldn't correctly read the meaning of "When the $ i $ character of $ S $ is $ x $, it won't work in $ i $ days from today", and I immediately went to the next problem. .. After reading the commentary, I noticed a mistake in reading, but even if I didn't make a mistake, I think I couldn't solve it, so I learned one more thing. I wondered if I had the experience to notice that it was already written in the commentary. Code of Kiri8128 who passed AC at an early stage in the submitted code I referred to 11525396). @ kiri8128

abc161e.py

n, k, c = map(int, input().split())
S = [1 if a == "o" else 0 for a in input()]
count = 0
X = [0] * n
Y = [0] * n
i = 0
while i < n:
    if S[i]:
        count += 1
        X[i] = 1
        # print(i+1)
        i += c + 1
    else:
        i += 1
if count > k:
    exit()
i = n - 1
while i >= 0:
    if S[i]:
        Y[i] = 1
        # print(i+1)
        i -= c + 1
    else:
        i -= 1
for i in range(0, n):
    if X[i] and Y[i]:
        print(i + 1)

It was helpful for how to receive S. After that, I don't know how to come up with a solution when I see this problem in production, but I feel that it is important to solve many problems anyway, so I will devote myself to it. I commented out print (i + 1) for those who couldn't understand it even after reading the explanation, so if you uncomment it and solve the example, you will see various things. Input example 1 shown below is taken as an example.

11 3 2 
ooxxxoxxxoo

The print output in the first for statement is 1, 6, 10 and the print output in the second for statement is 11, 6, 2. Therefore, the answer is 6. If you try these in the same way for other examples, it will be easier to understand why the answer comes out. (I couldn't come up with a good explanation in the text (sweat))

F problem Division or Subtraction

Problem statement Given a positive integer $ N $. Determine an integer $ K $ that is greater than or equal to 2 and less than or equal to $ N $, and repeat the following operation until $ N $ is less than $ K $. ・ Operation: When $ N $ is divisible by $ K $, replace $ N $ with $ N / K $. If not, replace $ N $ with $ N−K $. How many ways are there to determine $ K $ so that $ N $ will eventually become 1?

At the time of the contest, I quickly rounded up the E problem and challenged the F problem. The reason is that input example 2 is 3141, and $ K $ notices that 3141 and 3140 are included in the answer first, and that 3140 is the answer is around $ N- around 1570, 785 ... It turns out that all divisors of 1 $ are included in the answer. 「2, 4, 5, 10, 20, 157, 314, 628, 785, 1570」 From here, I don't know how to count that $ K = 2 $ is included in 6 of input example 1, and the time is over (sweat). With a little thought, I just checked to see if the divisor of $ N $ met the condition. Since the $ K $ candidate is a divisor, it can be divided until it can be divided.

abc161f.py

def make_divisors(n):
    divisors = []
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

n = int(input())
if n == 2:
    print(1)
elif n == 3:
    print(2)
elif n == 4:
    print(3)
else:
    count = 2
    check_list = make_divisors(n-1)
    count += len(check_list)
    check_list = make_divisors(n)
    for k in check_list:
        temp_n = n // k
        while(True):
            if temp_n % k == 0:
                temp_n = temp_n // k
            elif temp_n % k == 1:
                count += 1
                break
            else:
                break
    print(count)

Since it is chicken, when n is small, it is divided into cases, but it should be possible to solve it without doing it. The breakdown of count = 2 is $ N $ and $ N-1 $. I want to be able to solve this F problem in time, so I will do my best to continue.

Thank you for reading the second half to the end.