今回は良かったっすねー。Eで手こずったのがちょっと痛かったけど、Fは山を当てた。 ということでABCDEFの6完。Gはよくわからないし、まあ満足してます。
string::find を使う。頑張る。
string::substr を使う。頑張る。
lower_boundを使う。頑張る。
AtCoderはあんまりこういう問題を出してこなかったイメージだけど、やっぱり実装力も試す問題を出すようにしてきたのかなぁ。 それぞれのポリオミノに対して回転したもの４つに対して、上下左右に動かしたものを用意して、 それを全部配列に入れていく。これを３つに対して行うので、３つの配列ができる。 この３つの配列の中から、ポリオミノを選び出して、このときにちゃんとはまったら、YESにする。
凄まじくコードのコピペを繰り返して、やった。 関数に入れて処理するなんていう考えがめんどくて、めっちゃコードが長くなった・・・w でもわりとすんなり実装できたのはよかった。
現在の $i$ とあとどのくらいパラメータが必要か $now$ をキーにしたmapをメモ配列にして、DPをする。 全然バグが取れなくて、最終的にどこがおかしかったかというと、メモ配列がlong long型になってなかった、ってことだった。 なんか、変な値が急にでてきて、配列外参照かな？って思ってちょっとミスリードをしていた。
そうだよなぁ。mapでDPをあんまり書いたことないという経験不足がちょっとあるのかもね。30分くらいかかっちゃった。
普通のセグ木の類題をHOJで解いてたのもあって、これがすぐに遅延セグ木だとわかった。
勝手に紹介して良いのかな。
All you need is Segment Tree.
という問題なのだけれども。この問題には本当に感謝しかない。この問題の更新クエリのところを今回は区間でやろうっていうことだった。
今回は、区間に対して一気にデータを変えないといけないので、セグ木に乗せるデータ自体も変えないといけなかった。 だがこれは、0 に対するmaxlen, llen, rlen と、1 に対する maxlen, llen, rlen を同時に持つことで、データの反転に対応できる。 データの反転時に、0のデータと1のデータをスワップすればいいだけなのだ。
そして、自分の遅延セグ木はバグっていたので、非可換に対応できるように修正。これにて、解くことができた。 初めて遅延セグ木を問題に適応して、アドリブでよくできたなと、自分ながら褒めたい。 使い方すらもはや忘れてたし。まだ理解が足りてないね。
perf=2108だった。Eのバグ修正がなぁ・・・ｗ 今回のコンテストは少し AtCoder らしからぬ(なんて勝手にイメージを持っちゃってるけど)感じでしたね。 ある意味得意分野だったのかもしれない。ただ自分も実装力が鈍ってたなぁ。
Fも解説見たけど、遅延セグ木が想定解だったみたい。 AtCoderだからデータ構造で殴る問題はでないだろうみたいな偏見は捨てたほうが良いかもね。 まあ今回は嬉しいっす！
(2023/09/30 23:06)