Dまで。
コンテスト後のツイート
C 負を選ぶと、それ以降は全て負のものを選ぶことになる。
— titia (@titia_til) February 16, 2025
D 上のbitから考える。上のbitが0になっているか？ そのときそのbitが0なら次に1が出てきた場所で終わり。1なら、次のところまでは下のbitは守られ、その次で終わり。
E. Mycraft Sand Sort
解説AC。
簡単なのかと思ったら、全然簡単ではなくて、解説など色々参考しても理解するまでずっとかかってしまった。（なお、解説の方法は理解していないし、自分がやった方法に嘘の疑いもある）
Cは与えられたものと同じものを使うしかなく、Pの個数を求める。
P_iとP_jが交換可能なのは、
・iとjが隣接しており、同じ色なとき
だけではなく、
・iとjが同じ色で、iとjの間にあるもの全てが、P[i]やP[j]より小さいとき（これは、上の条件を内包している）
と気付かなくてはいけない。
コンテスト中はここにも辿り着いていなかったが、それをどう数え上げれば良いかが難しい。
解説とは（多分）違う、左右を管理する方法でやった。
P[i]が小さい方から見ていき、隣合っている同じ色がどの範囲までか、を見て、その要素数を答えにかける。その後、index iを削除する。
削除というのは、左右を管理し、
・RIGHT[LEFT[i]]=LEFT[i]
・LEFT[RIGHT[i]]=RIGHT[i]
のようにするということ。まあ、左右を管理するときはよく使う手法ですね。
ここで、毎回同じ色がどこまでか？ を調べるとTLEするので、Union-findでくっつけ、Unionできる端の値をもっておく。
しかし、そうすると、その端の値は既に消えていることがある。そのときは再計算（消えていないindexまでLEFT,RIGHTをたどる）してACした。
最後の再計算するところの計算量が怪しいけれど、今回はACできた。危ないテストケースはありますか？
0 件のコメント:
コメントを投稿