【ABC352】緑コーダーの競プロ参加記録 #16

igasu_7

2024年5月5日 14:48

今回はAtCoder Beginner Contest 352。使用言語はPythonです。

A問題 - AtCoder Line

コンテスト中の提出
https://atcoder.jp/contests/abc352/submissions/53081699

$${N}$$個の駅がある。
$${1}$$から$${N}$$の順番に停まる電車と、その逆向きの電車がある。
駅$${X}$$から駅$${Y}$$まで移動する間に駅$${Z}$$を通るか判定してね。

$${X}$$と$${Y}$$の間に$${Z}$$があるかどうかを素直に判定してよいです。

入力の時点では$${X < Y}$$ではない可能性があることに注意が必要です。

""" ACコード """
N, X, Y, Z = map(int, input().split())
if X < Z < Y or Y < Z < X:
    print('Yes')
else:
    print('No')

なお、入力の時点で$${X > Y}$$である場合に$${X < Y}$$となるように値を入れ替えておくと、判定が少しだけスッキリします。

""" X < Y になるようにswap """
N, X, Y, Z = map(int, input().split())
if X > Y:
    X, Y = Y, X
if X < Z < Y:
    print('Yes')
else:
    print('No')

B問題 - Typing

コンテスト中の提出
https://atcoder.jp/contests/abc352/submissions/53090981

文字列$${S, T}$$が与えられる。
$${S}$$の$${i}$$文字目が$${T}$$の何文字目にあるかすべて出力してね。

問題文がややこしいですが、題意はだいたい上記の通りです。

$${S}$$の先頭から1文字ずつ、$${T}$$の中での位置を特定していきます。

""" ACコード """
S = input()
T = input()
ans = []
i = 0
for s in S:
    while i < len(T) and T[i] != s:
        i += 1
    ans.append(i + 1)
    i += 1
print(*ans)

C問題 - Standing On The Shoulders

コンテスト中の提出
https://atcoder.jp/contests/abc352/submissions/53102523

$${N}$$人の巨人がいる。
$${i}$$番目の巨人は、肩の高さが$${A_i}$$、頭の高さが$${B_i}$$。
巨人を「肩の上に立つ」形式で積み重ねていく。
全長の最大値を出力してね。

「肩の上に立つ」ので、首を外して考えるとどのように積み上げても全長は同じになります。

全長に差が生まれるのは、一番上の巨人の頭の大きさが要因です。

よって、一番上に最も顔が大きい巨人を選べばよいです。
顔の大きさは$${B_i - A_i}$$です。

""" AC コード """
N = int(input())
max_head = 0
ans = 0
for _ in range(N):
    A, B = map(int, input().split())
    max_head = max(max_head, B - A)
    ans += A
ans += max_head
print(ans)

D問題 - Permutation Subsequence

コンテスト中の提出
https://atcoder.jp/contests/abc352/submissions/53119938

順列$${P}$$が与えられる。
連続する$${K}$$個の整数のインデックスの集合について、昇順に並べたものを$${i_1, i_2, …, i_K}$$とする。
$${i_K - i_1}$$の最小値を出力してね。

これも問題文がややこしいです。

連続する$${K}$$個の整数について、$${P}$$の中で一番左にある整数と一番右にある整数のインデックスの差を計算することを求められています。

整数$${a}$$から始まる連続$${K}$$個の整数の集合を$${S_a}$$とします。

$${S_a}$$から$${S_{a + 1}}$$に遷移するのは、$${S_a}$$から$${a}$$を除いて$${a + K}$$を追加すればよいです。

これを整数$${a}$$の$${P}$$におけるインデックスについて考えます。
$${P}$$における$${a}$$の位置を$${Q_a}$$とします。

""" 整数 a の位置 i を調べる """
N, K = map(int, input().split())
P = list(map(int, input().split()))
Q = [0] * (N + 1)
for i, a in enumerate(P):
    Q[a] = i

今回の問題で必要なのは、最大値と最小値のみです。

要素を追加したり削除したりしつつ最小値がほしいときに使えるデータ構造として優先度付きキューがあります。
要素の符号を反転すると最大値にも対応できます。

よって、最小値用と最大値用の2つの優先度付きキューを用意します。
まず$${S_1}$$について答えを求めてみます。

""" [1, 2, 3, ... , K] についてインデックスの最小・最大を調べる """
from heapq import *
hq_min = []
hq_max = []
for a in range(1, K + 1):
    heappush(hq_min, Q[a])
    heappush(hq_max, -Q[a])
ans = -hq_max[0] - hq_min[0]

この後は、$${Q_a}$$を削除して$${Q_{a + K}}$$を追加しながら処理を繰り返します。
このとき、$${Q_a}$$が現在のキューの最小値である場合のみ削除処理をすればよく、キューに含まれる最小値を$${i}$$として$${P_i <= a}$$を判定すればよいです。（最大値についても同様です。）

""" キューを更新をしながら処理を進めていく """
for a in range(1, N - K + 1):
    heappush(hq_min, Q[a + K])
    heappush(hq_max, -Q[a + K])
    while P[hq_min[0]] <= a:
        heappop(hq_min)
    while P[-hq_max[0]] <= a:
        heappop(hq_max)
    ans = min(ans, -hq_max[0] - hq_min[0])
print(ans)

公式解説にあるとおり、c++ であれば std::set を使用するのが想定解です。

しかし、Pythonにはそのようなデータ構造が標準で搭載されていません。
代わりになる外部ライブラリとして、SortedList というものがあります。

以前、ちょっとした記事を書いているのでよかったら読んでみてください。

なお、SortedList を使わずセグ木で解くこともできます。
私の提出コードはセグ木を使いました。

E問題 - Clique Connect

コンテスト中の提出
https://atcoder.jp/contests/abc352/submissions/53134192

$${N}$$頂点に対して、$${M}$$回の操作をする。
操作: ある$${K_i}$$個の頂点集合$${S_i}$$について、すべての2頂点の間にコスト$${C_i}$$の辺を追加する。
最終的なグラフが連結かどうか判定して、最小全域木のコストを出力してね。

「連結かどうかを判定しろ」と言われているのでUnionFindを用意します。

""" UnionFind """
class UnionFind:
    def __init__(self, n):
        self.par = [-1] * (n + 1)
    def root(self, x):
        if self.par[x] < 0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
    def size(self, x):
        return -self.par[self.root(x)]
    def same(self, x, y):
        return self.root(x) == self.root(y)

今回はよくある「辺$${i}$$は頂点$${U_i, V_i}$$を結ぶ」のような入力形式ではありません。
$${K_i}$$個の頂点に対して$${_{K_i}C_2}$$本の辺を張ることを要求されており、素直に辺を張ろうとすると$${O(10^{10})}$$になってしまいます。

実際のグラフの形や最小全域木はさておき、まず連結かどうかだけ考えてみます。
$${i}$$番目の操作で与えられる$${K_i}$$個の頂点からなるグラフを$${g_i}$$とします。

単に$${g_i}$$を連結なグラフとして構築したいとき、$${K_i}$$個の頂点を順番につなげていけばよいです。
具体的には、頂点$${A_{i, 1}}$$に対して$${K_i - 1}$$個の頂点を連結させます。

本来は$${g_i}$$に含まれるどの2頂点の間にも辺が存在するので、ここでどのように辺を張っても元のグラフ$${G}$$に存在しない辺が発生することはありません。

また、$${g_i}$$以外の頂点と連結させるときに$${g_i}$$のどの頂点を選んだとしても連結性は変わりません。

このことから、$${i \not = j}$$である$${g_i, g_j}$$について、$${g_i}$$に含まれる頂点が1つでも$${g_j}$$に含まれていれば、$${g_i, g_j}$$からなるグラフは連結となります。

よって、上図の連結方法を繰り返していれば本来のグラフ$${G}$$の連結性と同じグラフを構築できます。

最終的に$${G}$$が連結なグラフでなければ答えは -1 です。
判定には、頂点$${1}$$が含まれる連結成分のサイズが$${N}$$であるかをチェックします。

そして実は、$${G}$$が連結なグラフである場合、この連結方法を辺のコストが小さい順に行うことで最小全域木になります。これをクラスカル法といいます。

""" 入力を受け取る """
N, M = map(int, input().split())
K, C, A = [], [], []
for i in range(M):
    k, c = map(int, input().split())
    a = list(map(int, input().split()))
    K.append(k)
    C.append((c, i))
    A.append(a)

""" コストの小さい順に連結していく (クラスカル法) """
uf = UnionFind(N)
ans = 0
for c, i in sorted(C):
    k, a = K[i], A[i]
    for j in range(1, k):
        if uf.same(a[0], a[j]):
            continue
        uf.union(a[0], a[j])
        ans += c

""" 連結かどうかチェック """
if uf.size(1) == N:
    print(ans)
else:
    print(-1)

あとがき

今回はABCDE 5完 86分で 2307位、1168 perf でした。

ではまた～。

【更新履歴】
2024/05/05 (14時頃)：記事投稿。

この記事が気に入ったらサポートをしてみませんか？