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; } };