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での高速化を望める。

問題 初めて行列演算が腑に落ちた気がする。 行列演算を使うことで、ベクトルの各成分の入れ替えたり、ついでに成分の値を倍にしたりできる。この問題だと、位置を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の問題も解けるようになってくる。 今日はこちらの問題…

次のようなコードをエディタのスニペットに登録しておくと楽。 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の状態と遷移について、少しずつ考えるコツ…

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

もう数回は転職している。 しかもたいした理由もなく。 そのせいで、職歴がボロボロになってしまった。 履歴書を書くのが怖い。 けれど、やっぱり安定したところで働きたい。 自分に合った仕事をし、その間に少しずつ競プロの問題を解いたり自作アプリを作成…