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