[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 198 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
568: 2024/08/24(土)22:50 AAS
Fはガチの中度典型インコ問題
自力開発は大変だけどgrundy数NIM知ってたら一瞬
このスレではnimさんが主要人物だから解けなかったスレ民は過去スレ精進しなさい
569: 2024/08/24(土)22:51 AAS
Gマジでしょうもない問題で笑った
570(1): 2024/08/24(土)22:51 AAS
Gは何かの典型なの？
いつも通り俺の知らないデータ構造かと思って無視してEに走っちゃった
571: 2024/08/24(土)22:52 AAS
2^60>10^18なので60回以上この操作すると出力するべき値が制約を満たさないからです。

人類を舐めるな
572: 2024/08/24(土)22:53 AAS
>>570
というかl,rの計算が線形と見せかけて高々60回程度で回せるというだけか
しょうもな
573: 2024/08/24(土)22:53 AAS
無職つらい
生きてる価値は何かありますか
574: 2024/08/24(土)22:55 AAS
一次関数の複雑クエリはギャグ典型
575(1): 2024/08/24(土)22:55 AAS
F問題、素因数を石としたnimなんか
普通に約数を調和級数的に10^5個に突っ込んでMEXしてたわ
576: 2024/08/24(土)22:56 AAS
まあ最近の虚無ABCよりは歯応えある回だったな
577: 2024/08/24(土)22:57 AAS
無職なんてつまらんからG社で仕事しようぜ
578: 2024/08/24(土)22:57 AAS
解説放送でsnukeさんの弁明聞けるかなぁ
579: 2024/08/24(土)22:58 AAS
赤コーダーも一瞬迷ったらしい

>牛ゲーや改造 dijkstra に見えてかなり事故ってしまった
>落ち着くとイベントソートでよかった

ABC過学習er結構多いから、別の典型っぽく見えるってのは以外と穴なのかも
580: 2024/08/24(土)22:58 AAS
それ+問題設定が複雑だからね
581: 2024/08/24(土)22:59 AAS
>>575
皆これだと思うが
SSRSさんもびっくりしてるし
582: ころころ 2024/08/24(土)23:00 AAS
バイトすら受からないのにG社で働ける訳ないだろ馬鹿にしやがってクソが
583: 2024/08/24(土)23:00 AAS
この考察を必須にしたけりゃ制約を上げるんだったな
584(1): 2024/08/24(土)23:01 AAS
今日の最強コン皆楽しそうに話してていばしょ🧸いばしょ🧸になった
ジェネルシじゃなかったのかよ！！！
585: 2024/08/24(土)23:03 AAS
いや制約上げても意味ねーわ
約数の個数が少なすぎ
586: 2024/08/24(土)23:05 AAS
>>584
人間は馴れ合いインコに擬態できます
逆は無理
587: 2024/08/24(土)23:05 AAS
Ai<10^9でも通るっしょ
588: 2024/08/24(土)23:05 AAS
馴れ合い人間な
ただ能力が高いだけ
589: 2024/08/24(土)23:06 AAS
EはEDPC-Gの気持ちで解いた
590: 2024/08/24(土)23:06 AAS
最終形がAの要素が全部1であることを考えるとNimの山の石の数が全部0と同じになってNimそのものだと気づいて終わり
591: 2024/08/24(土)23:07 AAS
気づくもクソも問題設定の時点でnimの亜種なので
592: 2024/08/24(土)23:09 AAS
素因数の個数でないと解けない制約だと言語差とポラードローで荒れまくり禿げまくりだったろ
593: 2024/08/24(土)23:10 AAS
C++でポラードローする場合に限りチンパンmexで解けます、炎上不可避
594: 2024/08/24(土)23:11 AAS
MEXって多分log付くよね？
だとNlognlognを落として素因数の数の前計算nloglognを通す制約がいる気がする
5*10^6くらい？
いやCだと全然通せそう
595: 2024/08/24(土)23:11 AAS
約数の数ってオーダー何？
logn？
596: 2024/08/24(土)23:12 AAS
は？
597: 2024/08/24(土)23:12 AAS
競技検索で一発だから自分でそれくらい調べなさい
598: 2024/08/24(土)23:13 AAS
とりあえず篩が使える制約の話してない
599: 2024/08/24(土)23:14 AAS
約数を全部列挙してその約数のgrundy数を配列に入れる→ソートして小さい順に見てMEX計算
以外で求められるの？
600: 2024/08/24(土)23:15 AAS
公式解説を読んだ前提なんだがガイジか？
601: 2024/08/24(土)23:15 AAS
chatGPT君のせいでgrundy数が緑落ち
602: 2024/08/24(土)23:16 AAS
俺以外寒色
603: 2024/08/24(土)23:17 AAS
公式解説の篩で約数の個数カウントする解法を通して、約数列挙してMEX使う解法を落としたいって話じゃなくて？
604: 2024/08/24(土)23:19 AAS
ABCは完全にオワコンと化した感じ？
605: 2024/08/24(土)23:19 AAS
むしろArbitrary Nimよりはるかに簡単なのに緑上位もあることに驚き
606: 2024/08/24(土)23:19 AAS
ああそうじゃんポラードローに頭が支配されてた
俺がガイジでした
607: 2024/08/24(土)23:20 AAS
横からだけどmaxA以下の全ての数に対して約数列挙するとポラードローだとn^5/4かかりそう
608(1): 2024/08/24(土)23:20 AAS
GPT今回どこまで解けるん？
Dまでは行けそうだが
609: 2024/08/24(土)23:20 AAS
全てでやる必要ないだろ
N×d(Ai)でいい
610: 2024/08/24(土)23:22 AAS
ABCはAIリテラシーを問う意味で有益なコンテスト
611: 2024/08/24(土)23:22 AAS
レート1200までは同一視していい
GPTくんの実力なので
612(1): 2024/08/24(土)23:23 AAS
未定義動作ラインというわけ
613: 2024/08/24(土)23:23 AAS
約数列挙mexを殺すの無理だな
Ai<10^7で篩の空間に耐えてもらえばギリ殺せるか？
614: 2024/08/24(土)23:23 AAS
そう考えるとARCの境界線設定も的確
615: 2024/08/24(土)23:23 AAS
>>608
コンテスト後試したらFも丸投げでほぼ通ったよ(一か所軽微な修正だけ)
616: 2024/08/24(土)23:24 AAS
多分だけど何人かはポラードローで約数の数を数える話と約数列挙してgrundy数を計算してく話で混ざってそう
617: 2024/08/24(土)23:24 AAS
5*10^7で区間篩してもらお
618: 2024/08/24(土)23:25 AAS
ゲーム木探索とかもそうだが完全既出に強いにゃんね
619: 2024/08/24(土)23:25 AAS
ポラードローを想定解として認めるなら(ヒュだからまずないが)脳死mexは殺し放題じゃね
620: 2024/08/24(土)23:25 AAS
Eに謎の黄diffが定期的に置かれるのなんなんだ
621(1): 2024/08/24(土)23:26 AAS
緑のワイは黒コーダーってこと？
622: 2024/08/24(土)23:26 AAS
すぬけさんもびっくり
623: 2024/08/24(土)23:26 AAS
区間篩といえば今日の最強コンBの別解
624: 2024/08/24(土)23:27 AAS
>>621
はい
AGCのwriterがAtCで緑だったけど黒に丸め込まれていたことを見れば思想がわかる
625: 2024/08/24(土)23:30 AAS
>>612
俺の事バカにしてる？
626: 2024/08/24(土)23:30 AAS
チンパンmexの計算量、下からdpをメモ化再帰にされるだけでクソ減るから殺せねえ
627: 2024/08/24(土)23:31 AAS
緑と水の差、大きすぎる
628: 2024/08/24(土)23:32 AAS
確かに賢いな
Aのそれぞれの約数の全体だから結構減りそう
629: 2024/08/24(土)23:33 AAS
10^5まではmexを余計算、10^5～10^7はチンパンmexとしてもまー耐えるだろ
630: 2024/08/24(土)23:35 AAS
毎週gptで入水してる人が散見されるな
631: 2024/08/24(土)23:36 AAS
某ばななだいふくもほぼ完全GPTでレート1100だったので、GPTの実力はほんとにそのくらいだと思う(水下位くらい)
632: 2024/08/24(土)23:39 AAS
GPTは水色
633: 2024/08/24(土)23:40 AAS
異論なし
634: 2024/08/24(土)23:40 AAS
因みにGPT君の解法は脳死約数列挙mex(それはそう)
635: 2024/08/24(土)23:42 AAS
毎度思うけどgptに解かせてレート上げて何がしたいんだ
636: 2024/08/24(土)23:43 AAS
人間インコ境界線の2100も明確
637: 2024/08/24(土)23:44 AAS
こたつがめさん赤ハラ受けててウケる
638: 2024/08/24(土)23:44 AAS
それでもjobsでは評価されるので
639: 2024/08/24(土)23:44 AAS
grundy数とnimが緑はヤバいと思ったけど流石にGPTで一色下がってるか
640: 2024/08/24(土)23:45 AAS
インコ大王が就活評価カンスト
641: 2024/08/24(土)23:45 AAS
ゆうて鉄則本に乗ってるような知識は全部水未満になってるイメージがあるが
642: 2024/08/24(土)23:47 AAS
Eは燃えるのになぜDは茶緑で安定するんだ
もっと燃えろよ
643: 2024/08/24(土)23:47 AAS
載ってないため
典型90と蟻本には流石にある
644: 2024/08/24(土)23:48 AAS
grundy数むずいだろ
競プロやってない緑以下でもそこそこ解いてるのやばい
645: 2024/08/24(土)23:49 AAS
8問制以降最易か？
646: 2024/08/24(土)23:50 AAS
475とはいえ一応F最易か
次点が329Fのマージテクやるだけ1207
647: 2024/08/24(土)23:52 AAS
grundy数もnimも一回理解すれば自明だけど自力発明はできないタイプ
648: 2024/08/24(土)23:53 AAS
鉄則にありそうだけどないのか
二次元imos、ロリハ、ダブリングとかはあったけど
上下前次1-新書関写板覧索設栞歴
あと 354 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.019s