2015 Round 1A
起きたら終わっていました。
A
とあるものを減らす人と増やす人がいる。増やす人は好き勝手に増やす。減らす人も好き勝手に減らす場合、少なくともいくつ減らしたか、また、減らす人は常に同じペースで減らしたとする場合、少なくともいくつ減らしたか、をそれぞれ答えよ、という問題。
やるだけ。好き勝手減らすなら、減っているところを全部カウントするだけ。同じペースで減らすなら、一番減ったところを拾ってやる。ただし、同じペースの場合、0よりも小さくはできないので、その分だけ削っておく。
C
N個の点が与えられるので、それぞれの点について凸包の境界になるようにするには何個の点を除去すれば良いかの最小値を答えよ、という問題。
要はある点から開始して、自分が凸包作るときの次の点に選ばれるまでの順位を繰り上げる操作をすれば良さそう。実装面倒かな?