Hello 2022: F. Strange Instructions

こういうの苦手。
https://codeforces.com/contest/1621/problem/F

問題

01で構成される文字列Sが与えられる。
これに対し、以下の手順を任意回数行う。
1. S中の"00"を1か所"0"に置換し、コインA枚を得る
2. S中の"11"を1か所"1"に置換し、コインB枚を得る
3. S中の"0"を1か所削除し、コインC枚を失う

上記手順のうち、同じパリティのものを2連続では実行できない。
今非常に大量のコインを持っている場合、最大コインを増加できるか。

解法

基本的に3より1が得だが、例外的に3を優先する方がいい場合として"101"を3→2の手順で消す場合である。
これを踏まえて丁寧に場合分けすると以下の通り。
先に1or3と2どちらを行うかは、両方試そう。

• 2をしなければならない手順では、2を行う。
• 1か3をしなければならない手順では以下の通り。
  • そのままでは次に2が不可能である
    • 1を仮に行った場合の解を試す
    • それとは別に、"101"パターンがあれば3を消す
    • どちらもできなければ終了
  • 次に2が可能である
    • 真ん中で1を行えるなら行う
    • それができず、端で1を行えるなら行う
    • それができず、真ん中で3を行えるなら行う
    • それができず、端で3を行えるなら行う

int T;
ll N,A,B,C;
string S;

ll go(int corner,int edge,int num1,vector<int> zb,int turn) {
	multiset<int> MB;
	int SB=0;
	FORR(a,zb) {
		if(a==1) SB++;
		else MB.insert(a);
	}
	
	ll cur=0,ma=0;
	
	while(1) {
		if(turn==0) {
			if(num1) {
				cur+=B;
				num1--;
			}
			else {
				break;
			}
		}
		else {
			if(num1==0) {
				if(corner||MB.size()) {
					ma=max(ma,cur+A);
				}
				if(SB) {
					//間の0を抜く
					SB--;
					cur-=C;
					num1++;
				}
				else {
					break;
				}
			}
			else {
				if(MB.size()) {
					int x=*MB.begin();
					MB.erase(MB.begin());
					cur+=A;
					x--;
					if(x==1) {
						SB++;
					}
					else {
						MB.insert(x);
					}
				}
				else if(corner) {
					corner--;
					cur+=A;
				}
				else if(SB) {
					SB--;
					cur-=C;
					num1++;
				}
				else if(edge) {
					edge--;
					cur-=C;
				}
				else {
					break;
				}
			}
		
		}
		ma=max(ma,cur);
		turn^=1;
	}
	
	return ma;
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>A>>B>>C>>S;
		
		if(N==1) {
			cout<<0<<endl;
			continue;
		}
		
		vector<pair<int,int>> V={{0,0}};
		FORR(c,S) {
			c-='0';
			if(c!=V.back().first) V.push_back({c,0});
			V.back().second++;
		}
		if(V.back().first==1) V.push_back({0,0});
		
		if(V.size()==1) {
			cout<<A<<endl;
			continue;
		}
		
		int edge=(V[0].second>0)+(V.back().second>0);
		int corner=max(0,V[0].second-1)+max(0,V.back().second-1);
		int num1=0;
		vector<int> zb;
		for(i=1;i<V.size()-1;i++) {
			if(V[i].first==1) {
				num1+=V[i].second-1;
			}
			else {
				zb.push_back(V[i].second);
			}
		}
		cout<<max(go(corner,edge,num1,zb,0),go(corner,edge,num1,zb,1))<<endl;
		
	}
}

まとめ

本番中こういうの詰めるの大変そう。