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

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

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

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

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

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

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