SRM631Div1Medium

問題

直線上のにの猫がいる。ひとつのpositionに複数の猫がいるのはよくないことである。猫は1秒に左右どちらかに1だけ移動できる。移動しないことも可能である。t秒後において、複数の猫が存在しなけばならないpositionの数を答えよ。

解法

貪欲法で解ける。
positionに対して昇順にソートする。猫を分散可能な場合は左から埋めていき、不可能な場合は全ての猫を右端に置く。次のpositionで以前右端に置いた箇所に到達可能ならば、そこに全ての猫を移す。

計算量

ソート:
探索:

コード