AGC020

AGC 020
要復習:C

A問題
一次元で駒を動かすゲームで先手後手どちらが勝つかを出力する問題．
小さい数で少し実験して二者の間の距離の偶奇に注目するといいことがわかったのでなんとかなった．
B問題
x人に対してラウンドkののちに(int)x/a_k * a_k人になる　という操作を繰り返したのちに2になった．最初にいた人数の最小値と最大値を求めよ．
という問題．
各ラウンドの前の人数の範囲が具体的に求められるので後ろから順にその範囲を更新する感じ．
具体的に求められる　の部分の計算が遅すぎた．
C問題
部分和として考えられる数の中央値を求める問題
全体の和をSとするとある部分和がmになるとき補集合の和がS-mになることに注意すると，部分和の集合の中央値はS/2以上のもののうち最小の値となる．
S/2+2000(=maxA_i)までに解があるので部分和で作れるかを一つずつ確認する方法で行こうと思ったが，これだと2000*2000*2000ぐらいで間に合わなさそう．
ということでもう一捻りあるはずと思って悩んでいたのですが
どうやらbitsetというのを駆使すると高速化できるらしい．ということでこれの練習もかねて実装