ターミナルで cargo new my-crate を実行して my-crate プロジェクトを作成後、src/main.rs と src/lib.rs をそれぞれ次のように変更してコンパイルするとエラーが発生します。 // src/main.rs extern crate my_crate; use my_crate::MyStruct; fn main() { …

有向グラフがDAGである場合は"Yes"を、閉路を含む場合は"No"を出力するコードです。DAGであるときは、xにトポロジカルソートの結果が入ります。していることはBFSですが、キューを使わないことでグラフの辿る順序を保存できています。面白いです。 #include <bits/stdc++.h></bits/stdc++.h>…

シンプルなダイクストラの実装です。 本質部分の実装はわずか14行で済んでいます。 #include <bits/stdc++.h> using namespace std; const long long INF = 1e18; struct Edge { int to, cost; Edge(int to, int cost) : to(to), cost(cost) {} }; int main() { int n, m; c</bits/stdc++.h>…

昇順にソートされたリストから任意の値のインデックスを取得したいことがある。 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を行…

ABC152FでDPの解法を思いついた。けど、畳み込みがボトルネックになってO(N2^{2M})くらいかかる。計算量的には間に合わないけど、一度実装してみたいので実装する。 思いついた解法、もしかすると「アダマール変換」で高速化できるかも。もしそうだったら面…

AtCoder ABC152 F - Tree and Constraints https://atcoder.jp/contests/abc152/tasks/abc152_f 解けなくて悔しい。まだ解説に目を通していない。 解けるまで考えるか、解説を見てしまうか悩む。 おそらく言い換えることで簡単な問題になると思うけど、言い…

最新のもの https://gist.github.com/penguinshunya/62876b344a05600422965668f02b43cd ※以下のテンプレートは少し前のもの #include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < int(n); i++) #define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--) #defi</bits/stdc++.h>…

割り算を実装したのは久しぶり。 問題 yukicoder.me 考察 整数部分は普通にA / Bで計算し、小数点以下は筆算と同じ方法で計算する。 その際に「B * x <= Rを満たす最大の整数x」みたいなのを求めたくなるけど、これは数学を使うとO(1)で求められる。 具体的…

このタイトルを付けて思い出したけど、一昨日に多項式と形式的べき級数を学んだ。 具体的には、次のサイトの問題を解いた。 maspypy.com ということで、次の条件を満たす数え上げ問題は、多項式・形式的べき級数の問題に言い換えられるようになった。 状態が…

ceil(N / P) = Aを満たすNの最小値と最大値を求めたい。 この条件式は、A - 1 < N / P <= Aとも表せる。 そして、この条件式にPをかけてP(A - 1) < N <= PAを得る。 すべての変数が整数であるとき、(N_min, N_max) = (P(A - 1) + 1, PA)となる。 最初の太字…

さくさく解けて楽しかった。

検索される文字列をs、検索する文字列をtとおいたとき、次のようにループを書けばバグは発生しない。 for (int i = 0; i + t.size() <= s.size(); i++) { if (s.substr(i, t.size()) == t) { /* */ } } ポイントは半開区間[l, r)で考えること。 |S| = S.size…

次の3つのルールを守る。 キューに追加する直前に、まだ距離配列が更新されていないかをチェックする キューに追加するときに距離配列を更新する それ以外の場所で距離配列をチェックしたり、更新したりしない このルールを守ることで、シンプルかつバグの発…

問題 Convex-Hull Trickの入門に最適な問題。 DPの更新式を変形することでmin({ A[1]*x + B[1], ..., A[i]*x + B[i] })の形を得て、これはConvex-Hull Trickでの高速化を望める。