今回は ABCDEF の 6 完 (60:59, 0WA) 。 E が少しむずかしかったが、解けてよかった。
よくある空白区切り。
マックス求めて、排除してっていうのを愚直に。 ソートでユニークすればよかったかなぁ。
それぞれの文字の最大の連続した長さを記憶しておいて最後に和を出力。 バグらせないように注意。
あんまりいい方法が思いつかなかったので set に値とインデックスをマイナスしたのを入れて最大のものを出力した。
文字列 $S$ から消すことを考えて、その近傍にあるものを消せるかみたいな幅優先探索をすると通る。 消えた文字列は $T$ と比較するときは考えなくていいものとして考える。
結局塗りつぶされて消えてしまったものというのはどんな文字列であっても関係ないからである。
愚直に計算すると間に合わないのでマージテクを使う。ただこの時、移す箱が逆になってしまうので、 指し示すポインターのようなものを入れ替えて、$a$ を指す時 $b$ を指すといったようなことができていればいい。
最初なぜか Unionfind とかを使って実装しようとしたが、途中で全く必要ないことに気づいて時間を失った。
部分木に対する DP ができそうかもなぁと思いながら、ほとんど条件を詰めれず死んでいた。 なんか、lca がそれぞれ共有しないときはその lca からどっちに先に行かないといけないかは決まるなぁとか思っていた。
なんか爆死したわけでもなく、良かったわけでもない普通の回だった。感情が特に何もない。 E が難しかったなぁと思った。でも考えてみればまあそうかとはなった。 あまりやらないことをやっていたと思うので、思いつきづらいのかもしれないが、ここで手が止まりたくないなぁと思ってしまう。 実装さえできればできる問題は通したい。
(2023/11/18 22:54)