こっちの方がすんなり。
https://beta.atcoder.jp/contests/arc094/tasks/arc094_c
問題
2つのN要素の非負整数列A,Bがある。
要素の和は等しい。
AとBが異なる間、以下の処理を繰り返す。
- 先手がAのうち1つ正の要素を選び、デクリメントする。
- 後手がBのうち1つ正の要素を選び、デクリメントする。
先手は処理回数を最大化し、後手は最小化しようとするとき、処理回数は何回か。
解法
初期状態でA=Bなら0回。
まず、A[i]≦B[i]となる要素について、先手が先行してA[i]をデクリメントしていくと後手はA[i]=B[i]=0にせざるを得ない。
A!=Bより1つはA[i]<B[i]の要素があるので、後手がB[i]=0にしてるうちに先手はA[i]>B[i]となる要素に対しA[i]<B[i]となるよう余分にデクリメントできる。
その結果、もともとA[i]>B[i]である要素も後手がB[i]=0となるよう強いることができる。
結局、A[i]>B[i]のうち1つを除いて0となるように強いることができるので、B[i]が最少の物以外そうせざるを得ないようにすればよい。
int N; int A[202020]; int B[202020]; ll S; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; int dif=0; FOR(i,N) { cin>>A[i]>>B[i]; if(A[i]!=B[i]) dif=1; S+=A[i]; } if(dif==0) return _P("0\n"); ll ret=0; vector<ll> cand; FOR(i,N) { if(A[i]<=B[i]) ret+=B[i]; else cand.push_back(B[i]); } sort(ALL(cand)); reverse(ALL(cand)); FOR(i,cand.size()-1) ret+=cand[i]; cout<<ret<<endl; }
まとめ
ちょっと手間取ったけどDよりはマシ。