東京海上日動コン2020 C - Lamps (500)
最初の考察
一回の操作での変更についてはimos法を使うと$ O(N)でできる
単純にこれを繰り返すと$ O(NK)でTLEするのでNかKの改善が必要
操作を2回分まとめたりする方法がある?
最終的な考察
初回操作後は全ての電球の光の強さは1以上になる
全ての電球で光の強さは指数的に大きくなる
最大値はNなので$ O(\log N)回の操作でここに到達するのでそれ以降は見る必要が無い
値が全て最大値になったらそこで終了する
操作が減ったので$ O(N \log N)で解ける