今回は ABCDEF の 6 完 (68:39+10:00, D, Eで1WA) D に時間を掛けすぎている。実装方法を工夫できなかった。
かなり単純化されているので、d++ して D より大きくなったら 1 にして m++ する。このとき M より大きくなったら 1 にして y++ するという感じで解ける。
まあ 3 重ループを回して置こう。
大きい値から同じ値を同列にしながら処理して sum に値を足していく。 うまいことより大きいを取り出す。
大ハマリ。実装手段が一番大事。自分は愚直にすべてのパターンを求めたが、 よくよく考えてみると、$(0, 0)$ からの総和について求めて後で帳尻を合わせれば楽だったじゃないかとなった。 あまりにもあほうだ。 1WA した上 40 分掛けた。ヤバすぎ。 いま解いてみたらかなりコードが短くなってあぁ・・・となった。
打って変わって簡単。ある主菜を選んで副菜を価格の大きい方から見る。 この時、NG な組以外が出てきたときにそれがその主菜を選んだときの一番高い価格である。 そしてこれは全体で $M$ 回しか見ないので愚直にやってOK.
やったことがなかったが、Hash 値を RSQ に乗せれば良さそうだと思った。 そうすれば更新も区間の文字列も $O(\log N)$ で出せる。 reverse した文字列についての Hash の RSQ も作って、対応するところの文字列が一緒かどうかを見れば良い。 ただ、mod のバリエーションが 1 個であるのでかなり脆弱だった。
Sushi みたいな問題は見たことがあったが、$M \leq 2 \times 10^5$ であるので全然うまく行かない。 とりあえずどの数字を今取ったかという $S$ から全体集合 $U$ にするための期待値についての立式は してみたが、特に速くはならなそう。
同じ数字のカードについてうまくまとめるような処理ができるのかなぁ。
F のといた時間が 16 分程度とこれはかなり速い。 D が完全に思考停止だったことを除けばいい出来だとは思う。 こういう問題の賢い解法を考えられればもっと良くなっていくと思う。
(2023/12/02 23:01)F だが、完全にローリングハッシュのような値をセグ木で扱うことができることがわかった。 というのも、自分は当初解いたときに $\mathrm{base}^i \times S[i]$ のような値を入れてから、 クエリを計算したときに $\mathrm{base}^l$ で割るみたいな取り出し方をしていたのだが、 実際のローリングハッシュは累積和のようにただ取り出すだけで普通にハッシュ値がでてくれるはずである。
ローリングハッシュは値の入り方がどうなっていたかというと、$i$ からみたときに $i-j$ のような位置の文字は $\mathrm{base}^j$ 倍されて寄与されている。 これを考えると、ある長さ $L_1, L_2$ の区間 2 つを組み合わせる時、 2 つのハッシュ値を $h_1, h_2$ とすると、 $h_1 \times \mathrm{base}^{L_2} + h_2$ となるのが良いことがわかる。 こうすればその区間のハッシュ値がしっかりと求まるようになる。 また、$\mathrm{base}^{L_2}$ を実際に計算しようとすると $O(\log p)$ ( $p$ はハッシュ値の剰余の値) だけかかってしまうので、データは $\mathrm{base}^L$ ( $L$ は区間の長さ ) ごと入れてしまうのが良い。 このような長さの値を組み合わせるときは掛け合わせることで帳尻が合う。
今回の問題では新たに右からのハッシュ値の値もデータに入れることで、左からのハッシュ値と右からのハッシュ値が 一致するかで判断することができる。
普通にローリングハッシュがセグ木に乗っているような構造を作ることができて満足している。 ただ $\mathrm{base}$ の値や何で剰余するのかとかの部分はできていないので、脆弱性は全然ある。 ローリングハッシュが乗るセグ木のうまみは言うまでもないが、更新ができるところである。
(2023/12/30 01:04)