問題
直線上のに
の猫がいる。ひとつのpositionに複数の猫がいるのはよくないことである。猫は1秒に左右どちらかに1だけ移動できる。移動しないことも可能である。t秒後において、複数の猫が存在しなけばならないpositionの数を答えよ。
解法
貪欲法で解ける。
positionに対して昇順にソートする。猫を分散可能な場合は左から埋めていき、不可能な場合は全ての猫を右端に置く。次のpositionで以前右端に置いた箇所に到達可能ならば、そこに全ての猫を移す。
計算量
ソート:
探索: