[過去ﾛｸﾞ]
競技プログラミングにハマるプログラマのスレ 144 (1002ﾚｽ)
競技プログラミングにハマるプログラマのスレ 144 http://medaka.5ch.net/test/read.cgi/prog/1703346239/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
575: 仕様書無しさん [sage] 2023/12/25(月) 23:56:14.48 >>569 本番で分からなかったくせに時間に余裕ある中だと解けたから簡単でしたは草 そーいうのをイキリっていうんだよダサいぞ http://medaka.5ch.net/test/read.cgi/prog/1703346239/575
576: 仕様書無しさん [sage] 2023/12/25(月) 23:56:53.27 Hの順位表、この界隈では今まであまり見なかったタイプの水色コーダーが上位にいて面白い http://medaka.5ch.net/test/read.cgi/prog/1703346239/576
577: 仕様書無しさん [sage] 2023/12/25(月) 23:57:48.64 寝て起きたら10分で考察完了して は？ツイートしよ…ってなる気持ちはまあわかる http://medaka.5ch.net/test/read.cgi/prog/1703346239/577
578: 仕様書無しさん [sage] 2023/12/25(月) 23:59:30.33 コンテスト後にイキるのはマジで負け惜しみでしかないから避けてるわ http://medaka.5ch.net/test/read.cgi/prog/1703346239/578
579: 仕様書無しさん [sage] 2023/12/26(火) 00:00:27.24 >>574 人生詰みかけてるのは間違いないけど、さすがに酷すぎるだろ http://medaka.5ch.net/test/read.cgi/prog/1703346239/579
580: 仕様書無しさん [sage] 2023/12/26(火) 00:02:09.50 >>574 たまねぎ？ http://medaka.5ch.net/test/read.cgi/prog/1703346239/580
581: 仕様書無しさん [sage] 2023/12/26(火) 00:03:25.41 そう殺伐とすんなよ みんなで楽しくデアトークをしよう http://medaka.5ch.net/test/read.cgi/prog/1703346239/581
582: 仕様書無しさん [sage] 2023/12/26(火) 00:13:44.12 nimとスレ長、最近馴れ合い多いな http://medaka.5ch.net/test/read.cgi/prog/1703346239/582
583: 仕様書無しさん [sage] 2023/12/26(火) 00:16:19.11 >>579 最近なんか荒ぶってるやつがいるけど気にせずいこうぜ http://medaka.5ch.net/test/read.cgi/prog/1703346239/583
584: 仕様書無しさん [sage] 2023/12/26(火) 00:18:09.66 A水でH赤なんてのもいるんだな http://medaka.5ch.net/test/read.cgi/prog/1703346239/584
585: 仕様書無しさん [sage] 2023/12/26(火) 00:23:16.45 AHC029の順位表1ページ目、アルゴ緑が3人もいる http://medaka.5ch.net/test/read.cgi/prog/1703346239/585
586: 仕様書無しさん [sage] 2023/12/26(火) 00:27:11.69 低級インコにもチャンスがあるのがヒュだからな http://medaka.5ch.net/test/read.cgi/prog/1703346239/586
587: 仕様書無しさん [sage] 2023/12/26(火) 00:27:59.64 まあレート減少がない時点でただの人生ゲームみたいなおままごとでしかないので アルゴは人生そのもの http://medaka.5ch.net/test/read.cgi/prog/1703346239/587
588: 仕様書無しさん [sage] 2023/12/26(火) 00:49:47.09 むしろリアルの人生も遊びみたいなもんだしアルゴこそが真の人生だよ http://medaka.5ch.net/test/read.cgi/prog/1703346239/588
589: 仕様書無しさん [sage] 2023/12/26(火) 01:19:27.17 人生も競プロもやるだけですから http://medaka.5ch.net/test/read.cgi/prog/1703346239/589
590: 仕様書無しさん [sage] 2023/12/26(火) 01:30:49.97 来年の人間向けコンテスト(ARC/AGC)の日程はよ http://medaka.5ch.net/test/read.cgi/prog/1703346239/590
591: 仕様書無しさん [sage] 2023/12/26(火) 01:39:33.13 焦らされて年内に入黄出来なかったの悲しいね 今年はインコの年だったよ http://medaka.5ch.net/test/read.cgi/prog/1703346239/591
592: 仕様書無しさん [sage] 2023/12/26(火) 01:47:07.64 Gを分割統治せずUnkoUFだけで解こうとしたが無理ということがわかった oxoo oxuu uuux uはundo待ち緑マス、oは確定済緑マス、xは赤マス 確定済同士は経路圧縮できるから、undo待ちの親から確定済の頂点にリンクを張ればO(α(N)logN)で済みそうだが 上例のような確定済の緑マスがundo緑マスと複数連結するケースでリンクの本数が際限なく増えて終わった http://medaka.5ch.net/test/read.cgi/prog/1703346239/592
593: 仕様書無しさん [sage] 2023/12/26(火) 01:56:14.48 緑マス、赤マスとかいう露骨すぎるスレ語録 http://medaka.5ch.net/test/read.cgi/prog/1703346239/593
594: 仕様書無しさん [sage] 2023/12/26(火) 02:04:06.20 確定済ってのは期待値計算を終えた緑マスのことね undo順を自由に選べるし、確定済頂点の接点はundo待ち頂点ごとに高々1個って性質もあるからいけそうなんだけどな undo後、上下左右の緑マスは互いに連結か？が判定できればよくて、o-o, u-uは当然判定可能 o-uの連結判定は、u側にoの代表値はあるか？ができればよさそうにみえるが、ここが難しい http://medaka.5ch.net/test/read.cgi/prog/1703346239/594
595: 仕様書無しさん [sage] 2023/12/26(火) 02:05:44.16 緑色に塗られたマス・赤色に塗られたマスって書くのが面倒だから略したら語録衝突してたのか カス http://medaka.5ch.net/test/read.cgi/prog/1703346239/595
596: 仕様書無しさん [sage] 2023/12/26(火) 02:12:37.65 unko http://medaka.5ch.net/test/read.cgi/prog/1703346239/596
597: 仕様書無しさん [sage] 2023/12/26(火) 02:25:50.04 茶緑くらいの奴がが無理にアルゴの話題出そうとしてるが鬱陶しいからいいよ http://medaka.5ch.net/test/read.cgi/prog/1703346239/597
598: 仕様書無しさん [sage] 2023/12/26(火) 02:34:07.72 前回のGは茶緑レベルじゃないけどな 多分ガチで茶緑くらいの競プロやってないインコがundo可能UFをUFの文字だけ見てそう判断してるんだろうけど http://medaka.5ch.net/test/read.cgi/prog/1703346239/598
599: 仕様書無しさん [sage] 2023/12/26(火) 02:36:33.59 >>597 お前agerだろ 緑の頃はよく灰茶って言ってたからバレバレだぞ http://medaka.5ch.net/test/read.cgi/prog/1703346239/599
600: 仕様書無しさん [sage] 2023/12/26(火) 02:38:13.61 ager、並列二分探索の時も自分が話についていけないから同じ感じでデアの話からそらそうとしてたけど恥ずかしくならないのかな http://medaka.5ch.net/test/read.cgi/prog/1703346239/600
601: 仕様書無しさん [sage] 2023/12/26(火) 02:39:37.71 二分探索が灰レベルだから並列二分探索もせいぜい茶緑レベルやろ！ UFが灰レベルだからUndo可能UFもせいぜい茶緑レベルやろ！ ↑これがまともに競プロやってないagerの知能です 人間とインコの差は残酷だね http://medaka.5ch.net/test/read.cgi/prog/1703346239/601
602: 仕様書無しさん [sage] 2023/12/26(火) 02:40:15.68 ゴシップ好きインコだかagerだか知らんけどタマネギっていう餌を与えてやったんだから満足して巣に帰れよ http://medaka.5ch.net/test/read.cgi/prog/1703346239/602
603: 仕様書無しさん [sage] 2023/12/26(火) 02:43:06.77 何故インコの人間擬態はすぐバレてしまうのか http://medaka.5ch.net/test/read.cgi/prog/1703346239/603
604: 仕様書無しさん [sage] 2023/12/26(火) 02:50:35.00 ライブラリ持ってなくて先日のG upsolveおサボりしてるな http://medaka.5ch.net/test/read.cgi/prog/1703346239/604
605: 仕様書無しさん [sage] 2023/12/26(火) 03:15:17.84 なんかいける気がしてきたな 左上からZ順にロールバックしながら期待値計算し、計算が終わったマスは「確定済」の頂点としてUFを行う 以下、緑マスのうち確定済頂点をo undo待ち頂点をuとする 前提としてuとoは直接UFで繋がず、かわりにundo待ち側の親に、隣接する確定済頂点の代表値一覧（リンク）を持たせる たぶんリンクは集合じゃなくて辞書でないとだめ undoはu-uはよしなに、u-oはリンクから削除 期待値計算のu-oの連結判定は、「oの代表値はuに存在するか？」に読み替える 再uniteが面倒で o-o同士をUnion by size→小さい集合を即座に経路圧縮→o-uのリンクにも経路圧縮の結果を波及 とすれば、u側の代表値は常に最新のものになってうれしい 頭の中では全部O(logN)なんだよな 明日詰める http://medaka.5ch.net/test/read.cgi/prog/1703346239/605
606: 仕様書無しさん [sage] 2023/12/26(火) 03:20:14.03 緑マス、赤マスが問題に出てきたの奇跡だろ http://medaka.5ch.net/test/read.cgi/prog/1703346239/606
607: 仕様書無しさん [sage] 2023/12/26(火) 03:20:29.48 某野菜が自殺したら手を叩いて大笑いして祝杯上げそうｗ＞運営 http://medaka.5ch.net/test/read.cgi/prog/1703346239/607
608: 仕様書無しさん [sage] 2023/12/26(火) 03:23:21.40 確定済頂点がundo待ちを経由せずにつながる場合しか考えとらんやんけ 外周をぐるっと大回りする、o-u-oのケースを無視してたわ カス http://medaka.5ch.net/test/read.cgi/prog/1703346239/608
609: 仕様書無しさん [sage] 2023/12/26(火) 04:26:22.51 >>608 undo済側と未undo側の境界にあるW-1個の辺について、pair(上マスの代表値, 下マスの代表値)をキーとしたmapで辺の個数をカウントしておけばよさそう http://medaka.5ch.net/test/read.cgi/prog/1703346239/609
610: 仕様書無しさん [sage] 2023/12/26(火) 04:43:08.46 >>609 連結判定1クエリあたりO(W)かからない？ つまり 上→下・下→上の接続判定をO(1)で行うんだろ M型の縦方向にジグザグとした配置のとき、接続判定がW/2回発生すると思う http://medaka.5ch.net/test/read.cgi/prog/1703346239/610
611: 仕様書無しさん [sage] 2023/12/26(火) 04:43:58.17 >>609 代表値が変わる瞬間については、map[(新しい代表値, 新しい代表値)] += map[(古い代表値, 古い代表値)] というふうに移して、古い方はもちろん0にする http://medaka.5ch.net/test/read.cgi/prog/1703346239/611
612: 仕様書無しさん [sage] 2023/12/26(火) 04:50:06.58 >>610 map[(左/上の代表値, 右/下の代表値)]が正かどうか、つまりその2グループの境目になっている辺があるかどうかでO(1)で判定できると考えているが http://medaka.5ch.net/test/read.cgi/prog/1703346239/612
613: 仕様書無しさん [sage] 2023/12/26(火) 05:02:15.05 >>612 ちょっと考えてみる 1x222x3 1x2x2x3 uuuxvvv たとえばこの配置を考える 1,2,3はundo済み連結成分の代表値 u,vは未undo 代表値1に注目した時、辞書には何が入るんだ？ (1,u)だけでなく(1,v)まで辞書管理するなら、O(W)の項がどこかで生えてしまいそう http://medaka.5ch.net/test/read.cgi/prog/1703346239/613
614: 仕様書無しさん [sage] 2023/12/26(火) 05:04:26.14 ガイジスレ終了 http://medaka.5ch.net/test/read.cgi/prog/1703346239/614
615: 仕様書無しさん [sage] 2023/12/26(火) 05:08:57.13 >>610 （簡単のため下図は緑マスだけの状態） 12223 12?bc abbbc 例えば"?"マスの上下左右について判定したいときは、 {(1, a): 1, (2, b): 2, (3, c): 1} というmapを見て、(2, b)間に(2本)辺があるので連結だと分かる http://medaka.5ch.net/test/read.cgi/prog/1703346239/615
616: 仕様書無しさん [sage] 2023/12/26(火) 05:13:04.26 >>613 この場合は {(1, u): 1, (2, u): 1, (2, v): 1, (3, v): 1} を想定している http://medaka.5ch.net/test/read.cgi/prog/1703346239/616
617: 仕様書無しさん [sage] 2023/12/26(火) 05:20:54.86 ごめん、俺が問題点を理解してなかった 1111111 1x22213 1x2x2?3 uuuxvvv 上図で"?"マスを見たいとき、(1, v)の連結性でバグるわけか http://medaka.5ch.net/test/read.cgi/prog/1703346239/617
618: 仕様書無しさん [sage] 2023/12/26(火) 05:23:35.61 そうなるとちょっとの工夫では厳しそうだな http://medaka.5ch.net/test/read.cgi/prog/1703346239/618
619: 仕様書無しさん [sage] 2023/12/26(火) 05:27:02.43 >>617 図がおかしかったからこうで 1111111x3 1xxxxx1x3 1x222x1x3 1x2x2x?x3 uuuxvvvvv http://medaka.5ch.net/test/read.cgi/prog/1703346239/619
620: 仕様書無しさん [sage] 2023/12/26(火) 09:20:49.94 ガイジスレを中止します。 早くしなさい。 http://medaka.5ch.net/test/read.cgi/prog/1703346239/620
621: 仕様書無しさん [] 2023/12/26(火) 10:00:58.39 本物のインコに屹立包茎チンコぶっ込んだら内臓 http://medaka.5ch.net/test/read.cgi/prog/1703346239/621
622: 仕様書無しさん [] 2023/12/26(火) 10:23:29.80 鳥のインコにチンコ突っ込んでも緩くない？俺だけ？ http://medaka.5ch.net/test/read.cgi/prog/1703346239/622
623: 仕様書無しさん [sage] 2023/12/26(火) 11:01:22.19 最近気づいたんだけど俺真面目ではなくて勉強できて成績良いだけだった 授業サボりまくってるわ http://medaka.5ch.net/test/read.cgi/prog/1703346239/623
624: 仕様書無しさん [sage] 2023/12/26(火) 11:40:13.95 スレ民的にアルゴ式って埋める価値ある？ http://medaka.5ch.net/test/read.cgi/prog/1703346239/624
625: 仕様書無しさん [sage] 2023/12/26(火) 11:47:14.62 今私に死んでほしいと一番思ってるのは私の母親だ。 http://medaka.5ch.net/test/read.cgi/prog/1703346239/625
626: 仕様書無しさん [sage] 2023/12/26(火) 11:57:24.40 アルゴ式って上手く行ってるんかね b to bのビジネスしてるんだっけ http://medaka.5ch.net/test/read.cgi/prog/1703346239/626
627: 仕様書無しさん [sage] 2023/12/26(火) 12:11:59.87 ちょんさんが辞めてうまくいってるみたいだね http://medaka.5ch.net/test/read.cgi/prog/1703346239/627
628: 仕様書無しさん [sage] 2023/12/26(火) 12:14:22.52 onion find http://medaka.5ch.net/test/read.cgi/prog/1703346239/628
629: 仕様書無しさん [sage] 2023/12/26(火) 12:28:09.93 順位表のMSTさんやDSUさんの存在に言及することで解法を伝えるテクニック http://medaka.5ch.net/test/read.cgi/prog/1703346239/629
630: 仕様書無しさん [sage] 2023/12/26(火) 12:41:56.93 >>618 たぶん厳しいよね UFしない部分でボトルネックになってるから http://medaka.5ch.net/test/read.cgi/prog/1703346239/630
631: 仕様書無しさん [sage] 2023/12/26(火) 13:18:39.69 セグ木DPさんとか逆からUF DSUみたいなかなり具体的な名前でその解法で解ける問題だけ解く謎のユーザー100人発生したらどうなるんだ http://medaka.5ch.net/test/read.cgi/prog/1703346239/631
632: 仕様書無しさん [sage] 2023/12/26(火) 13:25:23.34 なるほど、順位表に解法を乗せればいいのか http://medaka.5ch.net/test/read.cgi/prog/1703346239/632
633: 仕様書無しさん [sage] 2023/12/26(火) 13:28:11.32 運営側がコンテストに参加するの普通に問題でしょ 今まで誰も指摘してこなかったのか http://medaka.5ch.net/test/read.cgi/prog/1703346239/633
634: 仕様書無しさん [sage] 2023/12/26(火) 13:28:24.21 順位表から解法を推測するのは典型だから問題ない http://medaka.5ch.net/test/read.cgi/prog/1703346239/634
635: 仕様書無しさん [sage] 2023/12/26(火) 13:30:12.67 そもそも社長は複垢とかもしたことあるしルール無用だよ http://medaka.5ch.net/test/read.cgi/prog/1703346239/635
636: 仕様書無しさん [sage] 2023/12/26(火) 13:53:14.75 AtCって複垢とか相談OKだったのか http://medaka.5ch.net/test/read.cgi/prog/1703346239/636
637: 仕様書無しさん [sage] 2023/12/26(火) 13:56:02.02 氷山の一角なんだよなあ http://medaka.5ch.net/test/read.cgi/prog/1703346239/637
638: 仕様書無しさん [sage] 2023/12/26(火) 13:58:44.84 binary_search、segment_tree、square_divisionみたいな垢を複数用意しておいて、出題に合わせて参加する垢を変えることでネタバレするテク http://medaka.5ch.net/test/read.cgi/prog/1703346239/638
639: 仕様書無しさん [sage] 2023/12/26(火) 14:00:55.26 >>631 べつに解く必要はなくて、全体に合図を出すならペナ吐くだけでいい セグ木DPさんがF特攻1ペナ、なんでやろなあ… http://medaka.5ch.net/test/read.cgi/prog/1703346239/639
640: 仕様書無しさん [sage] 2023/12/26(火) 14:09:57.59 ヒュでgreedy sa beamsearch垢つくって順位表で競わせるか http://medaka.5ch.net/test/read.cgi/prog/1703346239/640
641: 仕様書無しさん [sage] 2023/12/26(火) 14:11:26.55 ずっと真夜中でいいのに。(無限に寝たいため) http://medaka.5ch.net/test/read.cgi/prog/1703346239/641
642: 仕様書無しさん [sage] 2023/12/26(火) 14:15:52.74 （規約違反であることは前提に） 大量の複垢を操作して、DSUさんとセグ木DPさんとMSTさんにコンテスト中ペナ吐かせるのはDDoS以降不可能だし 組織的にチーミングしてコンテスト荒らしするなら別だけど、この行為にメリットがない以上は愉快犯には不可能 でもコンテスト開始5分後に 「累積和さんはCとDをまだ解いていないし、lowlinkさんはGを解いてないね」 みたいな意味深ツイートされた場合はまあはい 対策は最上位100人間以外コンテスト中匿名化 http://medaka.5ch.net/test/read.cgi/prog/1703346239/642
643: 仕様書無しさん [sage] 2023/12/26(火) 14:21:51.90 順位表の情報を絞れば対策容易なので、あとは裁量次第 Pythonのライブラリに詳しいだけの水色が爆速でG通してるな、ギャグか？ みたいな類推の面白さと、つまらなさの兼ね合いで調整してもろて http://medaka.5ch.net/test/read.cgi/prog/1703346239/643
644: 仕様書無しさん [sage] 2023/12/26(火) 14:30:48.45 別にAtC上で行わなくてもいい ・Xでセグ木DP、逆からUFとかの名前の垢をたくさん作る ・コンテスト時に出題された解法と一致するX垢だけ意味深投稿を大量にする(直接解法と言及しないのがミソ) これで不正として取り締まりようがないでしょ？もちろん人々に垢を知られないと意味ないが、一度誰かがネタにさえすれば終わり。不正と断定できる証拠がない。 http://medaka.5ch.net/test/read.cgi/prog/1703346239/644
645: 仕様書無しさん [] 2023/12/26(火) 14:34:23.22 ようやくXのインコ界隈も競プロが中受支配的だということに気づき始めてきたな http://medaka.5ch.net/test/read.cgi/prog/1703346239/645
646: 仕様書無しさん [sage] 2023/12/26(火) 14:35:01.87 髪切らなすぎて髪の長さを最大化するAHCで優勝した http://medaka.5ch.net/test/read.cgi/prog/1703346239/646
647: 仕様書無しさん [sage] 2023/12/26(火) 14:35:47.98 >>644 それ誰かがやったらお前教唆犯として逮捕な http://medaka.5ch.net/test/read.cgi/prog/1703346239/647
648: 仕様書無しさん [sage] 2023/12/26(火) 14:38:08.66 >>647 犯罪の想定解を洗い出すことは犯罪対策に貢献してるぞ http://medaka.5ch.net/test/read.cgi/prog/1703346239/648
649: 仕様書無しさん [sage] 2023/12/26(火) 14:42:34.93 灯油よりガソリンが危険と分かっても 対策の立てようがありませんが http://medaka.5ch.net/test/read.cgi/prog/1703346239/649
650: 仕様書無しさん [sage] 2023/12/26(火) 14:43:32.60 強い人がコンテスト中にいきなりMo's algoの記事にいいねをつけた場合 まあいたちごっこよ http://medaka.5ch.net/test/read.cgi/prog/1703346239/650
651: 仕様書無しさん [sage] 2023/12/26(火) 14:45:01.54 オンラインコンテストは始めから競技性はないよ http://medaka.5ch.net/test/read.cgi/prog/1703346239/651
652: 仕様書無しさん [sage] 2023/12/26(火) 14:45:43.41 実装力が低すぎてABC微減、ARC/AGC微増or大勝ち何だけどこれどうすれば直る？ ひたすらバチャか？ http://medaka.5ch.net/test/read.cgi/prog/1703346239/652
653: 仕様書無しさん [] 2023/12/26(火) 14:52:00.88 弱点分かってんなら黙って精進しろよ http://medaka.5ch.net/test/read.cgi/prog/1703346239/653
654: 仕様書無しさん [sage] 2023/12/26(火) 14:52:45.69 思考停止でバグなく書けばよいため たとえばダイクストラを書くたびに、ヒープの処理に思いを馳せてチンタラ考えるやつらには負けないよそれは http://medaka.5ch.net/test/read.cgi/prog/1703346239/654
655: 仕様書無しさん [sage] 2023/12/26(火) 14:55:37.72 お前らもこれ読んで中受精進しろよ https://ddd-smart.net/list2.php?type=2&keyword=%E9%A3%9F%E8%9C%82%E6%93%8D%E7%A5%88 http://medaka.5ch.net/test/read.cgi/prog/1703346239/655
ﾒﾓ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 347 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.012s