問題 初めて行列演算が腑に落ちた気がする。 行列演算を使うことで、ベクトルの各成分の入れ替えたり、ついでに成分の値を倍にしたりできる。この問題だと、位置を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の降順で選ぶのが最適」という簡単な事実にすら気付かなかった。解説をチラ見してこの事実を…