Cまで三完。過去最悪に近い成績。しかし、DもEも難しい気がしたが……。
コンテスト後のツイート
D ランレングス圧縮した後、左右の端から削っていくとか考えたが上手くいかず。
— titia (@titia_til) April 7, 2026
E 大きい数字を後ろから入れる貪欲を考えたが上手くいかず。正当性もまずそうだし、計算量も三乗になりそう。
D. Flip the Bit (Hard Version)
解説AC。
隣接する値が異なる場合は1、同じ場合は0とする配列を持っておく。
「ある区間の反転は、この配列の二項を反転させるもの」と捉えるのは（この前のARCのAで出題されたので）覚えていた。
さらに、この問題のようにindex iを含む区間の反転は、
★「iより左側とiより右側で反転させる」と捉えることができる。
ここで、P[i]で配列を区切っていくつかの区間を持つと、
★「二つの別の区間から反転する」という操作なら全て行えることが分かる。
★ところで、最終的な値を0にしたいなら、Aの左右に0が広がっていると考えても同じ。
そう捉えて区間を分割し、隣接項が違うものの個数を数えたものをSとすると、
・Sの異なる項から1ずつ引く
・Sの一つの項から1を引く
の操作を行ってSの全ての要素を0にするとき、最低何回必要か？ という問題になり、これは、最大値で場合分けしたりheapqを使ってシミュレーションしたりすれば解ける。
難しかった。
★で書いた三つとも自力では思いつけなかった。隣接xorを取る部分は定石だけど、それ以降の処理にも難しい部分があると、なかなか正解まではたどり着けない。
0 件のコメント:
コメントを投稿