SRM685 Div1 Easy "MultiplicationTable2"
解法
サブセットTにindex iを使うぞ！ と決めると、goodなTを作るために必要な他のindexを芋づる式に導き出すことができる。
なので、index 0～n-1を順に試して、必要なindexが一番少ないものを答えとすればよい。
事後
SRM696から過去へ遡ってEasyやってきたけど、久しぶりにEasyらしい問題ですね（白目）
ソースコード
vector<int> t; int n; bool use[55]; class MultiplicationTable2 { public: int minimalGoodSet(vector<int> table) { t = table; n = (int) sqrt(table.size()); int ans = n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { use[j] = false; } dfs(i); int count = 0; for (int j = 0; j < n; j++) { if (use[j]) count++; } ans = min(ans, count); } return ans; } void dfs(int cur) { use[cur] = true; for (int i = 0; i < n; i++) { if (!use[i]) continue; for (int j = 0; j < n; j++) { if (!use[j]) continue; int id = i * n + j; if (use[t[id]]) continue; dfs(t[id]); } } } };
SRM686 Div2 Hard "BracketSequenceDiv2"
解法
連続しない部分文字列の数え上げなので、基本的には以下のやり方で。
ekaing.hatenablog.com
あとは、最終的に全ての左カッコに右カッコのペアが出来ていなければならないので、超過した左カッコの数を記録しておく。
事後
難しいなぁ・・・
ソースコード
const long long MOD = 1000000007LL; long long dp[110][110]; class BracketSequenceDiv2 { public: int count(string s) { s += "D"; // ダミー int n = s.size(); // dp初期化 memset(dp, 0, sizeof(dp)); for (int i = 0; i < n; i++) { if (s[i] == '(') dp[i][1] = 1; } // dp更新 int open_pre_pos = -1; // iから見て左側最寄りの'('の位置 int close_pre_pos = -1; // iから見て左側最寄りの')'の位置 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int m = j; if (s[i] == '(') m--; if (s[i] == ')') m++; if (m < 0 || n < m) continue; // open if (open_pre_pos != -1) { dp[i][j] += dp[open_pre_pos][m]; dp[i][j] %= MOD; } // close if (close_pre_pos != -1) { dp[i][j] += dp[close_pre_pos][m]; dp[i][j] %= MOD; } } if (s[i] == '(') open_pre_pos = i; if (s[i] == ')') close_pre_pos = i; } return dp[n - 1][0]; } };
連続しない部分文字列の数え上げ
内容
文字列が与えられるから、連続しない部分文字列(*1)は何個あるか数え上げたい。
ただし、部分文字列の内容が同じであれば重複して数え上げてはいけない。
(*1)
連続しない部分文字列とは（自分で勝手に名付けたんだけど・・）、
以下のように、連続しない文字を選んでもいいやり方でとった部分文字列のこと。
元の文字列：Eakabgizxngge 選ぶ文字 ：^ ^^ ^ ^ ^ ⇔飛び飛びで連続してない！ 出来る部分文字列：Ekaing
解法
i番目の文字を"使って"部分文字列を作った時に、何個出来るのかを考えてみる。
0番目～i-1番目の文字については、数え上げは出来ているとする。
以下を見て欲しい。
index 8番目の文字を"使って"部分文字列が何個できるか考えている状況である。
また、0～7番目の文字を使った時の部分文字列の数はすでに判明している。
ここで、末尾がaのもの(緑)、末尾がbのもの(黄)、末尾がcのもの(青)を使用したとき、それぞれ重複せずに数え上げられる。
xxxxaa、xxxxba、xxxxcaとなり、内容が違う部分文字列になるからね。
では、末尾が同じもの同士は数え上げるにあたってどうしたらよいかというと、今考えている場所から直近のものだけを使い、それ以外のものは無視するのが良い。
例えば図でいうとindex5と6は同じaである。で、index6の部分文字列の数40は、index5の部分文字列を考慮して算出されたものであり完全に含めているため、index6を数を足し合わせれば、index5の数はいらなくなる。index3と7も同じことが言える。
よって、iのパターン数はindex4, 6, 7を足し合わせた数となる。
また、0～i-1番目の文字を全く使用せず、i番目の文字のみを使用する場合として、1を追加すれば、晴れて「i番目の文字を"使って"部分文字列を作った時に、何個出来るのか」の数え上げは完了である。
(図でいうならば、index8の場合、20 + 40 + 50 + 1 = 111となる)
ソースコード
string s; long long memo[100]; int main() { string input = "aaba"; s = input; memset(memo, 0, sizeof(memo)); long long output = f(s.size()); cout << "output : " << output << endl; return 0; } // i番目までの文字を使用し、i番目の文字を"使った"時の部分文字列の場合の数 long long f(int i) { if (i == 0) { // 最初の文字の場合 // 最初の文字を使うのは１パターンだけ return 1; } else { // 最初の文字以外の場合 // メモ long long &res = memo[i]; if (res == 0) { // メモがない場合 // 左最寄りの各文字でのパターンを足しこんでいく for (int j = 0; j < 26; j++) { char ch = j + 'a'; // 左最寄りの文字chのインデックスを見つける int pi = find_prev(i, ch); if (pi != -1) { // 見つかったら再帰でパターン数を取得して足しこむ res += f(pi); } } // i番目の文字だけを使う場合の１パターンを足す res++; } return res; } } // baseより左で最も近い文字chのインデックスを探す int find_prev(int base, char ch) { for (int i = base - 1; i >= 0; i--) { if (s[i] == ch) return i; } return -1; }
SRM686 Div1 Easy "BracketSequenceDiv1"
解法
区間dpる。
dp[L][R] := LからRまでの区間にて、シーケンスをcorrectにする消し方の場合の数
初期化
L == Rの場合、その一文字を消すしかcorrectにする方法はないので1
更新
Rのカッコに着目し、こいつを追加したときにどうやって更新するか考える。
まず、Rのカッコが"("や"["だった場合、これは消すしかcorrectにする方法がないので消すことにする。
すると、dp[L][R] = dp[L][R - 1]となる。
Rのカッコが")"や"]"だった場合、まず消す場合は同様にdp[L][R - 1]パターンでcorrectにできる。
それから、LからR - 1の間の"("か"["のカッコとペアを作ることが出来るため、消さないで残す方法があることになる。
ペアとするカッコのインデックスをiとすると、Lからi - 1, i + 1からR - 1それぞれでパターンを作ることができるので、それらを掛け合わせたdp[L][i - 1] * dp[i + 1][R - 1]だけcorrectにできる。
下図を見て欲しい。
図は、Rのカッコをindex4のカッコとペアにするぞ！！と意気込んでいる状態である。
すると、黄色の部分と緑の部分がそれぞれ独立してパターンを作ることができるので、dp[1][3] * dp[5][6]がdp[1][7]に足しこまれるという感じ。
ペアとするカッコはLからR - 1までを走査して、どんどん足しこんでく。
結果
dp[0][n - 1] - 1
※全部消すのはNGだ！
事後
Editorialのソースコードの簡潔さよ・・・
ソースコード
long long dp[45][45]; class BracketSequenceDiv1 { public: long long count(string s) { int n = s.size(); for (int len = 1; len <= n; len++) { for (int L = 0; L <= n - len; L++) { int R = L + len - 1; if (len == 1) { // 長さ1のところは消すの1パターン dp[L][R] = 1; } else { if (s[R] == '(' || s[R] == '[') { // 消すしかない！ dp[L][R] = dp[L][R - 1]; } else { // 消す！ dp[L][R] = dp[L][R - 1]; // ペアを順に探していく char pair = s[R] == ')' ? '(' : '['; for (int i = L; i < R; i++) { if (s[i] == pair) { // 1つ目のサブセット int L1 = i + 1; int R1 = R - 1; long long sub1 = L1 <= R1 ? dp[L1][R1] : 1; // 2つ目のサブセット int L2 = L; int R2 = i - 1; long long sub2 = L2 <= R2 ? dp[L2][R2] : 1; dp[L][R] += sub1 * sub2; } } } } } } return dp[0][n - 1] - 1; } };
SRM687 Div1 Easy "AlmostFibonacciKnapsack"
解法
A[i]の増加の仕方は2のべき乗ぐらいに凄く、A[90]ぐらいにはもうxの最大値である10^18を超える。
探索範囲は広くなさそうということで、枝刈り探索しました。
事後
Editorialを見ると、大きいものから順に貪欲に行けばいいらしい。
自分のやった枝刈り探索でも大きいものから順に試していったため、結果的にほぼベストなやり方となり、計算量が少なくなったようです。
ソースコード
const long long INF = -1; bool ans[100]; bool ok; bool work[100]; long long a[92]; long long s[92]; class AlmostFibonacciKnapsack { public: vector<int> getIndices(long long x) { // i番目の数値とi番目までの合計値を算出 a[1] = 2; a[2] = 3; s[1] = 2; s[2] = 5; for (int i = 3; i <= 91; i++) { a[i] = a[i - 1] + a[i - 2] - 1; s[i] = s[i - 1] + a[i]; } s[90] = s[91] = INF; // 枝刈り探索でいく for (int i = 1; i <= 91; i++) { work[i] = false; } ok = false; solve(91, x); // 答え設定 vector<int> res; if (ok) { for (int i = 1; i <= 91; i++) { if (ans[i]) res.push_back(i); } } else { res.push_back(-1); } return res; } void solve(int cur, long long rem) { // 答えが確定していたら何もしない if (ok) return; // 残りが0になったら答え確定 if (rem == 0) { ok = true; for (int i = 1; i <= 91; i++) { ans[i] = work[i]; } return; } // indexが0になったらアウト if (cur == 0) { return; } // 合計値が少なくなってしまったらアウト if (s[cur] != INF && s[cur] < rem) { return; } if (a[cur] <= rem) { // 使う work[cur] = true; solve(cur - 1, rem - a[cur]); work[cur] = false; } // 使わない solve(cur - 1, rem); } };
SRM688 Div1 Easy "ParenthesesDiv1Easy"
解法
こちらを参考にしましたm(_ _)m
mayokoex.hatenablog.com
参考先でも言っているように、開きカッコ閉じカッコのペアが成立しているものを取り除いていくと、最終的には「））））（（」とか「）（（（（（」とか「）））））））」とかになる。これを「（（（）））」とするためには高々２回フリップを使えばよい。最初に取り除いたカッコたちについては、フリップしたところでペアが成立することは変わらないので無視しても大丈夫。
事後
こうゆうちょっとした発想が必要な問題が解けるようになりたいなぁ・・
ソースコード
class Elm { public: int id; char c; Elm(int id, int c) { this->id = id; this->c = c; } }; class ParenthesesDiv1Easy { public: vector<int> correct(string s) { int n = s.size(); // 奇数だったら無理 if (n % 2 != 0) { vector<int> ans; ans.push_back(-1); return ans; } // ペアが成立したカッコは無視し、それ以外のカッコとそのindexを保持 vector<Elm> ps; for (int i = 0; i < n; i++) { if (s[i] == ')' && !ps.empty() && ps.back().c == '(') { ps.pop_back(); } else { ps.push_back(Elm(i, s[i])); } } // フリップすべきindexを算出 int m = ps.size(); int close_L_id = -1; int close_R_id = -1; int open_L_id = -1; int open_R_id = -1; for (int i = 0; i < m; i++) { if (ps[i].c == ')') { if (close_L_id == -1) { close_L_id = ps[i].id; } if (i < m / 2) { close_R_id = ps[i].id; } } else { if (open_L_id == -1 && m / 2 <= i) { open_L_id = ps[i].id; } open_R_id = ps[i].id; } } // 答えを設定 vector<int> ans; if (close_L_id != -1) { ans.push_back(close_L_id); ans.push_back(close_R_id); } if (open_L_id != -1) { ans.push_back(open_L_id); ans.push_back(open_R_id); } return ans; } };
SRM689 Div1 Easy "ColorfulGarden"
解法
それぞれの色の花において、その数がガーデンの幅（rowの長さ）を超えているものがあれば、どう配置しても隣り合ってしまうため配置不可となる。
逆にそうでない場合、以下のようにすれば必ず配置可能となる。
ガーデンの幅 = 7 aの数 = 3 bの数 = 6 cの数 = 5 とする。 数を降順にソートする。 b = 6 c = 5 a = 3 数が大きいものから順にジグザグに配置していく ①bを配置 row0 : b b b row1 : b b b ②cを配置 （ここでは右端に到達するため、左端からまたジグザグに配置しなおしている） row0 : b c b c b c row1 : c b c b b ③aを配置 row0 : b c b c b a c row1 : c b c b a b a 完成！
この方法では、「中途半端な位置から 数 = ガーデンの幅 の花を配置する」と隣り合ってしまいNGとなるが、数を大きいものから順に配置することによって、それを回避している。
ソースコード
class ColorfulGarden { public: vector<string> rearrange(vector<string> garden) { int n = garden[0].size(); // それぞれの色の数を数える int nums[26]; memset(nums, 0, sizeof(nums)); for (int i = 0; i < 2; i++) { for (int j = 0; j < n; j++) { nums[garden[i][j] - 'a']++; } } // nを超過しているかチェック for (int i = 0; i < 26; i++) { if (nums[i] > n) { vector<string> emptyList; return emptyList; } } // 大きいものから順に文字列結合する string str = ""; while(true) { int id = 0; int n = 0; for (int i = 0; i < 26; i++) { if (n < nums[i]) { id = i; n = nums[i]; } } if (n == 0) break; nums[id] = 0; for (int i = 0; i < n; i++) { str += id + 'a'; } } // 答えリストを作成 string str0 = ""; for (int i = 0; i < n; i++) { int id = i; if (i % 2 != 0) id += n; str0 += str[id]; } string str1 = ""; for (int i = 0; i < n; i++) { int id = i; if (i % 2 == 0) id += n; str1 += str[id]; } vector<string> ans; ans.push_back(str0); ans.push_back(str1); return ans; } };
