[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 184 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
278: 仕様書無しさん [sage] 2024/06/16(日) 23:03:14.61 AAS
umnikのrating below 3000 is just a number発言を参照すれば自明ですよね
279: 仕様書無しさん [sage] 2024/06/16(日) 23:14:08.29 AAS
そらfor文だけで解ける問題でフリーズしてたらびっくりするわな
280: 仕様書無しさん [sage] 2024/06/16(日) 23:25:54.43 AAS
射精するまで問題設定を生みまくる自慰作問すりゅ
281: 仕様書無しさん [sage] 2024/06/16(日) 23:37:18.22 AAS
射精りゅ
1,…,nが書かれた計n個のボールと、L,L+1,…,Rが書かれた計R-L+1個の箱がある
各ボールは自身の整数倍の箱にしかしまえず、各箱はボールを高々1個しかしまえない
箱にしまえるボールの個数を最大化
282: 仕様書無しさん [sage] 2024/06/16(日) 23:39:10.25 AAS
フロー
283: 仕様書無しさん [sage] 2024/06/16(日) 23:39:34.03 AAS
いや、制約次第だな
284: 仕様書無しさん [sage] 2024/06/16(日) 23:43:18.17 AAS
フローで自明に解けりゅ
貪欲でも解けりゅかもしれないけど自慰してるからわしはやりゃないゆ
285: 仕様書無しさん [sage] 2024/06/16(日) 23:47:55.67 AAS
制約が不明なのに解けたもなにもないだろ
286: 仕様書無しさん [sage] 2024/06/16(日) 23:49:48.68 AAS
解ける制約の上限を考えりゅといいゆ
287: 仕様書無しさん [sage] 2024/06/16(日) 23:53:06.10 AAS
n<100 1<L<R<10^9は解けりゅ
もっと厳しい制約で解けたらおしえてあげりゅ
288: 仕様書無しさん [sage] 2024/06/16(日) 23:56:56.38 AAS
線形かnlogn無いかなー？
6より2の方が入りやすいので、6を入れたあと2を入れようとしたほうがよさそう
同様にn以下の整数で約数であるような関係なら→でDAGを作ったとき入次数が0である数が良さそう
いや入次数が0のどの数を入れればいいのか不明になった
終わり
289: 仕様書無しさん [sage] 2024/06/17(月) 00:00:28.23 AAS
なんか|R-L|がnよりある程度大きかったら全部入るギャグ要素ありそう
290: 仕様書無しさん [sage] 2024/06/17(月) 00:09:57.60 AAS
幅nに必ずn以下の倍数が1つはあるからn^2なら最大で良いじゃん
というか上で言ってた表現はそれを見越してか
インコすぎて終わった
吊ってください
291: 仕様書無しさん [sage] 2024/06/17(月) 00:11:04.26 AAS
なんとなくでかい方からの貪欲でかなりの部分よさそうな気がするが、証明するのつらそう
292: 仕様書無しさん [sage] 2024/06/17(月) 00:12:40.75 AAS
射精したから作問やめりゅ
R-L>n^2ならインコの巣原理で自明全マッチ
そうでなければ二部マッチングをdinicでやればいけりゅ
293: 仕様書無しさん [sage] 2024/06/17(月) 00:16:04.36 AAS
目指さなくていいのか？
準線形をよぉ…
294: 仕様書無しさん [sage] 2024/06/17(月) 00:26:51.26 AAS
n^2よりもっと小さい下界がありそう
でもオーダー的には改善してなさそう
295: 仕様書無しさん [sage] 2024/06/17(月) 00:27:18.87 AAS
(全部マッチングさせられる)下界
296: 仕様書無しさん [sage] 2024/06/17(月) 00:27:51.12 AAS
原理に基づいてインコの巣にお帰りなさい
297: 仕様書無しさん [sage] 2024/06/17(月) 00:29:28.03 AAS
1以下は1でOK、
2以下は2でOK、
3以下は2+3でOK、
4以下は3+4でOK、
うーん、n^2/2にしかならなかった
298(1): 仕様書無しさん [sage] 2024/06/17(月) 00:59:43.09 AAS
強い人がやたら卑下しがちな現象、自分の実力未満のインコを未定義動作扱いしてることが起因だからな
299: 仕様書無しさん [sage] 2024/06/17(月) 01:11:57.85 AAS
ガイジ論法やめてね
300: 仕様書無しさん [sage] 2024/06/17(月) 03:25:59.34 AAS
「しょうもない遊び」の「しょうもない格付け」に対し「しょうもない選民思想」を抱く「しょうもない人間」が集まる「しょうもないスレ」
301: 仕様書無しさん [sage] 2024/06/17(月) 03:27:35.66 AAS
全てがしょうもない
302: 仕様書無しさん [sage] 2024/06/17(月) 04:15:45.46 AAS
Xの悪口やめてね
上下前次1-新書関写板覧索設栞歴
あと 700 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.023s