HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）F,G問題メモ

HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）

F - Black Jack

問題

整数 $N,L,D$ が与えられる
あなたとディーラーがゲームをする
- 各自、持ち点 $0$ からスタート
- 「$1～D$ の目が等確率で出るダイスを振って、出た目を持ち点に加算する」ことを好きなだけ繰り返す
- $N$ 点を超えたらバーストで負け
- 互いにバーストしていない場合、最終的な持ち点の多い方が勝ち
- 引き分け（互いにバーストした場合や、持ち点が同点の場合）はあなたの負け
ディーラーの行動は決まっていて、持ち点 $L$ 点未満の間ダイスを振り続け、$L$ 点以上になったらやめる
- あなたはディーラーの最終的な持ち点は知り得ないが、この行動基準は知っている
最適に行動した場合のあなたの勝率を求めよ
$1 \le L \le N \le 2 \times 10^5$

解法

自分が、バーストの可能性のある持ち点から続けて振るべきかどうかは、ディーラーの最終的な持ち点の確率分布が分からないと何とも言えない。

ディーラーの行動は決まっていて、持ち点 $i$ になる確率 $P_i$ は計算できる。
なのでまずそれを計算する。

$i=0～L-1$ に対して、ダイスの目の分だけ分配していけばいい。

N=5 D=3, L=4
                                 |→Burst
 i   0    1    2    3    4    5  |  6    7
     1    0    0    0    0    0  |  0    0
     `----v----v----v
       + 1/3  1/3  1/3
     0   1/3  1/3  1/3   0    0     0    0
          `----v----v----v
           +  1/9  1/9  1/9
     0    0   4/9  4/9  1/9   0     0    0
               `----v----v----v
                 + 4/27 4/27 4/27
     0    0    0  16/27 7/27 4/27   0    0
                    `----v----v-----v
                     + 16/81 16/81 16/81
Pi   0    0    0    0  37/81 28/81 16/81 0

以下を求める。

$W_i$: あなたが持ち点 $i$ で操作を終えたときの勝率
$S_i$: 操作を終えるかは関係なく、持ち点 $i$ からの勝率

$W_i$ に関して、あなたは持ち点でディーラーを真に上回らないといけないので、 $P_i$ の累積和を取って1つ右にずらしたものが暫定の $W_i$ となる。

                                 |→Burstにつき無意味
 i   0    1    2    3    4    5  |(   6     7   )
Wi   0    0    0    0    0  37/81|( 65/81 81/81 )

ただし、ディーラーがバーストした時は、あなたはバーストしてない限り勝つ。
ディーラーのバースト確率 $\frac{16}{81}$ を $W_i$ 全体に加算する。これが最終的な $W_i$ となる。

 i   0     1     2     3     4     5   (  6    7    8  ...)
Wi 16/81 16/81 16/81 16/81 16/81 53/81 (  0    0    0  ...)

あなたは、持ち点 $i$ の時、「操作をここで終えるか、ダイスを振って持ち点を $i+1～i+D$ のどれかにするか」を選べる。
勝率の高い行動を採用すべきである。

$i$ で操作を終えたときの勝率 $W_i$
$i$ からダイスを振った場合の勝率 $\displaystyle T_i = \frac{S_{i+1}+S_{i+2}+...+S_{i+D}}{D}$
- ただし $j \gt N$（バースト）のとき、$S_j=0$

$S_i=\max(W_i,T_i)$ となる。

$S$ をセグメント木などに載せ、$i$ の降順に $S_i$ を求めていき、$S_0$ が答え。

計算量は $O(N\log{N})$。少し実装が泥臭くなるが累積和を使うと、$O(N)$

Python3

from itertools import accumulate
from operator import add


class SegmentTreeInjectable:
    """
    単位元生成関数 identity_factory と二項演算関数 func を外部注入するセグメント木

    [生成]
    SegmentTreeInjectable(n, identity_factory, func)
    SegmentTreeInjectable.from_array(array, identity_factory, func)  # 既存の配列より作成

    [関数]
    add(i, x)               Aiにxを加算
    update(i, x)            Aiをxに書き換え
    get_range(a, b)         [a, b) の集約値を得る
    get_all()               全ての集約値を得る
    get_point(i)            Aiを得る
    leftmost(a, b, x, ev)   [a, b) の範囲で、ev(x, Ai)=True となる最も左の i を得る（前提条件あり）
    rightmost(a, b, x, ev)  [a, b) の範囲で、ev(x, Ai)=True となる最も右の i を得る（前提条件あり）
    debug_print()           深さ毎に整形して出力する
    """

    def __init__(self, n, identity_factory, func):
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [identity_factory() for _ in range(n2 << 1)]
        self.func = func
        self.idf = identity_factory

    @classmethod
    def from_array(cls, arr, identity_factory, func):
        """ 既存の配列から生成 """
        ins = cls(len(arr), identity_factory, func)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = func(ins.tree[l], ins.tree[r])
        return ins

    def add(self, i, x):
        """
        Aiにxを加算
        :param i: index (0-indexed)
        :param x: add value
        """
        i += self.offset
        self.tree[i] = self.func(self.tree[i], x)
        self.__upstream(i)

    def update(self, i, x):
        """
        Aiの値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        self.__upstream(i)

    def __upstream(self, i):
        tree = self.tree
        func = self.func
        while i > 1:
            i >>= 1
            lch = i << 1
            rch = lch | 1
            tree[i] = func(tree[lch], tree[rch])

    def get_range(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        tree = self.tree
        func = self.func
        result_l = self.idf()
        result_r = self.idf()

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result_r = func(tree[r - 1], result_r)
            if l & 1:
                result_l = func(result_l, tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return func(result_l, result_r)

    def get_all(self):
        return self.tree[1]

    def get_point(self, i):
        return self.tree[i + self.offset]

    def leftmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最初の index を得る。存在しない場合は-1。

        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        r_found = -1
        while l < r:
            if l & 1:
                if ev(x, tree[l]):
                    return self._leftmost_sub(l, x, ev)
                l += 1
            if r & 1:
                if ev(x, tree[r - 1]):
                    r_found = r - 1
            l >>= 1
            r >>= 1

        if r_found == -1:
            return -1

        return self._leftmost_sub(r_found, x, ev)

    def _leftmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も左のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l]):
                i = l
            else:
                i = l + 1
        return i - self.offset

    def rightmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最後の index を得る。存在しない場合は-1。

        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        l_found = -1
        while l < r:
            if r & 1:
                if ev(x, tree[r - 1]):
                    return self._rightmost_sub(r - 1, x, ev)
            if l & 1:
                if ev(x, tree[l]):
                    l_found = l
                l += 1
            l >>= 1
            r >>= 1

        if l_found == -1:
            return -1

        return self._rightmost_sub(l_found, x, ev)

    def _rightmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も右のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l + 1]):
                i = l + 1
            else:
                i = l
        return i - self.offset

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.tree[i:i * 2])
            i <<= 1


n, l, d = map(int, input().split())
p = 1 / d

dp = [0] * (n + d + 5)
dp[0] = 1
dp[1] = -1
for i in range(n + 1):
    dp[i + 1] += dp[i]
    if i < l:
        k = dp[i] * p
        dp[i + 1] += k
        dp[i + d + 1] -= k
        dp[i] = 0

y_burst = 1 - sum(dp[:n + 1])
win = list(accumulate([y_burst] + dp))
win[n + 1:] = [0.] * len(win[n + 1:])

sgt = SegmentTreeInjectable.from_array(win, float, add)
for i in range(n, -1, -1):
    no_dice = win[i]
    go_dice = sgt.get_range(i + 1, i + d + 1) * p
    if no_dice < go_dice:
        sgt.update(i, go_dice)
    # sgt.debug_print()

ans = sgt.get_point(0)
print(ans)

G - Retroactive Range Chmax

問題

長さ $N$ の数列、はじめは $A=(A_1,A_2,...,A_N)$
$Q$ 個のクエリに答える
- タイプ1:「1 l r x」で与えられ、$i=l,...,r$ に対して、$A_i$ を $\max(A_i,x)$ で置き換える
- タイプ2:「2 i」で与えられ、$i$ 番目のクエリを取り消す（$i$ 番目は必ずタイプ1のクエリ）
- タイプ3:「3 i」で与えられ、$A_i$ を出力する
$1 \le N,Q \le 2 \times 10^5$

解法

クエリの取り消しが必要。

取り消す更新が加算など逆演算の存在する操作なら、「操作を取り消す＝加算した分を減算する」が成り立つが、残念ながら max は操作後から操作前を復元できない。

縦に時間（クエリ番号）、横に $A$ のindexをもった2次元座標をイメージする。

  →index
↓
ク   ┌─┐
エ   │┌┼─┐
リ   └┼┘  │
       └──┘

クエリを先読みして、各クエリがいつ取り消されるかを求めておけば、ひとつのクエリの影響範囲は矩形になる。
この問題は「矩形 chmax、1点取得」のデータ構造があればよい。

双対2次元セグメント木がその条件を満たす。
$Q \times N$ の配列は持てないので必要な部分だけを作る動的セグメント木にすると、空間計算量は $O(Q \log{N} \log{Q})$ で済む。

時間計算量も $O(N+Q\log{N}\log{Q})$ となり、制限時間が長いので、通る。

Python3

from collections import defaultdict
from typing import TypeVar, Generic, Callable

T = TypeVar('T')


class Dynamic2dSegmentTreeDual(Generic[T]):
    """
    矩形加算・1点取得を行う 双対2次元セグメント木。
    O(HW) がメモリに乗らない場合に、Dictで必要な部分しか持たないことで、メモリを削減する。定数倍は重め。

    (T, func): 可換モノイド
    factory: 単位元の生成関数

    非可換の場合、2次元だとどういう順番で足すのか非自明なため、可換を前提とした実装。
    """

    def __init__(self, h: int, w: int, factory: Callable[[], T], func: Callable[[T, T], T]):
        self.data = defaultdict(dict)
        self.h_depth = (h - 1).bit_length()
        self.w_depth = (w - 1).bit_length()
        self.h_offset = 1 << self.h_depth
        self.w_offset = 1 << self.w_depth
        self.func = func
        self.factory = factory

    def add_range(self, i1: int, j1: int, i2: int, j2: int, x: T) -> None:
        """ [i1, i2) [j1, j2) に x を作用させる """
        data = self.data
        l = i1 + self.h_offset
        r = i2 + self.h_offset
        l2 = j1 + self.w_offset
        r2 = j2 + self.w_offset
        while l < r:
            if r & 1:
                self._add_row(l2, r2, data[r - 1], x)
            if l & 1:
                self._add_row(l2, r2, data[l], x)
                l += 1
            l >>= 1
            r >>= 1

    def _add_row(self, l: int, r: int, node, x: T) -> None:
        func = self.func
        while l < r:
            if r & 1:
                node[r - 1] = func(node[r - 1], x) if r - 1 in node else x
            if l & 1:
                node[l] = func(node[l], x) if l in node else x
                l += 1
            l >>= 1
            r >>= 1

    def get_point(self, i: int, j: int):
        data = self.data
        func = self.func
        result = self.factory()

        i += self.h_offset
        j += self.w_offset
        while i:
            if i in data:
                node = data[i]
                k = j
                while k > 0:
                    if k in node:
                        result = func(result, node[k])
                    k >>= 1
            i >>= 1

        return result


n = int(input())
aaa = list(map(int, input().split()))
q = int(input())

update_queries = {}
answer_queries = []

for qi in range(q):
    query = input()
    if query[0] == '1':
        _, l, r, x = map(int, query.split())
        update_queries[qi] = [qi, q, l - 1, r, x]
    elif query[0] == '2':
        _, i = map(int, query.split())
        update_queries[i - 1][1] = qi
    else:
        _, i = map(int, query.split())
        answer_queries.append((qi, i - 1))

sgt = Dynamic2dSegmentTreeDual(q, n, int, max)
for i, j, l, r, x in update_queries.values():
    sgt.add_range(i, l, j, r, x)

buf = []
for qi, i in answer_queries:
    ans = max(aaa[i], sgt.get_point(qi, i))
    buf.append(ans)

print('\n'.join(map(str, buf)))

目次

HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）F,G問題メモ

F - Black Jack

問題

解法

G - Retroactive Range Chmax

問題

解法