Codeforces Round #306 (Div. 2) E. Brackets in Implications

意外に大したことない。

問題

Problem - E - Codeforces

解法

すこし考えれば難しいアルゴリズムは何も必要ありません。

まず最後が1の時は絶対にムリ。
また,最後から3番目までずっと1で最後から2番目,1番目が0のときもムリ(これは帰納法的に示せる)。
それ以外は以下のようにして構成できる。
最後が0なので,最後以外の部分を使って1を構成できれば嬉しい。
最後から2番目が1の時は何が合っても最後以外の部分で1になるので何も考えず矢印をつなげる。

最後から2番目が0の場合はちょっと面倒だが,0->*が1になる性質を考えて前半で0を作ることを考える。今の仮定から途中に絶対に0が存在するので,最初に0が現れるところまでの区間をカッコで加工とその値は0になる。よって,
(...->0)->(...)->0
のような形になって,
0->*->0 = 1->0
となるので結果は0で嬉しい。

const int MAXN = 100100;
int a[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
	int n;
	cin >> n;
	int all1 = -1;
	bool renzoku = true;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (a[i] == 1 && renzoku) all1 = i;
		else renzoku = false;
	}
	if (a[n-1] == 1) {
		cout << "NO" << endl;
		return 0;
	}
	if (n == 1) {
		cout << "YES" << endl;
		cout << "0" << endl;
		return 0;
	}
	if (all1 == n-3 && a[n-2] == 0 && a[n-1] == 0) {
		cout << "NO" << endl;
		return 0;
	}
	cout << "YES" << endl;
	if (a[n-2] == 1) {
		for (int i = 0; i < n-1; i++) {
			cout << a[i] << "->" ;
		}
		cout << a[n-1] << endl;
		return 0;
	} else {
		int index = 0;
		for (int i = 0; i < n; i++) {
			if (a[i] == 0) {
				index = i;
				break;
			}
		}
		cout << "(" ;
		for (int i = 0; i < index; i++) {
			cout << a[i] << "->";
		}
		cout << a[index] << ")->(";
		for (int i = index+1; i < n-2; i++) {
			cout << a[i] << "->";
		}
		cout << a[n-2] << ")->";
		cout << a[n-1] << endl;
		return 0;
	}
    return 0;
}