問題 初めて行列演算が腑に落ちた気がする。 行列演算を使うことで、ベクトルの各成分の入れ替えたり、ついでに成分の値を倍にしたりできる。この問題だと、位置を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の状態と遷移について、少しずつ考えるコツ…

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

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

ある漫画の話をしているときに、僕はこのキャラが一番好きと発言したとする。 その発言をした人は、本当にそのキャラのことが好きなのか、みたいなことを考える。 もしかすると、「そのキャラが好きだと発言することで、自分はこのように思われたい」みたい…

数え上げ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で解くこと…

面白かった。 アニメもあるのでまた観る。

僕も切磋琢磨できるような仲間が欲しい。 似た実力の人を見つけて、お互いに問題を出し合ったりしたい。 そして、解法について話したりしたい。 しかし、僕は人とまともに会話することができないし、 もう30歳にもなるのに人に胸を張って言える仕事をしてい…

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

答えはシンプルで、ただ楽しく生きてほしい。 というか、別に「子→親」だけに限らない気がする。 少なくとも、僕の身内は僕に楽しく生きていてほしいと望んでいる。 そして、僕自身も楽しく生きたいと思っている。 僕も僕の身内も望んでいることなので、これ…

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