AtCoder Beginner Contest 093 Review of past questions

Time required

スクリーンショット 2020-04-04 16.48.55.png

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)

Recommended Posts

AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 085 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 051 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 119 Review of past questions
AtCoder Beginner Contest 151 Review of past questions
AtCoder Beginner Contest 075 Review of past questions
AtCoder Beginner Contest 110 Review of past questions
AtCoder Beginner Contest 117 Review of past questions
AtCoder Beginner Contest 070 Review of past questions
AtCoder Beginner Contest 105 Review of past questions
AtCoder Beginner Contest 112 Review of past questions
AtCoder Beginner Contest 076 Review of past questions
AtCoder Beginner Contest 089 Review of past questions
AtCoder Beginner Contest 079 Review of past questions
AtCoder Beginner Contest 056 Review of past questions
AtCoder Beginner Contest 087 Review of past questions
AtCoder Beginner Contest 067 Review of past questions
AtCoder Beginner Contest 093 Review of past questions
AtCoder Beginner Contest 046 Review of past questions
AtCoder Beginner Contest 123 Review of past questions
AtCoder Beginner Contest 049 Review of past questions
AtCoder Beginner Contest 078 Review of past questions
AtCoder Beginner Contest 081 Review of past questions
AtCoder Beginner Contest 047 Review of past questions
AtCoder Beginner Contest 060 Review of past questions
AtCoder Beginner Contest 104 Review of past questions
AtCoder Beginner Contest 057 Review of past questions
AtCoder Beginner Contest 121 Review of past questions
AtCoder Beginner Contest 126 Review of past questions
AtCoder Beginner Contest 090 Review of past questions
AtCoder Beginner Contest 103 Review of past questions
AtCoder Beginner Contest 061 Review of past questions
AtCoder Beginner Contest 059 Review of past questions
AtCoder Beginner Contest 044 Review of past questions
AtCoder Beginner Contest 083 Review of past questions
AtCoder Beginner Contest 048 Review of past questions
AtCoder Beginner Contest 124 Review of past questions
AtCoder Beginner Contest 116 Review of past questions
AtCoder Beginner Contest 097 Review of past questions
AtCoder Beginner Contest 088 Review of past questions
AtCoder Beginner Contest 092 Review of past questions
AtCoder Beginner Contest 099 Review of past questions
AtCoder Beginner Contest 065 Review of past questions
AtCoder Beginner Contest 053 Review of past questions
AtCoder Beginner Contest 094 Review of past questions
AtCoder Beginner Contest 063 Review of past questions
AtCoder Beginner Contest 107 Review of past questions
AtCoder Beginner Contest 071 Review of past questions
AtCoder Beginner Contest 064 Review of past questions
AtCoder Beginner Contest 082 Review of past questions
AtCoder Beginner Contest 084 Review of past questions
AtCoder Beginner Contest 068 Review of past questions
AtCoder Beginner Contest 058 Review of past questions
AtCoder Beginner Contest 043 Review of past questions
AtCoder Beginner Contest 098 Review of past questions
AtCoder Beginner Contest 114 Review of past questions
AtCoder Beginner Contest 045 Review of past questions
AtCoder Beginner Contest 120 Review of past questions