Codeforces Round #306 Div2 E: Brackets in Implications （貪欲）

問題

codeforces.com

解法

• ...->1->0の形にならないといけないので、最後の数字が0でなければNO
• x->1=1なので最後から2番めの数字が1ならばYES
• ...->0->0 となっている時、すなわち、最後の2つが0の時を考える
  • 最後の2つ以外に0が1つ以上ある場合、( (1->1->...->1->0)->(...->0))->0=(0->x)->0=0にできるのでYES。
  • 最後の2つだけが0で他が1の場合はNO

コード

import java.util.Scanner;

public class Main {
	public void solve() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] digits = new int[N];
		for (int i = 0; i < N; i++) {
			digits[i] = sc.nextInt();
		}

		if (digits[N - 1] != 0) {
			System.out.println("NO");
			return;
		} else if (N == 1) {
			System.out.println("YES");
			System.out.println("0");
			return;
		} else if (digits[N - 2] == 1) {
			System.out.println("YES");
			for (int i = 0; i < N - 1; i++) {
				System.out.print("(");
			}
			for (int i = 0; i < N; i++) {
				System.out.print(digits[i]);
				if (i < N - 1) {
					System.out.print(")->");
				}
			}
			System.out.println();
			return;
		}

		StringBuilder sb = new StringBuilder();
		int cur = 0;
		while (cur < N - 2) {
			if (digits[cur] == 0) {
				for (int j = 0; j <= cur; j++) {
					sb.append("(");
				}
				for (int j = 0; j <= cur; j++) {
					sb.append(digits[j]);
					sb.append(")->");
				}
				break;
			}
			cur++;
		}
		if (sb.length() == 0) {
			System.out.println("NO");
			return;
		}
		System.out.println("YES");
		for (int i = cur + 1; i < N - 1; i++) {
			sb.append("(");
		}
		for (int i = cur + 1; i < N - 1; i++) {
			sb.append(digits[i]);
			sb.append(")");
			if (i < N - 2) {
				sb.append("->");
			}
		}
		sb.insert(0, "(");
		sb.append(")->0");
		System.out.println(sb.toString());

	}

	public static void main(String[] args) {
		new Main().solve();
	}

}