ABC216G 01Sequence - geam1113’s diary

解説AC

牛ゲーとのことで、解法は公式解説を見るのが良いかと思います。
ここでは、自分なりの理解をつけ足したいと思います。

牛ゲーについては、別記事にまとめました。

また、ネットで調べると色々出てきます。

牛ゲーを適用するには、以下を満たす必要があります。

そこで今回、

ことを、

と言い換えをすることが１つポイントだと思います。

次に、以下の3つが今回の制約です。

制約1は自明かなと思います。

制約3は、0の数を最大化する問題とみなし、1の個数の制約を0の個数の制約に変換することで導き出されます。

制約2ですが、 $A_{i+1}$ を1にすれば $B_{i+1} - B_i \leq 0$ となり、 $A_{i+1}$ を0にすれば $B_{i+1} - B_i \leq 1$ となります。そこで、多重辺をもつような場合はどうなるのかという疑問が出ました。

おそらくですが、「0以下または1以下」なので大きい方の1以下のみが採用されます。これが、「0以下かつ1以下」であれば、0以下が採用されると思います。

牛ゲーでは、
$a - b \leq c$ という制約を「 $b$ から $a$ への重み $c$ の有向辺」
とみなします。これに従って、3つの制約式から有効辺を追加し、 $B_0$ を始点とした最短経路問題を解きます。重みが非負なので、ダイクストラ法が適用できます。

あとは、 $1 \leq i \leq N$ について、

として $A$ を構築できます。