競技プログラミングにハマるプログラマのスレ 144
■ このスレッドは過去ログ倉庫に格納されています
>>569
本番で分からなかったくせに時間に余裕ある中だと解けたから簡単でしたは草
そーいうのをイキリっていうんだよダサいぞ Hの順位表、この界隈では今まであまり見なかったタイプの水色コーダーが上位にいて面白い 寝て起きたら10分で考察完了して
は？ツイートしよ…ってなる気持ちはまあわかる コンテスト後にイキるのはマジで負け惜しみでしかないから避けてるわ >>574
人生詰みかけてるのは間違いないけど、さすがに酷すぎるだろ そう殺伐とすんなよ
みんなで楽しくデアトークをしよう >>579
最近なんか荒ぶってるやつがいるけど気にせずいこうぜ AHC029の順位表1ページ目、アルゴ緑が3人もいる まあレート減少がない時点でただの人生ゲームみたいなおままごとでしかないので
アルゴは人生そのもの むしろリアルの人生も遊びみたいなもんだしアルゴこそが真の人生だよ 来年の人間向けコンテスト(ARC/AGC)の日程はよ 焦らされて年内に入黄出来なかったの悲しいね
今年はインコの年だったよ Gを分割統治せずUnkoUFだけで解こうとしたが無理ということがわかった
oxoo
oxuu
uuux
uはundo待ち緑マス、oは確定済緑マス、xは赤マス
確定済同士は経路圧縮できるから、undo待ちの親から確定済の頂点にリンクを張ればO(α(N)logN)で済みそうだが
上例のような確定済の緑マスがundo緑マスと複数連結するケースでリンクの本数が際限なく増えて終わった 確定済ってのは期待値計算を終えた緑マスのことね
undo順を自由に選べるし、確定済頂点の接点はundo待ち頂点ごとに高々1個って性質もあるからいけそうなんだけどな
undo後、上下左右の緑マスは互いに連結か？が判定できればよくて、o-o, u-uは当然判定可能
o-uの連結判定は、u側にoの代表値はあるか？ができればよさそうにみえるが、ここが難しい 緑色に塗られたマス・赤色に塗られたマスって書くのが面倒だから略したら語録衝突してたのか
カス 茶緑くらいの奴がが無理にアルゴの話題出そうとしてるが鬱陶しいからいいよ 前回のGは茶緑レベルじゃないけどな
多分ガチで茶緑くらいの競プロやってないインコがundo可能UFをUFの文字だけ見てそう判断してるんだろうけど >>597
お前agerだろ
緑の頃はよく灰茶って言ってたからバレバレだぞ ager、並列二分探索の時も自分が話についていけないから同じ感じでデアの話からそらそうとしてたけど恥ずかしくならないのかな 二分探索が灰レベルだから並列二分探索もせいぜい茶緑レベルやろ！
UFが灰レベルだからUndo可能UFもせいぜい茶緑レベルやろ！
↑これがまともに競プロやってないagerの知能です 人間とインコの差は残酷だね ゴシップ好きインコだかagerだか知らんけどタマネギっていう餌を与えてやったんだから満足して巣に帰れよ ライブラリ持ってなくて先日のG upsolveおサボりしてるな なんかいける気がしてきたな
左上から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)なんだよな
明日詰める 某野菜が自殺したら手を叩いて大笑いして祝杯上げそうｗ＞運営 確定済頂点がundo待ちを経由せずにつながる場合しか考えとらんやんけ
外周をぐるっと大回りする、o-u-oのケースを無視してたわ
カス >>608
undo済側と未undo側の境界にあるW-1個の辺について、pair(上マスの代表値, 下マスの代表値)をキーとしたmapで辺の個数をカウントしておけばよさそう >>609
連結判定1クエリあたりO(W)かからない？
つまり 上→下・下→上の接続判定をO(1)で行うんだろ
M型の縦方向にジグザグとした配置のとき、接続判定がW/2回発生すると思う >>609
代表値が変わる瞬間については、map[(新しい代表値, 新しい代表値)] += map[(古い代表値, 古い代表値)] というふうに移して、古い方はもちろん0にする >>610
map[(左/上の代表値, 右/下の代表値)]が正かどうか、つまりその2グループの境目になっている辺があるかどうかでO(1)で判定できると考えているが >>612
ちょっと考えてみる
1x222x3
1x2x2x3
uuuxvvv
たとえばこの配置を考える
1,2,3はundo済み連結成分の代表値 u,vは未undo
代表値1に注目した時、辞書には何が入るんだ？
(1,u)だけでなく(1,v)まで辞書管理するなら、O(W)の項がどこかで生えてしまいそう >>610
（簡単のため下図は緑マスだけの状態）
12223
12?bc
abbbc
例えば"?"マスの上下左右について判定したいときは、
{(1, a): 1, (2, b): 2, (3, c): 1}
というmapを見て、(2, b)間に(2本)辺があるので連結だと分かる >>613
この場合は
{(1, u): 1, (2, u): 1, (2, v): 1, (3, v): 1}
を想定している ごめん、俺が問題点を理解してなかった
1111111
1x22213
1x2x2?3
uuuxvvv
上図で"?"マスを見たいとき、(1, v)の連結性でバグるわけか >>617
図がおかしかったからこうで
1111111x3
1xxxxx1x3
1x222x1x3
1x2x2x?x3
uuuxvvvvv 最近気づいたんだけど俺真面目ではなくて勉強できて成績良いだけだった
授業サボりまくってるわ アルゴ式って上手く行ってるんかね
b to bのビジネスしてるんだっけ 順位表のMSTさんやDSUさんの存在に言及することで解法を伝えるテクニック >>618
たぶん厳しいよね
UFしない部分でボトルネックになってるから セグ木DPさんとか逆からUF
DSUみたいなかなり具体的な名前でその解法で解ける問題だけ解く謎のユーザー100人発生したらどうなるんだ 運営側がコンテストに参加するの普通に問題でしょ
今まで誰も指摘してこなかったのか そもそも社長は複垢とかもしたことあるしルール無用だよ binary_search、segment_tree、square_divisionみたいな垢を複数用意しておいて、出題に合わせて参加する垢を変えることでネタバレするテク >>631
べつに解く必要はなくて、全体に合図を出すならペナ吐くだけでいい
セグ木DPさんがF特攻1ペナ、なんでやろなあ… ヒュでgreedy sa beamsearch垢つくって順位表で競わせるか （規約違反であることは前提に）
大量の複垢を操作して、DSUさんとセグ木DPさんとMSTさんにコンテスト中ペナ吐かせるのはDDoS以降不可能だし
組織的にチーミングしてコンテスト荒らしするなら別だけど、この行為にメリットがない以上は愉快犯には不可能
でもコンテスト開始5分後に
「累積和さんはCとDをまだ解いていないし、lowlinkさんはGを解いてないね」
みたいな意味深ツイートされた場合はまあはい
対策は最上位100人間以外コンテスト中匿名化 順位表の情報を絞れば対策容易なので、あとは裁量次第
Pythonのライブラリに詳しいだけの水色が爆速でG通してるな、ギャグか？
みたいな類推の面白さと、つまらなさの兼ね合いで調整してもろて 別にAtC上で行わなくてもいい
・Xでセグ木DP、逆からUFとかの名前の垢をたくさん作る
・コンテスト時に出題された解法と一致するX垢だけ意味深投稿を大量にする(直接解法と言及しないのがミソ)
これで不正として取り締まりようがないでしょ？もちろん人々に垢を知られないと意味ないが、一度誰かがネタにさえすれば終わり。不正と断定できる証拠がない。 ようやくXのインコ界隈も競プロが中受支配的だということに気づき始めてきたな 髪切らなすぎて髪の長さを最大化するAHCで優勝した >>644
それ誰かがやったらお前教唆犯として逮捕な >>647
犯罪の想定解を洗い出すことは犯罪対策に貢献してるぞ 灯油よりガソリンが危険と分かっても
対策の立てようがありませんが 強い人がコンテスト中にいきなりMo's algoの記事にいいねをつけた場合
まあいたちごっこよ 実装力が低すぎてABC微減、ARC/AGC微増or大勝ち何だけどこれどうすれば直る？
ひたすらバチャか？ 思考停止でバグなく書けばよいため
たとえばダイクストラを書くたびに、ヒープの処理に思いを馳せてチンタラ考えるやつらには負けないよそれは >>652
ABC ratedの間は何も考えずに過去問埋め(cfも) 偏差値 70 台の方へ
全国模試でベスト 100 位以内に入れるような高順位を何度も取っていると思います。このレベルだと、勉強自体が楽しくて、模試はゲーム感覚で楽しんでいる方も多いでしょう。そんな中でも、もし算数が特に好きでしたら、算数オリンピックなどに挑戦してみるのも面白いと思います！ 本物の天才パズルの世界が君を待っています！ で、けんちゃんは算数オリ数オリでどこまで行けたの？ >>657
なんでこう普通に避けられる自白をするのかね
>>655
だけならagerに敏感な人以外はスルーだったろうに 334批判してる人が逆に叩かれてるけど、ファンに失礼とかじゃなくて手垢ベタベタのネットミームでキャッキャやられるのだいぶキツイので俺も辞めて欲しいと思う
114514も辞めて欲しい クリスマスという文字列を見るだけで胸が締め付けられる思いになるのに、出題するとはチー牛差別だ！w >>670
あれ叩く側が容赦なさすぎて引いてる
「ちょっと叩かれるくらいでツイート消すくらいなら、はじめから言わないほうがいいとおもいます！」
とか正義感を盾に無謬主義を押し付けてて心底不愉快だった ■ このスレッドは過去ログ倉庫に格納されています
