■136:F - Enclosed Points(2334)
とりあえず図示してみる。
問題文を言い換えて、それぞれの頂点ごとに自分が含まれるような部分集合の場合の合計を求める。
自分自身が選ばれていれば残りのN-1個の頂点はどうでもいいので2^(N-1)が加算される
次に、自分自身が選ばれていない場合を考える。
他の点は、自分より右上右下左上左下のいずれかのゾーンに含まれる
①左上から一個以上、右下から一個以上選ぶ
②左下から一個以上、右上から一個以上選ぶ
のどちらかを満たしていれば自分自身が含まれる
ただし、①＋②だと右上右下左上左下全てのゾーンから一つ以上選んでいるケースが重複しているので
引く必要がある。
右上、左上、右下、左下の各要素はセグ木を２本持って管理しておき
forを回すごとに
①右から自分を外す
②計算する
③左に自分を入れる
を繰り返せばいい。
■137:F - Polynomial Construction
f(x) = 1-(x-t)^(p-1)
とおくと
x = t にてf(x) = 1;
それ以外でf(x) = 0;
これを加える。
■138:F - Coincidence
yの最上位bitを考える。
xの最上位ビットと一致してないとき
y xor x > x > y%x
となるため最上位ビットの位置が一致している必要がある。
また、このときyをxで割った商が1になるため
y - x = y xor x
となればいいことがわかる。
このための(x,y)の組み合わせは(0,0),(1,1),(0,1)のいずれか
あとは、桁dp
通常の桁dpと比較して２変数を同時に扱う必要がある。
以下のように状態を持つ。
dp[i][j][k][l]:=上からi桁見た,
j = 1 xがLより大きいことが確定している
k = 1 yがRより小さいことが確定している
l = 1 先頭ビッドがすでに現れた。
■139:F - Engines
制約を見るとNが小さいことがわかる。
図示して考察すると、連続する範囲を選択すればいいので
ソートして、全て試せば良い。
２周分持つのが鉄則。
■140:F - Many Slimes
貪欲。
注意すべきなのは
4,3,3,3,2,1,1,1
みたいなとき
4
4,3
4,3,3,2
4,3,3,3,2,1,1,1
のような場合でも問題がなく、単純に上からとれないとだめなわけではない。
