不参加だった回。
https://codeforces.com/contest/2113/problem/D
問題
1~2Nの番号が書かれたカードが1枚ずつあり、プレイヤーとディーラーににN枚ずつ山として渡される。
以下の手順をN回行うゲームを行う。
- 両者の山の最上段のカードの番号を比較し、大きい番号を持つカードを山から取り除き、そのカードを持つ側に1ポイントを与える。
プレイヤーは1回だけ2枚のカードの位置を入れ替えられる場合、ポイントの最大値を求めよ。
解法
解Pを二分探索する。
プレイヤーのカードの先頭P毎の最小値が、ディーラーのカードの(N-P+1)枚の最小値より大きければよいため、違反するカードを1回だけスワップして追い出せるか判定すればよい。
int T,N; int A[202020],B[202020]; int hoge() { int i,x,y; for(i=x=y=0;i<N;i++) { if(A[x]>B[y]) x++; else y++; } return x; } void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>N; FOR(i,N) cin>>A[i]; FOR(i,N) cin>>B[i]; int L=hoge(); int R=N; while(R-L>1) { int M=(L+R)/2; x=0; FOR(i,M) if(A[i]<A[x]) x=i; y=N-1; for(i=N-2;i>=M;i--) if(A[i]>A[y]) y=i; swap(A[x],A[y]); if(hoge()>=M) { L=M; } else { R=M; } swap(A[x],A[y]); } cout<<L<<endl; } }
まとめ
Editorialもえらく短いね。