Div1 https://community.topcoder.com/stat?c=round_overview&rd=16883
Div1 Easy. ParenthesisRemoval
()から成る文字列が与えられる。
- ()は良い文字列
- X,Yが良い文字列ならばXYも良い文字列
- Xが良い文字列ならば(X)も良い文字列
最も左の"("を1つ選んで、ある1つの")"を選んで消す。
この時、")"を消した後に良い文字列が保たれるように消す。
何通りの")"の選び方があるか(mod10^9+7)。
Div1 Med. NAddOdd
f(x) := x/2(xが偶数), x+K(xが奇数)
g(x) := xを関数xに通して何回目でK以下となるか、その回数
と定めるとき、sum{x=L...R}g(x)を求めよ
以下、解説
Div1 Easy. ParenthesisRemoval
#define rrep(i,a,b) for(int i=a;i>=b;i--) int mod = 1000000007; int add(int x, int y) { return (x += y) >= mod ? x - mod : x; } template<class... T> int add(int x, T... y) { return add(x, add(y...)); } int mul(int x, int y) { return 1LL * x * y % mod; } template<class... T> int mul(int x, T... y) { return mul(x, mul(y...)); } int sub(int x, int y) { return add(x, mod - y); } int modpow(int a, long long b) { int ret = 1; while (b > 0) { if (b & 1) ret = 1LL * ret * a % mod; a = 1LL * a * a % mod; b >>= 1; } return ret; } int modinv(int a) { return modpow(a, mod - 2); } //--------------------------------------------------------------------------------------------------- struct ParenthesisRemoval { int countWays(string s) { int ans = 1; int n = s.length(); int cnt = 0; rrep(i, n - 1, 0) { if (s[i] == ')') cnt++; else { ans = mul(ans, cnt); cnt--; } } return ans; } };
"("と")"のペアをマッチングさせるように解く。
後ろの"("からマッチングさせていくが、「マッチングできる")"は右にある")"の数-既にペアになっている右にある"("の数」通りのマッチングの組合せがある。
なので、これを掛ける。
これを繰り返して答えを求める。
Div1 Med. NAddOdd
typedef long long ll; int K; map<ll, ll> memo; ll get(ll x) { if (x <= K) return 0; if (memo.count(x)) return memo[x]; ll res = x - K + (x + 1) / 2 - (K + 1) / 2; res += get(x / 2); res += get((x + K) / 2); return memo[x] = res; } struct NAddOdd { ll solve(ll L, ll R, int k) { K = k; return get(R) - get(L - 1); } };
なぜ通るか分からない解答(XraYさんの解法)
