競技プログラミング総合スレ 64
レス数が1000を超えています。これ以上書き込みはできません。
↑2行になるようにする
競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ
次スレは>>950
AtCoder https://atcoder.jp/
yukicoder https://yukicoder.me/
Codeforces https://codeforces.com/
CodeChef https://codechef.com/
Project Euler https://projecteuler.net/
CLIST https://clist.by/
AtCoder Problems https://kenkoooo.com/atcoder/
AtCoder Clans https://kato-hiro.github.io/AtCoderClans/
※前スレ
競技プログラミング総合スレ 63
https://mevius.5ch.net/test/read.cgi/tech/1627477128
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured >>948
スパルタにすると諦めるからどのみちだめ >>954
詳しい経緯は話してないけど、少し前のツイートで「ICPCのメンバーとは決別した」って言ってたでしょ
今日も練習すっぽかしたって自分で言ってるしチーム内でうまく言ってないんじゃないの 初心者なのですが
ABC262BをACLのDSUを使って解くことは出来ますか？
解説などでは全く使ってなかったので
そもそもの方針が間違ってるのか知りたいです
https://atcoder.jp/contests/abc262/tasks/abc262_b 路じゃなくて辺が存在すればいいからDSUを使う意味がない さっき考えついた問題
はじめ、頂点1つの根付き木（当然その頂点が根）がある。これからN-1の頂点をこのグラフに以下の手順で一つずつ追加する：
・P/Qの確率で新たに加える頂点を根とした新たな根付き木を追加する。辺は加えない。
・1-P/Qの確率で、既にグラフに存在している頂点の一つを一様ランダムに選び、その頂点の子として新たに頂点を加える。
なお、帰納的にこのグラフは根付き木の森になる。このとき、以下の期待値を求めよ。
・根付き木の頂点数の平均値
・根付き木の頂点数の最大値
・根付き木の高さの平均値
・根付き木の高さの最大値
それぞれどの程度の制約でできるか。 >>959
まあちょっと下のやつを見るのが1番楽しいからな >>957
グラフやDSUなど全く理解出来ていない質問でしたすみません いえいえ！全く問題ないです！
色んな解法の解き方を考えると理解が深まるのでいいと思いますよ >>960
これ、できた森ごとに平均とったり最大取ったりするって話だよね？
例えば、頂点数が3の木が2つ、頂点数が2の木が1つの森ができたという状況なら、平均は8/3、最大は3みたいな
一番上はO(N)だけど、他はすぐにはよさげな方法が思いつかないね 例えば二個目だけど、f(n,m,k)をN=n、最大頂点数m、根付き木数kである確率として、f(n,m,k) = Σ_{i<n/m} Σ_{j<n} 何かの係数 * f(n-im,j,k-i)みたいな風なDPだったりするかね？ 1つ目の問題、操作後の木の数の期待値が1+((N-1)P/Q)個で頂点数がN個だから木の頂点数の平均はNQ/((N-1)P+Q)じゃね？って思ったけどもしかして俺トンチンカンな事言ってる？ ｵｯﾍﾟｹ Sr1f-v7Gx
ﾜｯﾁｮｲ 477c-It8h
金玉民はネットWatchにでもスレ立てて勝手にやっててくれ >>967
一般にE[1/X] != 1/E[X]なので、それは成立しないかも？
あ、でも、自分のO(N)解ってp = P/Qとして、
Σ_i p^i (1-p)^(N-1-i) comb(N-1, i)/(i+1)を計算するってやつで、積分使えそうな形だからO(1)でもできそうだね NGでいいでしょ
結局前の板でもネトスト辞めさせられなかったし てか、積分がどうのみたいな話もいらなくて、
N Σ_i p^i (1-p)^(N-1-i) comb(N-1, i)/(i+1)
= p^(i+1) (1-p)^(N-1-i) comb(N, i+1) / p
= (1-(1-p)^N)/p
かね
なんかすごく有名な話から自明に導かれる気がするけど思いだせない まあNGしてスルーしとけばいいんじゃないかな
ありスレは考えようによっていろいろな荒らし対策ができるので こいつ俺と考えることが全く同じで気持ち悪いな 黄溜りだろ 典型性高めの話なので、レベルが近かったら自ずと似たようなこと考えるんじゃないかな >>964
>これ、できた森ごとに平均とったり最大取ったりするって話だよね？
>例えば、頂点数が3の木が2つ、頂点数が2の木が1つの森ができたという状況なら、平均は8/3、最大は3みたいな
その認識であってる ありがとう
てかO(logN)だね、普通にlogは定数をやらかしてた 自分もこの前問題思いついた(既出かもしれない)んだけど、
N個の区間が与えられて、Q個の区間変更クエリに対して毎回区間スケジューリング問題を考える(重ならない区間の数の最大値を答える)って感じの問題なんだけど、これってN、Q≦2×10^5でも出来るかな？
区間に重みが無い場合は差分考えればいけそうな感じもするけど重みがつくと流石に厳しい？ どういう更新をするのか分からないけど、重み無しは解けない？
左からの区間スケジューリングと右からの区間スケジューリングを前計算しておけばいけると思う
重み有りの区間スケジューリングは自分は初めて聞いた 更新無しだとセグ木+DPとか？
重み有りでも左と右から前計算しておけば解けそうだけどなあ あーでも、更新クエリで区間が全然違う場所に移動することを考えると、前計算の意味ないか
嘘解法だった 重みありの区間スケジューリングは端点で座標圧縮してイベントソートした上でDPすれば解ける(蟻本のintervalsっていう問題のk=1の場合でも紹介されている)
一応クエリはオフラインでも可能なものを考えてたんだけどどうだろう ここに業務で詰まってる課題を投げれば解いてくれるって聞いたんですが本当ですか？ chatGPTに投げるとあと一歩で動きそうに見えるコードを書いてくれる あっち荒されてるからやっぱこっちでくんの話題します😭 >>987
ネトストガイジはネットWatch板に自分で巣を作ってどうぞ ガイジスレも政治スレになったから避難所としてここにいるしかないな
自治erもこのスレに移住させたがってたししばらくはここでいいんじゃないか？ 知らない人向けに説明すると、この「くんer」というのはプログラマー板の方で特定の競プロerにずっと粘着し誹謗中傷を繰り返していたやつで、IDなしスレだったのをいいことに自演連投していた疑惑が濃厚 くんerは結構いるっぽいぞ
twitterですら3‐4人見たことあるし
何が楽しいんかね 競プロスレで何が楽しいのかねはブーメランすぎるだろ そんなこといっても話題にしちゃうやつがいるから、別板の競プロスレでは困ってた
でもここならワッチョイのおかけでそれほど騒がれないだろうから比較的大丈夫かと atcoderのABCのBやC問題までの話ですが
提出で他者のコードと違いが無いのにほぼ毎回5ms前後差が付くのは誤差なんでしょうか？
例えば最速の1msのコードをコピペして提出しても差が出ます
特にテストケースの1つ目が極端に遅くて例えば10msで
それ以降は全て1msか2msなのに1つ目が10msなので結果が10msになってしまいます
気にするレベルでは無いと思いますが素朴な疑問です 競プロの実行時間にはある程度誤差がつくよ
だから時間制限ギリギリのコードが誤差で落ちないように、TLEが出ても内部的には3回ジャッジし直してる
あと最初のケースだけ遅いというのもよくある（立ち上げ時のオーバーヘッド？） このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 87日 9時間 22分 12秒 5ちゃんねるの運営はプレミアム会員の皆さまに支えられています。
運営にご協力お願いいたします。
───────────────────
《プレミアム会員の主な特典》
★ 5ちゃんねる専用ブラウザからの広告除去
★ 5ちゃんねるの過去ログを取得
★ 書き込み規制の緩和
───────────────────
会員登録には個人情報は一切必要ありません。
月300円から匿名でご購入いただけます。
▼ プレミアム会員登録はこちら ▼
https://premium.5ch.net/
▼ 浪人ログインはこちら ▼
https://login.5ch.net/login.php レス数が1000を超えています。これ以上書き込みはできません。
