[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 191 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
6: 2024/07/25(木)23:54 AAS
1-Nの番号がついたN個のボールと、L-Rの番号がついたR-L+1個の箱がある
ボールは自身の整数倍の番号の箱にしかしまえない
箱に入るボールは高々1個
箱に入るボールの個数の最大化
N<300 1<L<R<10^9
L+N^2<Rならインコの巣原理で全マッチ
そうでないならV=O(N^2) E=O(N^2)の辺容量1dinicだからO(FE)=O(N^3)で厳密解が得られる
でも例えばボールの番号の大きい順に貪欲して初期解を作ってからdinicしたらFが小さくなって高速化できん？
上下前次1-新書関写板覧索設栞歴
あと 996 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.147s*