python競技プログラミング

ABC 172C

スポンサーリンク

びっくりするほど難しい

 AとBが恐ろしく簡単で、Cも簡単目のやつでD頑張るかと思いきや、あれ…むずい…
 貪欲やナップザック的なDPか?とも思ったが、貪欲だと長めの時間が必要な本があった後に短めの連打されると多分詰むよなあ。と思ったのと、N,Mが10の5乗レベルまで行っているので、O(N2乗)だと間に合わんから愚直解は無理だな。と思ったのでとりあえずデータを整理するために累積和を取った。こうなるとその列は素直に増えていくだけだしAの机をiまで取ることにしてKからその所要分数を引いて、残りの分数でBをとれるところまで取ればいいのかということで二分探索した。
 二分探索はクソほど適当なつくりなのでもう少しまともな実装をしてライブラリとしたいところ。Aから1つも取らない場合が想定されていないよな。と思いつつもとりあえず方向性を間違っていないことを確認するため提出して1WA食らった。いやマジこのクソコードで1WAで済んだものである。
 久々に緑パフォ+難度緑の問題をコンテスト中に解くことができた。いや2年前参加してた時なら緑どころか水色だろうこれ…

N,M,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
SA=[]
SB=[]
goukeiA=0
goukeiB=0
for i in range(N):
    goukeiA+=A[i]
    SA.append(goukeiA)
for i in range(M):
    goukeiB+=B[i]
    SB.append(goukeiB)

#def binary_search()
Mcount=0



for i in range(N+1):
    if i!=N:
        
    
        count=0
        nokori=K-SA[i]
        if nokori >=0 and nokori >=SB[M-1]:
            count+=i+1+M
        elif nokori >=0:
            count+=i+1
            tmp=nokori
            left=0
            right=M-1
            #flag=False
            while left<=right:
                #print("mohu")
                mid=(left+right)//2
                if SB[mid]<=nokori and SB[mid+1]>nokori:
                    count+=mid+1
                    #print("es",count,mid)
                    break
                elif SB[mid]>nokori:
                    #print(nokori,mid)
                    right=mid-1
                elif SB[mid]<nokori:
                    #print(nokori,mid)
                    left=mid+1
                else:
                    print("イレギュラーな例につかまりました")
                    exit()
    else:
        count=0
        nokori=K
        if nokori >=SB[M-1]:
            count+=M
        elif nokori >0:
            tmp=nokori
            left=0
            right=M-1
            #flag=False
            while left<=right:
                #print("mohu")
                mid=(left+right)//2
                if SB[mid]<=nokori and SB[mid+1]>nokori:
                    count+=mid+1
                    #print("es",count,mid)
                    break
                elif SB[mid]>nokori:
                    #print(nokori,mid)
                    right=mid-1
                elif SB[mid]<nokori:
                    #print(nokori,mid)
                    left=mid+1
                else:
                    print("イレギュラーな例につかまりました")
                    exit()        
    
    if Mcount<count:
        #print("kita",count)
        Mcount=count
            
    
        
print(Mcount)

世の中に出していいレベルのコードではない…

コメント

タイトルとURLをコピーしました