読者です 読者をやめる 読者になる 読者になる

ARC 059 F バイナリハック

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倍されるようになりますが、あんまり変わりません(投げ槍)