技術室奥プログラミングコンテスト#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
これから満点解法も考える.