yukicoder : No.1328 alligachi-problem

ありがちかなぁ？
https://yukicoder.me/problems/no/1328

問題

N個のボールがあり、それを左右1列に並べたい。
その時、各ボールに配置には以下の条件が設定される。

• そのボール自身の色(青または赤)
• そのボールの左側に、青または赤の指定された色のボールが置かれるべき数

条件を満たす並べ方が存在するなら1例を求めよ。

解法

貪欲法で行う。

• 今の青ボールの配置数で置ける青ボールを条件とするボールがなければ、赤ボール数を条件とする青ボール置く
• （上記赤・青反転したもの）
• 今の青ボールの配置数で置ける青ボールが1個ならそれを置く
• （上記赤・青反転したもの）
• どれでもない場合、ボールを置けないので終了。

int N;
int A[202020],B[202020];
int Y[202020];

vector<int> C[2][2][202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	FOR(i,N) {
		cin>>s;
		A[i]=s=="B";
		cin>>s;
		B[i]=s=="B";
		cin>>Y[i];
		C[A[i]][B[i]][Y[i]].push_back(i+1);
	}
	
	int a=0,b=0;
	vector<int> R;
	while(a+b<N) {
		if(C[1][0][a].size()&&C[0][1][b].empty()&&C[1][1][b].empty()) {
			R.push_back(C[1][0][a].back());
			C[1][0][a].pop_back();
			b++;
		}
		else if(C[0][1][b].size()&&C[0][0][a].empty()&&C[1][0][a].empty()) {
			R.push_back(C[0][1][b].back());
			C[0][1][b].pop_back();
			a++;
		}
		else if(C[1][1][b].size()==1&&C[0][1][b].empty()) {
			R.push_back(C[1][1][b][0]);
			C[1][1][b].clear();
			b++;
		}
		else if(C[0][0][a].size()==1&&C[1][0][a].empty()) {
			R.push_back(C[0][0][a][0]);
			C[0][0][a].clear();
			a++;
		}
		else {
			cout<<"No"<<endl;
			return;
		}
	}
	cout<<"Yes"<<endl;
	FOR(i,N) {
		if(i) cout<<" ";
		cout<<R[i];
	}
	cout<<endl;
	
}

まとめ

問題名が思い浮かばなかったのかな。