math, tokoharu, n_vip(と僕)の集合知によりmagicを使用しないO(N)解が錬成されました。
はじめに
解説のとおりに"なんでもいいので最終的な長さがM"となる操作の仕方を考えています。
操作列の条件
0add, 1add, delの3種類がありますが、とりあえずaddを1種類で考えます。
長さNのadd, delの列が、最終的に長さMの数列を生成する条件はなんでしょうか？
これは、逆から見てmax(今までのadd - 今までのdel) = Mが条件です。
つまり、addを+1, delを-1として数列 a_1, a_2, ..., a_N を作ると、
max(a_i + a_{i+1} + ... + a_N)が最終的な長さになります。
経路へ
逆から見るとシンプルな条件になったので、経路で考えます。
addを上移動(y+=1), insを右移動(x+=1)とすると、最終的な数列の長さは経路上のmax(y-x)となります。
よって最終的な長さがM以下 ←以下です！！！！ぴったりMじゃないですよ！！！！！！！！！！❕❕❕❕❕❕❕❕ となる操作列は
- (0, 0) からスタートして、y - x <= M を満たしながらN回移動
と対応します。
N回移動した後の目標地点は高々O(N)個しかないので、それぞれについて経路数を求めて足せばよいです。
これでM以下が出せたので、M以下-(M-1)以下を求めればよいです。
addを2種類へ
y+=1するときに2倍されるようになりますが、あんまり変わりません(投げ槍)
