A - Past ABCs
リンク:A - Past ABCs (atcoder.jp)
概要:文字列の後ろ3文字が数字であり、この数字が001~315、317~349の範囲であるか判定してね
文字列は6文字与えられますが頭から3文字は"ABC"であること、後ろ3文字は数字の羅列であることが保証されています。
後ろ3文字を数字として扱って上記の条件を満たすか判定すればOKです。
(S=ABC000の可能性を忘れて1WA叩いたのは自分だけでいい・・・)
#ABC350 B - Dentist Aoki
from collections import Counter
N, Q = map(int, input().split())
T = list(map(int, input().split()))
num = Counter(T)
ans = N
for key in num:
if num[key] % 2 == 1:
ans -= 1
print(ans)
提出リンク:提出 #52558777 - AtCoder Beginner Contest 350(Promotion of AtCoderJobs)
B - Dentist Aoki
リンク:B - Dentist Aoki (atcoder.jp)
概要:青木くんの奇行シリーズ。こんな歯医者にかかりたくない。
同じ歯に対して何回治療行為が行われたかを判定して、回数が偶数なら歯が生えている状態、奇数なら歯が抜かれた状態となります。
なので度数分布を取って各歯の治療回数を2で割った余りを見て歯の増減を計算していきます。
#ABC350 B - Dentist Aoki
from collections import Counter
N, Q = map(int, input().split())
T = list(map(int, input().split()))
num = Counter(T)
ans = N
for key in num:
if num[key] % 2 == 1:
ans -= 1
print(ans)
提出リンク:提出 #52558777 - AtCoder Beginner Contest 350(Promotion of AtCoderJobs)
C - Sort
概要:配列に対して2つの要素を選んで位置を交換することで小さい順に並べ替えたいです。必要な操作を出力してね
操作は最小回数である必要は無いので、1を1番目に、2を2番目に、・・・という方針で解きました。
並び変える数字がどこにあるかをindex()で探すと毎回の計算量になりTLEします。
で探したいので連想配列を使いました。
方針は間違っていないのですが大バグりしてしまい終了3分前になんとかACできました。
(連想配列の一方のみを並べ替えてはそのまま使っており、並び替えたはずが実際には変わっていないので変なことになっていた
提出 #52606088 - AtCoder Beginner Contest 350(Promotion of AtCoderJobs))
数字の並びと位置を記録した配列の両方をしっかりスワップしていきましょう。
Pythonにはswap関数は用意されていないので、
a, b = b, a
のようにして位置を交換します。
#ABC350 C - Sort
from collections import defaultdict
N = int(input())
A = [0] + list(map(int, input().split()))
pos = [0] * (N+1)
for i in range(N+1):
pos[A[i]] = i
ans = []
for i in range(1, N+1):
if A[i] != i:
ans.append((i, pos[i]))
tmp = A[i]
A[i], A[pos[i]] = A[pos[i]], A[i]
pos[i], pos[tmp] = pos[tmp], pos[i]
n = len(ans)
print(n)
for a, b in ans:
print(a, b)
提出リンク:提出 #52639001 - AtCoder Beginner Contest 350(Promotion of AtCoderJobs)
D - New Friends
リンク:D - New Friends (atcoder.jp)
概要:XとYは友達、YとZは友達のときにXとZを友達とする操作を行える最大数を出力してね
友達の友達の友達の・・・を辿れるだけ辿ってグループとします。
グループの人数が人ならば交友関係の数はなので、これから元々あった交友関係の数を引けば答えとなります。
無向グラフを作成してBFSでグループの人数を把握し、上記の計算で答えを出します。
計算量はだと思います。
#ABC350 D - New Friends
from collections import deque
N, M = map(int, input().split())
G = [[] for i in range(N+1)]
for _ in range(M):
a, b = map(int, input().split())
G[a].append(b)
G[b].append(a)
visited = [True] + [False for i in range(N)]
def bfs(G, start):
q = deque()
q.append(start)
group = []
group.append(start)
visited[start] = True
while q:
pos = q.popleft()
for i in G[pos]:
if visited[i]:
continue
else:
q.append(i)
group.append(i)
visited[i] = True
return len(group)
ans = 0 - M
for i in range(1, N+1):
if visited[i] == True:
continue
else:
n = bfs(G, i)
ans += (n*(n-1)) // 2
print(ans)
提出リンク:提出 #52661681 - AtCoder Beginner Contest 350(Promotion of AtCoderJobs)
グループの人数を知りたいのでUnionFindでも同じことができます。
(他の方々の提出を見るとUnionFindを使う人のほうが多そうでした)
UnionFind部分は誰かの提出を元にしているので内容や計算量あんまりわかってないです。
#ABC350 D - New Friends
class UnionFind():
"""
集合を木と捉え、各要素にその根を持たせる
Union : 2つの木を合併する
Find : 要素の根を返す
"""
def __init__(self, n) -> None:
"""
parameter
n : 要素数
"""
self.n = n
self.parents = [-1]*n
self.rank = [0]*n
def find(self, x):
"""
xの根を返す
"""
if self.parents[x]==-1:
return x
else:
# 値を更新しながら根を探す
# 深さは最大でlog(n)なので、再帰関数でok
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def union(self, x, y):
"""
xを含む木とyを含む木を合併する
"""
x = self.find(x)
y = self.find(y)
if x==y:
return
if self.rank[x] > self.rank[y]:
x, y = y, x
self.parents[x] = y
if self.rank[x] == self.rank[y]:
self.rank[y] += 1
N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
a, b = map(int, input().split())
a -= 1
b -= 1
uf.union(a, b)
size = [0]*N
for i in range(N):
size[uf.find(i)] += 1
ans = 0 - M
for i in size:
ans += (i * (i-1)) // 2
print(ans)
提出リンク:提出 #52622719 - AtCoder Beginner Contest 350(Promotion of AtCoderJobs)
結果
C問題で大いに躓きました。
A~Cの3完117分(WA×4含)でした
初めてのレート降下。
C問題でもたついてなければD問題まで4完できていたかもしれない・・・