AtCoder ABC #166 : F - Three Variables Game

本番だと混乱して手間取りそう。
https://atcoder.jp/contests/abc166/tasks/abc166_f

問題

A,B,Cの3つの変数における初期値が与えられる。
以下のクエリに順次答えることを考える。

• 変数のうち2つが指定されるので、片方をインクリメントし、片方をデクリメントする。

途中で変数の値が負にならないようなインクリメントする変数の選び方を答えよ。

解法

• A+B+C≦1の時、2つの変数がともに1以上であることはないので、選択肢はないのでどん欲に行えばよい。
• A+B+C≧3の場合、少ない方をインクリメントして多い方をデクリメントしよう。
  • 初手以降は常に2変数が正になるので、詰むことはない。
• 問題はA+B+C=2の時で、2変数がどちらも1以外の時は上記同様少ない方をインクリメントして多い方をデクリメントしていればよい。
  • 残る2変数が1の時が問題。今が最後の手番の時はどうでもよい。次の2変数が今回と同じなら、次回逆の選択を取ればよいので今回はどうでもよい。そうでない場合、次回クエリで対象となる変数の方に寄せよう。

int N,X[3];
int C[101010][2];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X[0]>>X[1]>>X[2];
	
	string T;
	FOR(i,N) {
		cin>>s;
		if(s=="AB") {
			C[i][0]=0,C[i][1]=1;
		}
		else if(s=="BC") {
			C[i][0]=1,C[i][1]=2;
		}
		else {
			C[i][0]=2,C[i][1]=0;
		}
	}
	
	FOR(i,N) {
		if(X[C[i][0]]==0 && X[C[i][1]]==0) return _P("No\n");
		if(X[C[i][0]]==1 && X[C[i][1]]==1) {
			if(i==N-1 || C[i][0]==C[i+1][0]) goto pat0;
			if(C[i+1][1]==C[i][0]) goto pat0;
			goto pat1;
			
		}
		else if(X[C[i][0]]>=X[C[i][1]]) {
			pat1:
			T+='A'+C[i][1];
			X[C[i][0]]--;
			X[C[i][1]]++;
		}
		else {
			pat0:
			T+='A'+C[i][0];
			X[C[i][0]]++;
			X[C[i][1]]--;
		}
	}
	cout<<"Yes"<<endl;
	FORR(c,T) cout<<c<<endl;
}

まとめ

この週末、こんだけ解いてることになるんだけど…。

• AtCoder: 27問(PAST+ABCx2)
• Codeforces: 12問ぐらい(ECR+通常回(これから))
• LeetCode: 8問
• yukicoder: 6問
• GCJ: 3問

これから行われるCFのDiv1D以上を除けば初級～中級だけどそれでも50問超える計算になるな…。