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

色々機能を追加する前の実装。 参考にしたページ 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/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 解けなくて悔しい。まだ解説に目を通していない。 解けるまで考えるか、解説を見てしまうか悩む。 おそらく言い換えることで簡単な問題になると思うけど、言い…

割り算を実装したのは久しぶり。 問題 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での高速化を望める。

問題 初めて行列演算が腑に落ちた気がする。 行列演算を使うことで、ベクトルの各成分の入れ替えたり、ついでに成分の値を倍にしたりできる。この問題だと、位置を64要素を持つベクトルと見て、移動を64x64行列の演算と見なせる。 今回の問題の自然な解き方…

問題 蟻本の復習みたいな感じ。 まずはじめに思いつくDPは以下のようなもの。 DP定義 dp[i][j][k] = 真偽値 i : 解いた問題の数 j : 雪男くんの解いた問題の合計秒数 k : 雪女さんの解いた問題の合計秒数 初期値 dp[0][0][0] = true dp[i][j][k] = false (i …

DP配列の大きさを制約ギリギリの大きさにする修行を行っている。 境界値に強くなりたいという理由。 けっこう境界値に強くなっていってる感覚はある。いい傾向。

次の問題を解いた。 yukicoder No.783 - 門松計画 問題 この問題の解説を見ることで、個数制限なしナップサックDPを使えるようになった。個数制限なしナップサックDPについて少し勘違いしていて、次の順序でDPをするものだと思っていた。 荷物1を可能な限り…

yukicoder No.798 - コレクション 問題 自力で解けなかった。悲しい。 Ai + Bi * dという式を見た途端、頭の中がConvex-Hull Trickで支配された。そのせいか、「Biの降順で選ぶのが最適」という簡単な事実にすら気付かなかった。解説をチラ見してこの事実を…

問題 解けなかった。悔しい。 想定解法は、累積和といもす法という2つの基本的なアルゴリズムを組み合わせるというもの。しかし、これがわからなかった。通した今でもよくわかっていない。 図を書いて理解した。 dp[i][j]を配るという発想ではなく、範囲に着…

そんな病気にかかっているので、しばらく過去問を解く期間が続きます。

Convex-Hull Trickについては理解したけど、DPの遷移式をどのように変形するかがわからない。そこで、問題にあるタグ「Monge」で検索すると、何だかそれらしい情報がヒットする。しかし、これについても結局よくわからなかった。 Mongeを知っていく過程でこ…

DPは他の知識と組み合わせて使う場合が多い。 累積和だったりセグ木だったりコンビネーションだったり。 つまり、DPの問題を安定して解くためには、それら周辺知識が必要不可欠。 周辺知識を増やせばDPの問題も解けるようになってくる。 今日はこちらの問題…