トヨタ自動車プログラミングコンテスト2024#11(AtCoder Beginner Contest 379) F,G 問題メモ

C問題に誤読しやすい罠があり、その罠に気付かせるような入力例も用意されていなかったため、序盤の問題にしては結構な人がWAしていた。
ABC-Cのくせに よわよわサンプル なさけな～い♥ ざあこ♥ざあこ♥

F - Buildings 2

• ビル $1$, ビル $2$, $\ldots$, ビル $N$ の $N$ 棟がこの順で東西に一列に並んでおり、ビル $1$ が最も西に、ビル $N$ が最も東に建っています。ビル $i\ (1\leq i\leq N)$ の高さは $H_i$ です。
• 整数の組 $(i,j)\ (1\leq i\lt j\leq N)$ に対して、以下の条件を満たすとき ビル $i$ からビル $j$ を見ることができます。
  • ビル $i$ とビル $j$ の間にビル $j$ より高いビルが存在しない。すなわち、$H_k\gt H_j$ を満たす整数 $k\ (i\lt k\lt j)$ が存在しない。

• $Q$ 個の質問に答えてください。$i$ 番目の質問では整数の組 $(l_i,r_i)\ (l_i\lt r_i)$ が与えられるので、ビル $r_i$ より東にあるビル（ビル $r_i+1$, ビル $r_i+2$,$\ldots$,ビル $N$ ）のうちビル $l_i$ とビル $r_i$ の両方から見ることができるものの個数を答えてください。

• $ 2\leq N\leq 2\times 10^5$
• $ 1\leq Q\leq 2\times 10^5$
• $ 1\leq H_i\leq N$
• $ H_i\neq H_j\ (i\neq j)$
• $ 1\leq l_i\lt r_i\leq N$
• 入力は全て整数

数列 $A$ に対し、先頭から見ていってこれまでに出てきた最大値を更新した値だけを抽出した数列を $f(A)$ とする。

  A :  3 1 2 5 4 6
↓
f(A):  3 5 6

まず $r$ から見えるビルだけに絞って考える。そのようなビル群（の高さ）は、以下のようになる。

• $B=f((H_{r+1},H_{r+2},...,H_N))$

$r$ から見えないビルが $l$ から見えることは無いが、逆に $r$ から見えるビルが $l$ から見えないことはある。
$\max(H_{l+1},H_{l+2},...,H_{r})$（これを $T$ とする）より高くないと、$l$ からは見えない。

$B$ に出てくる、$T$ 以上の値の数が答えとなる。
$B$ は単調増加なので、二分探索して $T$ 以上となる境界を求められる。

$T$ はセグメント木やSparceTableなどを利用して求められる。

$B$ は、全クエリを通して、末尾からスタックを利用して構築できる。
$k=N,N-1,...,1$ の順に $B$ を更新し、各クエリは $r_i=k$ となったタイミングで処理すればよい。

Python3

from bisect import bisect
from collections import defaultdict

from atcoder.segtree import SegTree


def solve(n, q, hhh, queries):
    sgt = SegTree(max, 0, hhh)
    pos = defaultdict(list)
    result = [-1] * q
    for i, (l, r) in enumerate(queries):
        pos[r - 1].append((l - 1, i))
    stack = []
    for r in range(n - 1, 0, -1):
        if r in pos:
            for l, qi in pos[r]:
                m = sgt.prod(l + 1, r + 1)
                k = bisect(stack, -m)
                result[qi] = k
        h = -hhh[r]
        while stack and stack[-1] > h:
            stack.pop()
        stack.append(h)
    return result


n, q = map(int, input().split())
hhh = list(map(int, input().split()))
queries = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(n, q, hhh, queries)
print('\n'.join(map(str, ans)))

クエリを先読みしなくても解く方法がある。

• 解説 - トヨタ自動車プログラミングコンテスト2024#11(AtCoder Beginner Contest 379)

G - Count Grid 3-coloring

• 1,2,3,? からなる $H$ 行 $W$ 列のグリッド $S$ が与えられます。上から $i$ 行目、左から $j$ 列目の文字は $S_{i,j}$ です。
• $S$ の各 ? を 1,2,3 のいずれかに置き換えて得られるグリッドは ? の個数を $q$ として $3^q$ 通りありますが、そのうち以下の条件を満たすものはいくつありますか？ $998244353$ で割った余りを出力してください。
  • 隣接する（辺を共有する）どの $2$ つのマスにも異なる数字が書かれている。

• $1\leq H,W$
• $H\times W\leq 200$
• $H,W$ は整数
• $S$ は 1,2,3,? からなる $H$ 行 $W$ 列のグリッド

$H \times W$ が小さい。
$14^2=196$ なので、短い方は $14$ 以下であることが保証されている。
必要に応じてグリッドを転置させて、$H \ge W$ である（$W \le 14$ である）状態にしておく。

左上から1要素ずつ、$1/2/3$ の何を置いたかを状態に持ったDPで決めていく。
「$(i,j)$ に置いた数字は上・左に置かれた数字（存在すれば）のいずれとも異なる」ことを、「$(i,j)$ は条件を満たす」と呼ぶことにする。

• $\mathrm{DP}[i,j,S]:=$ 下記のような状態で、□■は全て条件を満たしていて、■にそれぞれ置いた数字の列が $S$ である場合の数

     j
  □□□□□□
  □□□□□□    ■は、(i-1,j+1) から (i,j) までの W 個のマスを示す
  □□■■■■
i ■■

$(i,j)$ に条件を満たしつつ何の数字を置けるかは、$\mathrm{DP}[i,j-1,S]$ からそれぞれの $S$ につき、1つ上と1つ左に置いた数字の情報があるので決められる。
その他の■は $(i,j)$ を決めるのには直接参照しないものの、次の $(i,j+1)$ 以降の更新では参照されるため、必要となる。

$S$ の状態数は $3^2 \times 2^{W-2}$ なので、全体 $O(HW \times 3^2 \times 2^{W-2})$。 制約の代入で $7.4 \times 10^5$ 程度と見積もられる。

Python, PyPyでは、$S$ をそのまま列で持つ（辞書のキーにタプルを用いる）と遅くなるし、遷移時に $S$ をスライドさせる処理も $O(W)$ 余分にかかるため、TLEになりやすい。
1マスに2bitずつ用いて、$2W$ bitの整数で持たせると、辞書アクセスが速くなり、スライド処理も bitshift で高速化できる。

Python3

from collections import defaultdict


def solve(h, w, field):
    if h < w:
        field = list(zip(*field))
        return solve(w, h, field)
    MOD = 998244353

    mask_full = (1 << (w * 2)) - 1

    def key_get_above(key):
        return key >> (w * 2 - 2)

    def key_get_left(key):
        return key & 3

    def key_append(key, el):
        return ((key << 2) | el) & mask_full

    dp = {}
    dp[0] = 1
    for i in range(h):
        for j in range(w):
            c = field[i][j]
            ndp = defaultdict(int)
            if c == 0:
                for key, pattern in dp.items():
                    s0 = key_get_above(key)
                    s1 = key_get_left(key) if j > 0 else 0
                    for k in (1, 2, 3):
                        if k == s0 or k == s1:
                            continue
                        new_state = key_append(key, k)
                        ndp[new_state] += pattern
                        ndp[new_state] %= MOD
            else:
                for key, pattern in dp.items():
                    if key_get_above(key) == c or (j > 0 and key_get_left(key) == c):
                        continue
                    new_state = key_append(key, c)
                    ndp[new_state] += pattern
                    ndp[new_state] %= MOD
            dp = ndp

    return sum(dp.values()) % MOD


h, w = map(int, input().split())
field = []
for _ in range(h):
    row_str = input()
    row = tuple('?123'.index(c) for c in row_str)
    field.append(row)
ans = solve(h, w, field)
print(ans)