問題 蟻本の復習みたいな感じ。 まずはじめに思いつく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の問題も解けるようになってくる。 今日はこちらの問題…

次のようなコードをエディタのスニペットに登録しておくと楽。 struct $1 { $2 bool operator<(const $1 &that) const { #define lt(x) if (x != that.x) return x < that.x; #define gt(x) if (x != that.x) return x > that.x; $0 #undef gt #undef lt ret…

こちらの問題を解いたのだけど、証明がまだきちんとできないことに気付いた。 証明したいのは「既に食べるピザが決まっているとき、価格の降順でソートして前から有料→無料→有料→…のように買うのが最善」という命題。交互に食べることが最善だなんてどうやっ…

桁DPの基本形 auto digit = [](long long n, int x) { while (x - 1) n /= 10, x--; return n % 10; }; dp[0][0][0] = 1; rep(i, 20) rep(j, 2) rep(k, 2) rep(d, 10) { if (j == 0 && d > digit(N, 20 - i)) continue; int _i = i + 1; int _j = j == 0 && …

問題を作った 1以上N未満の整数のうち、数字が昇順になっているものはいくつあるか。たとえば159, 1124457889, 5などがこれに該当する。制約は1 <= N <= 10^18。 解説 遷移は以下の図。 状態数は10。遷移は、現在の状態の数字よりも選択した数字のほうが小さ…

オートマトンと桁DP 桁DPは以下の図でだいたい説明できる。 0埋めDP（今命名）は以下の図。 この2つのDPの状態は独立しているので積が取れる（以下の表のNは上限）。 桁DP 0埋めDP 意味 0 0 N = 0のときの0 0 1 N > 0のときのN 1 0 N > 0のときの0 1 1 0 < D …

TopCoderのDPの問題を解いていて、色々思うことがあるので書いていく。 DPの種類 数え上げDP 配るDPが多い。初期値は dp[0][0]...[0] = 1みたいなのが多く、この1を様々な状態に分配していく。根から葉への有向辺をもつ木をイメージするとわかりやすい。 遷…

遅延伝搬セグメント木（遅延評価セグメント木、遅延セグ木）の実装。 #include <bits/stdc++.h>とusing namespace std;があれば動く。 コンストラクタは6つの引数を取る。 要素の数 2つの範囲の値をマージした結果を返す関数 遅延させていた値を範囲の値に反映する関数。第</bits/stdc++.h>…

TopCoder SRM 771 Div1 Medium - TwoMonthScheduling 問題自体が複雑なので、理解するのに半日かかった。 そして、そこから実際に解き終わるのにも半日かかった。 とても本番のコンテストで解けそうにない。 ただ、問題が解けたということは知識量的には問題…

TopCoder SRM 771 Div1 Medium - TwoMonthScheduling こちらの問題に昨日から挑戦している。 丸一日かかってようやく実装の方向性が見えてきた。 おそらく遅延セグ木とかを使って計算量O(N2 logN)になると思う。 DPの状態と遷移について、少しずつ考えるコツ…

貪欲法には「小さい順に選ぶのが最善」みたいなのがよくある。 しかし、それが最善である根拠は特になくて、「自明」であったり「なんとなく」であったりする。 僕もこれまで「なんとなく正しそうだから」という理由で貪欲法を使うことがあった。しかしそれ…

数え上げDPで求められる対象はDAGだけ。 ただ、閉路が含まれていても、移動回数が有限であれば求められる。 確率と期待値はこれと異なり、DAGでないかつ移動回数が無限であっても求められることがある。ただ、求める際には代数学の式変形を使う必要がある。 …

寝て起きたら解けた。 TopCoder SRM 771 Div1 Easy - AllEven A以上B以下の整数のうち、0 ~ 9の各数字の出現回数が偶数である整数はいくつあるか、を求める問題。たとえば121222, 77, 355232などがこの条件を満たす。制約は0 <= A, B <= 10^18 - 1。 DPで解…

DPで解く問題だとわかっていても解けない。 たとえば以下の問題。 TopCoder SRM 771 Div1 Easy - AllEven A以上B以下の整数のうち、0 ~ 9の各数字の出現回数が偶数である整数はいくつあるか、を求める問題。制約は0 <= A, B <= 10^18 - 1。 既にDPで解くこと…

Topcoder SRM 774 Div1 Medium ClassRankings 上記の問題を解こうとしたけど解けなかった。 Topcoderの検索ページでカテゴリ「Dynamic Programming」で検索した際に一番上に表示された問題がこの問題だった。 DPを次のように定義する。 dp[x][a][b][c] := 点…

昨日DPの問題を解いたとき、おかしなDPを定義してしまった。 シンプルにいえば次のような定義をした。 dp[i] := 2iの最大値 一番おかしい点は「2iの最大値」の部分である。 2iに最大値も最小値もないのに、このような定義をしてしまった。 シンプルな例であ…

文字列検索の計算量を減らしたいときに使われるアルゴリズムの一覧です。といっても、2019/07/29現在はローリングハッシュのみです。随時追加していきます。【2019/07/30追記】Z AlgorithmとKMP法と接尾辞配列の項目を追加しました。 文字列\(S\)に部分文字…

yukicoder.me 考察 この問題は、「合計が\(X\)以下となる\(0\)以上の整数\(D-1\)個の組はいくつあるか」という問題に言い換えられます。そしてこの問題はベル数やスターリング数を求めるときのように、漸化式を立てることで数え上げることができます。 実装 …

yukicoder.me 概要 以下の条件を満たす数列\((A_1, \ldots, A_N)\)は何通りあるでしょうか。\(10 ^ 9 + 7\)で割った余りを求めてください。 \(A_1 + \ldots + A_N = S\) 任意の\(i(1 \le i \le N - 1)\)に対して\(A_i + K \le A_{i + 1}\) 制約：\(2 \le N \…

Link-Cut Treeについてのメモです。 回転操作を行っても、左右の位置関係の情報は失われない 最初は、回転操作を行うと左右の位置関係の情報は失われると思っていました。Link-Cut Treeの仕組みの理解を妨げていた最大の誤解です。平衡二分探索木で回転操作…

atcoder.jp 概要 \(N\)頂点\(M\)辺の単純な無向グラフがあります。以下のクエリが\(Q\)個与えられるので答えてください。 頂点\(A, B, C\)について、同じ辺を2度通らないパス\(A\)→\(B\)→\(C\)は存在するか 制約：\(3 \le N \le 10 ^ 5\)、\(1 \le M \le 2 \…

木DPを使って解ける問題には、以下のものがあります。 ある頂点から最も遠い頂点までの距離はいくつか ある頂点を根としたときの木の深さはいくつか これらの問題に共通していることは、「ある頂点」という文言が含まれていることです。頂点数を\(N\)とおい…

LCAを求める方法はいくつかありますが、今回はダブリングを使う方法とHL分解（Heavy Light Decomposition）を使う方法を紹介します。【追記】オイラーツアーを使う方法を追加しました。【追記】Link-Cut Treeを使う方法を追加しました。 ダブリングによる実…