[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 144 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
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
思考停止でバグなく書けばよいため
たとえばダイクストラを書くたびに、ヒープの処理に思いを馳せてチンタラ考えるやつらには負けないよそれは
655(3): 2023/12/26(火)14:55 AAS
お前らもこれ読んで中受精進しろよ
外部ﾘﾝｸ[php]:ddd-smart.net
656: 2023/12/26(火)14:56 AAS
>>652
ABC ratedの間は何も考えずに過去問埋め(cfも)
657(1): 2023/12/26(火)14:56 AAS
誤爆した
外部ﾘﾝｸ:qiita.com
658: 2023/12/26(火)14:56 AAS
ABCなんてライブラリペタッ！で終了
659: 2023/12/26(火)14:57 AAS
>>655
あのさぁ...
660: 2023/12/26(火)14:59 AAS
agerさぁ…さすがに恥ずかしすぎるだろ
661: 2023/12/26(火)15:01 AAS
これは恥ずかしい
662: 2023/12/26(火)15:07 AAS
偏差値 70 台の方へ
全国模試でベスト 100 位以内に入れるような高順位を何度も取っていると思います。このレベルだと、勉強自体が楽しくて、模試はゲーム感覚で楽しんでいる方も多いでしょう。そんな中でも、もし算数が特に好きでしたら、算数オリンピックなどに挑戦してみるのも面白いと思います！ 本物の天才パズルの世界が君を待っています！
663: 2023/12/26(火)15:10 AAS
>>655
もうスレに書き込めないね
664(1): 2023/12/26(火)15:10 AAS
で、けんちゃんは算数オリ数オリでどこまで行けたの？
665: 2023/12/26(火)15:13 AAS
JJMO 銀賞
666: 2023/12/26(火)15:14 AAS
>>664
jmo本選まで行ってる
ガチの天才
667: 2023/12/26(火)15:18 AAS
マジの天才じゃん
外部ﾘﾝｸ:x.com
668: 2023/12/26(火)15:19 AAS
けんちゃんager
669: 2023/12/26(火)15:21 AAS
>>657
なんでこう普通に避けられる自白をするのかね
>>655
だけならagerに敏感な人以外はスルーだったろうに
670(1): 2023/12/26(火)15:26 AAS
334批判してる人が逆に叩かれてるけど、ファンに失礼とかじゃなくて手垢ベタベタのネットミームでキャッキャやられるのだいぶキツイので俺も辞めて欲しいと思う
114514も辞めて欲しい
671: 2023/12/26(火)15:27 AAS
810は中受したら避けられないぞ
672: 2023/12/26(火)15:29 AAS
そもそもクリスマスを題材にするのは大丈夫なのか
673: 2023/12/26(火)15:31 AAS
クリスマスという文字列を見るだけで胸が締め付けられる思いになるのに、出題するとはチー牛差別だ！w
674: 2023/12/26(火)15:33 AAS
>>670
あれ叩く側が容赦なさすぎて引いてる
「ちょっと叩かれるくらいでツイート消すくらいなら、はじめから言わないほうがいいとおもいます！」
とか正義感を盾に無謬主義を押し付けてて心底不愉快だった
上下前次1-新書関写板覧索設栞歴
あと 328 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.016s