result

Impressions

Since yesterday, I decided to do Kodofo bacha every day as much as possible to increase the amount of solving. AtCoder's D ~ F is blocked by a problem that seems to be solved a little more every time, so solve div2 or edufo of Kodofo near the level band. ABC was fine, but I filled in about 70% of the problems and felt that there were few problems that were at the level, so I decided to solve Kodofo.

This time, I misread the C and D questions and used them for a long time, so I couldn't solve the D question during the contest. Neither is difficult, so if you don't know, try to reread the problem **.

Problem A

Even with this problem, the sample did not match because I made a mistake in outputting **. For the given sequence $ p $, if there is even one ** inversion of increase / decrease (extreme value) **, the number is recorded and output together with before and after that. Also, when there is no extremum, the entire sequence decreases or increases monotonically, so there is no set of $ i, j, k $ that satisfies the subject, and No should be output.

`A.py`


#misreading(Output mistake)
t=int(input())
for _ in range(t):
    n=int(input())
    p=list(map(int,input().split()))
    for i in range(1,n-1):
        if p[i-1]<p[i] and p[i]>p[i+1]:
            print("Yes")
            print(i,i+1,i+2)
            break
    else:
        print("No")

Problem B

The order of rock-paper-scissors changes depending on the pos, but ** $ c_1c_2… c_n $ will each play $ n $ times against another hand ($ s_1s_2… s_n $) ** (** Paraphrase of subject and object) **). Therefore, for $ c_i $, you should choose the winning move against $ s_1s_2… s_n $. If there are many, "R" and "P" should be the most, and if there are many, "S" should be used. Also, this can be said for any $ i $, so you can output a string with the length of the number of rock-paper-scissors.

`B.py`


t=int(input())
for i in range(t):
    S=input()
    l=len(S)
    r=S.count("R")
    s=S.count("S")
    p=S.count("P")
    m=max(r,s,p)
    if m==r:
        print("P"*l)
    elif m==s:
        print("R"*l)
    else:
        print("S"*l)

C problem

I thought that there shouldn't be any surplus people who misread it, but if you look closely, it says that there may be surplus people. It is a reflection.

In this case, you can combine the programmers with the highest skill so that they exceed ** $ x $ in order, and there is a possibility that some programmers will not exceed $ x $ even if they are combined at the end. , Such combinations can be ignored.

Also, with this greedy algorithm, ** the smallest number of people can form a group **, so it can be said that the number of groups is the largest.

`C.py`


t=int(input())
for _ in range(t):
    n,x=map(int,input().split())
    a=sorted(list(map(int,input().split())),reverse=True)
    now=[100000000000,0]
    for i in range(n):
        now=[min(now[0],a[i]),now[1]+1]
        if now[0]*now[1]>=x:
            d.append(now)
            now=[100000000000,0]
    print(len(d))

D Problem

I also misread this and made it difficult to think that ** Berserk can specify two discontinuous people **. Actually, it's not that difficult because there are only two people in a row.

People who are continuous can be defeated, so pay attention to the part where the person who defeats is continuous ** (hereinafter referred to as the continuous part). Also, if you want to defeat the last remaining person in a continuous part with Berserk, one of the non-defeated people ($ L $ and $ R $) who sandwiches that part must have ** more power than that person * * So, we need the information of the person who sandwiches it.

Here, if the length of the continuous part is divided by $ k $ and a remainder appears, it is necessary to reduce the remainder by Berserk, and at this time, the person with the maximum power in the continuous part ($ X $) It is best to select and defeat the people located on both sides of it.

Also, if $ X $ has a higher power than $ L $ and $ R $, you need to ** defeat that $ X $ with Fireball **, and Fireball cannot be used ($ \ leftrightarrow $ length of continuous part). When (is shorter than $ k $) and when the order of the remaining people is different, the subject is not satisfied, so -1 should be output.

The above is implemented and it looks like the following, but since I couldn't think about it very well, the code becomes a little messy.

`D.py`


n,m=map(int,input().split())
x,k,y=map(int,input().split())
a=list(map(int,input().split()))
c=list(map(int,input().split()))
b=set(c)
d=[]
now=[]
for i in range(n):
    if a[i] not in b:
        now.append(i)
        if i==n-1:
            d.append([now[0]-1,a.index(max(a[now[0]:now[-1]+1])),now[-1]+1])
    else:
        if now!=[]:
            #Edge and max index(The edge is-1,n can be)
            d.append([now[0]-1,a.index(max(a[now[0]:now[-1]+1])),now[-1]+1])
            now=[]
#The one whose position is not in order
now=0
lc=len(c)
for i in range(n):
    if a[i]==c[now]:
        now+=1
        if now==lc:
            break
else:
    exit(print(-1))
l=len(d)
ans=0
for i in range(l):
    e=d[i]
    f=e[2]-e[0]-1
    if e[0]==-1:
        m=a[e[2]]
    elif e[2]==n:
        m=a[e[0]]
    else:
        m=max(a[e[0]],a[e[2]])
    if m>a[e[1]]:
        ans+=(f%k*y)
        ans+=min((f//k)*x,(f//k)*k*y)
    else:
        if f<k:exit(print(-1))
        ans+=(f%k*y)
        #I have to defeat them once with k
        ans+=x
        ans+=min((f//k-1)*x,(f//k-1)*k*y)
print(ans)

After the E problem

I can't solve this time.

Educational Codeforces Round 91 Bacha Review (7/28)