math, tokoharu, n_vip(と僕)の集合知によりmagicを使用しないO(N)解が錬成されました。 はじめに 解説のとおりに"なんでもいいので最終的な長さがM"となる操作の仕方を考えています。 操作列の条件 0add, 1add, delの3種類がありますが、とりあえずaddを1種…

まず黒の連結成分の個数で場合分けする。これをKとする 連結成分ごとに、a1, a2, .., amを使うとすると長さ[max(a1,a2, .., am), a1+a2+..+am]の連結成分が作れることに注目する。 すると、塗れる範囲というのはK次元平面上の長方形たちの和集合で表せること…