読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

Topcoder SRM 714 問題と解説

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さんの解法)