ARC133

3完。つよい人向けのコンテストという感じ。これでレート下がるのはどうでもいいかな。Cはまあ簡単だった。Bは難しい(特に早解きが難しい)。Dは難しいかどうか以前にやりたくない。Eはむずかしそう。

いつもと違って全然文章書けなくてやばいな。合わないセットでも淡々とやれたし、あまりイヤな気持ちにもならない。興味がないのか?

A - Erase by Value

先頭から見ていく。aの最初の数が、Aの最初の数と同じになるかならないかどっちか。同じにならないなら、Aで次に現れる数になる。それで小さくなるならそうするし、大きくなるなら最初は確定。え待って文章書けん。あとは同じことを繰り返す。消す数を更新しながら回して確定したら抜けるとすればコーナーケースも大丈夫。

ランレングスのライブラリを使ったら全部同じ数になって破滅。何回か使ってるコードなのにな。原因が全くわからず、結局自分で書いた(苦手だからライブラリにしてるのにな(まあこのくらいは書けるけど))。今でも全く原因がわからない。

そういえば、それまでに出た(一旦スルーした)値を消すことになったらまずいというのを考えてなかった。実際は、消すものが決まるまで単調増加で決まったとき減ってその直前の要素の値が選ばれるので、そういうことは起こらない。まあでかい数を消すってことだよな。よくわかんないけど。

(追記)decltypeしててそこで意図せず参照のvectorを生成していた。全部同じ数になっていたのはそのため。コンテスト後にデバッグしても全然わからなかった。IDEの機能でテンプレート引数を指定できるんだけど、それを早くやるべきだった。

B - Dividing Subsequence

解けそうにないので先にCをやった。

つなぐ候補はO(N*log(N))しかない。それでも、どうやっても2乗になる。と思っていたが、DPするときにその候補毎にそことそこより左だけでの最大の長さでやれそう。BITを使えばできる。片方が同じやつをまとめて処理する必要があってめんどい。最近やったよな。まあ解説を見ると必要なかったんですが。意味わからん勘違いで1WA。なんか片方の値が切り替わるときに境界を1ずれて認識してた。

(追記)最近やったと思ったのは、ARC126のBだった。

C - Row Column Sums

とりあえず一つ構成しようとして交差する1箇所が難しいなとか思ってたらこれは必ず合うんだ。合わないときは-1。さて、それならマックス(全部K-1で埋めたやつ)の状態から引いていくか。その場合の和で合っていればそれでよし、合わないときは合うまでは少なくとも減らす必要がある。どれだけ減らすか、AとBででかいほうのぶんは減らす必要がある。(減らすのが)小さい側を合わせることができれば都合がいいが、順番に小さい側へ合わせて減らし、残りはKの倍数なので1列にまとめて置けばいい。0じゃなくて-1がベースなので混乱してそもそも落ち着いてもよくわからなくて実装にかなり時間がかかった。