제출 #209562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
209562		E869120	Security Gate (JOI18_security_gate)	C++14	0 / 100	648 ms	1048580 KiB

securitygate

#include <iostream>
#include <string>
#include <cassert>
#include <algorithm>
using namespace std;

const int MAX_N = 104;

// 73 点解法
long long mod = 1000000007;
long long N; string S;

int dpl[MAX_N][MAX_N][MAX_N], sl[MAX_N][MAX_N][MAX_N];
int dpr[MAX_N][MAX_N][MAX_N], sr[MAX_N][MAX_N][MAX_N];
int dp1[MAX_N][MAX_N][MAX_N][MAX_N];
int dp2[MAX_N][MAX_N][MAX_N * 2][MAX_N];

void all_init() {
	for (int i = 0; i < MAX_N; i++) {
		for (int j = 0; j < MAX_N; j++) {
			for (int k = 0; k < MAX_N; k++) {
				dpl[i][j][k] = 0; sl[i][j][k] = 0;
				dpr[i][j][k] = 0; sr[i][j][k] = 0;
				for (int l = 0; l < MAX_N * 1; l++) dp1[i][j][l][k] = 0;
				for (int l = 0; l < MAX_N * 2; l++) dp2[i][j][l][k] = 0;
			}
		}
	}
}

void solve_1(int pos) {
	dp1[pos][pos][0][0] = 1;
	for (int i = pos; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				if (dp1[pos][i][j][k] == 0) continue;
				if ((S[i] == '(' || S[i] == 'x') && j >= 0) {
					dp1[pos][i + 1][j + 1][max(j + 1, k)] += dp1[pos][i][j][k];
					if (dp1[pos][i + 1][j + 1][max(j + 1, k)] >= mod) dp1[pos][i + 1][j + 1][max(j + 1, k)] -= mod;
				}
				if ((S[i] == ')' || S[i] == 'x') && j >= 1) {
					dp1[pos][i + 1][j - 1][max(j - 1, k)] += dp1[pos][i][j][k];
					if (dp1[pos][i + 1][j - 1][max(j - 1, k)] >= mod) dp1[pos][i + 1][j - 1][max(j - 1, k)] -= mod;
				}
			}
		}
	}
	for (int i = pos; i <= N; i++) {
		for (int j = 0; j <= N; j++) {
			for (int k = N; k >= 0; k--) {
				dp1[pos][i][j][k] += dp1[pos][i][j][k + 1];
				if (dp1[pos][i][j][k] >= mod) dp1[pos][i][j][k] -= mod;
			}
		}
	}
}

void solve_2(int pos) {
	dp2[pos][pos][N][0] = 1;
	for (int i = pos; i < N; i++) {
		for (int j = 0; j <= N * 2; j++) {
			for (int k = 0; k < N; k++) {
				if (dp2[pos][i][j][k] == 0) continue;
				if (S[i] == '(' || S[i] == 'x') {
					int val = max(j + 1 - (int)N, k);
					dp2[pos][i + 1][j + 1][val] += dp2[pos][i][j][k];
					if (dp2[pos][i + 1][j + 1][val] >= mod) dp2[pos][i + 1][j + 1][val] -= mod;
				}
				if (S[i] == ')' || S[i] == 'x') {
					int val = max(j - 1 - (int)N, k);
					dp2[pos][i + 1][j - 1][val] += dp2[pos][i][j][k];
					if (dp2[pos][i + 1][j - 1][val] >= mod) dp2[pos][i + 1][j - 1][val] -= mod;
				}
			}
		}
	}
}

void init() {
	// 正しいカッコ列の数を計算する（左側から）
	dpl[0][0][0] = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				if (dpl[i][j][k] == 0) continue;
				if ((S[i] == '(' || S[i] == 'x') && j >= 0) {
					dpl[i + 1][j + 1][max(j + 1, k)] += dpl[i][j][k];
					dpl[i + 1][j + 1][max(j + 1, k)] %= mod;
				}
				if ((S[i] == ')' || S[i] == 'x') && j >= 1) {
					dpl[i + 1][j - 1][max(j - 1, k)] += dpl[i][j][k];
					dpl[i + 1][j - 1][max(j - 1, k)] %= mod;
				}
			}
		}
	}

	// 正しいカッコ列の数を計算する（右側から）
	dpr[N][0][0] = 1;
	for (int i = N - 1; i >= 0; i--) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				if (dpr[i + 1][j][k] == 0) continue;
				if ((S[i] == ')' || S[i] == 'x') && j >= 0) {
					dpr[i][j + 1][max(j + 1, k)] += dpr[i + 1][j][k];
					dpr[i][j + 1][max(j + 1, k)] %= mod;
				}
				if ((S[i] == '(' || S[i] == 'x') && j >= 1) {
					dpr[i][j - 1][max(j - 1, k)] += dpr[i + 1][j][k];
					dpr[i][j - 1][max(j - 1, k)] %= mod;
				}
			}
		}
	}

	// 累積和を計算する
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= N; j++) {
			for (int k = 0; k <= N; k++) sl[i][j][k] = dpl[i][j][k];
			for (int k = N; k >= 0; k--) { sl[i][j][k] += sl[i][j][k + 1]; sl[i][j][k] %= mod; }
		}
	}
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= N;j++) {
			for (int k = 0; k <= N; k++) sr[i][j][k] = dpr[i][j][k];
			for (int k = N; k >= 0; k--) { sr[i][j][k] += sr[i][j][k + 1]; sr[i][j][k] %= mod; }
		}
	}

	for (int i = 0; i <= N; i++) {
		solve_1(i);
		solve_2(i);
	}
}

long long solve2(int maxval, int dep) {
	int goal = maxval - dep / 2;
	if (goal >= dep - 1) {
		long long ans = 0;
		for (int i = 0; i <= N - 1; i++) {
			if (S[i] == ')') continue;
			long long v1 = sl[i][dep - 1][0];
			long long v2 = dpr[i + 1][0][maxval - dep];
			ans += v1 * v2;
			ans %= mod;
		}
		return ans;
	}
	else {
		long long ans = 0;
		for (int i = 0; i <= N - 1; i++) {
			if (S[i] == ')') continue;
			long long v1 = dpr[i + 1][0][maxval - dep];
			for (int j = 0; j < i; j++) {
				if (S[j] == ')') continue;
				long long v2 = sl[j][goal][0];
				long long v3 = (dp1[j + 1][i][dep - 2 - goal][0] - dp1[j + 1][i][dep - 2 - goal][goal] + mod) % mod;
				ans += v1 * (v2 * v3 % mod) % mod;
				ans %= mod;
			}
		}
		return ans;
	}
}

long long solve4(int maxv, int dep) {
	long long ans = 0;
	int bo = max({ 0, dep, maxv });
	int cl_border = (bo + 1) / 2;
	int cr_border = (bo + 1) / 2 + dep / 2;
	if (cl_border * 2 + maxv + abs(maxv - dep) + min(0, cr_border - dep) * 2 > N) return 0;

	for (int i = 0; i <= N - 1; i++) {
		if (S[i] == '(') continue;
		long long v1 = sl[i][0][cl_border];
		for (int j = i + 1; j <= N - 1; j++) {
			if (S[j] == ')') continue;
			long long v2 = dp2[i + 1][j][dep + N][maxv + 1];
			long long v3 = sr[j + 1][0][cr_border - dep];
			ans += v1 * (v2 * v3 % mod) % mod;
			ans %= mod;
		}
	}
	return ans;
}

int main() {
	cin >> N >> S; assert(N <= 100);
	if (S.size() % 2 == 1) { cout << "0" << endl; return 0; }
	init();

	// パターン 1（カッコ列が正しい）
	long long ans1 = sl[N][0][0];

	// パターン 2（dep > 0、左側が全体）
	long long ans2 = 0;
	for (int i = N; i >= 1; i -= 2) {
		for (int j = i; j <= N; j++) {
			if (2 * j - i > N) continue;
			ans2 += solve2(j, i);
			ans2 %= mod;
		}
	}

	// パターン 4（どちらも全体ではない）
	long long ans4 = 0;
	for (int i = -1; i <= N; i++) {
		for (int j = -N; j <= N; j += 2) {
			ans4 += solve4(i, j);
			ans4 %= mod;
		}
	}

	// 折り返す
	reverse(S.begin(), S.end());
	for (int i = 0; i < S.size(); i++) {
		if (S[i] == '(') S[i] = ')';
		else if (S[i] == ')') S[i] = '(';
	}
	all_init();
	init();
	
	// パターン 3（パターン 2 の逆）
	long long ans3 = 0;
	for (int i = N; i >= 1; i -= 2) {
		for (int j = i; j <= N; j++) {
			if (2 * j - i > N) continue;
			ans3 += solve2(j, i);
			ans3 %= mod;
		}
	}

	// 出力
	cout << (ans1 + ans2 + ans3 + ans4) % mod << endl;
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

securitygate.cpp: In function 'int main()':
securitygate.cpp:216:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++) {
                  ~~^~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 43
• Subtask 5: 0 / 27