Codeforces #306 Div2 E. Brackets in Implications

凡ミスもったいない。
http://codeforces.com/contest/550/problem/E

問題

"→"は以下の特性を持つ左結合の二項演算子とする。

• 0 → 0 = 1
• 0 → 1 = 1
• 1 → 0 = 0
• 1 → 1 = 1

A[0] → A[1] → A[2] → ... → A[N-1]
という形の式が与えられる。（A[i]は0か1）
この式に括弧を加え、全体の評価値を0にせよ。

解法

Nが1,2の時は括弧を加えても演算順に影響しないので、単に今の値を評価するだけ。
以下Nが3以上の時を考える。

重要なのは、この演算子は二項目が1だと結果が1になる点である。

• A末尾が1の場合：
  • どの順で計算しても、最後の項が常に1になってしまい0に出来ない。
• Aがxxxx10の形の場合(xxxxは任意個)：
  • 上の考え方よりxxxx1の部分はどう計算しても1に出来る。最後に1→0=0で0を得られる。
  • よって、括弧を加えなくても左から順に計算するだけで0になる。
• Aがxxxx000の形の場合(xxxxは任意個)：
  • 前2個の0に対して0→0=1を1回適用すると、xxxx10となる。後は上のケースと同じ。
• Aがxxxx100の形の場合(xxxxは任意個)：
  • これが一番厄介。
  • xxxxが0を含まない場合、どうやっても0にはならない。
  • xxxxが0を含む、すなわち全体がyyy011...1100のような形になる場合。
    • 11...110がどうやっても0になることを利用すると、yyy0(1→1→....→1→0)0のように結合してyyy000と変換できるので、後は上記xxxx000のパターンを適用できる。

int N,A[101000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	if(A[N-1]==1) return _P("NO\n");
	
	if(N>=3) {
		if(A[N-2]==0 && A[N-3]==1) {
			for(i=N-3;i>=0;i--) if(A[i]==0) break;
			if(i<0) return _P("NO\n");
			_P("YES\n");
			
			FOR(j,i) _P("%d->",A[j]);
			_P("(0->(");
			for(i++;i<N-2;i++) _P("%d->",A[i]);
			_P("%d))->%d\n",0,A[N-1]);
			return;
		}
		_P("YES\n");
		
		FOR(i,N-3) _P("%d->",A[i]);
		if(A[N-2]==1) {
			_P("%d->%d->%d\n",A[N-3],A[N-2],A[N-1]);
		}
		else {
			_P("(%d->%d)->%d\n",A[N-3],A[N-2],A[N-1]);
		}
	}
	else if(N==1) {
		return _P("YES\n0\n");
	}
	else if(N==2) {
		if(A[0]==0) return _P("NO\n");
		return _P("YES\n1->0\n");
	}
}

まとめ

こちらも適度に頭を使う問題。