はじめに
ユーザ名 hidehico
コンテスト名 日本レジストリサービス（JPRS）プログラミングコンテスト2025#1（AtCoder Beginner Contest 392）
順位 2027th / 12461 (top 1.68%)
パフォーマンス 1253
レーティング 901 → 943 (+42) Highest更新！
段級位 6 級
やったー水パフォ、勝ったぜ
結果は、ABCDE 5完2ペナでした
コンテスト中の流れ
開始3秒
acc newを実行する
開始57秒
脳死で、Aをpermutationsで通す
開始2分
なんか見た事あるなーと思いつつも、Bを通す
開始5分
Cを通す
問題文が難しかった
開始29分
Dで2ペナ食らう
開始33分
嘘解法っぽいなーと思いつつも、Dを通す
開始67分
実装が面倒臭かったものの、Eを通す
流石に、Fは通せなそうだったし、流石に水パフォ出るだろと思い、離脱
みたいな感じでした
使っているライブラリ
前回からの、変更点は、BIT(なんかFの解法、BITだったような)とDPのライブラリを追加したぐらいです
そんじゃ、一問ずつ感想書きますか
A問題
n=3と分った瞬間、脳死でpermutationsを使って通した
ACコード(ライブラリ抜粋)
YE関数は、Trueだったら、Yesを出力してexitです
A = il()
for p in permutations(A):
YE(p[0] * p[1] == p[2])
print("No")
B問題
setで通したけど、listでもokっぽい
ACコード(ライブラリ抜粋)
N, M = il()
A = il()
L = set(range(1, N + 1))
for a in A:
L.remove(a)
print(len(L))
print(*L)
C問題
問題文の理解に時間がかかった
普通に求めればいい
ACコード(ライブラリ抜粋)
N = ii()
P = il(-1)
Q = il(-1)
ans = [-1] * N
for i in range(N):
ans[Q[i]] = Q[P[i]] + 1
print(*ans)
D問題
確率はすぐ分っただけど、どうやって高速化するかで時間を潰してしまった
両方に出てくる要素で探索したため、テストケースが弱くて助かったが、もうちょっと強かったらやばかった
ACコード(ライブラリ抜粋)
N = ii()
L = []
T = []
ans = 0
for _ in [0] * N:
A = il()
D = defaultdict(int)
nt = set()
for a in A[1:]:
nt.add(a)
D[a] += 1
for t in D.keys():
D[t] = D[t] / A[0]
L.append(D)
T.append(list(nt))
for i in range(N):
for k in range(i + 1, N):
cur = 0
for t in set(T[i] + T[k]):
cur += L[i][t] * L[k][t]
ans = max(ans, cur)
print(ans)
E問題
まず連結成分をまとめる
そしたら、その連結成分で、余っている辺を探す(unionfindを使って、クラスカル法っぽく)
連結成分の情報には、その連結成分に含まれれる適当な頂点一つ、余っている辺の数、余っている辺の情報
を入れておく
そして、余っている辺が多い連結成分から、操作を行なっていく
そしたらACできた
ACコード(ライブラリ抜粋)
コメント追加しておきました
N, M = il()
G = defaultdict(list)
L = []
for i in range(M):
A, B = il(-1)
G[A].append((B, i))
G[B].append((A, i))
UF = UnionFind(N)
used = [False] * N
for i in range(N):
if used[i]:
continue
T = [i]
Q = deque()
used[i] = True
Q.append(i)
while Q:
cur = Q.popleft()
for nxt, _ind in G[cur]:
if used[nxt]:
continue
used[nxt] = True
T.append(nxt)
Q.append(nxt)
S = set()
ND = [] # 余っている辺の情報
for a in T:
for b, ind in G[a]:
if ind in S: # 同じ辺がもうあるならスキップ
continue
if UF.same(a, b): # 同じ連結成分か
ND.append((b, ind)) # 余っている辺に追加
else:
UF.unite(a, b)
S.add(ind)
L.append((i, len(ND), ND))
L.sort(reverse=True, key=lambda x: x[1]) # 余ってる辺が多い順にソート
ans = []
Q = deque()
Q.append(L[0])
nokori = L[1:] # まだ連結されていない、連結成分
while Q and nokori:
cur, cl, cd = Q.popleft()
if cl == 0:
continue
nxt, nl, nd = nokori.pop()
b, ind = cd.pop()
cl -= 1
ans.append((ind + 1, b + 1, nxt + 1))
Q.append((cur, cl, cd))
Q.append((nxt, nl, nd))
print(len(ans))
for l in ans:
print(*l)
最後に
なんか最近、CとかD難しくなった気がします
そして、Eのdiffが、1200前後で推移している感じがします
まあ5完できたので満足です
最後まで見ていただいて、ありがとうございました
:qa!