AtCoder Beginner Contest 128

参加記 atcoder

はい。
https://atcoder.jp/contests/abc128
ooo--- 943(+1)でした。無駄にWAはなし。まぁこんなものでしょう。

A - Apple Pie

PyPy3

a,p=map(int,input().split())
print((a*3+p)//2)

場合分けして計算する。

B - Guidebook

PyPy3

n=int(input())
ans=[]
for i in range(n):
    s,p=map(str,input().split())
    ans.append((s,int(p)*-1,i+1))
ans.sort()
for i in ans: print(i[2])

本番中はすごい無駄に苦戦して凄い無駄に行数書いた。でもそんな必要なかったですね。

C - Switches

PyPy3

def sol():
    n,m=map(int,input().split())
    k=[]
    for i in range(m):
        l=[int(i) for i in input().split()]
        k.append([l[j]-1 for j in range(1,l[0]+1)])
    p=[int(i) for i in input().split()]
    ans=0
    for i in range(2**n):
        s=bin(i)[2:]
        s="0"*(n-len(s))+s
        s=s[::-1]
        for a,j in enumerate(k):
            chk=f=0
            for x in j:
                if s[x]=="1":
                    chk+=1
            if chk%2!=p[a]:
                f=1
                break
        if f==0:
            ans+=1
    print(ans)
 
if __name__=="__main__":
    sol()

制約をよく見て全探索すればいいっぽいと気づいたし、01の作り方も過去の失敗を踏まえて書いて一発ACしたのでよかった。01でスイッチのon/off状態の全パターン作ってそれぞれパターンに対してそれぞれの電球の番目のスイッチのonの個数数える。数えたらpを見て偶数個奇数個を確認して〜で全部調べて数えるとACします。多分。

D - equeue

PyPy3

n,k=map(int,input().split())
v=[int(i) for i in input().split()]
ans=0
chk=[0,0]
c=[]
for x in range(min(n,k)+1):
    if x>0:
        chk[0]+=v[x-1]
        if v[x-1]<0:
            c.append(v[x-1])
    ans=max(ans,chk[0])
    d=[]
    chk[1]=0
    for y in range(min(n,k)+1):
        if x+y>=k or x+y>=n:
            break
        if y>0:
            chk[1]+=v[-y]
            if v[-y]<0:
                d.append(v[-y])
        ans=max(ans,chk[0]+chk[1])
        e=c+d
        e.sort(reverse=True)
        t=0
        for z in range(k):
            if x+y+z>k or len(e)==0:
                break
            if z>0:
                t+=-(e[-1])
                e.pop()
                ans=max(ans,chk[0]+chk[1]+t)
print(ans)

コンテスト中には解けず、しかも最初に思いついた方針が悪くて実装出来ないで暫く放置してました。左から取れるだけ取ってから1手ずつずらして右から取ってから捨て方はどうしようか？となっていました。
あとから3重ループでなんとかなりそうかなー、と思いついた気がしました。3重ループにして左から取るのをx手、右から取るのをy手、大きな負の数を捨てるのをz手。x+y+zが合計k手以内、x+yが数列の長さ以内になるようにすると全パターン調べられるはずなので1手ごとに比較して最大値を保存しておいて最後に出力をすれば大丈夫だと思います。

E問題以降はまた今度に