【ABC195】E - Lucky 7 Battle
ゲーム系の問題でDPをするときはメモ化再帰の方が書きやすい気がする。
解法
$ S_i $か0かの選択をする際に、その選択をした結果7の倍数を作れるor作れないことが分かれば、常に最適な行動を取れる。
ということで、前の桁から$ S_i $か0かの選択をした未来で7の倍数を作れるかどうかを再帰的に検証していくことにする。
メモ化再帰
ただ、愚直に全探索しようとするとO(2N)になるため、間に合わない。
ここでDPの考え方を用いる。
再帰的に次の桁を呼び出すとき必要になる情報は、今何桁目で決定している合計値(mod 7)がいくつかという2つである。
この2つの情報を状態として持つDPテーブルを作成しメモ化すれば、何度も同じ計算をする事態を避けることができる。
どう検証するか
メモ化再帰の定義は次のようになる。
rec(i, cur) ← 前からi桁目までの選択が確定している場合に、確定している値を7で割った値がcurであるときに7の倍数を作れるか
rec(i, cur)は7の倍数を作れるときtrueを返し、作れないときfalseを返すようにする。
次の桁に遷移するときは次のように2つに分かれる。
- rec(i+1, (cur + S[i]) mod 7) ← i桁目でS[i]を選択したとき
- rec(i+1, cur) ← i桁目で0を選択したとき
i桁目の時点で青木くんのターンであった場合、7の倍数を作ることができない未来を2つの遷移先から選択すればよく、逆に高橋くんのターンであった場合、7の倍数を作ることができる未来を選べばよい。
実装
rec(i+1, (cur + S[i]) mod 7) と rec(i+1, cur)の戻り値を、それぞれflag1、flag2とする。
青木君のターンには、なるべくfalseを戻り値としたい。
7の倍数を作れない未来を選択できるのは、flag1 = true, flag2 = trueのパターン以外のときなので、flag1とflag2の論理積をとったとき、trueである場合のみ7の倍数を作らざるを得ないことになる。
よって、青木君のターンにはflag1 && flag2を戻り値とする。
逆に高橋君のターンでは、なるべくtrueを戻り値にしたい。
7の倍数を作れる未来を選択できるのは、flag1とflag2のどちらかがtrueの時なので、高橋君のターンにはflag1 || flag2を戻り値とする。
// mint: mod 7 のmodint構造体 int N; string S, X; bool rec(int i, int cur, vector<vector<int>> &memo) { if (i == 0) { if (cur) return 0; // curが0以外であるとき else return 1; // cur=0のとき } if (memo[i-1][cur] != -1) return memo[i-1][cur]; mint nx = modpow((mint)10, i) * (S[N-i] - '0') + cur; // S[i]を選択する場合 bool flag1 = rec(i-1, nx.val, memo); // 0を選択する場合 bool flag2 = rec(i-1, cur, memo); // 青木君のターンのとき、7の倍数を作れない未来を選択する if (X[N-i] == 'A') return memo[i-1][cur] = flag1 && flag2; // 高橋君のターンのとき、7の倍数を作れる未来を選択する else return memo[i-1][cur] = flag1 || flag2; } void solve(){ vector<vector<int>> memo(N+1, vector<int>(7, -1)); if (rec(N, 0, memo)) c("Takahashi") else c("Aoki") } int main(){ cin >> N >> S >> X; solve(); return 0; }```
【ABC202】E - Count Descendants
公式解説とは違う方法らしい。
解法
この問題は、頂点 $ U_i $の子要素で根からの距離が $ D_i $である頂点はいくつか、というクエリに回答せよ、と言い換えられる。
複数のクエリに回答する問題
複数のクエリに回答する問題は、次のような解法パターンがある。
- それぞれのクエリで何かしらの調査をして答えを計算する
- 事前調査の結果を用いて、一気にクエリに回答する
- クエリを先読みしておき、調査しながら回答する
この問題を1つ目の解法で解こうとすると、毎回DFSをして愚直に回答する方法が思い浮かぶ。
しかし、この方法だとO(N2)になり、時間がかかりすぎてしまう。
2つ目の解法で解くことを考えてみると、頂点ごとにどんな子要素があるかを表す配列を作る方法が思いついた。
しかしメモリを大量に消費する恐れがあるため、解法としては不十分。
最後に3つ目の解法で解けないか考えてみる。
DFS＋クエリ先読みで解く
木に関する問題はDFSで解けることが多い。 根からDFSを始めて、頂点 $ U_i $まで到達した時に頂点 $ U_i $に関するクエリに回答することにする。
また、距離に関する問題であるため、根からの距離がiであるような頂点がいくつあるか、という配列distを作成しておく。
頂点 $ U_i $に到達したときに、その時点でのdistがどうなっているかを記録しておき、頂点 $ U_i $からその親要素に戻る際にもう一度distを確認して、記録しておいた時との差分を取れば、子要素に距離iの要素がいくつあるかを知ることができる。
ただし、頂点ごとにdistをコピーして保存するとMLEになってしまうため、その頂点のクエリに関係する値だけを記録しておく。
具体例
$ U_i = j, D_i = 2 $というクエリに回答することを考える。
頂点jに到達した時点でdist[2]が3であり、頂点jから親要素に戻るときにdist[2]が5だった場合、頂点jの子要素に根からの距離が2である要素が5 - 3 = 2個あることがわかり、これがクエリの答えになる。
実装
クエリ先読み周りの実装が汚くなってしまった。
void dfs(int n, int p, int d, vector<int> &dist, vector<map<int, pair<int, int>>> &query, vector<vector<ll>> &G) { for (auto &q : query[n]) { q.second.second -= dist[q.second.first]; } dist[d]++; for (auto a : G[n]) { if (a != p) { // 親への逆流防止 dfs(a, n, d+1, dist, query, G); } } for (auto &q : query[n]) { q.second.second += dist[q.second.first]; } } void solve(long long N, std::vector<long long> P, long long Q, std::vector<long long> U, std::vector<long long> D) { // グラフ構築 vector<vector<ll>> G(N); REP (i, N-1) { G[P[i]-1].push_back(i+1); } // 根からの距離 vector<int> dist(N, 0); // クエリを保管する配列 map.key: index, map.value.first: D[i], map.value.second: 答え vector<map<int, pair<int, int>>> query(N); REP (i, Q) { query[U[i]-1].insert({i, {D[i], 0}}); } dfs(0, -1, 0, dist, query, G); // クエリの順番を元に戻す vector<int> ans(Q, 0); REP (i, N) { for (auto q : query[i]) { ans[q.first] = q.second.second; } } // 出力 REP (i, Q) c(ans[i]); }
感想
公式解説の方法も勉強しておきます。
【ABC145】E - All-you-can-eat
解法
T - 0.5分後というのは、T-1分後と言い換えることができる。
T-1秒をこえて、料理を食べることができない場合、ただのナップザックDPで解くことができる。
具体的にDPの定義は次のようになる。
dp[i][j] ← i番目の料理まで食べるかどうか決め、最初の注文からj秒立っている時の満足度の最大値
ただしこの問題では、最後の料理だけはT-1秒を越えて食べることができる。
T-1秒を越えて食べることができるのは、最後の料理1つだけであるため、DPでどの料理を食べるかの探索だけを行い、一番食べる時間がかかる料理を最後に食べれば良い。
とりあえず昇順に並べておけば、最後に食べる料理を一番時間がかかる料理にできるため簡単に解くことができる。
実装
void solve(long long N, long long T, std::vector<long long> A, std::vector<long long> B){ vector<pair<ll, ll>> vec; REP (i, N) { vec.push_back({A[i], B[i]}); } // 昇順に並べておく ALL(sort, vec); // DPテーブル vector<vector<ll>> dp(N+1, vector<ll>(T+1, 0)); REP (i, N) { REP (j, T) { // i番目の料理を食べる場合 chmax(dp[i + 1][min(T, j + vec[i].first)], dp[i][j] + vec[i].second); // i番目の料理を食べない場合 chmax(dp[i + 1][j], dp[i][j]); } // これを忘れない chmax(dp[i + 1][T], dp[i][T]); } // 集計して最大値を探す ll ans = 0; REP (i, T+1) chmax(ans, dp[N][i]); cout << ans << endl; }```
【ABC161】F - Division or Subtraction
解法
次のように定義する。
操作1、N が K で割り切れるとき、N を N/K に置き換える
操作2、そうでないとき、N を N−K に置き換える
場合分けして考える。
操作2だけでNを1にできるような数
これは、N-1の1以外の約数すべてが該当する。
理由
m回操作2を行うとNは、になる。(ただし、m≠0)
これが1になるとき、という方程式を立てることができ、変形すると、
になる。
mは整数であるため、KはN-1の約数になることがわかった。
操作1を1回以上行って、Nを1にできるような数
これはNの約数のうち、最初に操作1をn回行ったのち、操作2をm回行うことによってNを1にできるような数が該当する。
理由
操作2を1回でも行ったあとに、操作1をすることはできない。
これは、 であり、操作2を何回行ってもKで割り切れる数になることはないから。
そのため、操作1は最初にしか行うことができず、最初に操作1を行うことができる数は、Nの約数が該当する。
実装
Nが2以外の場合、必ずNとN-1が条件を満たすため、先に答えに加算しておく。
Nが2の場合、N-1=1となるため、条件を満たさないことに注意。(問題文をよく読もう)
あとは約数列挙して条件を満たすか確認すれば良い。
// 最初に操作1をn回行ったのち、操作2をm回行うことによってNを1にできるかどうかを判定 bool judge(ll i, ll N) { ll n = N; while (n > 1) { if (n % i == 0) n /= i; else break; } if ((n-1) % i == 0) return true; return false; } void solve(long long N){ if (N == 2) { cout << 1 << endl; return; } ll ans = 2; // N-Kの操作だけで1にできる数を求める for (long long i = 2; i * i <= N-1; ++i) { if ((N-1) % i == 0) { ans++; if ((N-1)/i != i) ans++; } } // N/Kを1回以上使って1にできる数を求める for (long long i = 2; i * i <= N; ++i) { if (N % i == 0) { ans += judge(i, N); if (N/i != i) ans += judge(N/i, N); } } cout << ans << endl; }
【ABC120】D - Decayed Bridges
解法
島をノード、橋を辺とするグラフを考える。
グラフの辺を削除するというのを、高速なアルゴリズムで実装するというのは難しい。
そのため、辺の削除をUnionFind-Treeなどを使って辺をつなげていくことで同じことを表現できないかを考えることにする。
(これは典型)
この問題では、辺を削除する順番が決まっているため、逆順に辺を追加していくことで答えを後ろから計算できそうな気がしてくる。
1~Mの全ての辺が削除された状態では、全ての島の組で不便な状態になっているため、不便さの合計は、になる。
ここで、M番目の辺を追加してみると、島の組のひとつが不便ではなくなるため、不便さの合計は、になる。
M-1, M-2, ..., とどんどん辺を追加していき、i番目の辺を追加したときの不便さの合計をans[i-1]とする。
i番目の辺を追加したとき、不便さは次のように計算できる。
- A[i]とB[i]が既に連結であったとき
- 不便ではなくなる島の組は増えないため、不便さはans[i]になる。
- A[i]とB[i]が連結ではなかったとき
- A[i]を含む連結成分の数をa、B[i]を含む連結成分の数をbとすると、不便さはans[i] - a * bになる。
- A[i]を含む連結成分とB[i]を含む連結成分から1つずつ島を取り出すような、組み合わせ方がa * b
実装
struct UnionFind { vector<long long> par, siz; UnionFind(long long n) : par(n, -1) , siz(n, 1) { } // 根を求める long long root(long long x) { if (par[x] == -1) return x; else return par[x] = root(par[x]); } // x と y が同じグループに属するかどうか (根が一致するかどうか) bool issame(long long x, long long y) { return root(x) == root(y); } // x を含むグループと y を含むグループとを併合する bool unite(long long x, long long y) { x = root(x), y = root(y); if (x == y) return false; if (siz[x] < siz[y]) swap(x, y); par[y] = x; siz[x] += siz[y]; return true; } // x を含むグループのサイズ long long size(long long x) { return siz[root(x)]; } }; void solve(long long N, long long M, std::vector<long long> A, std::vector<long long> B){ UnionFind Uf(N+1); // 答え vector<ll> ans(M, 0); // sum(n): 1~nまでの総和を返す ans[M-1] = sum(N-1); // 後ろから橋をつなげていく for (int i = M-1; i >= 1; i--) { // 既にA[i]とB[i]が行き来可能ではない場合 if (!Uf.issame(A[i], B[i])) { ans[i - 1] = ans[i] - Uf.size(A[i]) * Uf.size(B[i]); Uf.unite(A[i], B[i]); // 橋を作る } else { ans[i - 1] = ans[i]; } } REP (i, M) { cout << ans[i] << endl; } }
【ABC122】D - We Like AGC
解法
3つの条件を上から順に条件1、条件2、条件3と呼ぶことにする。
3つ目の条件が存在しない場合、次のDPで解くことができる。
dp[i][j][k] ← 長さiでi-1文字目がj、i文字目がkであるような条件1,2を満たす文字列はいくつあるか
遷移をする際には、i + 1文字目に追加する文字列をcとすると、
- j = 'A', k = 'G', c = 'C' であるとき
- 部分文字列に'AGC'を含むため、遷移しない
- それ以外のとき
- dp[i+1][k][c] ← dp[i+1][k][c] + dp[i][j][k]
ただしこの問題では、隣接する文字をスワップした場合に、条件1,2を満たさない文字列は排除しないといけないため、このDPを改良する必要がある。
上のDPでは、末尾3文字の並びがどうなっているかによって遷移の仕方を変えていたので、改良するに当たって、条件1,2を満たし、条件3を満たさないような末尾の文字列の並び方にどのようなものがあるかを考える。
すると、下のようなパターンがあることがわかる。
- 末尾3文字の文字列が条件3だけ満たさないとき
- サンプル1の解説を見るとわかるが、'ACG'と'GAC'が該当する
- 末尾4文字の文字列が条件3だけ満たさず、'ACG'と'GAC'を含まないとき
- 任意の文字を＊と表現すると、'A＊GC'と'AG＊C'が該当する
- 末尾5文字以上の文字列が条件3だけ満たさず、'ACG'、'GAC'、'A＊GC'、'AG＊C'を含まないとき
ということで、末尾4文字の並びがどうなっているかを状態に持つDPをすれば解けることがわかった。
定義は、
dp[i][j][k][l] ← 長さiでi-2文字目がj、i-1文字目がk、i文字目がlであるような条件1~3を満たす文字列はいくつあるか
遷移をする際には、i + 1文字目に追加する文字列をcとすると、
- 'AGC'、'ACG'、'GAC'、'A＊GC'、'AG＊C'が末尾に含まれるとき
- 条件1~3を満たさないため、遷移しない
- それ以外の場合
- dp[i+1][k][l][c] ← dp[i+1][k][l][c] + dp[i][j][k][l]
初期化する際には、少し注意が必要で、'T'が条件に影響を及ぼさないことを利用し、
dp[0]['T']['T']['T'] ← 1
としておく。
すべての遷移が終了後、j, k, lを全探索し、dp[N][j][k][l]を集計すれば答えを得ることができる。
実装
void solve(long long N){ // dpテーブル vector<vector<vector<vector<mint>>>> dp(N+1, vector<vector<vector<mint>>> (4, vector<vector<mint>>(4, vector<mint>(4, 0)))); // 文字とインデックス番号の対応付け vector<char> c = {'A', 'C', 'G', 'T'}; // 無害なTで初期化 dp[0][3][3][3] = 1; REP (i, N) { REP (j, 4) { REP (k, 4) { REP (l, 4) { REP (m, 4) { // AGC if (k == 0 && l == 2 && m == 1) continue; // ACG if (k == 0 && l == 1 && m == 2) continue; // GAC if (k == 2 && l == 0 && m == 1) continue; // A*GC if (j == 0 && l == 2 && m == 1) continue; // AG*C if (j == 0 && k == 2 && m == 1) continue; dp[i + 1][k][l][m] += dp[i][j][k][l]; } } } } } // 答えを集計 mint ans = 0; REP (j, 4) { REP (k, 4) { REP (l, 4) { ans += dp[N][j][k][l]; } } } // 出力 cout << ans << endl; }
【ABC220】D - FG operation
解法
全探索しようとするとO(2N)になってしまうような問題はDPで解けることが多い。
なので、DPで解くことを考えてみる。
i回目の操作F, Gは次のように言い換えられる。
- 左端と左からi + 1番目の値を計算して、現在の左端と入れ替える
ここで、i回目の操作を行った後に、i + 1回目の操作に影響するのは、i回目現在の左端の数字だけである。
(左からi + 1番目の値は最初から決まっているので)
そのため、現在の左端の数字を状態として持つDPをすることにする。
DPの定義としては、
・ dp[i][j] ← i回目の操作をした結果、左端の数字がjであるような場合の数
遷移は、操作F or 操作Gの二択になるので、
- 操作Fをするとき
- (現在の左端の数字 + A[i + 1]) を10で割った数が次の左端の数字になるので、
- dp[i + 1][(j + A[i + 1]) mod 10] += dp[i][j] mod 998244353
- 操作Gをするとき
- (現在の左端の数字 × A[i + 1]) を10で割った数が次の左端の数字になるので、
- dp[i + 1][(j × A[i + 1]) mod 10] += dp[i][j] mod 998244353
初期値は、左端の数字が最初のパターンになるので、
・dp[0][A[0]] = 1
答えは、N-1回操作した後に左端がjであるような数字をそれぞれ出力すればいいので、下のように実装すればよい。
for (int j = 0; j < 10; j++) { // dp[N-1][j]を出力 cout << dp[N-1][j] << endl; }
実装
modintを使ったので、mod 998244353の部分は省略しています。
void solve(long long N, std::vector<long long> A) { // DPテーブル vector<vector<mint>> dp(N, vector<mint>(10, 0)); dp[0][A[0]] = 1; REP (i, N-1) { REP (j, 10) { // 操作Fをした場合 dp[i + 1][(j + A[i + 1]) % 10] += dp[i][j]; // 操作Gをした場合 dp[i + 1][(j * A[i + 1]) % 10] += dp[i][j]; } } // 出力 REP (j, 10) { c(dp[N-1][j].val); } }
