【ABC350】緑コーダーの競プロ参加記録 #14
今回は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時頃): 記事投稿。