【ABC350】緑コーダーの競プロ参加記録 #14

igasu_7

2024年4月21日 01:01

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

A問題 - Past ABCs

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

長さ$${6}$$の文字列$${S}$$が与えられる。
$${S}$$が過去に開催されたコンテストの略称かどうか判定してね。

文字列$${S}$$は前半3文字が 'ABC' で、後ろ3文字が数字です。

過去のコンテストとは、ABC の後ろの数字が「'001' から '349' のうち '316' を除いたもの」とのことなので、これを判定します。

数字なので int に変換してよいです。

""" AC コード """
S = input()
T = int(S[3:])
if T < 1 or T == 316 or T > 349:
    print('No')
else:
    print('Yes')

B問題 - Dentist Aoki

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

$${N}$$本の歯が生えている。
$${Q}$$回の治療のうち、$${i}$$回目は歯$${T_i}$$を治療した。
治療 1: 歯$${T_i}$$があれば抜く。
治療 2: 歯$${T_i}$$がなければ生やす。
最終的な歯の本数を出力してね。

おそろしい問題設定。

$${N, Q \leq 1000}$$なので、$${k}$$番目の歯が生えているかどうかを True / False で管理して素直にシミュレーションできます。
そして最終的に True の数をカウントすればよいです。

""" True / False でシミュレーション """
N, Q = map(int, input().split())
T = list(map(int, input().split()))
res = [True] * N
for t in T:
    res[t - 1] = not res[t - 1]
ans = res.count(True)
print(ans)

True / False を 1/ 0 で管理することもできます。
その場合、$${X}$$を反転する処理には$${X \mathrm{xor} 1}$$や$${1 - X}$$といった方法もあります。

""" 1 / 0 と XOR でシミュレーション """
N, Q = map(int, input().split())
T = list(map(int, input().split()))
res = [1] * N
for t in T:
    res[t - 1] ^= 1
ans = sum(res)
print(ans)

C問題 - Sort

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

長さ$${N}$$の数列$${A}$$が与えられる。
$${A}$$をソートするための$${0}$$回以上$${N-1}$$回以下の操作を出力してね。
操作 1: $${(i, j)}$$を選んで$${A_i, A_j}$$を入れ替える。

操作は$${N-1}$$回行ってよいです。
つまり、効率は関係なく$${1}$$から順に位置を決めていってよいということです。

そのためには数$${k}$$の位置を$${O(1)}$$で求められるようにしておきたいです。
数$${k}$$の位置を$${P_k}$$とします。

""" 数 k の位置を前計算する """
N = int(input())
A = list(map(int, input().split()))
P = [0] * (N + 1)
for i, k in enumerate(A):
    P[k] = i

$${i = 1, 2, …, N}$$の順に、$${A_i = i}$$でなければ、$${A_i}$$と$${A_{P_i}}$$を入れ替えます。
このとき、$${A}$$だけでなく$${P}$$も更新することに注意してください。

""" 1 から順に swap していく """
ans = []
for i in range(N):
    if A[i] == i + 1:
        continue
    j = P[i + 1]
    P[A[i]], P[A[j]] = P[A[j]], P[A[i]]
    A[i], A[j] = A[j], A[i]
    ans.append((i + 1, j + 1))
print(len(ans))
for res in ans:
    print(*res)

D問題 - New Friends

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

$${N}$$人のユーザーがSNSに登録している。
ユーザー$${A_i}$$と$${B_i}$$は友達。
操作 :「$${X}$$と$${Y}$$が友達かつ $${Y}$$と$${Z}$$が友達」である場合、「$${X}$$と$${Z}$$を友達にする」
操作を最大で何回行えるか出力してね。

いったん図で整理します。

図で描いてみると、グラフっぽいですね。

グラフ問題として捉えたとき、操作は「グラフ上の任意の 2 頂点$${(x, y)}$$の間に辺を張る」ということになります。

頂点数$${v}$$のグラフでは 2 頂点の選び方は$${_vC_2}$$通りあります。
すでに辺が張られているような 2 頂点は選べないため、辺の数を$${e}$$とすると、新たに張ることのできる辺の数は$${_vC_2 - e}$$本です。

ここで、「グラフ」は連結であるものに限ります。
連結成分ごとに頂点の数、辺の数をカウントするためにUnionFindを使います。

""" 辺の数もカウントする UnionFind """
class UnionFind:
    def __init__(self, n):
        self.par = [-1] * (n + 1)
        self.edge = [0] * (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)
        self.edge[x] += 1
        if x == y:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        self.edge[x] += self.edge[y]
        self.edge[y] = 0
        self.par[x] += self.par[y]
        self.par[y] = x

上記のような実装の場合、連結成分の頂点の数は根$${i}$$に対して$${-par[i]}$$となります。辺の数は$${edge[i]}$$です。

頂点$${i}$$が根であることは$${par[i] < 0}$$であることと同じです。

""" AC コード """
N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
    a, b = map(int, input().split())
    uf.union(a, b)
ans = 0
for i in range(1, N + 1):
    if uf.par[i] < 0:
        v = -uf.par[i]
        e = uf.edge[i]
        ans += v * (v - 1) // 2 - e
print(ans)

辺の数$${e}$$の合計は$${M}$$なので、後でまとめて引いてもよいです。そうすると辺の数をカウントする必要もないですね。
(私は本番で気づきませんでした。)

E問題 - Toward 0

upsolve
https://atcoder.jp/contests/abc350/submissions/52625885

こんな感じで小さい数から期待値を求めていけばよさそうで、メモ化再帰の出番です。

""" upsolve """
from sys import setrecursionlimit
from collections import defaultdict
setrecursionlimit(100100100)

def dfs(n):
    if E[n] != -1:
        return E[n]
    res = 0
    for i in range(2, 7):
        res += dfs(n // i)
    E[n] = min(X + E[n // A], (res + 6 * Y) / 5)
    return E[n]

N, A, X, Y = map(int, input().split())
E = defaultdict(lambda: -1)
E[0] = 0
ans = dfs(N)
print(ans)

$${X, Y}$$の式への組み込み型が間違っていて解けませんでした。残念。
期待値の考え方がよく分かってないです。

あとがき

今回はABCD 4完 45分 (2ペナ) で 2417位、1149 perf でした。

コンスタントに水 perf 出すのって大変だよなぁと、改めて水コーダーの方々のすごさを感じている今日この頃です。

ではまた～。

【更新履歴】
2024/04/21 (1時頃): 記事投稿。

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