AtCoder ARC #014 : C - 魂の還る場所

今回かなり勝敗が分かれた問題。
http://arc014.contest.atcoder.jp/tasks/arc014_3

問題

両端に穴の開いた筒があり、左右からボールを入れられる。
筒の中で同じ色のボールが２つ並ぶと、互いに消すことができる。
筒に入れるボールの色の順番が与えられるとき、最後に残るボール数を答えよ。

解法

Smallはボール数N<=15なので、筒の両側から入れるパターンを全列挙すればよい。

自分の場合、筒内のボールのパターンを列挙して両側から入れるパターンを試した。
ただ、このままだと2^Nかかるので、その時点で最も少ないボール数+5個までのボール数で実行した。
色の数は３色なので、そんなに筒内にボールは溜まらないだろう、ということで枝刈り。

…ただ、最終的には実はボール順がどんなパターンでも偶数個分はすべて消せるようだ。
自分はそこまで確信が持てなかったので枝刈りシミュレーションしたけど。
ほかの人を見ると、枝刈りシミュレーションの人はそこそこいるけど半分以下っぽいな…。
みんなどうやって確信を持ったんだろう。自分も「最少+5個」とかやってる時点で確信せず枝刈りしてるけどさ。

int N;
string S;
set<string> SS[2];

void solve() {
	int f,r,i,j,k,l;
	int bad[2];
	
	N=GETi();
	cin>>S;
	
	SS[0].insert("");
	FOR(i,N) {
		SS[1]=SS[0];
		SS[0].clear();
		k = 50;
		ITR(x,SS[1]) k=min(k,(int)x->length());
		
		ITR(x,SS[1]) {
			const string& s=*x;
			l = s.length();
			if(l>k+5) continue;
			char cc[2];
			cc[0]=S[i];
			cc[1]=0;
			
			if(l==0) SS[0].insert(cc);
			else {
				if((*x)[0]==S[i]) SS[0].insert(s.substr(1));
				else if(l<=N/2+3) SS[0].insert(string(cc) + s);
				if(s[l-1]==S[i]) SS[0].insert(s.substr(0,l-1));
				else if(l<=N/2+3) SS[0].insert(s + string(cc));
			}
		}
	}
	
	k = 50;
	ITR(x,SS[0]) k=min(k,(int)x->length());
	_P("%d\n",k);
	
	
	return;
}

まとめ

地味にいやらしい問題で、枝刈りで苦戦した人も多そうだ。