CF712 Div2 F Flip the Cards

内容

• CodeForces 712 Div2 F問題を、pythonでといた

  問題

https://codeforces.com/contest/1504/problem/Fcodeforces.com

考えたこと

• 解説ACです。

codeforces.com

ポイント

• 減少列を分解するの頭いい。(minf>maxfのとこ)
  • この条件の時、new_eleは、seq1,seq2のどっちにも入れる。
  • つまり、これまでのseq1,seq2のどっちをひっくり返すかが、今後の要素に影響しない-> 切り離せる。

実装

import heapq
N = int(input())
cards=[list(map(lambda x:int(x)-1,input().split())) for _ in range(N)]

#(1=N)のカードの、反対側の値
rev_cards=dict()

#(1~N)のカードについて、(min,max)の形にするためにひっくり返した?
flipped=dict()

#全てのカードを、((1~N),(N+1~2*N))にするために必要なcost
costs=0
for a,b in cards:
    ar,br= min(a,b),max(a,b)
    #両方ともNより小さいなら無理
    if br<N:
        print(-1)
        exit()

    rev_cards[ar]=br
    if b==br:
        flipped[ar]=False
    else:
        flipped[ar]=True
        costs+=1



# i以降のmax(先に求めておく)
suff_max=[-1]*(N+1)
for i in reversed(range(N)):
    suff_max[i] = max(suff_max[i+1],rev_cards[i])
# iまでのmin(更新しながら進む)
pre_min=float("inf")

#costi -> def_seq_iのなかで、前処理ですでにflipされているカード数
cost1=0
cost2=0

#答え
ans=0

#二つの減少列
def_seq1=[float("inf")]
def_seq2=[float("inf")]

for i in range(N):
    pre_min=min(pre_min,rev_cards[i])

    rev = rev_cards[i]
    if rev<def_seq1[-1]:
        def_seq1.append(rev)
        cost1+=int(flipped[i])
    elif rev<def_seq2[-1]:
        def_seq2.append(rev)
        cost2+=int(flipped[i])
    else: #減少列の数が3つ以上になると無理
        print(-1)
        exit()

    #これを満たす時、iとi+1で、減少列を分解できる。
    if pre_min>suff_max[i+1]:
        print("i=>",i)
        print(def_seq1,def_seq2)
        print(cost1,cost2)
        s1= len(def_seq1)-1
        s2 = len(def_seq2)-1

        #dec_seq2をひっくり返す (seq1の前処理でひっくり返されたやつ + seq2ひっくり返すながさ -seq2で前処理でひっくり返された数)
        rev2=cost1+s2-cost2
        #dec_seq1をひっくり返す
        rev1=cost2+s1-cost1

        ans += min(rev1,rev2)
        if rev1<rev2:
            print("rev=>",def_seq1)
        else:
            print("rev=>",def_seq2)
        cost1=0
        cost2=0
        def_seq1=[float("inf")]
        def_seq2=[float("inf")]
        print("ans=>",ans)

print(ans)

終わりに