kmjp's blog

競技プログラミング参加記です

AtCoder ARC #094 : E - Tozan and Gezan

こっちの方がすんなり。
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よりはマシ。