読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

yukicoder No.437 cwwゲーム

問題 問題概要 省略。 解法 何番目の文字を使用したかをsetで保持しながら、再帰関数でやった。再帰関数の中は、条件を満たすものを3重ループで全探索している。メモ化再帰しなくてもギリギリ通る。メモ化すると、だいぶ速くなった。 ミス TLEを連発してつら…

yukicoder No.134 走れ!サブロー君

問題 問題概要 巡回セールスマン問題に辺のコストを加えたもの。 解法 巡回セールスマン問題ですね。bitDPで解きました。ただ今回の問題は、荷物をどれだけ持っているかで、1単位を移動するのにかかる時間が異なるので、それを前計算で、weight[mask] := mas…

yukicoder No.107 モンスター

問題 問題概要 省略 解法 bitDPで解いた。 dp[mask][lim] := 集合maskのモンスターと戦った時に最大体力が lim * 100 の時に、残りの体力の最大値 として、ループで回していった。 limは100から100とばしに1600までしか使わないので、簡単な座圧的な感じで、…

yukicoder No.50 おもちゃ箱

問題 問題概要 もっとも多くの区間に含まれている数字を囲んでいる区間の総数を求める問題。 解法 すぐbitDPだろうなというのはわかる。ただ、どうやって、実装するかわからん。箱を使う最小値を求めればいいのだから、箱は大きいものから使用していけばいい…

yukicoder No.357 品物の並び替え (Middle)

問題 問題概要 数字を並び替えた時に、条件を満たし、もっとも得点を獲得できる時の得点を求める。 解法 数字の数の最大値が14である。数字をすべて並び替える解法だと、計算量が(n!)になるので、TLE。そのためには計算量を(2n)にしなければならない。そこで…

yukicoder No.286 Modulo Discount Store

問題 問題概要 省略 解法 bitDP。どの商品をすでに購入したかを示す集合を要素として持ち、dpをすればいい。集合が決まっている時の、支払う金額の最小値を求めておけば、その集合内でどの順番で商品を買ったかは関係ないので、dpで解ける。 dp[mask] := (ma…

ABC041 D - 徒競走

問題 問題概要 M個のクエリ満たす数字の並びを求める問題。 解法 まず、 どのような数字が数字の集合としてあり得るのかを計算してflagに入れておく。そして漸化式でdpを解く。感覚的には空集合の場合の数から全集合の場合の数へ、集合の数を増やす感じに計…