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