[過去ﾛｸﾞ]
競技プログラミングにハマるプログラマのスレ 167 (1002ﾚｽ)
競技プログラミングにハマるプログラマのスレ 167 http://medaka.5ch.net/test/read.cgi/prog/1710987911/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
903: 仕様書無しさん [sage] 2024/03/26(火) 00:18:36.62 緑って偏差値70もあるのか 青は偏差値80ぐらいか？ http://medaka.5ch.net/test/read.cgi/prog/1710987911/903
904: 仕様書無しさん [sage] 2024/03/26(火) 00:27:21.11 >>898 想定は前者 998と1097でハッシュ化すれば絶対に衝突しない もう少し頭使うと末尾の0の個数でN!内の5の指数がわかるので5択問題と化す こっから上手い性質探せたら良かったのだがたった5択なら愚直判定が通るのでインコ問送り決定 http://medaka.5ch.net/test/read.cgi/prog/1710987911/904
905: 仕様書無しさん [sage] 2024/03/26(火) 00:33:36.61 インコ部屋に収容せよ http://medaka.5ch.net/test/read.cgi/prog/1710987911/905
906: 仕様書無しさん [sage] 2024/03/26(火) 00:39:34.72 昨日のBの隣接swap版どうやるんだろう http://medaka.5ch.net/test/read.cgi/prog/1710987911/906
907: 仕様書無しさん [sage] 2024/03/26(火) 00:41:14.53 入力がN!でなくてP!(Pは素数)だったならハッシュ化せずとも末尾0個数+桁dp除算判定が可能なのでケチはつかんがインコ問のそしりは免れないため http://medaka.5ch.net/test/read.cgi/prog/1710987911/907
908: 仕様書無しさん [sage] 2024/03/26(火) 00:43:22.66 >>903 緑で偏差値55で青で偏差値65とかそんなもんだろ 高受偏差値70はポテ青上位 http://medaka.5ch.net/test/read.cgi/prog/1710987911/908
909: 仕様書無しさん [sage] 2024/03/26(火) 00:54:37.47 >>850 Nが小さいからPython使えば愚直にO(N)判定でできないのかと思ったけど、多倍長整数がどれくらいおそくなるのかわかんないや http://medaka.5ch.net/test/read.cgi/prog/1710987911/909
910: 仕様書無しさん [sage] 2024/03/26(火) 01:14:40.38 Bの隣接swap版はreplace回数の三分探索で解きたいがたぶん嘘 簡単のため文字列Sの(個数=)個数とする 隣接swapだけでカッコ列の対応を取るシミュレートを貪欲法で行い、実行後の対応の取れたカッコ列をTとする SとTのカッコの差分を見比べると、交換するべき()の位置が浮かび上がってくる ()同士の距離が小さいほうから隣接swapだけで交換するかreplace2回でやるか貪欲に決定する でどうだ http://medaka.5ch.net/test/read.cgi/prog/1710987911/910
911: 仕様書無しさん [sage] 2024/03/26(火) 01:15:51.13 >>909 多倍長整数の掛け算はかなり時間かかる O(1) ではないと思うが正確な計算量はわからん 自分の環境（Pypy3）だと200000!を計算するだけで7秒かかった http://medaka.5ch.net/test/read.cgi/prog/1710987911/911
912: 仕様書無しさん [sage] 2024/03/26(火) 01:17:09.07 >>911 math.factorial(200000)を使え http://medaka.5ch.net/test/read.cgi/prog/1710987911/912
913: 仕様書無しさん [sage] 2024/03/26(火) 01:21:03.03 >>912 0.16 sec だったけど、Nの特定はできなくない？全探索の代わりに二分探索しても重いぞ http://medaka.5ch.net/test/read.cgi/prog/1710987911/913
914: 仕様書無しさん [sage] 2024/03/26(火) 01:22:28.92 よく考えたら素数p≦200000 で割り切れるかどうかで二分探索→Nの範囲を絞り、そこからは適当に多倍長整数でやる でも出来るな（20万以下では素数の間隔は100以下なので間に合う） http://medaka.5ch.net/test/read.cgi/prog/1710987911/914
915: 914 [sage] 2024/03/26(火) 01:28:12.56 まあこれやるなら末尾の0の個数に注目するのとあまり変わらないか http://medaka.5ch.net/test/read.cgi/prog/1710987911/915
916: 仕様書無しさん [sage] 2024/03/26(火) 01:31:36.29 >>913 まあそれはそうで、math頼みの階乗計算は200msかかるので愚直計算はできても10回まで N!の末尾の0の個数が5の指数と一致することを使えば愚直5回で判定できてこれなら余裕 素数法だと素数砂漠の探索前に多倍長/多倍長をすればよく、これはn<200000なら400msで可能なので通せる http://medaka.5ch.net/test/read.cgi/prog/1710987911/916
917: 仕様書無しさん [sage] 2024/03/26(火) 03:40:32.71 久しぶりに会話したらコミュ力ゴミカスになってて草 もう終わりだよ http://medaka.5ch.net/test/read.cgi/prog/1710987911/917
918: 仕様書無しさん [sage] 2024/03/26(火) 04:21:37.56 ひととかかわれません http://medaka.5ch.net/test/read.cgi/prog/1710987911/918
919: 仕様書無しさん [sage] 2024/03/26(火) 04:32:48.35 健常者志望 http://medaka.5ch.net/test/read.cgi/prog/1710987911/919
920: 仕様書無しさん [sage] 2024/03/26(火) 04:33:47.45 今は？ http://medaka.5ch.net/test/read.cgi/prog/1710987911/920
921: 仕様書無しさん [sage] 2024/03/26(火) 04:41:05.08 ジェネルシ より正確にはモンスター 宇宙人 http://medaka.5ch.net/test/read.cgi/prog/1710987911/921
922: 仕様書無しさん [sage] 2024/03/26(火) 05:16:59.89 病気治してえー http://medaka.5ch.net/test/read.cgi/prog/1710987911/922
ﾒﾓ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 80 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.019s