きろく

特筆すべき記録のまとめ

技術室奥プログラミングコンテスト#4 Day2:F - Segtree☆Magica

問題

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_f

解法

前から要素を見ていく.a_i > 0 となっている要素があれば a_i, a_(i + 1), ... から 1, 4, ... を a_i 倍したものを引いていき,最終的に全ての要素が 0 になっているかどうかをシミュレーションをして判定すればよい.これは N, K <= 1333 の部分点解法であるが,なぜか満点が取れてしまう.O(NK).

解答

https://atcoder.jp/contests/tkppc4-2/submissions/6637094

これから満点解法も考える.

f:id:babcs2035:20190802211058p:plain