ABC392振り返り


前回の振り返り(ABC391は都合により不参加)

https://qiita.com/comet725/items/9fcbfa037ddaed8355a3

今日はABC392開催日だったので参加結果を振り返る

https://atcoder.jp/contests/abc392

今週はA,B,C,Dの4完(0ペナ)


# A

順列全探索で成り立つパターンを探す

## ソースコード

```python:main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import permutations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def main():
    A = rLI()
    for b1,b2,b3 in permutations(A,3):
        if b1*b2==b3:
            print("Yes")
            break
    else:
        print("No")
    
if __name__ == '__main__':
    main()

```

# B

一旦全部集合に入れて、
Aに入っている要素を除外する。

昇順に出す必要があるので念の為 SortedSetを使う

## ソースコード

```python:main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations

from sortedcontainers import SortedSet
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def main():
    N, M = rLI()
    A = rLI()
    X = SortedSet([i+1 for i in range(N)])
    for a in A:
        X.remove(a)
    print(len(X))
    print(*list(X))
    
if __name__ == '__main__':
    main()

```

# C

i番目のゼッケンの人が誰を見ているのか1から順番に並べて、

見られている人のゼッケンを順番に出力

## ソースコード

```python:main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def main():
    N = rI()
    P = rLI1()
    Q = rLI()
    R = list(sorted(P,key=lambda x: Q[x]))
    print(*[Q[P[r]] for r in R])
    
if __name__ == '__main__':
    main()

```

# D

サイコロの目と、同じ目の個数と、そのサイコロの目の種類すべてと、それぞれの目がでる確率を求める。

あとは組み合わせ全探索で、共通の目が同時に出る確率の最大値を探す。

## ソースコード

```python:main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def main():
    N = rI()
    A = [0]*N
    B = [0]*N
    C = [0]*N
    P = [0]*N
    for i in range(N):
        K, *A[i] = rLI()
        B[i] = Counter(A[i])
        C[i] = set(B[i].keys())
        P[i] = {k:v/K for k,v in B[i].items()}
        err(i,K,P[i])
    ans = 0
    for a,b in combinations(range(N),2):
        D = C[a] & C[b]
        err(a,b,D)
        ret = 0
        for d in D:
            value = P[a][d]*P[b][d]
            err(d,P[a][d],P[b][d],value)
            ret += value
        ans = max(ans,ret)
    print(ans)
if __name__ == '__main__':
    main()

```

# E

UnionFindで余っているケーブルを割り出すまでは簡単にできたが、
あまりのケーブルを付け替える処理がうまくいかず、
コンテスト終了1分前に提出したがTLE...

## ソースコード

<details><summary>TLEコード</summary>

```python:main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * -~n
        self.rank = [1] * -~n
        self.roots= set([-~i for i in range(n)])
        self.count = n
    def root(self, x):
        while (p:=self.parent[x]) != -1:
            x = p
        return x
    def union(self, x, y):
        xr = self.root(x)
        yr = self.root(y)
        if xr == yr: return
        elif (rx:=self.rank[xr]) < (ry:=self.rank[yr]):
            self.parent[xr] = yr
            self.rank[yr] += rx
            self.roots.remove(xr)
        else:
            self.parent[yr] = xr
            self.rank[xr] += ry
            self.roots.remove(yr)
        self.count -= 1
    def same(self,x,y):
        # err(self.root(x), self.root(y))
        return self.root(x) == self.root(y)

def main():
    N, M = rLI()
    UF = UnionFind(N)
    spare = []
    for i0 in range(M):
        i = -~i0
        a,b = rLI()
        if a!=b and UF.root(a) != UF.root(b):
            UF.union(a,b)
        else:
            spare.append((i,a,b))
    print(UF.count-1)
    # err(*UF.roots)
    # err(*spare)
    if UF.count > 1:
        r = defaultdict(list)
        for s in spare:
            r[UF.root(s[1])].append(s)
        # err(dict(r))
        while UF.count > 1:
            roots = list(UF.roots)
            for x,y in combinations(roots,2):
                xr = UF.root(x)
                yr = UF.root(y)
                if len(r[xr]) > 0:
                    i,a,b = r[xr].pop()
                    print(i,b,yr)
                elif len(r[yr]) > 0:
                    i,a,b = r[yr].pop()
                    print(i,b,xr)
                else :continue
                UF.union(x,y)
                if UF.root(x) != x:
                    for rx in r[x]:
                        r[y].append(rx)
                else:
                    for ry in r[y]:
                        r[x].append(ry)  
                break      
        
if __name__ == '__main__':
    main()

```

</details>



# F

D解いた直後ではこっちのほうが解いている人が多かったので先に取り掛かった。

問題のシンプルさとは裏腹に
普通のリストは挿入アルゴリズムが激重なことを考えると非常に厳しく、
最初は色々データ構造を模索してみたものの、うまくいかず、Eに逆戻り

# G

終了後に問題見たけど成約数大きくて戦慄

# まとめ

Eが惜しいところまで行ったが無念のTLE

グラフ関係の実装力がほしい