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