[PYTHON] AtCoder Grand Contest 048 Review

This time's results

Impressions of this time

It is a dreg that can only be solved quickly in the self-explanatory frame ... I was thinking about the C problem for a long time, but I couldn't solve it at all.

I was on Twitter just because I couldn't solve it. I feel like I can't do it in the future without a little more physical strength.

Problem A

I should have been able to avoid WA if I calmed down, which is disappointing. I think it was solved relatively quickly (in terms of time) as if you could see it in Kodofo.

First, if you only have $ a $, it's obviously -1. Similarly, if the given string is already larger than the string "atcoder", it is trivially 0.

Also, if there is a character other than $ a $, you can always enlarge it in dictionary order by bringing that character first. Here, if $ x $ is the index that has a character that is not $ a $ for the first time counting from the front, the minimum number of swaps required to bring that character first is $ x $. I would like to answer this, but if the character existing in ** $ x $ is larger than "t", it can be enlarged in lexicographic order by bringing it to the second character **, so once. You can lexicographically order a small number of times. On the contrary, if it is other than these two patterns, it will be the character string "aa ..." and will not be larger than "atcoder" in the dictionary order.

A.py

for _ in range(int(input())):
    s=input()
    if all(i=="a" for i in s):
        print(-1)
    else:
        n=len(s)
        if "atcoder"<s:
            print(0)
            continue
        for i in range(n):
            if s[i]!="a":
                if s[i]>"t":
                    print(i-1)
                else:
                    print(i)
                break

B problem

I speeded up various things and got the fastest code → Submit (I just gave up speeding up my code and speeded up yosupo's code I'm sorry yosupo.).

I had a short-circuited thought that it was DP-like but impossible, and I was thinking about the C problem all the time. Thinking calmly, DP is impossible, so I just look for another method. Since it seems difficult to decide by DP or honestly, I think that there is some kind of rule ** and consider it. Also, the typical solution of parentheses is to handle the cumulative sum, but it seems impossible because there are too many patterns.

Anyway, ** experiment ** for problems that do not apply to such a typical solution. Also, since parentheses are only valid if there are both opening and closing, it is good to ** pay attention to evenness ** (I do not consider this area during the contest, I will look at TL later I noticed ...).

Furthermore, it should be noted that (and) and [and] can be freely selected when selecting an index that becomes $ A, B $. Therefore, the positional relationship of the indexes is considered to be important. Then, if both the index that becomes $ A $ and the index that becomes $ B $ ** have the same number of even-numbered indexes and odd-numbered indexes, **, by arranging () and [] well, the subject must be You can create a parenthesis string that satisfies (Proof is [maspy's article](https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6 % 83% B3-2020-10-19agc048 # toc3)).

Also, since the above logic is rather vague (✳︎1), I think it is better to refer to the solution of editorial to be exact. Since it will be copied as it is, it will be omitted here.

Also, the method of selecting the set of indexes $ x \ _1, x \ _2,…, x \ _k $ where [] is placed in the editorial and considering the conditions ** is highly abstract. I think it's a general idea. During the contest, this ** consideration in the index set ** was completely omitted, so I regret it (✳︎2).

(✳︎1)… ** Consideration by experiment and consideration by abstraction ** are often omitted, so I would like to make it compatible.

(✳︎2)… I felt that it was necessary to stabilize the consideration because such an abstraction could be made if things were going well. First of all, it's really a mystery that I couldn't come up with the idea of ** making the assumption of a set of indexes ** in this problem.

B.py

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
s=sum(a)
e,o=[b[i]-a[i] for i in range(n) if i%2==0],[b[i]-a[i] for i in range(n) if i%2==1]
e.sort(reverse=True)
o.sort(reverse=True)
for i in range(n//2):
    if e[i]+o[i]>0:
        s+=e[i]+o[i]
    else:
        break
print(s)

C problem

As you can see from other people's commentary, it seems that you can do it with the scale method, but I could not think of a good implementation. I will come back to solve it someday.

After C problem

I will skip this time.