SRM 671 Div1

結果

--- 1317 -> 1292
今回も1問も解けなかった.

[Easy 300: BearCries ]

問題

';'と'_'からなる長さNの文字列messageが与えられる.
messageにはいくつかの悲しいを表す顔文字が含まれる.
悲しい顔文字は';'が両端に1文字づつあり,その間に1文字以上の'_'が含まれる文字列のことを言う.
最小の悲しい顔文字は";_;"である(他は";___:"とか";_______;").
messageを正しい悲しい顔文字に分ける分け方の総数を求めよ.

1 <= N <= 200

方針

動的計画法で解きます.
状態は次のように持ちます.
  dp[i][j][k] := messageの初めからi文字みたときに,ペアを持っていない';'の数がj個(顔文字の左端か右端か決まっていない),";_・・・"と顔文字の左端が決まっているものの数がk個という状態の顔文字の総数

求める状態は dp[N][0][0](messageの全体を見た時にペアが決まってない';'の数が0個の時の顔文字の総数)となります.

dp[i][j][k] からの状態遷移はmessageのi文字目(0-index)によって変わります.配るdpと呼ばれているもの?になると思います.詳しくはソースコードを見てください.

ソースコード
#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

const int MAX_N = 210;
const ll MOD = 1000000007;

inline void Add(ll &x, ll y) {
    x = (x + y) % MOD;
}

class BearCries {

    ll dp[MAX_N][MAX_N][MAX_N];
public:
	int count(string message) {
        string s = message;
        const int n = s.length();

        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                for (int k = 0; k < n; ++k)
                    dp[i][j][k] = 0;

        dp[0][0][0] = 1;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j <= i; ++j)
                for (int k = 0; k <= i; ++k) {
                    if (dp[i][j][k] == 0)
                        continue;

                    if (s[i] == ';') {
                        Add(dp[i + 1][j + 1][k], dp[i][j][k]);
                        if (0 < k) // 左端候補';_'のk個のいづれかと顔文字を作る
                            Add(dp[i + 1][j][k - 1], dp[i][j][k] * k);
                    }
                    else {
                        Add(dp[i + 1][j][k], dp[i][j][k] * k);
                        if (0 < j) // 未決定候補';'のj個のいづれかを左端候補にする
                            Add(dp[i + 1][j - 1][k + 1], dp[i][j][k] * j);
                    }
                }

        return (int)dp[n][0][0];
	}
};

[Med 500: BearDarts ]

問題

N個の配列wが与えられる.
a < b < c < d で w[a] * w[c] = w[b] * w[d] となる組合せ数を求めよ.

1 <= w[i] <= 10^9, 4 <= N <= 10^3

方針

roitiさんの解法を見て解きました.
Topcoder SRM671 Div1 Med: BearDurts - roiti46's blog

w[a]/w[b] = w[d]/w[c] と式変形をして,両辺をそれぞれ分子分母の最大公約数で割った値をペアで持つ.
a' = w[a]/gcd(w[a],w[b]), b' = w[b]/gcd(w[a],w[b])
c' = w[c]/gcd(w[c],w[d]), d' = w[d]/gcd(w[c],w[d])
とすると,
(a',b') = (d',c')
となるペアを求める問題となる.ただし,a < b < c < d .
cを0からN-1まで見るときに,mapには a < b < c となる (a',b') のペアがすべて含まれるようにする.そして,c < d を満たす (c,d) のペアに対してmapで検索すると計算量は O(N^2 logN) となる.

(規約分数やmapに登録する探索順番など自分の注意力では解けなかった気がする)

ソースコード
#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

class BearDarts {
public:
	long long count(vector <int> w) {
        const int n = w.size();

        ll ans = 0;
		map<pair<int, int>, ll> cnt;

        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int gcd = __gcd(w[j], w[i]);
                ++cnt[make_pair(w[j] / gcd, w[i] / gcd)];
            }
            for (int j = i + 2; j < n; ++j) {
                int gcd = __gcd(w[j], w[i + 1]);
                ans += cnt[make_pair(w[j] / gcd, w[i + 1]/ gcd)];
            }
        }

        return ans;
	}
};