Codeforces #343 Div2 C

問題文

codeforces.com

考察

・の文字列内の開き括弧と閉じ括弧の個数が同じでなければならない

・に使われている開き括弧と閉じ括弧の数が分かればに使われる開き括弧と閉じ括弧の数が分かる

・長さの文字列で開き括弧が閉じ括弧より個多いときの組み合わせ

・に対して'('を追加した時は , が1以上の時に')'が追加された時は

参考：
codeforces.com

mayokoex.hatenablog.com

kmjp.hatenablog.jp

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

import java.util.*;

public class Main {
	static int MOD = (int)1e9 + 7;
	int N,M,D;
	String s;
	long[][] dp;
	
	public void solve() {
		N = nextInt();
		M = nextInt();
		D = N - M;
		s = next();
		//dp[i][j] = 長さiの文字列で開き括弧が閉じ括弧よりj個多い組み合わせ
		dp = new long[D + 2][D + 2];
		
		int left = 0;//閉じ括弧と開き括弧の差の最終的な値
		int diff = 0;
		for(int i = 0;i < M;i++){
			if(s.charAt(i) == '(')left++;
			else left--;
			//sをi番目まで見たときの開き括弧が閉じ括弧より少ない最小値
			diff = Math.min(diff,left);
		}
		
		dp[0][0] = 1;
		for(int i = 0;i < D;i++){
			
			for(int j = 0;j <= i;j++){
				
				dp[i + 1][j + 1] += dp[i][j];
				dp[i + 1][j + 1] %= MOD;
				
				if(j > 0){
					dp[i + 1][j - 1] += dp[i][j];
					dp[i + 1][j - 1] %= MOD;
				}
			}
		}
		
		int ans = 0;
		for(int i = 0;i < D + 1;i++){
			
			for(int j = 0;j <= i;j++){
				//j + diffが0より小さい場合はp + s + qを前から順番に見ていった時に途中で')'が多くなってしまう
				//j + left > D - iの場合はleft + j(開き括弧の数)が文字を決められる残り文字数より大きくなって、Nの長さに収まらない
				if(j + diff >= 0 && j + left <= D - i){
					//dp[i][j] = pの長さがi,開き括弧が閉じ括弧よりj多い時の組み合わせ
					//dp[D - i][j + left] = qの長さがD - iで,開き括弧が閉じ括弧よりj + left多い時の組み合わせ
					ans += dp[i][j] % MOD * dp[D - i][j + left] % MOD;
					ans %= MOD;
				}
			}
		}
		
		out.println(ans);
		
	} 

	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}
	
	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}