AtCoderBeginnerContest174 Review & Summary (second half)

AtCoder ABC174 This is a summary of the problems of AtCoder Beginner Contest 174, which was held on 2020-08-02 (Sun), in order from problem A, taking into consideration the consideration. The second half deals with the DE 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 Alter Altar

Problem statement The altar is enshrined with $ N $ stones lined up from left to right. The color of the $ i $ th $ (1 \ leqq i \ leqq N) $ stone from the left is given as the letter $ c_i $, which is red when $ c_i $ is'R'and white when it is'W'. You can perform the following two operations as many times as you like in any order. ・ Select $ 2 $ stones (not necessarily next to each other) and replace them. ・ Select $ 1 $ stones and change the color of the stones (red for white, white for red). According to the fortune-teller, the white stone placed to the left of the red stone causes disaster. How many operations is required to reach the state without such white stones?

When I read the problem, I thought that I could solve it just by "Selecting $ 2 $ stones (not necessarily next to each other) and replacing them." By not using "・ Select $ 1 $ stones and change the color of the stones (red for white, white for red)", the state without the final answer is fixed. For example, at $ N = 9 $ 'WRWWWRRWR' Input is 'RRRRWWWWW' The answer can be given by considering the minimum operation so that. This is the number of red stones included in the input $ N_r $, and it can be seen that the number of white stones from $ 1 $ to $ N_r $ th in the input is the required number of operations. (In the case of the example, $ 3 $ is the answer because it is the number of white stones in the $ 1 $ to $ 4 $ th'WRWW'of'WRWWWRRWR'.)

abc174d.py

n = int(input())
mozi = input()
a_list = []
for i in range(n):
    if mozi[i] == 'W':
        a_list.append(0)
    else:
        a_list.append(1)
r_count = sum(a_list)
print(r_count - sum(a_list[0:r_count]))

E problem Logs

Problem statement There are $ N $ logs, each of which is $ A_1, A_2, ⋯, A_N $. You can cut these logs up to a total of $ K $ times. If you cut a log of length $ L $ from one end at the position of $ t (0 <t <L) $, it will be divided into logs of length $ t, L−t $. After cutting the log up to a total of $ K $, find the minimum length of the longest log and output the value rounded up to the nearest whole number.

I didn't notice the binary search, and I was greedily searching from $ x = 1 $, so I couldn't solve it during the contest.

abc175e.py

n, k = map(int, input().split())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)
if k == 0:
    print(a_list[0])
else:
    start = 1
    end = a_list[0]
    x = (start + end) // 2 
    while True:
        k_count = 0
        flag = 1
        for a in a_list:
            temp_k = 0
            if a % x == 0:
                temp_k = a // x - 1
            else:
                temp_k = a // x
            if temp_k == 0:
                flag = 1
                break
            k_count += temp_k
            if k_count > k:
                flag = 0
                break
        if flag == 1:
            end = x
        if flag == 0:
            start = x
        next_x = (start + end) // 2
        if next_x == x:
            if flag == 1:
                print(x)
            if flag == 0:
                print(x + 1)
            break
        x = next_x

Thank you for reading the second half to the end.