AtCoder Grand Contest 048 Review

This time's results

スクリーンショット 2020-10-22 10.07.12.png

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.

Recommended Posts

AtCoder Grand Contest 041 Review
AtCoder Grand Contest 048 Review
AtCoder Grand Contest 045 Review
AtCoder Grand Contest 044 Review
AtCoder Grand Contest 046 Review
AtCoder Beginner Contest 152 Review
AtCoder Regular Contest 105 Review
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 167 Review
AtCoder Beginner Contest 164 Review
AtCoder Beginner Contest 169 Review
AtCoder Beginner Contest 181 Review
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
AtCoder Beginner Contest 180 Review
AtCoder Beginner Contest 177 Review
AtCoder Beginner Contest 168 Review
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Regular Contest 106 Review
AtCoder Beginner Contest 176 Review
AtCoder Beginner Contest 175 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review
AtCoder Beginner Contest 161 Review
AtCoder Beginner Contest 170 Review
AtCoder Regular Contest 104 Review
AtCoder Beginner Contest 165 Review
AtCoder Beginner Contest 173 Review
AtCoder Beginner Contest 155 Review
AtCoder Beginner Contest 162 Review
AtCoder Grand Contest 040 Participation Report
AtCoder Grand Contest 047 Participation Report
AtCoder Grand Contest Past Question Challenge 2
AtCoder Grand Contest Past Question Challenge 1
AtCoder Beginner Contest 066 Review past questions
AtCoder Beginner Contest 177
yukicoder contest 259 Review
yukicoder contest 264 Review
AtCoder Beginner Contest 179
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180
yukicoder contest 261 Review
AtCoder Beginner Contest 173
yukicoder contest 266 Review
Atcoder Beginner Contest 153
yukicoder contest 263 Review
yukicoder contest 268 Review
AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 113 Review of past questions
AtCoder Beginner Contest 074 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 054 Review of past questions
AtCoder Beginner Contest 117 Review of past questions