−目次

デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）D,F,G,Ex問題メモ

デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）D,F,G,Ex問題メモ

デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）

電装とは、自動車の内部パーツのうち、電気・電子機器の総称。

D - Prime Sum Game

問題

高橋君と青木君がゲームをする
まず高橋君が $A$ 以上 $B$ 以下の好きな整数を1つ言う（青木君にも伝わる）
次に青木君が $C$ 以上 $D$ 以下の好きな整数を1つ言う
2人の合計が素数なら青木君の勝ち、素数でなければ高橋君の勝ち
互いが最適に行動したとき、勝つのはどちらか
$1 \le A \le B \le 100$
$1 \le C \le D \le 100$

解法

制約が少ないので単純にループを回せばいいけど、より値の範囲が大きい場合でも可能な解法（公式解説のBonus）。

$N$ を、2人の整数の和の取り得る最大値（ $=B+D$ ）とする。

$N$ までの、素数なら1、それ以外なら0の配列を作る。エラトステネスのふるいで $O(N\log\log{N})$ で作れる。

0 1 2 3 4 5 6 7 8 9 10 11 ... 200
0 0 1 1 0 1 0 1 0 0  0  1 ...  0

「自身を含めたこの先 $D-C+1$ （青木君が自由に選べる幅）個の連続する整数の中に素数があれば0、なければ1」の配列を作る。
これを $f(x)$ とする。枠をずらしながらの差分更新などで $O(N)$ で作れる。

D-C+1 = 3

  x   0 1 2 3 4 5 6 7 8 9 10 11 ... 198 199 200
素数  0 0 1 1 0 1 0 1 0 0  0  1 ...  0   1   0
f(x)  0 0 0 0 0 0 0 0 1 0  0  0 ...  0   -   -

高橋君は、 $f(自分の選んだ数 + C) = 1$ となる数を選べば、勝てる。 $A～B$ の中にそのような整数が無い場合は、必敗。
存在するかどうかは、 $A+C～B+C$ の合計が $1$ 以上かどうかで判定できる。 $O(N)$

全体で $O(N\log\log{N})$ 。

Python3

F - Construct Highway

問題

$N$ 頂点 $M$ 辺の無向グラフがある
ここに以下の条件を満たしつつ $N-M-1$ 本の辺を追加したい
条件
- 全体が連結
- 各頂点の次数がそれぞれちょうど $D_1,D_2,...,D_N$
可能か判定し、可能なら追加する辺の一例を示せ
$2 \le N \le 2 \times 10^5$

解法

木に関するデータ構造についての典型を組み合わせた上で、ある程度の実装力が求められる。

最終的なグラフは $N$ 頂点 $N-1$ 辺で全体が連結となり、その条件を満たすグラフはすなわち木となる。

よって、以下に1つでも該当するものはハナからアウト。

全体の次数合計が $2(N-1)$ 以外
最初の $M$ 辺の時点で次数が $D_i$ 以上になってしまう頂点がある
最初の $M$ 辺の時点で閉路がある
最初の時点で、以下のような連結成分が存在する
- 構成する頂点の $D_i$ を全てその中だけで使ってしまい、外部と接続するための次数が残っていない

閉路の条件はUnionFindで、追加しようとしている辺が既に同じ連結成分で無いかチェックしていけばよい。

最初のM辺を追加し終わったら追加する辺を求めていく。
常に別々の連結成分に属する頂点同士を結んでいくことを繰り返せばいつの間にか木ができるはずなのだが、下手に結んでしまうと上記アウト条件の4番目のような、残り次数0の独立した連結成分ができてしまう。

そのような場合というのは（最後以外で）互いに残り次数が1の連結成分同士を結んでしまう時。
よって、残り次数の多い連結成分から結んでいけば、回避できる。
以下の方法などで実装できる。

優先度付きキューを使って管理する
残り頂点2以上と1とで分けてストックする

(連結成分の総次数, 連結成分内で次数が残っている頂点リスト) みたいにして順につなぐと完成。

また解説のように、「次数が残っている頂点リスト」を「残っている次数だけ頂点番号を重複させたリスト」にしておくと、個数を気にせずpop・統合していけばよいので実装は楽になる。ただしリストの要素数が増えるため、統合にかかる実行速度は若干遅くなる。

解説 - デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）

Python3

        
          
          
              
              from collections import defaultdict
from heapq import heapify, heappop, heappush
 
 
class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n
 
    def root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x
 
    def find(self, x, y):
        return self.root(x) == self.root(y)
 
    def unite(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return False
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1
        return True
 
    def get_size(self, x):
        return -self.table[self.root(x)]
 
 
n, m = map(int, input().split())
ddd = list(map(int, input().split()))
 
if sum(ddd) != 2 * (n - 1):
    print(-1)
    exit()
 
uft = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    ddd[a] -= 1
    ddd[b] -= 1
    if ddd[a] < 0 or ddd[b] < 0 or not uft.unite(a, b):
        print(-1)
        exit()
 
extra_i = defaultdict(list)
extra_c = defaultdict(int)
for i in range(n):
    if ddd[i] > 0:
        r = uft.root(i)
        extra_i[r].append(i)
        extra_c[r] += ddd[i]
 
q = []
for r, c in extra_c.items():
    q.append((-c, r))
 
heapify(q)
ans = []
 
for _ in range(n - m - 1):
    if len(q) < 2:
        print(-1)
        exit()
    c1, r1 = heappop(q)
    c2, r2 = heappop(q)
    u = extra_i[r1][-1]
    v = extra_i[r2][-1]
    ddd[u] -= 1
    ddd[v] -= 1
    ans.append(f'{u + 1} {v + 1}')
 
    if ddd[u] == 0:
        extra_i[r1].pop()
    if ddd[v] == 0:
        extra_i[r2].pop()
 
    extra_i[r1].extend(extra_i[r2])
    heappush(q, (c1 + c2 + 2, r1))
 
print('\n'.join(ans))

            

        
      

G - Builder Takahashi

問題

$N$ 頂点 $M$ 辺の無向グラフ
いくつかの頂点を通行不能にすることで、頂点 $1$ から $N$ にたどり着けないようにしたい
- 頂点 $1$ と $N$ を直接結ぶ辺は無い
- 頂点 $1$ または $N$ を通行不能にすることはできない
頂点 $i$ を通行不能にするには、コスト $C_i$ かかる
可能な最小コストと、その時の通行不能にする頂点の一例を示せ
$3 \le N \le 100$

解法

ほぼ最小カット問題そのままなので、知ってるかどうかが大きかったか。

最小カットは辺にコストが設定されているが、今回は頂点にコストがあるので、そこは少しグラフを工夫する。
頂点を2重にして、「どっかから入るための頂点」「どっかへ出るための頂点」に分け、入→出を結ぶ辺にコスト $C_i$ を設定すればよい。

さらに今回は、カットすべき辺を求める必要がある。

最大流を求めた後のグラフでもう一度始点から探索し、たどり着ける頂点→たどり着けない頂点を結ぶ辺が、その辺となる。

「容量が残っていない辺」とかだとダメで、ボトルネックが複数あった場合にどれを使うべきか判断できなくなる。

                    （※頂点を2重にする表現は省略）
    ①→②→③→④    最大流まで流した後のグラフでは
Ci       5   5        ②も③も容量が残っていないが、
                      通行不能にするのはどちらかだけでよい

Python3

        
          
          
              
              from collections import deque
from typing import List, Tuple
 
 
class Dinic:
    """
    Usage:
       mf = Dinic(n)
    -> mf.add_link(from, to, capacity)
    -> mf.max_flow(source, target)
    """
 
    def __init__(self, n: int):
        self.n = n
        self.links: List[List[List[int]]] = [[] for _ in range(n)]
        # if exists an edge (v→u, capacity)...
        #   links[v] = [ [ capacity, u, index of rev-edge in links[u], is_original_edge ], ]
 
    def add_link(self, from_: int, to: int, capacity: int) -> None:
        self.links[from_].append([capacity, to, len(self.links[to]), 1])
        self.links[to].append([0, from_, len(self.links[from_]) - 1, 0])
 
    def bfs(self, s: int) -> List[int]:
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev, _ in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        return depth
 
    def dfs(self, s: int, t: int, depth: List[int], progress: List[int], link_counts: List[int]) -> int:
        links = self.links
        stack = [s]
 
        while stack:
            v = stack[-1]
            if v == t:
                break
            for i in range(progress[v], link_counts[v]):
                progress[v] = i
                cap, to, rev, _ = links[v][i]
                if cap == 0 or depth[v] >= depth[to] or progress[to] >= link_counts[to]:
                    continue
                stack.append(to)
                break
            else:
                progress[v] += 1
                stack.pop()
        else:
            return 0
 
        f = 1 << 60
        fwd_links = []
        bwd_links = []
        for v in stack[:-1]:
            cap, to, rev, _ = link = links[v][progress[v]]
            f = min(f, cap)
            fwd_links.append(link)
            bwd_links.append(links[to][rev])
 
        for link in fwd_links:
            link[0] -= f
 
        for link in bwd_links:
            link[0] += f
 
        return f
 
    def max_flow(self, s: int, t: int) -> int:
        link_counts = list(map(len, self.links))
        flow = 0
        while True:
            depth = self.bfs(s)
            if depth[t] < 0:
                break
            progress = [0] * self.n
            current_flow = self.dfs(s, t, depth, progress, link_counts)
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, depth, progress, link_counts)
        return flow
 
    def cut_edges(self, s: int) -> List[Tuple[int, int]]:
        """ max_flowしたあと、最小カットにおいてカットすべき辺を復元する """
        q = [s]
        reachable = [0] * self.n
        reachable[s] = 1
        while q:
            v = q.pop()
            for cap, u, li, _ in mf.links[v]:
                if cap == 0 or reachable[u]:
                    continue
                reachable[u] = 1
                q.append(u)
        edges = []
        for v in range(self.n):
            if reachable[v] == 0:
                continue
            for cap, u, li, orig in mf.links[v]:
                if orig == 1 and reachable[u] == 0:
                    edges.append((v, u))
        return edges
 
 
n, m = map(int, input().split())
mf = Dinic(n * 2)
INF = 1 << 60
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    mf.add_link(a + n, b, INF)
    if a != 0 and b != n - 1:
        mf.add_link(b + n, a, INF)
ccc = list(map(int, input().split()))
for i, c in enumerate(ccc):
    if c > 0:
        mf.add_link(i, i + n, c)
    else:
        mf.add_link(i, i + n, INF)
 
ans = mf.max_flow(0, n - 1)
print(ans)
 
edges = mf.cut_edges(0)
used = [f + 1 for f, t in edges if t == f + n]
 
print(len(used))
print(*used)

            

        
      

Ex - Dice Product 2

問題

$1～N$ の目が等確率で出るサイコロでゲームをする
ゲーム
- はじめ $X=1$
- サイコロを振る毎に出た目を $X$ にかけていく
- $X$ が $M$ を超えたら終わり
終わるまでにサイコロを振る回数の期待値を $\mod{10^9+7}$ で求めよ
$2 \le N \le 10^9$
$1 \le M \le 10^9$

解法

$O(NM)$ 解法

余裕のTLEとなるが、まずはゴールから計算していくことを考える。

現在の値が $X=x$ であるときの残り回数期待値を $f(x)$ とする。
$x \ge M+1$ において、 $f(x)=0$ である。

ゴール一歩手前 $f(M)$ を求める。 $X=M$ である状態からサイコロを1回振ったときの残り回数は、

確率 $\dfrac{1}{N}$ で $1$ が出たとき、 $f(M)$
確率 $\dfrac{1}{N}$ で $2$ が出たとき、 $f(2M)=0$
確率 $\dfrac{1}{N}$ で $3$ が出たとき、 $f(3M)=0$
…
確率 $\dfrac{1}{N}$ で $N$ が出たとき、 $f(NM)=0$

よってこれらをまとめると $f(M)=\dfrac{1}{N}f(M)+1$ より、 $f(M)=\dfrac{N}{N-1}$ となる。
1が出たとき $X$ が変わらないため、式の両辺に同じ値が出てくるが、そこは上手く移項して打ち消す。

$f(M-1),f(M-2),...$ と徐々に減らした値が順次 $O(N)$ で求まっていき、 $f(1)$ が求まると答え。

実際は、サイコロの目 $k=1,2,...,N$ を調べる過程で $kx \gt M$ となったら打ち切れるので、 $f(x)$ の遷移先の個数は $\frac{M}{x}$ となり、全体で均すと $O(M \log{M})$ で求められる。
まぁ、いずれにしろTLE。

想定解法

実は上記の話で、 $f(M)～f(\frac{M}{2}+1)$ は全て同じ値である。
なぜなら、いずれも $2$ 以上が出たらゴールなので、計算式が変わらないため。

また、 $f(\frac{M}{2})～f(\frac{M}{3}+1)$ も全て同じ値。
$2$ が出たら $M～\frac{M}{2}+1$ のどこかに遷移し、 $3$ 以上が出たらゴールのため。

このように、 $g(d)=d$ 倍まではゴールしない（ $d+1$ 倍ではじめてゴールする）場合の残り計算期待値、という括りでまとめても問題ない。

M=39
x  >=40  39-20  19-14  13-10  9-8  7  6  5  4   3   2   1
d    0     1      2      3     4   5  6  7  9  13  19  39

$g(d)$ の状態からサイコロの目 $k$ が出たら、遷移先は $g(d/k)$ となる。（切り捨て）

$g(0)=0$ を始点として $d=1,2,...$ と順に求めていき、 $g(M)$ を求められれば答えとなる。

だが上の表を見ると、 $x$ が大きいときには1つの $d$ が多くの $x$ を代表するが、中盤で1対1対応となり、終盤では飛び飛びになっている。 $g(d)$ を1つずつ求めるのも、終盤は非効率。

だが、実質的な状態数は、だいたい

$d = 0 ～ \sqrt{M}$ なら、各 $d$ についてそれぞれの状態
$d = \sqrt{M}～$ なら、各 $x=1,2,...,\sqrt{M}$ についてそれぞれの状態

の、約 $2 \sqrt{M}$ 個の状態に限られることがわかる。
これらについて、 $f(x)$ または $g(d)$ を求められればよいことになる。

実装方法はいろいろ考えられるが、例えば再帰関数で次のように求められる。

$g(d)$ を求めたいとする
各遷移先の残り回数期待値を合計する変数 $t=0$ を用意する
「遷移先が同じになるサイコロの目の範囲 $[l,r]$ 」を順に求める
- $l=2$ からスタートする
- 遷移先は $d'=d/l$ なので、 $g(d')$ を再帰で求める
- また、 $d$ からの遷移で $d'$ となる最大のサイコロの目 $r=\min(n, d/d')$ を求める
- $\dfrac{r-l+1}{N}$ の確率で $g(d')$ に遷移する
  - $t+=\dfrac{r-l+1}{N} \times g(d')$
- $l←r+1$ に更新し、遷移先が $g(0)$ になるか、 $l$ が $N$ を超えるまで繰り返す
今振った1回と、1の目が出たときの項を加えると、以下の式で表せるので
- $g(d)=\dfrac{1}{N}g(d)+t+1$
移項して整えれば、 $g(d)$ がわかる
- $g(d)=\dfrac{N}{N-1}(t+1)$

ただし同じ $g(d)$ が何回も呼ばれうるため、高速化のためメモ化しておく。

$O(\sqrt{M})$ 個の状態につき $g(d)$ を求め、それぞれは $O(\sqrt{d})$ 回の遷移先の計算をする場合、全体では $O(M^{3/4})$ となるらしい。

$M=10^9$ の場合は約 $5.6 \times 10^7$ 程度となるが、まぁ定数倍の関係か、実際にやってみると間に合う。

Python3

−目次

デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）D,F,G,Ex問題メモ

D - Prime Sum Game

問題

解法

F - Construct Highway

問題

解法

G - Builder Takahashi

問題

解法

Ex - Dice Product 2

問題

解法

O(NM)O(NM) 解法

想定解法

$O(NM)$ 解法