AtCoder Beginner Contest 404（Promotion for Engineer Guild）F,G問題メモ

AtCoder Beginner Contest 404（Promotion for Engineer Guild）

F - Lost and Pound

問題文

$N$ 個の押しボタンがあります。このうち $1$ 個が当たりで、残りの $N-1$ 個はハズレです。
青木君はどのボタンが当たりであるか知っており、高橋君は知りません。また高橋君には $N$ 個のボタンの区別はつきません。
このボタンを使って青木君と高橋君がゲームを行います。ゲームは以下の一連の流れの $T$ 回の繰り返しからなります。
1. 青木君が $N$ 個のボタンをランダムな順序に並べる
2. 高橋君が「ボタンを $1$ つ選び、そのボタンを押す」という操作を $M$ 回行う。同じボタンを複数回選んでもよい
3. ゲーム開始時からこれまでに当たりのボタンが何回押されたかを青木君が高橋君に教える
$T$ 回の繰り返しで、当たりのボタンを合計 $K$ 回以上押すことができたとき、かつ、そのときに限り高橋君の勝ちです。
勝つ確率が最大になるように高橋君が行動したときの、高橋君の勝率を求めてください。
真の解との絶対誤差または相対誤差が $10^{-6}$ 以下のとき正解と判定される。

制約

$1 \leq N \leq 2\times 10^5$
$1 \leq T \leq 30$
$1 \leq M \leq 30$
$1 \leq K \leq 30$
入力は全て整数

解法

めっちゃ誤読して、ボタンは最初以外、並び替えられないものと考えてしまっていた。
結果によって当たりボタンを絞り込んでいけると思ったら、そうではなかった。

毎回並び替えられてしまうので、今回の操作で押したボタンに当たりが含まれていても、次回はどこに行ったかわからない。
よって、毎回、左詰で押していくと考えてよい。

ボタンの押し方の数は、合計が $M$ になるような正整数の組合せの数、つまり $M$ の分割数になる。
分割数は $M=30$ でも $5604$ 個であり、その具体的な分割の仕方を同時に求めても、 $O(M^3)$ で済む。

その上で、以下の関数を考える。 $f(T,K)$ を求められればよい。

$f(t,k):=$ 残りターン $t$ 、残り必要押し回数 $k$ である時の勝率

ある押し方で、ボタンを押す回数を $X=\{x_1,x_2,...,x_p\}$ 回とする。（ $\sum_i x_i = M$ ）

ボタン $i$ が当たりである確率は $1/N$
その時、これ以降の勝率は $f(t-1,k-x_i)$

また、

どれも当たりでない確率は $(N-p)/N$
その時、これ以降の勝率は $f(t-1,k)$

押し方 $X$ の勝率は、これらの和となる。

$\displaystyle \sum_{i=1}^{p}\frac{f(t-1,k-x_i)}{N} + \frac{(N-p)f(t-1,k)}{N}$

全ての押し方の中の最大値が、 $f(t,k)$ となる。

よって、状態数 $O(TK)$ 、1回の遷移 $O(p(M)M)$ となる。（ $p(M)$ を $M$ の分割数とする）
全体 $O(M^3 + TKM p(M))$ で求められる。

Python3

G - Specified Range Sums

問題文

整数 $N$ と長さ $M$ の整数列 $L=(L_1,L_2,\dots,L_M),R=(R_1,R_2,\dots,R_M),S=(S_1,S_2,\dots,S_M)$ が与えられるので、次の問題を解いてください。
以下の条件を満たす長さ $N$ の正整数列 $A$ が存在するか判定し、存在する場合は $A$ の総和としてありうる最小値を求めてください。
- 全ての $i$ ( $1 \le i \le M$ ) について、 $\displaystyle \sum_{j=L_i}^{R_i} A_j = S_i$ を満たす。

制約

入力は全て整数
$1 \le N,M \le 4000$
$1 \le L_i \le R_i \le N$
$1 \le S_i \le 10^9$

解法

$A$ の代わりに、累積和 $B_0,B_1,...,B_N$ を考えることにする。 $B_0=0$ として、 $B_N$ の取り得る最小値が答えとなる。

各条件 $(L,R,S)$ は、 $B_{L-1}+S=B_{R}$ という制約となる。
また、 $A$ は正整数列より、 $B_{i}+1 \le B_{i+1}$ という制約もある。

前者の制約は、ポテンシャル付きUnionFindで、 $(L,R)=(1,2),(2,3),(1,3)$ のように、ループする関係性について矛盾するか調べられる。
矛盾したら答えは無し。

矛盾しなかったら、各連結成分の中で1つの値が決まったら残りも全部決まる。
後は後者の制約に違反しないように、各連結成分のオフセットを決めるか、矛盾することを判定できればよい。

各連結成分 $c$ について、以下のように暫定オフセット値 $O_c$ を調べていく。
最初は各 $c$ に対し $O_c=0$ とする。

$i=1,2,...,N$ の順に、以下の2つを計算する。
- $p$ : $i$ の属する連結成分 $c_i$ のオフセット $O_{ci}$ を元にした値
- $q$ : $i-1$ の箇所から1大きい値
$p \lt q$ の時、現在のオフセットでは足りないということなので、足りない分、オフセットを更新する。

1周しただけでは、正しい答えが求まる保証はない。
$i$ が後の方でのオフセットの更新の影響が、前の方に遡るかもしれないので。

だが、更新の発生は「連結成分の数」周以内に収まる（TODO 未証明）。
Bellman-Ford と似た要領で、何周か更新を繰り返した上で、次の1回でも更新が発生した場合、矛盾する区間があったということになる。

Python3

        
          
          
              
              from operator import add, sub
from typing import TypeVar, Generic, Callable
 
T = TypeVar('T', int, float, tuple)  # データ構造に載せそうな型のうち、Immutable なもの（漏れてたら追加可）
 
 
class UnionFindWithPotential(Generic[T]):
    """ポテンシャル付きUnion-Find
 
    以下の2つのクエリを処理する。
      * unite(x,y,d): 2要素間の差分に対する制約 (x - y = d) を決める。
      * diff(x,y):    2要素間の差を返す。未定義（x と y が連結でない）なら None を返す。
 
    載せられるのはアーベル群に限る(?)。
    つまり2項間の「加算演算」「減算演算」が定義でき、また「加算演算が可換」である場合に限る。
 
    Attributes:
        table (list[int]): 各頂点の、親の頂点番号を表すList。または親である場合は(-要素数)
        values (list[T]): 各頂点の、親との差分を表すList
    """
 
    def __init__(self,
                 n: int,
                 init: T,
                 func: Callable[[T, T], T],
                 rev_func: Callable[[T, T], T]):
        """コンストラクタ
 
        Args:
            n: 要素数
            init: 単位元
            func: 2項間加算演算 (add)
            rev_func: 2項間減算演算 (sub)
        """
        self.table = [-1] * n
        self.values = [init] * n
        self.init = init
        self.func = func
        self.rev_func = rev_func
 
    def root(self, x: int) -> int:
        stack = []
        tbl = self.table
        vals = self.values
 
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        if stack:
            val = self.init
            while stack:
                y = stack.pop()
                val = self.func(val, vals[y])
                vals[y] = val
                tbl[y] = x
        return x
 
    def is_same(self, x: int, y: int) -> bool:
        return self.root(x) == self.root(y)
 
    def diff(self, x: int, y: int) -> T | None:
        """ x と y の差（y - x）を取得。同じグループに属さない場合は None。
        """
        if not self.is_same(x, y):
            return None
        vx = self.values[x]
        vy = self.values[y]
        return self.rev_func(vy, vx)
 
    def unite(self, x: int, y: int, d: T) -> bool:
        """ x と y のグループを、y - x = d となるように統合（順序に注意）
        既に x と y が同グループで、矛盾する場合は AssertionError。矛盾しない場合はFalse。
        同グループで無く、新たな統合が発生した場合はTrue。
        """
        rx = self.root(x)
        ry = self.root(y)
        vx = self.values[x]
        vy = self.values[y]
        if rx == ry:
            assert self.rev_func(vy, vx) == d
            return False
 
        rd = self.rev_func(self.func(vx, d), vy)
        self.table[rx] += self.table[ry]
        self.table[ry] = rx
        self.values[ry] = rd
        return True
 
    def get_size(self, x: int) -> int:
        return -self.table[self.root(x)]
 
 
def solve(n, m, constraints):
    uft = UnionFindWithPotential(n + 1, 0, add, sub)
    for l, r, s in constraints:
        l -= 1
        s -= r - l
        if s < 0:
            return -1
        try:
            uft.unite(l, r, s)
        except AssertionError:
            return -1
 
    groups = [{i} for i in range(n + 1)]
    for i in range(n + 1):
        r = uft.root(i)
        groups[i] = groups[r]
        groups[r].add(i)
 
    min_l = [-1] * (n + 1)
    potentials = [0] * (n + 1)
    for i in range(n + 1):
        if min_l[i] != -1:
            continue
        for j in groups[i]:
            min_l[j] = i
            potentials[j] = uft.diff(i, j)
 
    result = [-1] * (n + 1)
    result[0] = 0
    updated = False
    for _ in range(len(set(min_l)) + 1):
        updated = False
        for i in range(1, n + 1):
            res_min = result[min_l[i]] + potentials[i]
            res_prv = result[i - 1]
            if res_min >= res_prv:
                if result[i] < res_min:
                    result[i] = res_min
                    updated = True
            else:
                if result[i] < res_prv:
                    result[i] = res_prv
                    result[min_l[i]] = res_prv - potentials[i]
                    updated = True
        if updated == False:
            break
 
    if result[0] > 0:
        return -1
    if updated:
        return -1
 
    return result[n] + n
 
 
n, m = map(int, input().split())
constraints = [tuple(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, constraints)
print(ans)

            

        
      