430.1

インフレしてた分をちょっと返済。情けない結果ではあるが。安心して年越せないやこれ。

250

ある数Xと2進数で足し算を行った時に、キャリーが出ない数のうちK番目のものを答えよ、という問題。

適当にinf取ったらinfが小さ過ぎた。どうしようもない。下から順番に決めていけば、細かいことは気にしなくてもいい。

500

ある距離以上の二都市間を結ぶことを考える。各都市の次数はK以下であるとして、全部で何本の枝を張ることができるか、またそのときの距離の和の最小値を求めよ、という問題。

各都市のランクから状態を作って、一番外側の都市の分だけ巻き戻した状態からDPする。

1000

N人を同じ人数の二つのグループに分ける。ある人がグループ1にいるときの点数とグループ2にいるときの点数が与えられるので、それぞれのグループの点数の差ができるだけ小さくなるように分割せよ、という問題。同点なら辞書順で先頭のものを返す。

取り敢えず半分ずつに分ける。前半分からK人をグループ1にする場合と後ろ半分からK人をグループ1にする場合について、それぞれのグループの点数を計算する。(実際には差分を計算する。)前半分からK人ならば、後ろ半分からはN-K人しか選べないので、その二つの合計ができるだけ均等になるようにする。そのためには前半分からK人選ぶ時の差分と後ろ半分からN-K人選ぶ時の差分の和を見れば良く、前者を昇順、後者を降順にソートすると、両方のリストを1度ずつなめるだけで良くなる。

後は同点のときにどのように選ぶか。差分と同時にそのときの選び方を整数にエンコードすると、先頭の人がどちらに属するかを優先するにはその人に対応するビットを最上位ビットにすれば良い。(事前に同点の時の処理をやっておくと、途中で煩雑な分岐がいらなくなる。)