はまやんはまやんはまやん

hamayanhamayan's blog

2019-01-02から1日間の記事一覧

Tapris and Noel play the game on Treeone [yukicoder No.768]

https://yukicoder.me/problems/no/768 前提知識 バックトラック 全方位木DP 考察過程 1. 全頂点についてなにかするやつは全方位木DPを真っ先に疑ってしまう 2. 違う場合の方が多いのだが、今回はそれで行けそう 3. 一般化すると、全頂点の判定はまず1頂点に…

UNOシミュレータ [yukicoder No.769]

https://yukicoder.me/problems/no/769 解説 https://yukicoder.me/submissions/307913色々な変数を定義して、シミュレーションをしよう。 cards[i] := プレイヤーiが何個のカードを出したか cu := 現在のプレイヤー dir := 現在の方向(1か-1) draw2 := ド…

しおり [yukicoder No.771]

https://yukicoder.me/problems/no/771 前提知識 bitDP 解法 https://yukicoder.me/submissions/307901制約からbitDP感がある。 その方向で考えると、以下のDPができる。 dp[msk][lst] := 今までmskの本が本棚に入っていて、最後の本がlstのときの醜さ ここ…

コンテスト [yukicoder No.773]

https://yukicoder.me/problems/no/773 解法 https://yukicoder.me/submissions/307869d=23,24,25でA≦d≦Bを満たさないものを数えることにする。 「A≦d かつ d≦B」の否定は「A>d または d>B」なので、これを判定する。 この法則はドモルガンの法則と呼ばれ…

A Simple RMQ Problem [yukicoder No.776]

https://yukicoder.me/problems/no/776 前提知識 特殊なマージをするセグメント木 解説 https://yukicoder.me/submissions/307861実装をする。 セグメントツリーに複数要素をもたせるパターンがある。 セグメントツリーの各頂点には以下の要素をもたせる。 …

再帰的ケーキ [yukicoder No.777]

https://yukicoder.me/problems/no/777 前提知識 座標圧縮(座圧) 動的計画法 区間maxのセグメントツリーによるDP高速化 考察過程 1. 今回の問題のように包含関係を使うものは、上における場合にケーキの間に有効辺を貼るとDAGになるので、DPになりやすい傾…