緑によるABC392振り返り

# はじめに

> ユーザ名	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は通せなそうだったし、流石に水パフォ出るだろと思い、離脱

みたいな感じでした

### 使っているライブラリ

https://github.com/hidehic0/library

前回からの、変更点は、BIT(なんかFの解法、BITだったような)とDPのライブラリを追加したぐらいです


そんじゃ、一問ずつ感想書きますか

# [A問題](https://atcoder.jp/contests/abc392/tasks/abc392_a)
n=3と分った瞬間、脳死でpermutationsを使って通した

ACコード(ライブラリ抜粋)
YE関数は、Trueだったら、Yesを出力してexitです
```py
A = il()

for p in permutations(A):
    YE(p[0] * p[1] == p[2])

print("No")
```

# [B問題](https://atcoder.jp/contests/abc392/tasks/abc392_b)

setで通したけど、listでもokっぽい

ACコード(ライブラリ抜粋)
```py
N, M = il()
A = il()
L = set(range(1, N + 1))

for a in A:
    L.remove(a)

print(len(L))
print(*L)
```

# [C問題](https://atcoder.jp/contests/abc392/submissions/62510036)

問題文の理解に時間がかかった
普通に求めればいい

ACコード(ライブラリ抜粋)
```py
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問題](https://atcoder.jp/contests/abc392/tasks/abc392_d)

確率はすぐ分っただけど、どうやって高速化するかで時間を潰してしまった
両方に出てくる要素で探索したため、テストケースが弱くて助かったが、もうちょっと強かったらやばかった

ACコード(ライブラリ抜粋)
```py
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問題](https://atcoder.jp/contests/abc392/tasks/abc392_e)

まず連結成分をまとめる
そしたら、その連結成分で、余っている辺を探す(unionfindを使って、クラスカル法っぽく)
連結成分の情報には、その連結成分に含まれれる適当な頂点一つ、余っている辺の数、余っている辺の情報
を入れておく
そして、余っている辺が多い連結成分から、操作を行なっていく

そしたらACできた

ACコード(ライブラリ抜粋)
コメント追加しておきました
```py
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!