全探索
atcoder.jp 概要 N個のふりかけが売られていて、それぞれのふりかけの番号はA[i]でおいしさがB[i]である。あなたはKという整数を持っている。次の条件を満たすようにふりかけを選んだ時のおいしさの和の最大値を求めよ。K>=XのようなXがあり、えらばれたふり…
codeforces.com 概要 サイズNの木が与えられる。そのN-1本の辺に、それぞれ1つずつ、0~N-2の数字を重複なく割り当てていく。 頂点uと頂点vの間を通る単一のパス(木なので必ず存在する)上の辺に含まれる数の集合をSとする。Sに含まれない、最小の非負整数をME…
atcoder.jp 概要 ある文字列sが存在し、次の操作を考える。 sの空でない連続部分文字列を1つ選び、これをpとする。pのそれぞれの番目を'?'に置き換えるorそのままにする。 この操作で得られた3つの文字列、a, b, cが存在するとき、元のsの最短の長さを答えよ…
arc073.contest.atcoder.jp ナップサック問題に制約、 Wがばかでかいので当然普通のdpではMLEする。 ここでNが小さいときに注目、Nが小さいときにうまくいくのは全探索、全列挙的な手法となる。 100では全列挙は厳しいけど、ここで、重さは4通りしかない…