CodeQUEEN 2024 決勝 : G - Quintuple Scoop Ice Cream

ABCの前半を手厚くしたような配点。
https://atcoder.jp/contests/codequeen2024-final-N9tn8QqD/tasks/codequeen2024_final_g

問題

N種類のフレーバーのアイスがあり、それぞれの個数が与えられる。
ここで、5段重ねのアイスをできるだけ多く作りたい。
その際、同じフレーバーのアイスが2段連続してはならない。

5段重ねのアイスの最大数と、その一例を答えよ。

解法

貪欲に、一番残り数が多いフレーバーのうち、直前の段と異なるものを選んでいけばよい。

int N;
int C[202020];
vector<int> V[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	multiset<pair<int,int>> M;
	cin>>N;
	FOR(i,N) {
		cin>>C[i];
		M.insert({-C[i],i+1});
	}
	M.insert({0,-1});
	int num=0;
	while(1) {
		int pre=-1;
		FOR(i,5) {
			auto it=M.begin();
			if(it->second==pre) it++;
			if(-it->first<=0) break;
			x=it->second;
			M.erase(it);
			C[x-1]--;
			pre=x;
			M.insert({-C[x-1],x});
			V[num].push_back(x);
		}
		if(i==5) num++;
		else break;
	}
	cout<<num<<endl;
	FOR(i,num) {
		FORR(a,V[i]) cout<<a<<" ";
		cout<<endl;
	}
}

まとめ

証明とか考えずにやって通っちゃいそう。