C - 部分文字列と括弧 codeFlyer (bitFlyer Programming Contest)オープンコンテスト
問題概略
()からなる文字列が与えられる。
空文字列
ある括弧の対応が取れている文字列 A,B が存在し、 A,B をこの順に連結した文字列
ある括弧の対応が取れている文字列 A が存在し、 (, A, ) をこの順に連結した文字列
以上を括弧の対応が取れている文字列とした時、(i,j)の組でそれを満たすものはいくつか
解法
()も()()も左に対して対応が取れている物だと考えるから難しくなる。
条件1,3を満たすものを条件aとする。
条件aについて考えてみると(に対応する物は1つ以下である。
あるiについて対応するjの数は、aを満たすものがつながっている数である。
(A)(B)(C)なら3つ
よってそれぞれの左括弧について条件aを満たす右括弧の位置、nextを事前に記録しておき、メモ化再帰をすればいい。
dp[i] := iに対応するjの数として
iが)の時、または条件aを満たす括弧が無い時 : dp[i]=0
その他 : dp[i] = 1 + dp[next[i]+1]
o(N)
public static void solve() throws Exception { //longを忘れるなオーバーフローするぞ s = nca(); N = s.length; next = new int[N]; fill(next, -1); ArrayDeque<Integer> q = new ArrayDeque<>(); for (int i = 0; i < N; i++) { if (s[i] == '(') { q.add(i); } else { if (i + 1 < N && s[i + 1] == '(') { next[i] = i + 1; } if (!q.isEmpty()) { next[q.pollLast()] = i; } } } q.clear(); memo = new long[N]; fill(memo, -1); for (int i = 0; i < N; i++) { dfs(i); } long res = 0; for (int i = 0; i < N; i++) { res += u0(memo[i]); } System.out.println(res); } public static long dfs(int i) { if (i == -1 || s[i] == ')') return 0; if (memo[i] != -1) return memo[i]; if (next[i] == -1) { return memo[i] = 0; } else { return memo[i] = 1 + dfs(next[next[i]]); } }