This time's results

Impressions of this time

I tried to get two questions at once by sticking to problem B, but I couldn't solve it. If I had solved it, I wouldn't have dreamed of the 200th place, so I'm very disappointed. I will work hard every day to pass this level of problems during the contest someday.

Also, I forgot the problem after reviewing the problem of Edufo's bacha that I solved last week, so if I solve it so that it will not happen in the future ** I will definitely review it by the next day ** I want to

Problem A

** I misunderstood the longest common prefix as the longest common substring **, and it was dangerous because it seemed to be a DP.

Since it is the longest common prefix, $ s [i], s [i + 1] $ should be different by the amount of $ a [i] $ given. Also, to make it easier to implement, ** only a or b ** is used in the string. Furthermore, since $ a [i] $ can be up to 50, the length of the output ** character string is unified to 50 **.

If the character string to be output at the $ i $ th is $ s [i] $, the $ s [i + 1] $ is different from the $ s [i] $ from the front to the $ a [i] $ th ( A should be b, b should be a), and $ a [i] + 1 $ should be the same from the third.

`A.py`


for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    s="a"*50
    ans=[s]
    for i in range(n):
        s=""
        for j in range(50):
            if j<a[i]:
                s+=ans[-1][j]
            else:
                if ans[-1][j]=="a":
                    s+="b"
                else:
                    s+="a"
        ans.append(s)
    for i in range(n+1):
        print(ans[i])

B1 problem, B2 problem

First of all, I thought I would save the number of seconds (or the height of the wave) at each point and perform DP, but ** B2 problem seemed to be too late, so $ O (N) I thought of a new policy ** that would be $.

Here, the time that can be at each point is $ 0 $ ~ $ min (k, l-d_i) $ and $ 2t-min (k, l-d_i) $ under $ mod \ 2K $. It becomes ~ $ 2t-1 $, and you can see that it is a ** continuous interval **. Also, since it takes 1 second to swim to the next point, ** Think about the common part of the section by shifting the section? I was thinking **, but I couldn't come up with the idea of combining the sections into one, or I forgot to think about the case where the section would be $ 2k $ (described later), so I had to go to the point of regret.

(From here, it will be a consideration after the contest.)

First of all, in the above, the section is divided into two, but if you set $ -min (k, l-d_i) $ ~ $ min (k, l-d_i) $, ** combine the sections into one **. I can. Furthermore, it is easy to handle because it becomes symmetric ** at ** 0.

Under this, consider the ** greedy algorithm **, which is the basis of the transitional problem (then DP). Here we will deal with the fifth sample. The input is as follows. (You can also see that the greedy algorithm needs to be done with ** $ O (N) $ **.)

7 2 3
3 0 2 1 3 0 1

In addition, the section from the above input is shown below. The time axis is from top to bottom.

Consider transitioning from the left side (closer to the beach) in the above figure, but an example is shown in the figure below. The red line shows how it takes 1 second to move to the next point in the transition.

Here, the red arrow goes diagonally downward, so the source of the ** arrow should be as high as possible ** (to fit within the interval). Also, if the section is $ 2k $, you can always stay there **, so you can leave at any time you like. Therefore, I tried to select the uppermost part of the section as the source of the arrow **, but it does not work for the green arrow. If the tip of the arrow is above the section like this, you can move the ** arrow so that the tip of the arrow is at the top of the section. By repeating this, if the tip of the arrow does not extend beyond the section in any section, Yes, and if there is even one section that protrudes, No. can be output.

`B.py`


#Greedily simulate
#To be as small as possible
for _ in range(int(input())):
    n,k,l=map(int,input().split())
    d=list(map(int,input().split()))
    seg=[]
    for i in range(n):
        if l-d[i]<0:
            print("No")
            break
        #Make sure the end is 0 or more
        seg.append([-min(l-d[i],k),min(l-d[i],k)])
    else:
        now=seg[0][0]
        for i in range(1,n):
            if seg[i]==[-k,k]:
                now=seg[i][0]
            else:
                now+=1
                if now<seg[i][0]:
                    now=seg[i][0]
                elif now>seg[i][1]:
                    print("No")
                    break
        else:
            print("Yes")

C problem

Is it good or bad because I passed it half with Esper?

In the following, the $ i $ th of $ a, b $ will be $ a_i, b_i $, and the larger (or smaller) alphabets will be in alphabetical order.

It was just a matter of greed. For the time being, $ a_i, b_i will be simulated by changing the $ different alphabet, but it must be ** moved in a direction that does not cause any loss **. Before that, you can't change from $ a $ to $ b $ when $ a_i> b_i $, because this problem can only make the alphabet bigger (otherwise it always changes from $ a $ to $ b $). You can).

First of all, since you can only make the alphabet larger, you can see that it seems better to start with the smaller alphabet ** $ a $ **. Here, when there is only one alphabet that you want to change for $ a $, you only need to change that alphabet, but when there are multiple alphabets that you want to change for ** $ a $ **, all the alphabets correspond to each. It's best to change to the smallest of the $ b $ alphabets you do. This is because there is no loss even if you change it **, and there is a possibility that you can create new ones with the same alphabet (this is the first pattern of the sample. ** ← If you don't understand, try the sample! **).

Since there are at most 20 alphabets that appear in $ a and b $, the simulation can be completed in about 20 times, and you can write a sufficiently fast program.

`C.py`


for _ in range(int(input())):
    n=int(input())
    a=list(input())
    b=list(input())
    for i in range(n):
        if a[i]>b[i]:
            print(-1)
            break
    else:
        s=sorted(list(set(a)|set(b)))
        ans=0
        for j in s:
            f=False
            x=set()
            for k in range(n):
                if a[k]==j and a[k]!=b[k]:
                    x.add(b[k])
                    f=True
            x=sorted(list(x))
            for k in range(n):
                if a[k]==j and a[k]!=b[k]:
                    a[k]=x[0]
            if f:ans+=1
        print(ans)

After D problem

I will skip this time

Codeforces Round # 659 (Div. 2) Bacha Review (8/5)