Google Code Jam 2021 Qualification Round : B. Moons and Umbrellas

101ptを逃した…。
https://codingcompetitions.withgoogle.com/codejam/round/000000000043580a/00000000006d1145

問題

C,J,?で構成される文字列Sが与えられる。
S中で"CJ"が連続するとXポイント、"JC"が連続するとYポイントのコストがかかる。
"?"をCかJに任意に置き換えたとき、コストの最小値を求めよ。

解法

直前の文字がCかJか、を持つ単純なDPで解ける。

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	int X,Y;
	string S;
	cin>>X>>Y>>S;
	ll from[2]={1LL<<60,1LL<<60};
	if(S[0]=='C'||S[0]=='?') from[0]=0;
	if(S[0]=='J'||S[0]=='?') from[1]=0;
	S.erase(S.begin());
	FORR(c,S) {
		ll to[2];
		if(c=='C') {
			to[0]=min(from[0],from[1]+Y);
			to[1]=1LL<<60;
		}
		else if(c=='J') {
			to[0]=1LL<<60;
			to[1]=min(from[0]+X,from[1]);
		}
		else {
			to[0]=min(from[0],from[1]+Y);
			to[1]=min(from[0]+X,from[1]);
		}
		swap(from,to);
	}
	
	
	_P("Case #%d: %lld\n",_loop, min(from[0],from[1]));
}

まとめ

初期化部分をミスしてHardが通らず…。