This time's results

Impressions of this time

I misread it again as I did last time. See C problem for details. It is inefficient to solve only 3 questions over 2 hours, so we will gradually increase the number of problems that can be solved.

Problem A

If the shortest common subsequence of $ a $ and $ b $ exists, the length will be 1, so you can output one of the common characters of $ a $ and $ b $. Also, here you can find out if there are any characters contained in $ a $ that are also contained in $ b $, and if one of them has a set structure, you can check with $ O (N) $.

`A.py`


t=int(input())
for _ in range(t):
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    b=set(map(int,input().split()))
    for i in a:
        if i in b:
            print("YES")
            print(f"1 {i}")
            break
    else:
        print("NO")

Problem B

First of all, it is a game problem, so ** pay attention to the final state **. When paying attention to the final state, all the mountains will be 0, but just before that, only the last mountain will remain as it is.

What I paid attention to here was whether to leave each mountain or not (** binarization! **). That is, if the number of stones in each mountain is greater than 1, the player who chooses that mountain cannot give his opponent a choice. This can be done by leaving only one stone from the mountain and handing it to the other party.

However, ** if the number of stones in the mountain is originally one **, the player who chooses the mountain has no choice but to remove that one stone. Therefore, when operating on a mountain with more than 1 stone, you can adjust whether to leave one stone or remove all stones from that mountain depending on whether the number of stones in the next mountain is one or not. Also, if a mountain with only one stone continues from the first mountain, the player has no choice, so the player who can choose a mountain without one stone for the first time has the choice and wins. Can be said to be possible

`B.py`


t=int(input())
for i in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=["First","Second"]
    ans=0
    for i in range(n):
        if a[i]!=1:
            ans=i
            break
    else:
        ans=n-1
    print(s[ans%2])

C1 problem

I misread it completely. I thought that the inversion operation was the entire character string, but when I often saw the problem statement, it was written that it was done only with the prefix that I chose. In Codeforces, I read the original English text as it is, and there are many mistakes, so I would like to focus on ** eliminating such non-essential mistakes **.

As for the problem, the first policy is to think about what happens to the $ i $ th bit (** abstraction **). At this time, consider the case of inverting only the $ i $ th bit, but here it is possible by selecting in the order of $ i $ → $ 1 $ → $ i $. Also, in this simulation, it will be about $ 3n $ times. The first $ i $ operation changes the $ i $ th element to the $ 1 $ th element, so the $ 1 $ operation reverses only the originally $ i $ th element at the $ 1 $ th element, and finally $ Think of it as undoing with i $. If you don't know, I think you should show it. I feel that such problems can only be solved discoverably, so I think the important thing is ** familiarity and experimentation **.

`C1.py`


#misreading…
t=int(input())
for _ in range(t):
    n,a,b=int(input()),input(),input()
    ans=[]
    for i in range(n):
        if a[i]!=b[i]:
            ans.append(f"{i+1}")
            ans.append("1")
            ans.append(f"{i+1}")
    print(f"{len(ans)}"+" "+" ".join(ans))

After the C2 problem

I will skip this time

Codeforces Round # 658 (Div. 2) Bacha Review (7/29)