[PYTHON] AtCoder Beginner Contest 093 Review of past questions

Time required

Impressions

D The problem was difficult ... I was scared of the 700-point problem, and it took a long time to review it. It's not as difficult as it sounds, so I'd like to have a solid awareness of ** verbalizing the process **.

Problem A

Sort and combine → The characters included in the character string are the same, so here it consists of only a, b, and c, so it is judged whether the length of the set is 3.

answerA.py

s=input()
print("Yes" if len(set(s))==3 else "No")

B problem

If you follow a → b in order, the maximum is $ 2 \ times10 ^ 9 $, so a → a + k-1 and b-k + 1 → b are output separately.

answerB.py

a,b,k=map(int,input().split())
if (b-a+1)>=2*k:
    for i in range(a,a+k):
        print(i)
    for i in range(b-k+1,b+1):
        print(i)
else:
    for i in range(a,b+1):
        print(i)

C problem

The operation of selecting one number and increasing it by two and the operation of selecting two numbers and increasing it by one have the same effect on the total total **. Also, in the case of the operation of increasing by 1, the ** even-odd relationship between the two selected numbers and the one not selected changes **, and in the case of the operation of increasing by two, the selected one and the two unselected numbers It means that the ** even-odd relationship between numbers does not change **. In other words, if the evenness of the three numbers is equal at the beginning, you only have to increase by 2 to increase the number to the maximum, and if the evenness of the three numbers is not equal, the two are equal and one is different. You can equalize the evenness of the three numbers by selecting and increasing by one. Also, the former is the code written during the test, and the latter is the code shortened by using the XOR operator. Also, as you can see from the Answer, if you follow the Writer solution, you can write even shorter code.

answerC.py

a,b,c=map(int,input().split())
if a%2==b%2 and b%2==c%2:
    x=sorted([a,b,c])
    print((x[2]-x[1])//2+(x[2]-x[0])//2)
elif a%2==b%2:
    a+=1
    b+=1
    x=sorted([a,b,c])
    print((x[2]-x[1])//2+(x[2]-x[0])//2+1)
elif b%2==c%2:
    b+=1
    c+=1
    x=sorted([a,b,c])
    print((x[2]-x[1])//2+(x[2]-x[0])//2+1)
else:
    c+=1
    a+=1
    x=sorted([a,b,c])
    print((x[2]-x[1])//2+(x[2]-x[0])//2+1)

answerC_shorter.py

a,b,c=map(int,input().split())
p=(a%2!=b%2)or(b%2!=c%2)
a,b,c=sorted([a+((a%2==b%2)^(a%2==c%2)),b+((b%2==a%2)^(b%2==c%2)),c+((c%2==a%2)^(c%2==b%2))])
print((c-a)//2+(c-b)//2+p)

D problem

I was scared when I first saw it ... The answer was written in a genius style, so it took me a while to understand it, but [Kenchon's blog](https://drken1215.hatenablog.com/entry/2018/09/08/ I was able to formulate my own way of thinking by referring to 195000) and kmjp's blog. (It's difficult, but as I proceeded with my consideration, I realized that it was a very good problem.)

First, we will proceed with the discussion based on this assumption because $ A \ leqq B $ does not lose its generality. Here, ** If the person in 1st to A-1st place in the first time takes B + A-1 to B + 1st place in the second time, , the product is AB from the condition of $ A \ leqq B $. It will be smaller. Similarly, if the 1st to A-1st place in the 2nd time take the B + A-1 to B + 1st place in the 1st time, these people will also have a product smaller than $ A \ times B $. Therefore, it can be seen that the solution to be sought is 2A-2 or more ** ( narrow down the range to be searched as much as possible !! **). From here, you should consider ** how many of the first A + 1 ~ B and second A ~ B-1 people will score less than AB **. First, when A = B, there is no such person, and when A = B-1, the first time is A + 1 and the second time is B-1 so the score is AB + (BA) + 1> Since it is AB, the score will not be lower than AB (exclude these two firmly **). From the above, we will consider under B> A + 1. Here, suppose that the person in the A + 1 to A + x position in the first time takes the A + x-1 to A position in the second time, respectively. The maximum value of the product at this time is $ (2A + x) // 2 \ times ((2A + x)-(2A + x) // 2) $ (✳︎1). Therefore, for $ 1 \ leqq x \ leqq BA $, $ (2A + x) // 2 \ times ((2A + x)-(2A + x) // 2) $ is less than AB ** the largest x You can find **, and such x can be found by ** binary search **. From the above, pay attention to A <= B for the answer you are looking for. 2A-2 when A = B or A = B-1 When A <B-1, 2A-2 + x (1 <= x <= B-A) (✳︎2)

(✳︎1)… $ x \ times y $ (x + y = k) (x, y, k are all positive integers) takes the maximum value (x, y) = (k // 2, kk It will be at the time of // 2). This is clear if you eliminate x or y and consider the maximum and minimum, or the symmetry of x and y.

(✳︎2)… Here, when x is 1 from B> A + 1, the first time is A + 1 and the second time is A, so A (A + 1) <AB holds for the score. Therefore, it can be said that x> = 1.

(✳︎3)… When "each" is written above, it means to combine in the reverse order. Also, at that time, it is written that it will be smaller than AB, but please actually calculate and check if it is smaller than AB by yourself. Also, by searching before and after the combination that becomes ** AB, you can find the combination that is smaller than the last minute **. (I couldn't do it during the Virtual Console, but while looking at other people's articles, I felt it was a natural idea.)

answerD.py

q=int(input())
def check(t,a,b):
    k=(2*a+t)//2
    return k*(2*a+t-k)<a*b

for i in range(q):
    a,b=sorted(map(int,input().split()))
    if a==b or a==b-1:
        print(2*a-2)
        continue
    l,r=1,b-a
    while l+1<r:
        t=(l+r)//2
        if check(t,a,b):
            l=t
        else:
            r=t
    if check(r,a,b):
        print(2*a-2+r)
    elif check(l,a,b):
        print(2*a-2+l)
    else:
        print(2*a-1)