103. 今日解いた問題（2022.04.15）

問題一覧

D - Lamp (Diff: 1103)
E - Simple String Queries (Diff: 1443)

自分の解法など

D - Lamp

12分。

累積和的な処理で解けないかな、と考えました。たとえば「#....#」となっている箇所は、「012340」という風に置き換えられます。これを、その場所に明かりを置いたとき照らせるマスの数と考えると、「044440」が適切です。ということは、左から累積和的なものを作ったあと、右から「最大値」（ただし、0で囲まれた範囲で）で上書きしていけばよさそうです。

行方向・列方向でそれぞれこの処理を走らせて得られた配列を $A, B$ とします。 $(i, j)$ に明かりを置いたとき照らせるマスの数は $A_i + B_j - 1$ なので、これの最大値を全探索すればよいです。

というわけで、最初の累積和的な処理が $O(H + W)$ 、最後の全探索処理が $O(HW)$ で全体として $O(HW)$ です。

E - Simple String Queries

13分。

いかにもセグ木を使いたくなる問題です。クエリ 1 はセグ木を使えば $O(\log N)$ で更新できるのでよさそうです。クエリ 2 にどうやって対応するか考えます。

アルファベットがそれぞれ含まれる・含まれないという状態をビットで管理できないか考えます。26文字なので int で十分管理できます。この上で考えてみると、セグ木のデフォルト値を 0、子 $(x, y)$ から親への更新演算を $x \; or \; y$ とすればよいことが分かりました。クエリ 2 には、セグ木から得られた値で 1 となっているビットの数を答えとして出力すればよいです。