[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 198 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
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、ロリハ、ダブリングとかはあったけど
649: 2024/08/24(土)23:56 AAS
競プロ専用知識が緑になるのさすがに敷居が上がりすぎでは
いまに始まったことじゃないかもしれんが
650: 2024/08/24(土)23:57 AAS
nimはまだ教養だからいい
セグ木緑とかのほうが普通にやばい
651: 2024/08/24(土)23:58 AAS
セグ木どころか遅延セグ木も緑
652(1): 2024/08/24(土)23:59 AAS
ダブリングは先週水中位だったな
いずれにせよ昔は青、黄色になる為に必要とされた知識(参考: qiita.com/e869120/items/acba3dd8649d913102b5)は今は水色になる為に必要 (またはGPTを使うか)
653: 2024/08/25(日)00:00 AAS
340Eのことだろうけど緑水で解いてる層は遅延セグ木使ってるよな 認めたくねー
654: 2024/08/25(日)00:01 AAS
gptやるだけだから敷居は下がってますが
655: 2024/08/25(日)00:01 AAS
遅延セグ木チートシートにのってる基本的なクエリなら誰でも使えるんやろうな
range add range minとかrange sumとか
656: 2024/08/25(日)00:06 AAS
grundyとロリハは確実に下がってる
座圧は知らんギャグだろ
657: 2024/08/25(日)00:07 AAS
Eが黄色でFが緑ということは"知識"を学ぶことだけが精進だと勘違いしているインコが増えているということだな
658: 2024/08/25(日)00:09 AAS
>>652
4年で随分様変わりしたなぁ
659: 2024/08/25(日)00:14 AAS
インコは論理的な思考ではなく過去の経験に基づくオウム返しでしか解けないため
660: 2024/08/25(日)00:22 AAS
Eは赤でも沼ると7ペナ40分かかってるくらいむずい
661: 2024/08/25(日)00:22 AAS
水色になる方法: GPTの使い方を習得すればOK！
662: 2024/08/25(日)00:26 AAS
むしろ必要な知識量だけで判断して難易度推定をミスったということでは
663: 2024/08/25(日)00:29 AAS
びっくりしませんかという話
664: 2024/08/25(日)00:30 AAS
ABCは必要知識の敷居で配点付けてる
665(1): 2024/08/25(日)00:31 AAS
結局暖色になろうと思ったらgpt使ってレート上げても何の意味もないんだよな
666: 2024/08/25(日)00:33 AAS
nimがC問題で出てくる日もそう遠くはないな
667: 2024/08/25(日)00:37 AAS
E問題本当に難しい要素がわからないんだが，どこが難しいの？
668(1): 2024/08/25(日)00:38 AAS
>>665
就活での評価は水色でも暖色でも大差ないので
上下前次1-新書関写板覧索設栞歴
あと 334 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.012s