パナソニックグループ プログラミングコンテスト2025（AtCoder Beginner Contest 427）E,F,G問題メモ

from collections import deque


def solve(h, w, field):
    ti, tj = 0, 0
    for i in range(h):
        try:
            j = field[i].index('T')
        except:
            continue
        ti = i
        tj = j
        break

    def blows_out_all(u, d, l, r):
        i1 = min(h, max(0, d - ti))
        i2 = min(h, max(0, h - (ti - u)))
        j1 = min(w, max(0, r - tj))
        j2 = min(w, max(0, w - (tj - l)))
        cnt = 0
        for i in range(i1, i2):
            cnt += field[i][j1:j2].count('#')
        # print(f'{u=} {d=} {l=} {r=} {i1=} {i2=} {j1=} {j2=} {cnt=}')
        return cnt == 0

    def can_move(u, d, l, r, i, j, direction):
        if direction == 0:
            i -= 1
            if i < d - ti:
                return True
        elif direction == 1:
            i += 1
            if i >= h - (ti - u):
                return True
        elif direction == 2:
            j -= 1
            if j < r - tj:
                return True
        else:
            j += 1
            if j >= w - (tj - l):
                return True
        if i < 0 or h <= i or j < 0 or w <= j:
            return True
        return field[i][j] != '#'

    dp = {(ti, ti, tj, tj, ti, tj): 0}
    q = deque([(ti, ti, tj, tj, ti, tj)])
    while q:
        key = q.popleft()
        u, d, l, r, i, j = key
        cost = dp[key]
        if blows_out_all(u, d, l, r):
            return cost
        for dd, (di, dj) in enumerate(((-1, 0), (1, 0), (0, -1), (0, 1))):
            if not can_move(u, d, l, r, i, j, dd):
                continue
            ni = i + di
            nj = j + dj
            nu = min(u, ni)
            nd = max(d, ni)
            nl = min(l, nj)
            nr = max(r, nj)
            nk = (nu, nd, nl, nr, ni, nj)
            if nk in dp:
                continue
            dp[nk] = cost + 1
            q.append(nk)

    return -1


h, w = map(int, input().split())
field = [input() for _ in range(h)]
ans = solve(h, w, field)
print(ans)

from collections import defaultdict


def solve(n, m, aaa):
    def half(si, ti, step):
        dp0 = defaultdict(int, {0: 1})
        dp1 = defaultdict(int)
        for i in range(si, ti, step):
            a = aaa[i]
            ndp = defaultdict(int)
            for b, c in dp0.items():
                ndp[(a + b) % m] += c
            for b, c in dp1.items():
                dp0[b] += c
            dp1 = ndp
        return dp0, dp1

    if n == 1:
        if aaa[0] % m == 0:
            return 2
        return 1

    h = n // 2
    f0, f1 = half(0, h, 1)
    b0, b1 = half(n - 1, h - 1, -1)
    ans = 0
    for fb, fc in f0.items():
        bb = -fb % m
        if bb in b0:
            ans += b0[bb] * fc
        if bb in b1:
            ans += b1[bb] * fc
    for fb, fc in f1.items():
        bb = -fb % m
        if bb in b0:
            ans += b0[bb] * fc
    return ans


n, m = map(int, input().split())
aaa = list(map(int, input().split()))
ans = solve(n, m, aaa)
print(ans)

Codon用

class _Node:
    value: int
    max_key: int
    max_val: int
    left: Optional[_Node]
    right: Optional[_Node]
    __slots__ = ('value', 'max_key', 'max_val', 'left', 'right')

    def __init__(self):
        self.value = 0
        self.max_key = 0
        self.max_val = 0
        self.left = None
        self.right = None


class DynamicSegmentTree:
    """区間和 動的セグメント木。

    問題用の ad-hoc な以下の関数を含む。

    - キー空間 ``[key_lo, key_lo + n)``。
    - ``bisect_existing(func)``: 実在 key に限定した bisect を ``O(log n)``。
      ``(key, prefix_at_key)`` を返す。
    - ``floor_key(key)``: ``key`` 以下で実在する最大 key を ``O(log n)``。
      ``(key, val_at_key, prefix_at_key)`` を返す。
    """

    n: int
    key_lo: int
    root: Optional[_Node]

    def __init__(self, n: int, key_lo: int = 0):
        self.n = n
        self.key_lo = key_lo
        self.root = None

    def update(self, key, x):
        self.root = self._update(self.root, 0, self.n, key - self.key_lo, x)

    def _update(self, node, lo, hi, i, x):
        if node is None:
            node = _Node()
        if hi - lo == 1:
            node.value = x
            node.max_key = lo + self.key_lo
            node.max_val = x
            return node
        mid = (lo + hi) >> 1
        if i < mid:
            node.left = self._update(node.left, lo, mid, i, x)
        else:
            node.right = self._update(node.right, mid, hi, i, x)
        left = node.left
        right = node.right
        node.value = (left.value if left is not None else 0) + (right.value if right is not None else 0)
        if right is not None:
            node.max_key = right.max_key
            node.max_val = right.max_val
        else:
            node.max_key = left.max_key
            node.max_val = left.max_val
        return node

    def get_range(self, a, b):
        return self._get_range(self.root, 0, self.n, a - self.key_lo, b - self.key_lo)

    def _get_range(self, node, lo, hi, a, b):
        if node is None or b <= lo or hi <= a:
            return 0
        if a <= lo and hi <= b:
            return node.value
        mid = (lo + hi) >> 1
        return self._get_range(node.left, lo, mid, a, b) + self._get_range(node.right, mid, hi, a, b)

    def delete(self, l, r):
        self.root = self._delete(self.root, 0, self.n, l - self.key_lo, r - self.key_lo)

    def _delete(self, node, lo, hi, l, r):
        if node is None or r <= lo or hi <= l:
            return node
        if l <= lo and hi <= r:
            return None
        mid = (lo + hi) >> 1
        node.left = self._delete(node.left, lo, mid, l, r)
        node.right = self._delete(node.right, mid, hi, l, r)
        left = node.left
        right = node.right
        if left is None and right is None:
            return None
        node.value = (left.value if left is not None else 0) + (right.value if right is not None else 0)
        if right is not None:
            node.max_key = right.max_key
            node.max_val = right.max_val
        else:
            node.max_key = left.max_key
            node.max_val = left.max_val
        return node

    def bisect_existing(self, func):
        """``func(key, prefix)`` がはじめて False になる実在 key を ``O(log n)`` で返す。

        Returns
        -------
        (key, prefix_at_key) : Tuple[int, int]
            見つからない場合は ``(key_lo + n, 全体合計)``。
        """
        node = self.root
        if node is None:
            return (self.key_lo + self.n, 0)

        lo = 0
        hi = self.n
        prefix = 0

        while True:
            if hi - lo == 1:
                key = lo + self.key_lo
                if not func(key, prefix):
                    return (key, prefix)
                return (self.key_lo + self.n, prefix + node.value)
            mid = (lo + hi) >> 1
            left = node.left
            if left is not None:
                last_left = left.max_key
                prefix_at_last_left = prefix + left.value - left.max_val
                if not func(last_left, prefix_at_last_left):
                    node = left
                    hi = mid
                    continue
                prefix += left.value
            right = node.right
            if right is None:
                return (self.key_lo + self.n, prefix)
            node = right
            lo = mid

    def floor_key(self, key):
        """``key`` 以下で実在する最大 key を ``O(log n)`` で返す。

        Returns
        -------
        (key, val_at_key, prefix_at_key) : Tuple[int, int, int]
            該当なしの場合 ``(key_lo - 1, 0, 0)`` (key_lo - 1 は不正値の sentinel)。
        """
        not_found = self.key_lo - 1

        i = key - self.key_lo
        if i < 0:
            return (not_found, 0, 0)
        if i >= self.n:
            i = self.n - 1

        node = self.root
        if node is None:
            return (not_found, 0, 0)

        lo = 0
        hi = self.n
        prefix = 0
        fallback_node: Optional[_Node] = None
        fallback_prefix = 0

        while True:
            if node is None:
                break
            if hi - 1 <= i:
                return (node.max_key, node.max_val, prefix + node.value - node.max_val)
            mid = (lo + hi) >> 1
            if i >= mid:
                left = node.left
                if left is not None:
                    fallback_node = left
                    fallback_prefix = prefix
                    prefix += left.value
                node = node.right
                lo = mid
            else:
                node = node.left
                hi = mid

        if fallback_node is not None:
            return (fallback_node.max_key, fallback_node.max_val,
                    fallback_prefix + fallback_node.value - fallback_node.max_val)
        return (not_found, 0, 0)


def solve(n, a, b, ppp, q, queries):
    sgt = DynamicSegmentTree(1 << 51, key_lo=-1 << 50)
    offset = 0
    ab = a + b

    def update(p):
        nonlocal offset

        p -= offset
        bs_key1 = lambda i, acc: (i - acc * ab) <= p
        bs_key2 = lambda i, acc: (i - acc * ab) <= p + ab + 1
        i, prefix_i = sgt.bisect_existing(bs_key1)
        j, prefix_j = sgt.bisect_existing(bs_key2)
        x = p + prefix_i * ab
        loop = (prefix_j - prefix_i) + 1
        sgt.delete(i, j)
        sgt.update(x, loop)
        offset += a

    def query(x):
        key, cur_loop, before_loop = sgt.floor_key(x)
        if key < sgt.key_lo:
            return x + offset
        if x == key:
            partial_loop = 0
        elif x > key + cur_loop * ab:
            partial_loop = cur_loop
        else:
            partial_loop = (x - key - 1) // ab + 1
        return x - (before_loop + partial_loop) * ab + offset

    for pi in range(n):
        update(ppp[pi])

    buf = []
    for t, x in queries:
        if t == 1:
            update(x)
        else:
            buf.append(query(x))

    return buf


if __name__ == '__main__':
    n, a, b = list(map(int, input().split()))
    ppp = list(map(int, input().split()))
    q = int(input())
    queries = [list(map(int, input().split())) for _ in range(q)]
    ans = solve(n, a, b, ppp, q, queries)
    print('\n'.join(map(str, ans)))