CODE FESTIVAL 2015 決勝 : E - ショートコーディング

想定解法と違いそう。
http://code-festival-2015-final-open.contest.atcoder.jp/tasks/codefestival_2015_final_e

問題

単項演算子'-''!'がある。
前者は数値の符号を反転させ、後者は0なら1、0以外なら0を返す。

ある単項演算子の列が与えられる。

• 256～256の各数値に、これら単項演算子を右から順に適用すると、ある数値になる。

同じ計算結果を得られる単項演算子列のうち最短のものを求めよ。

解法

'!'がないなら、-の偶奇に合わせて-を0個または1個出力すればよい。

'!'が1個でもあるとき、入力は実質0かそれ以外かしか関係がなくなる。
そこで入力に0と1を入れて計算してみる。

• 0,1の出力が0,1の時 : "!!"を答えればよい。
• 0,1の出力が0,-1の時 : "-!!"を答えればよい。
• 0,1の出力が1,0の時 : "!"を答えればよい。
• 0,1の出力が-1,0の時 : "-!"を答えればよい。

int L;
string S;

int hoge(int v) {
	int i;
	for(i=L-1;i>=0;i--) {
		if(S[i]=='!') v=(v==0)?1:0;
		else v=-v;
	}
	return v;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	L=S.size();
	
	FOR(i,L) if(S[i]=='!') break;
	
	if(i==L) {
		if(L%2) cout<<"-"<<endl;
		else cout<<endl;
		return;
	}
	
	int v0=hoge(0);
	int v1=hoge(1);
	
	if(v0==0) {
		if(v1==1) cout<<"!!"<<endl;
		if(v1==-1) cout<<"-!!"<<endl;
	}
	else {
		if(v0==1) cout<<"!"<<endl;
		if(v0==-1) cout<<"-!"<<endl;
	}
	
}

まとめ

本番わりとすんなり思いつけた。