深さ優先探索において,引数に母親を指定する
久々の更新ですが,メモを書いておきます. 深さ優先探索において,母親を指定しておくと一回行ったかどうかを判定しなくてもいい.
void dfs (ll i, ll pa = -1) { dp[i][0] = 1; dp[i][1] = 1; for (auto j : box[i]) { if (j != pa) { dfs(j, i); dp[i][0] = ((dp[i][0] % mod) * ((dp[j][0] + dp[j][1]) % mod)) % mod; dp[i][1] = ((dp[i][1] % mod) * (dp[j][0] % mod)) % mod; } } }
深さ優先探索において,引数に母親を指定する
久々の更新ですが,メモを書いておきます. 深さ優先探索において,母親を指定しておくと一回行ったかどうかを判定しなくてもいい.
void dfs (ll i, ll pa = -1) { dp[i][0] = 1; dp[i][1] = 1; for (auto j : box[i]) { if (j != pa) { dfs(j, i); dp[i][0] = ((dp[i][0] % mod) * ((dp[j][0] + dp[j][1]) % mod)) % mod; dp[i][1] = ((dp[i][1] % mod) * (dp[j][0] % mod)) % mod; } } }
深さ優先探索において,引数に母親を指定する
久々の更新ですが,メモを書いておきます. 深さ優先探索において,母親を指定しておくと一回行ったかどうかを判定しなくてもいい.
D - Remainder Reminder 〜ABC090〜
問題
感想
かなり手こずった... 簡単な方のD問題のはずなのだが.
考え
a, b, k
のいずれか一つを全探索する方法でない限り,制約条件的に時間以内にACすることはできない.
b
に注目することで,余りの周期性を利用することができるためb
とa
の上限n
からあまりがk
以上の組み合わせを求めることができる.
a
やらk
を全探索することを考えてずっと手こずっていました.....悔しい.
Accepted Program
#include <iostream> #include <math.h> using namespace std; #define ll long long int main () { ll n, k; ll ans = 0; cin >> n >> k; if (k == 0) { cout << n * n << endl; return 0; } for (ll i = k + 1; i <= n; i++) { ans += i - k; ll sub = n % i; if (sub >= k) { ans += sub - k + 1; } sub = n / i - 1; ans += sub * (i - k); } cout << ans << endl; }
D - Wide Flip 〜ABC083〜
問題
はじめに
あけましておめでとうございます。
今年も精進していきます。
考え
計算量をまず考えると,O(NlogN)
の解法を思いつかないといけないことに気づく。logN
の計算量を持つ解法としてニブタンぐらいしか知らない()ので,とりあえずニブタンでできないか考える。
K
がある値i
のとき,S
の要素を0にできるとすると,i
以下の値では必ずS
の要素を0にすることができるということがわかる。
つまり,配列としてdp[i]:K = i の時成功したら1,成功しなかったら0
と言うように考えると二分探索に落とし込むことができる。なぜならある値i
で成功しなかったら,左側(left = mid
)として,成功したら,右側(right = mid
)とすることができるからである。
なので,最終的には二分探索 + K = i
の時に成功できるか否かを決める関数,を実装することで完成する。
Accepted Program
#include <iostream> #include <string.h> using namespace std; int solve (string s, int k, string sub) { int sum = 0; for (int i = 1; i <= s.size() - k; i++) { if (i <= k) { int now = s[i] - '0'; now = (now + sum) % 2; if (now == 1) { sum++; sub[i] = '1'; } } else { if (sub[i - k] == '1') { sum++; } int now = s[i] - '0'; now = (now + sum) % 2; if (now == 1) { sum++; sub[i] = '1'; } } } // sub[i] == '1'→ 0と1を回転させた. int first = 0; for (int i = (s.size() - k); i < s.size(); i++) { int now = s[i] - '0'; if (i == (s.size() - k)) { now = (now + sum) % 2; first = now; if (first == 1) { sub[i] = '1'; } else { sub[i] = '0'; } } else { if (i - k >= 1) { if (sub[i - k] == '1') { sum++; } } now = (now + sum) % 2; if (now == 1) { sub[i] = '1'; } } } // まずは,連続しているか確かめる bool follow = true; char last; int count = 0; int num = 0; for (int i = s.size() - k; i <= s.size() - 1; i++) { if (sub[i] == '1') { if (k <= (i - 1)) { // ok } else { follow = false; } } } if (follow) { return 1; } return - 1; } int main () { string s; cin >> s; s = "a" + s; string sub; for (int i = 0; i < s.size(); i++) { sub = sub + "0"; } int left = 0; int right = s.size(); /* for (int i = 1; i <= s.size() - 1; i++) { cout << i << " " << solve(s, i, sub) << endl; } */ while (left < right - 1) { int mid = (left + right) / 2; if (solve(s, mid, sub) == 1) { left = mid; } else { right = mid; } } cout << left << endl; }
D - トランプ挿入ソート
問題
感想
最長増加部分列むずい.....
考え方
どの要素を取り出してもよくて,それからどこに挿入してもよいということなので,取り出さなくてよい数(組)はどのようなものなのかを考えると良い。
要素を取り出して挿入するということは,その取り出した数字はsortされていなかったということになる。つまり,取り出さない数字の組は逆に言うとsort済みということである。
よって,結果的には,与えられた組に対して最長増加部分列を求めればよいことになる。
とはいえ,最長増加部分列の実装はかなり悩みました。解説ではニブタンを使ってますが自分の実装はちょっと変ですね....笑
Accepted Program
#include <iostream> #include <utility> #include <algorithm> #include <map> using namespace std; int main () { int n; cin >> n; int a[n + 1]; map<int, int> box; a[0] = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; box[a[i]] = i; } int dp[n + 2]; for (int i = 0; i <= n + 1; i++) { dp[i] = 0; } int now = 0; for (int i = 1; i <= n; i++) { if (i == 1) { dp[i] = a[i]; now = i; } else { int jmax = a[i] - 1; if (a[i] > now) { jmax = now; } for (int j = jmax; j >= 0; j--) { if (dp[j] < a[i]) { if (dp[j + 1] > a[i] || dp[j + 1] == 0) { dp[j + 1] = a[i]; now = (j + 1 > now) ? j + 1 : now; } break; } } } } int max = -1; for (int i = 1; i <= n; i++) { if (dp[i] > 0) { max = i; } } cout << n - max << endl; }
D - サプリメント 〜ABC017〜
問題
D: サプリメント - AtCoder Beginner Contest 017 | AtCoder
考え方
動的計画法を用いる。
AtCoder Beginner Contest 017 解説 の言葉で言う,「dpで足せる区間」を求める際に自分はlatest[i] = j
を使った(i
というサプリメントが直近で一番最初に出てくる番号はj
)。
実装が大変でした。プログラム自体はそこまで長くはないのですが,「dpで足せる区間」が具体的に何に該当するか分かるまでに時間がかかりました。
Accepted Program
#include <iostream> #include <map> using namespace std; #define ll long long #define mod 1000000007 #define max 100001 ll pure[max], latest[max]; void init (void) { // 2^n ll sub = 1; pure[0] = 1; pure[1] = 1; latest[1] = -1; for (ll i = 2; i < max; i++) { latest[i] = -1; } } int main () { init(); ll n, m; cin >> n >> m; ll f[n]; ll ans[n]; ll sum[n + 1]; sum[0] = 0; ll num[n]; bool ok[n]; for (ll i = 0; i < n; i++) { cin >> f[i]; ans[i] = 0; sum[i + 1] = 0; num[i] = 0; ok[i] = false; } for (ll i = 0; i < n; i++) { if (i == 0) { num[i] = 1; latest[f[i]] = 0; } else { if (latest[f[i]] == -1) { num[i] = num[i - 1] + 1; } else { // まずは i の位置とlatest[f[i]]の位置の差を見て // num[i - 1]との関係を求める. int j = i - num[i - 1]; int l = latest[f[i]]; if (j > l) { ok[i] = true; num[i] = num[i - 1] + 1; } else { num[i] = i - l; } } latest[f[i]] = i; } } for (ll i = 0; i < max; i++) { latest[i] = -1; } for (ll i = 0; i < n; i++) { if (i == 0) { ans[i] = 1; } else { if (num[i] == i + 1) { ans[i] = (ans[i - 1] * 2) % mod; } else { if (ok[i]) { ans[i] = (ans[i - 1] * 2) % mod; } else { ans[i] = (ans[i - 1]) % mod; ans[i] = (ans[i] + sum[i - 1]) % mod; ans[i] = (ans[i] + mod - sum[i - num[i]]) % mod; } } } sum[i + 1] = (sum[i] + ans[i]) % mod; latest[f[i]] = i; } cout << ans[n - 1] << endl; }