昇順にソートされたリストから任意の値のインデックスを取得したいことがある。 lower_bound()を使えばいいかもしれないけど、検索対象のデータ構造がvector<pair<int, int>>で、検索したいのがペアの1つ目の要素であるようなとき、lower_bound()を使う方法だと少しよくわか</pair<int,>…

C++では、通常、再帰呼び出しを行うラムダ関数には型定義を与える必要がある。 しかし、少し冗長な書き方をすることで型定義を省略できる。 auto dfs = [&](auto dfs, int u) -> void { for (auto v : g[u]) dfs(dfs, v); }; -> voidの部分は忘れやすいので…

遅延セグ木よりも定数倍速い。 遅延セグ木のコードの実行時間 : 1154ms 遅延セグ木部分だけをBITに置き換えたコードの実行時間 : 701ms 参考にしたページ Binary Indexed Tree のはなし - hos.ac verify済み Submission #70922924 - Codeforces struct Fenwi…

verify済み関数 for_each_edge : https://atcoder.jp/contests/abc133/submissions/10044047 lca : http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4170006#2 subtree_edge : http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4169995#2 for_e…

色々機能を追加する前の実装。 参考にしたページ http://beet-aizu.hatenablog.com/entry/2017/12/12/235950 https://codeforces.com/blog/entry/53170 struct HLD { vector<vector<int>> g; vector<int> vid; vector<int> head; HLD(vector<vector<int>> g) : g(g) { int n = g.size(); vid = </vector<int></int></int></vector<int>…

場合の数に関する新たな事実を知った。 「赤の玉が3個、緑の玉が4個、青の玉が2個のときに、横に並べる方法は何通りあるか」の答えは「9個から3個を選び、残りの6個から4個を選ぶ」と同じであるため\( {}_9 \text{C}_3 \times {}_6 \text{C}_4 \)となるが、…

木DPが苦手なので、克服するために木DPの問題を解いている。 そして先ほど、Typical DP Contest N - 木を解説ありで解いた。数ヶ月前は解説を読んでも理解できずに諦めていたので、多少は成長しているよう。 自分なりの木DPの書き方を確立できているのも大き…

AtCoder Educational DP Contest T - Permutation こちらの問題の解法を理解したので書き残す。 …と思ったけど、言葉にできるほどきちんと理解していないことに気付いた。 とりあえず、中途半端な状態だけど書き残すことにする。 順列の位置を横軸、要素の値…

こちらの問題を、ネットの情報を参考にしながら解いた。 ビット集合で区間DPのようなことをできるという発想が面白いし、何よりもビット集合Sの部分集合Tをfor (int T = S; T >= 0; T = (T - 1) & S) { ... }で重複なく不足なく列挙できるとは思わなかった。…

DP まとめコンテストの問題を解いていってるのだけど、T問題が自力で解けそうにない。答えを見ずに解くか、それとも見てしまうか微妙なライン。もう少し考えれば解ける気がする。寝ながら考えよう。

先ほどJavaScriptで書いた三分探索のコード。 const binary_search = () => { let l = -10, r = 10; for (let i = 0; i < 30; i++) { let l_ = l + (r - l) / 3; let r_ = r - (r - l) / 3; if (query(l_) > query(r_)) l = l_; else; r = r_; } return l; };…

LCA LCAが思っていた以上に使えることがわかった。 重み付きの木で「ある頂点からある頂点までのコストを求めよ」という105個くらいのクエリに答えたいとき、別に全方位木DPを使わなくてもよくて、LCAで事足りる。 LCAの準備の過程で根からの深さも求まって…

木の問題はたいてい何回かDFSを行う必要がある。まだDFSに慣れていないので、バグなく一発で実装を終えることは稀。 たとえば、DFSを中断させたくてreturnしたのに、再帰呼び出し側でreturnせずに処理を続行させてしまったり…みたいなバグを埋め込んでしまう…

問題 https://atcoder.jp/contests/abc147/tasks/abc147_f 考察 普通に全探索すると、列挙だけで\(O(2 ^ N)\)かかるので間に合わない。ここで高橋君の取る要素の数を\(k\)とおくと、\(S - T\)は以下の式で表せる。 $$kX + tD - ((N - k)X + aD)$$ \(t\)は高…

コンテスト本番だと解けそうにない…。 問題 https://atcoder.jp/contests/abc150/tasks/abc150_d 考察 条件式を変形すると「任意の\(k\)に対して\(\frac{X}{a_k} - \frac{1}{2}\)が非負整数か」と言い換えられ、\(a_k = 2b_k\)とおくと更に「任意の\(k\)に対…

パスの端点sとtが与えられるので、パス経路上の点と辺を列挙してください。頂点数は106です。 随時更新

問題 https://atcoder.jp/contests/abc152/tasks/abc152_f 考察 次のようなDPを定義する。 dp[i][j] := 通り数 i : 頂点番号 j : 満たす制約の集合 あらかじめ、「ある辺を黒で塗ったときにどの制約を満たすか」を求めておく。その上で、根付き木上でDPを行…