前回の振り返り(ABC391は都合により不参加)
今日はABC392開催日だったので参加結果を振り返る
今週はA,B,C,Dの4完(0ペナ)
A
順列全探索で成り立つパターンを探す
ソースコード
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を使う
ソースコード
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から順番に並べて、
見られている人のゼッケンを順番に出力
ソースコード
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
サイコロの目と、同じ目の個数と、そのサイコロの目の種類すべてと、それぞれの目がでる確率を求める。
あとは組み合わせ全探索で、共通の目が同時に出る確率の最大値を探す。
ソースコード
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...
ソースコード
TLEコード
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()
F
D解いた直後ではこっちのほうが解いている人が多かったので先に取り掛かった。
問題のシンプルさとは裏腹に
普通のリストは挿入アルゴリズムが激重なことを考えると非常に厳しく、
最初は色々データ構造を模索してみたものの、うまくいかず、Eに逆戻り
G
終了後に問題見たけど成約数大きくて戦慄
まとめ
Eが惜しいところまで行ったが無念のTLE
グラフ関係の実装力がほしい