オムロンプログラミングコンテスト2025（AtCoder Beginner Contest 397）E,F,G問題メモ

オムロンプログラミングコンテスト2025（AtCoder Beginner Contest 397）

コンテスト開始数分前から、AtCoderのトップページが500エラーで落ちていた。
コンテストページは無事だったためか、特にアナウンスも無く、普通にRatedだった。参加するコンテストページは直接把握しておいた方が良さそう。
（ABCなら、https://atcoder.jp/contests/abcXXX）

E - Path Decomposition of a Tree

問題文

$NK$ 頂点の木が与えられます。頂点には $1,2,\dots,NK$ の番号がついており、$i$ 番目 ($i=1,2,\dots,NK-1$) の辺は頂点 $u_i,v_i$ を双方向に結んでいます。
この木を $N$ 本の長さ $K$ のパスに分解できるか判定してください。より詳細には、以下を満たす $N \times K$ 行列 $P$ が存在するかどうか判定してください。
- $P_{1,1},\dots,P_{1,K},P_{2,1},\dots,P_{N,K}$ は $1,2,\dots,NK$ の並べ替えである。
- 各 $i=1,2,\dots,N,\;j=1,2,\dots,K-1$ について、頂点 $P_{i,j}$ と頂点 $P_{i,j+1}$ を結ぶ辺が存在する。

制約

$1 \leq N$
$1 \leq K$
$NK \leq 2 \times 10^5$
$1 \leq u_i \lt v_i \leq NK$
与えられるグラフは木である
入力はすべて整数

解法

適当な頂点を根として木DP。
$\mathrm{DP}[v]$ を、以下を表すものとして定義する。

$v$ 以下の部分木は、1本の「$v$ を端点の1つとする長さ $\mathrm{DP}[v]$ のパス」と、0本以上の「長さ $K$ のパス」に分解できる

葉は $\mathrm{DP}[v]=1$ である。

子を持つ頂点は、子のDPの値の中に $K$ でない数が含まれる個数で場合分けする。

$0$ 個の時
- そこから新たなパスを開始できる。$\mathrm{DP}[v]=1$
$1$ 個の時
- パスを引き継ぐ。その子を $c_i$ として、$\mathrm{DP}[v]=\mathrm{DP}[c_i]+1$
$2$ 個の時
- $v$ を介して、その2本を折り返す形で繋ぐ場合のみ許される。
- 2つの子を $c_i,c_j$ として、$\mathrm{DP}[c_i]+\mathrm{DP}[c_j]+1=K$ ならOK。
  - $\mathrm{DP}[v]=K$ とする。（$v$ が端点ではないが、後の処理に問題ないので便宜的な措置）
- その他の場合、不可能。
$3$ 個以上の時
- 不可能。

不可能にならず、根までDPを完遂できたら可能。

Python3

def solve(n, k, edges):
    links = [set() for _ in range(n * k)]
    for u, v in edges:
        u -= 1
        v -= 1
        links[u].add(v)
        links[v].add(u)
    dp = [-1] * (n * k)
    q = [0]
    while q:
        u = q[-1]
        if dp[u] == -1:
            dp[u] = -2
            for v in links[u]:
                links[v].remove(u)
                q.append(v)
            continue
        q.pop()
        tmp = []
        for v in links[u]:
            if dp[v] == k:
                continue
            tmp.append(dp[v])
        if len(tmp) > 2:
            return False
        if len(tmp) == 2:
            v, w = tmp
            if v + w + 1 == k:
                dp[u] = k
            else:
                return False
        elif len(tmp) == 1:
            dp[u] = tmp[0] + 1
        else:
            dp[u] = 1
    return dp[0] == k


n, k = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(n * k - 1)]
if solve(n, k, edges):
    print('Yes')
else:
    print('No')

F - Variety Split Hard

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。
$A$ を $2$ か所で区切って $3$ 個の空でない連続する部分列に分割するとき、数列に含まれる数の種類数の和としてありえる最大値を求めてください。
より厳密には、$1 \leq i \lt j \leq N-1$ を満たす整数の組 $(i,j)$ について $(A_1,A_2,\ldots,A_i) , (A_{i+1},A_{i+2},\ldots,A_j) , (A_{j+1},A_{j+2},\ldots,A_{N})$ のそれぞれに含まれる整数の種類数の和としてありえる最大値を求めてください。

制約

$3 \leq N \leq 3 \times 10^5$
$1 \leq A_i \leq N$ ($1 \leq i \leq N$)
入力はすべて整数である

解法

C問題の強化版であると問題冒頭にあったおかげで、F問題と考察をまとめることができた。
完全にコードを流用できるわけではなくても、こういう情報を明示してくれるのはありがたい。

ある数字が $k$ 回（$k \ge 2$）出現するとして、$(1,2),(2,3),...,(k-1,k)$ 番目に出てくる箇所をそれぞれ両端とした区間を考える。

    3   1   4   1   5   9   2   6   5   3   5   8   9   7   9
3  (  *   *   *   *   *   *   *   *   *  )
1      (  *   *  )
5                  (  *   *   *   *  )
5                                  (  *   *  )
9                      (  *   *   *   *   *   *   *  )
9                                                  (  *   *  )

ある区間について、そこに含まれる「*」（数字と数字の間）で部分列を分けた時、区間の両端の数字が別々に数えられる。
逆に、それ以外（区間が部分列に完全に内包される）の場合、両端の数字は必ずダブってしまう。

よって、問題は以下のように言い換えられる。

$A$ 全体に含まれる数字の種類数は、必ず確保できる。
各区間について、それを分割する位置で部分列を分けた場合、「分割した区間数」だけ追加ボーナスが入る。
追加ボーナスを最大化せよ。

なるべく多くの区間をぶった切れる箇所で部分列を分割するとよい。

C問題は分割箇所を1つ決めればよいので、重なり数の最大値を取ればよい。

C問題の答え = （$A$ 全体に含まれる数字の種類数）+（「*」が重なっている最大数）
- 下例では、$9 + 3 = 12$

    3   1   4   1   5   9   2 | 6   5   3   5   8   9   7   9
3  (  *   *   *   *   *   *   +   *   *  )
1      (  *   *  )            |
5                  (  *   *   +   *  )
5                             |    (  *   *  )
9                      (  *   +   *   *   *   *   *  )
9                             |                    (  *   *  )

F問題は3つの区間に分割するので分割箇所を2つ決めるが、難しいのは「分割箇所と区間の交点数」を最大化するのではなく、「分割される区間数」を最大化したいので、ある区間が複数の分割箇所を含んでいても、数えられるのは1回である点である。

    3   1   4   1   5   9 | 2   6   5 | 3   5   8   9   7   9
3  (  *   *   *   *   *   +   *   *   +  )
1      (  *   *  )        |           |
5                  (  *   +   *   *  )|
5                         |        (  +   *  )
9                      (  +   *   *   +   *   *   *  )
9                         |           |            (  *   *  )

計6個の交点があるが、3, 9 は1つの区間が2回区切られているため、
「分割される区間数」としては4個。

右側の分割箇所を左から右へ全探索する。

左側の分割箇所は、「右側の分割箇所が完全に過ぎ去った区間」だけで重なり数の最大値を取りたい。
これは、各区間の始点・終点位置を前計算しておけば、区間add操作・区間max取得の遅延セグメント木で可能である。

Python3

from operator import add
from typing import TypeVar, Generic, Callable, List

T = TypeVar('T')
U = TypeVar('U')


class LazySegmentTreeInjectable(Generic[T, U]):
    def __init__(self,
                 n: int,
                 identity_data: Callable[[], T],
                 identity_lazy: Callable[[], U],
                 operation: Callable[[T, T], T],
                 mapping: Callable[[T, U], T],
                 composition: Callable[[U, U], U],
                 ):
        self.n = n
        self.depth = n.bit_length()
        self.offset = 1 << self.depth
        self.identity_data = identity_data
        self.identity_lazy = identity_lazy
        self.operation = operation
        self.mapping = mapping
        self.composition = composition
        self.data = [identity_data() for _ in range(self.offset << 1)]
        self.lazy = [identity_lazy() for _ in range(self.offset)]

    @classmethod
    def from_array(cls,
                   arr: List[T],
                   identity_data: Callable[[], T],
                   identity_lazy: Callable[[], U],
                   operation: Callable[[T, T], T],
                   mapping: Callable[[T, U], T],
                   composition: Callable[[U, U], U],
                   ):
        ins = cls(len(arr), identity_data, identity_lazy, operation, mapping, composition)
        ins.data[ins.offset:ins.offset + ins.n] = arr
        for i in range(ins.offset - 1, 0, -1):
            ins.update(i)
        return ins

    def push(self, i: int) -> None:
        if i < self.offset:
            data = self.data
            lazy = self.lazy
            lz = lazy[i]

            lch = i << 1
            rch = lch + 1
            data[lch] = self.mapping(data[lch], lz)
            data[rch] = self.mapping(data[rch], lz)
            if lch < self.offset:
                lazy[lch] = self.composition(lazy[lch], lz)
                lazy[rch] = self.composition(lazy[rch], lz)
            lazy[i] = self.identity_lazy()

    def update(self, i: int) -> None:
        lch = i << 1
        rch = lch + 1
        self.data[i] = self.operation(self.data[lch], self.data[rch])

    def all_apply(self, i: int, d: U) -> None:
        self.data[i] = self.mapping(self.data[i], d)
        if i < self.offset:
            self.lazy[i] = self.composition(self.lazy[i], d)

    def propagate(self, l: int, r: int) -> None:
        for i in range(self.depth, 0, -1):
            if ((l >> i) << i) != l:
                self.push(l >> i)
            if ((r >> i) << i) != r:
                self.push((r - 1) >> i)

    def range_update(self, l: int, r: int, d: U) -> None:
        l += self.offset
        r += self.offset
        self.propagate(l, r)

        l2 = l
        r2 = r
        while l < r:
            if (l & 1) == 1:
                self.all_apply(l, d)
                l += 1
            if (r & 1) == 1:
                r -= 1
                self.all_apply(r, d)
            l >>= 1
            r >>= 1
        l = l2
        r = r2

        for i in range(1, self.depth + 1):
            if ((l >> i) << i) != l:
                self.update(l >> i)
            if ((r >> i) << i) != r:
                self.update((r - 1) >> i)

    def range_query(self, l: int, r: int) -> T:
        l += self.offset
        r += self.offset

        self.propagate(l, r)
        sml = self.identity_data()
        smr = self.identity_data()
        while l < r:
            if (l & 1) == 1:
                sml = self.operation(sml, self.data[l])
                l += 1
            if (r & 1) == 1:
                r -= 1
                smr = self.operation(self.data[r], smr)
            l >>= 1
            r >>= 1
        return self.operation(sml, smr)

    def point_set(self, p: int, d: T) -> None:
        p += self.offset
        for i in range(self.depth, 0, -1):
            self.push(p >> i)
        self.data[p] = d
        for i in range(1, self.depth + 1):
            self.update(p >> i)

    def point_get(self, p: int) -> T:
        p += self.offset
        for i in range(self.depth, 0, -1):
            self.push(p >> i)
        return self.data[p]

    def debug_print(self) -> None:
        i = 1
        while i <= self.offset:
            print(*map('{: 4d}'.format, self.data[i:i * 2]))
            i <<= 1
        i = 1
        while i <= self.offset:
            print(*map('{: 4d}'.format, self.lazy[i:i * 2]))
            i <<= 1


def solve(n, aaa):
    first = {}
    last = {}
    for i, a in enumerate(aaa):
        if a not in first:
            first[a] = i
        last[a] = i
    firsts = set(first.values())
    lasts = set(last.values())

    identity_data = int
    identity_lazy = int
    operation = max
    mapping = add
    composition = add

    lst = LazySegmentTreeInjectable(n, identity_data, identity_lazy, operation, mapping, composition)
    tmp = 0
    ans = 0
    prev = {}
    for i, a in enumerate(aaa):
        if a in prev:
            lst.range_update(prev[a], i, 1)
        prev[a] = i

        if i in firsts:
            tmp += 1
        if i in lasts:
            tmp -= 1
        ans = max(ans, tmp + lst.range_query(0, lst.offset))

    return len(set(aaa)) + ans


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

G - Maximize Distance

問題文

$N$ 頂点 $M$ 辺の有向グラフが与えられます。
- 頂点には $1,2,\dots,N$ の番号がついており、辺 $j$ ($j=1,2,\dots,M$) は頂点 $u_j$ から頂点 $v_j$ に向かいます。
- 頂点 $1$ から頂点 $N$ に到達可能であることが保証されます。
はじめ、すべての辺の重みは $0$ です。
$M$ 本の辺からちょうど $K$ 本の辺を選んで重みを $1$ に変更するとき、変更後のグラフにおける頂点 $1$ から頂点 $N$ への最短距離としてあり得る最大値を求めてください。

制約

$2 \leq N \leq 30$
$1 \leq K \leq M \leq 100$
$1 \leq u_j,v_j \leq N$
$u_j \neq v_j$
与えられるグラフにおいて、頂点 $1$ から頂点 $N$ へ到達可能である
入力はすべて整数

誤った解法

最短距離を $1$ にするのに必要な本数は「最小カット」と一致するので、これが $K$ 以下になるかどうかで「少なくとも答えが $1$ 以上になるかどうか」はわかる。

なんとなくこの繰り返し、つまり「最小カットを解き、カットされた辺をINFにする」を、必要なカット辺の累積本数が $K$ を超えるまで繰り返せばよいのでは？という解法が思いつく。

だが、これは最小カットの候補が複数あるとき、どれを選ぶかによって2回目以降の結果が異なる場合があり、WAとなる。

N=4 M=6 K=5
             最適解は、③→②以外の5辺を採用した、最短距離 2。
①⇉②→④   しかし、1回目で「①→③ と ②→④」の組がカット辺として成立する。
  ↘↑↗     それを選んだ場合、2回目は全ての辺をカットせねばならず、
    ③       K を超えるため、最短距離 1 と判定されてしまう。
             ※1回目に「②→④ と ③→④」をカット辺とすると成功する。

ジャッジサーバに用意されたテストケースでは、この解法で1ケース以外通ってしまったんだよな。

解法

二分探索 + k値燃やす埋める。頂点の意味の持たせ方が難しい。

「最短距離を $d$ にするために必要な本数は $K$ 以下か？」を判定する。
この判定問題が解けるなら、$d$ を二分探索すればよい。

最小カットで解く。
最小カットとは、「頂点集合を $S,T$ の2グループに分類する方法のうち、始点は $S$、終点は $T$ である全ての方法の中で、$S→T$ の間に張られた辺の重み合計が最小となるような分類、またその時の重み合計値」なので、それで判定問題が解けるように上手く辺を張る。

$d \times N$ 頂点用意して、長方形に並べる。

d=3 N=4

(1,1)  (1,2)  (1,3)  (1,4)

(2,1)  (2,2)  (2,3)  (2,4)

(3,1)  (3,2)  (3,3)  (3,4)

頂点 $(k,v)$ は、グループ $S,T$ のそれぞれに分類されたとき、以下を意味するものとする。

$S$ に分類されたとき、頂点 $1$ から $v$ までの最短距離は $k$ 未満
$T$ に分類されたとき、頂点 $1$ から $v$ までの最短距離は $k$ 以上

縦に並ぶ頂点間には、以下のように辺を張る。

$k=1,2,...,d-1$ について、$(k,v)→(k+1,v)$ の辺は、
- $(k,v)$ が $S$、$(k+1,v)$ が $T$ に分類された場合、頂点 $v$ の最短距離が「$k$ 未満」かつ「$k+1$ 以上」ということになってしまう。
- あり得ないため、カットを禁じるように $\infty$ の辺を張る。
- 言い換えれば、$(1,v),(2,v),...,(d,v)$ の分類は必ず $T,...,T,S,...S$ となるようにする。$S$ または $T$ の連続数が0のこともある。
  - 問題に答える上では特に個別に求める必要は無いが、最後に $T$ に分類された頂点を $(k,v)$ とすると、$k$ が「最小カットに従ってコストを1にする辺を設定した状態における頂点 $v$ の最短距離」となる

また元のグラフに存在した辺を $u→v$ として、

$(k,u)→(k,v)$
- これが $S→T$ となる場合、$u$ が $k$ 未満かつ $v$ が $k$ 以上となることを表す。$u→v$ にコスト1の辺を張る。
$(k,u)→(k+1,v)$
- これが $S→T$ となる場合、$u$ が $k$ 未満かつ $v$ が $k+1$ 以上となるが、1本の辺によって直接結ばれた頂点間の距離が2以上異なることはあり得ない。$\infty$ の辺を張る。

これで $(1,1)$ から $(d,N)$ まで流せば、最小カットが「最短距離を $d$ にするときの必要な本数」となる。

Python3

from collections import deque, Counter
from typing import Tuple, List


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 self.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 self.links[v]:
                if orig == 1 and reachable[u] == 0:
                    edges.append((v, u))
        return edges

    def cut_edges_rev(self, t: int) -> List[Tuple[int, int]]:
        q = [t]
        reachable = [0] * self.n
        reachable[t] = 1
        while q:
            u = q.pop()
            for cap, v, li, _ in self.links[u]:
                if cap == 0 or reachable[v]:
                    continue
                reachable[v] = 1
                q.append(v)
        edges = []
        for v in range(self.n):
            if reachable[v] == 0:
                continue
            for cap, u, li, orig in self.links[v]:
                if orig == 0 and reachable[u] == 0:
                    edges.append((u, v))
        return edges


def solve(n, m, k, edges):
    edges = [(u - 1, v - 1, c) for (u, v), c in Counter(edges).items()]
    INF = 1 << 50

    def check(d):
        dnc = Dinic(n * d)
        for l in range(d - 1):
            for v in range(n):
                dnc.add_link(v + l * n, v + (l + 1) * n, INF)
            for u, v, c in edges:
                dnc.add_link(u + l * n, v + l * n, c)
                dnc.add_link(u + l * n, v + (l + 1) * n, INF)
        for u, v, c in edges:
            dnc.add_link(u + (d - 1) * n, v + (d - 1) * n, c)
        f = dnc.max_flow(0, n * d - 1)

        return f <= k

    l = 0
    r = n
    while l + 1 < r:
        mid = (l + r) // 2
        if check(mid):
            l = mid
        else:
            r = mid
    return l


n, m, k = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, k, edges)
print(ans)

目次

オムロンプログラミングコンテスト2025（AtCoder Beginner Contest 397）E,F,G問題メモ

E - Path Decomposition of a Tree

問題文

制約

解法

F - Variety Split Hard

問題文

制約

解法

G - Maximize Distance

問題文

制約

誤った解法

解法