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. ABC161D.jpg 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.

Recommended Posts

AtCoderBeginnerContest178 Review & Summary (second half)
AtCoderBeginnerContest161 Review & Summary (second half)
AtCoderBeginnerContest164 Review & Summary (second half)
AtCoderBeginnerContest176 Review & Summary (second half)
AtCoderBeginnerContest168 Review & Summary (second half)
AtCoderBeginnerContest169 Review & Summary (second half)
AtCoderBeginnerContest166 Review & Summary (second half)
AtCoderBeginnerContest171 Review & Summary (second half)
AtCoderBeginnerContest174 Review & Summary (second half)
AtCoderBeginnerContest173 Review & Summary (second half)
AtCoderBeginnerContest177 Review & Summary (second half)
AtCoderBeginnerContest175 Review & Summary (first half)
AtCoderBeginnerContest164 Review & Summary (first half)
AtCoderBeginnerContest169 Review & Summary (first half)
AtCoderBeginnerContest174 Review & Summary (first half)
AtCoderBeginnerContest173 Review & Summary (First Half)
AtCoderBeginnerContest165 Review & Summary (first half)
AtCoderBeginnerContest170 Review & Summary (first half)
AtCoderBeginnerContest167 Review & Summary (first half)
AtCoderBeginnerContest177 Review & Summary (first half)
AtCoderBeginnerContest168 Review & Summary (first half)
AtCoderBeginnerContest178 Review & Summary (first half)
AtCoderBeginnerContest171 Review & Summary (first half)
AtCoderBeginnerContest166 Review & Summary (first half)
AtCoderBeginnerContest161 Review & Summary (first half)
AtCoderBeginnerContest172 Review & Summary (first half)
AtCoderBeginnerContest176 Review & Summary (first half)
AtCoderBeginnerContest180 Review & Summary
AtCoderBeginnerContest181 Review & Summary
AtCoderBeginnerContest182 Review & Summary
AtCoderBeginnerContest183 Review & Summary
AtCoderBeginnerContest179 Review & Summary
Django Girls Tutorial Summary First Half