2019/10/26

Codeforces 1251 E

最小値 

適当な順番を定めてコストを最小化する

前にmi人選んでいる場合、i番目の人にコストpiを払う必要はなくなる(ノーコスト化)

 

ノーコスト化する人数を貪欲に最大にすることを考える

i(1<=i<=n)番目に選ぶ人はm<=i-1かつpが最も高い人として良い(条件を満たす人がいない場合は次)

iの昇順でこれを決めて、残った人のコストの和が答え

 

ノーコスト化する人数が最大でない場合、ma<=j-1でj番目より前に選ばれている人A、j-1<mbであるk(>j)番目の人Bが存在する この時A,Bの順番をswapすることで必要なコストを真に小さくできる

 

Codeforces 1247 A

a==9,b==1の場合、a+1==bの場合、a==bの場合で分ける

場合分けゲーが苦手なのはわかっているのでもっと慎重にやるべき

 

Codeforces 1247 B

テストケースがクエリ形式の場合、パケットのサイズに注意(毎回固定長にするとパケットの構築が間に合わない)

 

Codeforces 1247 C

最小値 答えになりうる値は高々30程度なので全探索できる

xが答えになりうるかを調べるとき、n-xpをx個の2の累乗で表せるかどうかを判定する

0<=nのとき、2^n==2^(n-1) + 2^(n-1)と分解できることから、n-xpの立っているbitの数<=x<=n-i*p(summandの最大値、1+1+1...の場合)を満たすかどうか調べればよい

 

__builtin_popcountllの存在を知った