−目次

鹿島建設プログラミングコンテスト2025（AtCoder Beginner Contest 394）E,F,G問題メモ

鹿島建設プログラミングコンテスト2025（AtCoder Beginner Contest 394）E,F,G問題メモ

鹿島建設プログラミングコンテスト2025（AtCoder Beginner Contest 394）

開催日がにゃんにゃんにゃん(02/22)

E - Palindromic Shortest Path

問題文

$N$ 頂点の有向グラフがあります。
- 頂点には $1, 2, \ldots, N$ の番号が付いています。
- 辺の情報は $N^2$ 個の文字 $C_{1, 1}, C_{1, 2}, \ldots, C_{1, N}, C_{2, 1}, \ldots, C_{N, N}$ によって与えられます。ここで、 $C_{i, j}$ は英小文字あるいは - です。
- $C_{i, j}$ が英小文字のとき頂点 $i$ から頂点 $j$ へ向かう辺がちょうど $1$ つ存在してラベル $C_{i, j}$ が付いており、 $C_{i, j}$ が - のとき頂点 $i$ から頂点 $j$ へ向かう辺は存在しません。
$1 \leq i, j \leq N$ を満たす各整数組 $(i, j)$ について、以下の問題に対する答えを求めてください。
- 頂点 $i$ から頂点 $j$ に向かう（単純とは限らない）パスのうち、辺に付けられたラベルの文字を順に結合した文字列が回文となるようなものの中で最も短いものの長さを求めよ。ただし、そのようなパスがない場合は答えは $-1$ とせよ。

制約

$1 \leq N \leq 100$
$N$ は整数
$C_{i, j}$ は英小文字あるいは -

解法

Froyd-Warshall の亜種で解いたが、計算量的にヤバくなるケースがない確認はできていない。
公式Editorialは頂点と辺を定義しなおしてBFSとして解いていて、そちらは上限が保証される。

4
ab--
--b-
---a
c---

a┌①--b-->②--b-->③--a-->④
 └＾↖________c___________/

回文を、「空文字列、または長さ1の文字列の両端に、同じ文字をくっつけていく」ことで作るのをイメージする。

求めたい行列を $A$ とする。
まず、長さ0か1の回文は、入力から簡単に埋められる。

A  1  2  3  4
1  0  1
2     0  1
3        0  1
4  1        0

後は、同じアルファベットをラベルに持つ辺のペアの集合を $E$ として、

全ての辺のペア $((a,b),(c,d)) \in E$ について以下のように更新する（※「←」はchmax）
- $A_{a,d} \underset{\max}{\leftarrow} A_{b,c}+2$
- $A_{c,b} \underset{\max}{\leftarrow} A_{d,a}+2$

を更新がなくなるまで繰り返せばよい。

どれくらい繰り返せばよいか、最長ケースを考えると、

a┌○-b->○-a->○-a->○-a->...-a->○
 └＾

のようなとき、約 $2N$ の長さ（約 $N$ 回の更新）が必要となるケースがある。
おそらくこれが最大と思うので、 $N$ 回繰り返せば十分となる。

ただし、一律に全てのケースで $N$ 回繰り返すとTLEしてしまった。
「ほぼ全ての頂点間に同じラベルが付いている」ケースだと、 $|E|$ が $O(N^4)$ となり、全体が $O(N^5)$ となる。
ただこの場合は早々に更新が発生しなくなるので、更新の有無を確認して打ち切ることで間に合う。

Python3

F - Alkane

問題文

$N$ 頂点の無向木 $T$ が与えられます。頂点には $1, 2, \ldots, N$ の番号が付いており、 $i$ 番目の辺は頂点 $A_i$ と頂点 $B_i$ を結ぶ無向辺です。
グラフがアルカンであるとは以下の条件をともに満たしていることであると定義します。
- グラフは無向木である
- すべての頂点の次数が $1$ または $4$ であり、次数 $4$ の頂点が $1$ つ以上存在する

$T$ の部分グラフであってアルカンであるものが存在するか判定し、存在する場合はそのようなものの頂点数の最大値を求めてください。

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i, B_i \leq N$
与えられるグラフは無向木
入力される値はすべて整数

解法

次数4以上の頂点が1つも無い場合、答えは存在しない（ $-1$ ）。以下、1つはあるとする。

アルカンでは「次数4の頂点同士が互いに繋がり、余っている手を次数1の頂点が埋めている」感じとなる。
頂点数は、次数4の頂点の個数を $k$ とし、 $3k+2$ となる。この式は以下のように考えると導ける。

$k=1$ の時、アルカンの頂点数は5
そこから増やすには「次数1の頂点のどれかを、次数4+周囲の次数1の頂点3つと置き換える」ことでのみ可能

よって、 $T$ から取れる最大の $k$ （＝次数4の頂点同士を繋げられる最大数）を求めればよい。

単純に「UnionFindで次数4以上の頂点を繋げ、最大サイズを見る」などの解法では以下のようなケースで上手くいかない。

④  ④  ④
  ＼｜／      ④:次数4以上の頂点（そこにくっつく次数1の頂点は省略）
④--④--④
  ／｜＼      1つの頂点に次数4以上の頂点が
④  ④  ④    5個以上くっついていても、使えるのは4個まで

木DPをする。

$\mathrm{DP}[v]:=$
- $v$ の次数が $4$ 未満の場合、 $0$
- $v$ の次数が $4$ 以上の場合、以下の条件を満たす $v$ の部分木の、次数4の頂点の最大個数
  - $v$ を含み、 $v$ の次数は $4$ 。
  - 全ての頂点の次数が1か4であり、互いに繋がっている。
    - ただし、 $v$ 自身のみ子の数は3個（未探索の親が1つあるので）

     ｜
     ④←v
  ／/｜\＼     ❹: 次数4以上だが、
 ④④④❹❹        個数オーバーによりDP[v]には寄与できない頂点
  /|\＼
 ④④④❹

次数4以上の $v$ の探索時、暫定の答え $k$ と $\mathrm{DP}[v]$ を更新していく。 $k$ は初期値 $0$ とする。

$v$ を含む部分木で完結する（親は使わない）
- $v$ が子を4つ以上持つ場合のみ可能。
- $k \underset{\max}{\leftarrow}$ 「 $v$ の各子の $\mathrm{DP}[c]$ のうち、上位4つの和+1」で更新
$v$ を含む部分木で完結する（親を次数1の頂点として使う）
- 根以外の頂点で可能
- $k \underset{\max}{\leftarrow}$ 「 $v$ の各子の $\mathrm{DP}[c]$ のうち、上位3つの和+1」で更新
$v$ を親に繋げる
- $\mathrm{DP}[v]=$ 「 $v$ の各子の $\mathrm{DP}[c]$ のうち、上位3つの和+1」とする

これで、最後まで木DPをおこなうと $k$ が求めたいものとなっている。

Python3

G - Dense Buildings

問題文

東西南北方向に $H\times W$ 個の区画に区切られた街があり、各区画にはちょうど $1$ つのビルが立っています。
- 具体的には北から $i$ 番目 $(1\leq i\leq H)$ かつ西から $j$ 番目 $(1\leq j\leq W)$ の区画（以下、区画 $(i,j)$ とよぶ）には $F_{i,j}$ 階建てのビルがあります。
高橋君には $2$ 種類の移動方法があり、区画 $(i,j)$ のビルの $X$ 階 $(1\leq X\leq F_{i,j})$ にいるとき、そこから次のような移動が可能です。
- 同じビルの中の $1$ つ上の階または $1$ つ下の階へ階段を使って移動する。ただし、 $1$ 階から $1$ つ下の階への移動および、 $F_{i,j}$ 階から $1$ つ上の階への移動はできない。
- 東西南北に隣接する区画にあるビルのうち、 $X$ 階建て以上であるものを $1$ つを選び、そのビルの $X$ 階へ（上空）通路を使って移動する。

$Q$ 個の質問が与えられるので、それぞれの質問に答えてください。 $i$ 個目 $(1\leq i\leq Q)$ の質問は次のようなものです。
- 区画 $(A_i,B_i)$ にあるビルの $Y_i$ 階から、区画 $(C_i,D_i)$ にあるビルの $Z_i$ 階へ高橋君が移動する時に、階段を使う回数としてあり得る最小の値を求めよ。
- ここで、階段を使う回数は $1$ つ上の階または $1$ つ下の階へ移動するたびにカウントされ、同じビルの中でも重複してカウントされるものとする。
  - 例えば、あるビルを $1$ 階から $6$ 階まで移動したとき、 $5$ 回階段を使用したと数える。
- また、通路の使用回数を最小とする必要はないことに注意せよ。

制約

$1\leq H \leq 500$
$1\leq W \leq 500$
$1\leq F_{i,j} \leq 10^6$
$1\leq Q\leq 2\times 10^5$
$1\leq A_i,C_i\leq H$
$1\leq B_i,D_i\leq W$
$1\leq Y_i\leq F_{A_i,B_i}$
$1\leq Z_i\leq F_{C_i,D_i}$
$(A_i,B_i,Y_i)\neq (C_i,D_i,Z_i)$
入力はすべて整数
実行制限時間 5秒

解法

クエリ $k$ には、以下の問題が解ければ答えられる。

$(A_k,B_k)$ から $(C_k,D_k)$ まで、なるべく大きい $F_{i,j}$ を辿ってビル間を移動した時、通る $F_{i,j}$ の最小値はいくつ？

この問題に対する答えを $x$ として、元の問題の答えは以下になる。

そもそも $(A_k,B_k)=(C_k,D_k)$ なら $|Y_k-Z_k|$
それ以外で $\min(Y_k,Z_k) \le x$ なら、 $|Y_k-Z_k|$
それ以外なら、 $Y_k+Z_k-2x$

各クエリに対し、言い換えた問題の答えをどのように求めるかとなる。

部分永続UnionFindを使った。通常のUnionFindから、以下の点が異なる。

unite(x,y) をした時、内部時間 $t$ が1進む。
is_same(x,y,t) は、「時刻 $t$ で、 $x,y$ が連結だったか」を調べる。
- ※各操作のコストはいずれも $O(\log{N})$

Union-Find木
やぶについて書きます（camypaper氏の解説スライド）

各 $(i,j)$ を頂点、隣接頂点の関係を辺、辺のコストを $\min(F_{i,j},F_{i,j+1})$ （横に隣接する場合）、 $\min(F_{i,j},F_{i+1,j})$ （縦に隣接する場合）とする。

辺を全て列挙し、コストの高い順から部分永続UnionFindで結合していく。

各クエリでは、 $(A_k,B_k)$ と $(C_k,D_k)$ が初めて連結になった時刻 $t$ を二分探索で求める。
そのときに最後に結合した辺のコストが、クエリに対する答えとなる。

計算量は $O(N\log{N}+Q (\log{N})^2)$ となる。

Python3

        
          
          
              
              from bisect import bisect
 
 
class PartialPersistentUnionFind:
    """
    時刻 t は、「t番目のuniteクエリ完了時点」を意味する。初期状態は t=0。
 
    root(x [, t]): 時刻 t の x の根（t 省略時は最新）
    find(x, y [, t]): 時刻 t に x と y が同一グループか判定
    unite(x, y): x と y を結合
    get_size(x [, t]): 時刻 t の x の属するグループの要素数
    """
 
    def __init__(self, n: int):
        self.t = 0
        self.timetable = [[0] for _ in range(n)]
        self.valuetable = [[-1] for _ in range(n)]
 
    def _getvalue(self, x: int, t: int):
        i = bisect(self.timetable[x], t) - 1
        return self.valuetable[x][i]
 
    def root(self, x: int, t: int = -1):
        # 更新が行われるのは、その時点の根に対してだけなので、
        # x の最終更新時刻 > t なら、t 時点では確実に x は根。
        # そうでない場合は最終更新時の値の正負で、通常のUnionFindと同様、根か、親を持っているか判別。
        if t == -1:
            t = self.t
        while self.timetable[x][-1] <= t and self.valuetable[x][-1] >= 0:
            x = self.valuetable[x][-1]
        return x
 
    def is_same(self, x: int, y: int, t: int = -1):
        return self.root(x, t) == self.root(y, t)
 
    def unite(self, x: int, y: int):
        self.t += 1
        r1 = self.root(x, self.t)
        r2 = self.root(y, self.t)
        if r1 == r2:
            return False
        self.timetable[r1].append(self.t)
        self.timetable[r2].append(self.t)
        d1 = self.valuetable[r1][-1]
        d2 = self.valuetable[r2][-1]
        if d1 <= d2:
            self.valuetable[r1].append(d1 + d2)
            self.valuetable[r2].append(r1)
        else:
            self.valuetable[r1].append(r2)
            self.valuetable[r2].append(d1 + d2)
        return True
 
    def get_size(self, x: int, t: int = -1):
        if t == -1:
            t = self.t
        r = self.root(x, t)
        return -self._getvalue(r, t)
 
 
def solve(h, w, field, q, queries):
    edges = []
    for i in range(h):
        for j in range(w):
            if i > 0:
                edges.append((min(field[i - 1][j], field[i][j]), (i - 1) * w + j, i * w + j))
            if j > 0:
                edges.append((min(field[i][j - 1], field[i][j]), i * w + j - 1, i * w + j))
    edges.sort(reverse=True)
    # print(edges)
 
    uft = PartialPersistentUnionFind(h * w)
    for _, u, v in edges:
        uft.unite(u, v)
 
    ans = []
    for a, b, y, c, d, z in queries:
        s = (a - 1) * w + (b - 1)
        g = (c - 1) * w + (d - 1)
        if s == g:
            ans.append(abs(y - z))
            continue
        l = 0
        r = len(edges)
        while l + 1 < r:
            m = (l + r) // 2
            # print(f'{s=} {g=} {l=} {r=} {m=} {uft.is_same(s,g,m)=}')
            if uft.is_same(s, g, m):
                r = m
            else:
                l = m
 
        min_f = edges[l][0]
        if min(y, z) <= min_f:
            ans.append(abs(y - z))
        else:
            ans.append(y + z - min_f * 2)
 
    return ans
 
 
h, w = map(int, input().split())
field = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
queries = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(h, w, field, q, queries)
print('\n'.join(map(str, ans)))

            

        
      

その他の解法

いろいろある。

並列二分探索

競技プログラミングをするフレンズ氏のTwitter上の解説

マージ過程を表す木 + LCA

マージ過程を表す木
- $H \times W$ の各マスを葉頂点とする。
- コストの大きい隣接マスからマージしていく。実際にマージされるたびに新たな頂点を作り、マージされた2頂点をその子とする。

この木上でLCAを求めると、2つのマスがマージされたタイミングとそのコストが分かる。

マージテク

Union-Findの各リーダーに「自身の連結成分の中に、始点または終点が属しているクエリ番号」の集合を持たせる。
つまり、初期状態では各頂点にSetを持たせ、 $(A_q,B_q),(C_q,D_q)$ の2頂点にそれぞれ $q$ を登録しておく。

コストの大きい隣接マスからUnion-Findで繋いでいくにあたり、クエリ番号の集合もマージテクで統合していく。

その際、統合しようとする双方の集合に共通して含まれる要素 $q$ があったら、クエリ $q$ の2頂点は、今繋ごうとしている辺で初めて連結になることが分かる。