結果

問題 No.3345 Reducible Sequence
コンテスト
ユーザー Koi
提出日時 2025-11-13 23:17:54
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,429 bytes
コンパイル時間 354 ms
コンパイル使用メモリ 82,156 KB
実行使用メモリ 112,176 KB
最終ジャッジ日時 2025-11-13 23:18:04
合計ジャッジ時間 9,251 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

# TLE👹
import sys
readline = sys.stdin.readline
write = sys.stdout.write

# X, Y, E = map(int, readline().split())

class BipartiteMatching:
    def __init__(self, n):
        self.n=n  # n of vertices 
        self.graph=[[] for _ in range(n)]

    def add_edge(self,u,v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def dfs(self,v,match,used):
        used[v]=True
        for u in self.graph[v]:
            w=match[u]
            if w<0 or (not used[w] and self.dfs(w,match,used)):
                match[v]=u
                match[u]=v
                return True
        return False

    def mactching(self):
        match=[-1]*self.n 
        for v in range(self.n):
            if match[v]>=0:
                continue 
            used=[False]*self.n
            self.dfs(v,match,used)
        return match



N = int(input())
A = list(map(int, input().split()))
MA = max(A)
L = [[] for _ in range(MA + 1)]
for i in range(1, N + 1):
    x = i
    while x <= MA:
        L[x].append(i)
        x += i
ok = 1
ng = N + 1
while (ng - ok) > 1:
    mid = (ok + ng) // 2
    bm = BipartiteMatching(mid+N)
    
    for i in range(N):
        for x in L[A[i]]:
            if(x <= mid):
                bm.add_edge(x - 1, mid + i)
            else:
                break
    match = bm.mactching()
    if(len(match) - match.count(-1) == mid * 2):
        ok = mid
    else:
        ng = mid

print(ok)
0