競技プログラミング総合スレ 64

競技プログラミング総合スレ 64 at TECH

[前50を表示]
950:デフォルトの名無しさん (ﾜｯﾁｮｲ 7bd7-CvDm)
22/12/26 19:54:14.04 45xsZ8H/0.net
>>948
まあちょっと下のやつを見るのが1番楽しいからな

951:デフォルトの名無しさん (ﾜｯﾁｮｲ 17e6-dxp0)
22/12/26 20:12:21.63 qC77tL+z0.net
>>946
グラフやDSUなど全く理解出来ていない質問でしたすみません

952:デフォルトの名無しさん
22/12/26 20:18:45.79 CkzYHyzir.net
いえいえ！全く問題ないです！
色んな解法の解き方を考えると理解が深まるのでいいと思いますよ

953:デフォルトの名無しさん
22/12/26 21:33:49.83 0EESOEy50.net
>>949
これ、できた森ごとに平均とったり最大取ったりするって話だよね？
例えば、頂点数が3の木が2つ、頂点数が2の木が1つの森ができたという状況なら、平均は8/3、最大は3みたいな
一番上はO(N)だけど、他はすぐにはよさげな方法が思いつかないね

954:デフォルトの名無しさん
22/12/26 21:35:18.96 0EESOEy50.net
例えば二個目だけど、f(n,m,k)をN=n、最大頂点数m、根付き木数kである確率として、f(n,m,k) = Σ_{i<n/m} Σ_{j<n} 何かの係数 * f(n-im,j,k-i)みたいな風なDPだったりするかね？

955:デフォルトの名無しさん
22/12/26 22:11:29.09 A4uXrTBpH.net
高さの方はさらにむずいな

956:デフォルトの名無しさん
22/12/26 22:32:21.55 89yBpVXU0.net
1つ目の問題、操作後の木の数の期待値が1+((N-1)P/Q)個で頂点数がN個だから木の頂点数の平均はNQ/((N-1)P+Q)じゃね？って思ったけどもしかして俺トンチンカンな事言ってる？

957:デフォルトの名無しさん
22/12/26 22:38:07.30 lgGpVqEr0.net
ｵｯﾍﾟｹ Sr1f-v7Gx
ﾜｯﾁｮｲ 477c-It8h
金玉民はネットWatchにでもスレ立てて勝手にやっててくれ

958:デフォルトの名無しさん
22/12/26 22:49:50.80 0EESOEy50.net
>>956
一般に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)でもできそうだね

959:デフォルトの名無しさん
22/12/26 23:02:59.61 89yBpVXU0.net
NGでいいでしょ
結局前の板でもネトスト辞めさせられなかったし

960:デフォルトの名無しさん
22/12/26 23:05:37.69 0EESOEy50.net
てか、積分がどうのみたいな話もいらなくて、
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
かね
なんかすごく有名な話から自明に導かれる気がするけど思いだせない

961:デフォルトの名無しさん
22/12/26 23:10:06.86 0EESOEy50.net
まあNGしてスルーしとけばいいんじゃないかな
ありスレは考えようによっていろいろな荒らし対策ができるので

962:デフォルトの名無しさん
22/12/26 23:11:27.69 0EESOEy50.net
>>960
二行目Σが抜けてる

963:デフォルトの名無しさん
22/12/26 23:13:00.30 DjfcghMN0.net
こいつ俺と考えることが全く同じで気持ち悪いな黄溜りだろ

964:デフォルトの名無しさん
22/12/26 23:15:08.45 0EESOEy50.net
典型性高めの話なので、レベルが近かったら自ずと似たようなこと考えるんじゃないかな

965:デフォルトの名無しさん
22/12/26 23:17:26.16 DjfcghMN0.net
いなすのが上手

966:デフォルトの名無しさん
22/12/26 23:34:21.03 0neW5JWbM.net
>>953
>これ、できた森ごとに平均とったり最大取ったりするって話だよね？
>例えば、頂点数が3の木が2つ、頂点数が2の木が1つの森ができたという状況なら、平均は8/3、最大は3みたいな
その認識であってる

967:デフォルトの名無しさん
22/12/26 23:41:02.76 0EESOEy50.net
ありがとう
てかO(logN)だね、普通にlogは定数をやらかしてた

968:デフォルトの名無しさん
22/12/27 00:59:43.64 q4+xdjXF0.net
自分もこの前問題思いついた(既出かもしれない)んだけど、
N個の区間が与えられて、Q個の区間変更クエリに対して毎回区間スケジューリング問題を考える(重ならない区間の数の最大値を答える)って感じの問題なんだけど、これってN、Q≦2×10^5でも出来るかな？
区間に重みが無い場合は差分考えればいけそうな感じもするけど重みがつくと流石に厳しい？

969:デフォルトの名無しさん
22/12/27 04:13:23.69 Dyt+8YEa0.net
重み無しでも10^5は無理だと思う

970:デフォルトの名無しさん
22/12/27 07:21:55.50 4MTJolmy0.net
どういう更新をするのか分からないけど、重み無しは解けない？
左からの区間スケジューリングと右からの区間スケジューリングを前計算しておけばいけると思う
重み有りの区間スケジューリングは自分は初めて聞いた更新無しだとセグ木+DPとか？
重み有りでも左と右から前計算しておけば解けそうだけどなあ

971:デフォルトの名無しさん
22/12/27 07:30:35.83 4MTJolmy0.net
あーでも、更新クエリで区間が全然違う場所に移動することを考えると、前計算の意味ないか
嘘解法だった

972:デフォルトの名無しさん
22/12/27 07:53:19.24 q4+xdjXF0.net
重みありの区間スケジューリングは端点で座標圧縮してイベントソートした上でDPすれば解ける(蟻本のintervalsっていう問題のk=1の場合でも紹介されている)
一応クエリはオフラインでも可能なものを考えてたんだけどどうだろう

973:デフォルトの名無しさん (ｵｯﾍﾟｹ Sref-1V6l)
22/12/27 08:40:43.45 04KLziRpr.net
ここに業務で詰まってる課題を投げれば解いてくれるって聞いたんですが本当ですか？

974:デフォルトの名無しさん
22/12/27 09:08:16.53 ImJeuIiNr.net
競プロ風に形成すれば解いてくれそう

975:デフォルトの名無しさん
22/12/27 11:19:54.22 8jh3A4jF0.net
chatGPTに投げるとあと一歩で動きそうに見えるコードを書いてくれる

976:デフォルトの名無しさん
22/12/27 22:55:47.95 v6hw5ZGxr.net
あっち荒されてるからやっぱこっちでくんの話題します😭

977:デフォルトの名無しさん
22/12/27 23:59:27.38 wEYGAABC0.net
>>976
ネトストガイジはネットWatch板に自分で巣を作ってどうぞ

978:デフォルトの名無しさん (ﾜｯﾁｮｲ 7bd7-pcZM)
22/12/28 00:32:52.20 3WFyEPkg0.net
ガイジスレも政治スレになったから避難所としてここにいるしかないな
自治erもこのスレに移住させたがってたししばらくはここでいいんじゃないか？

979:デフォルトの名無しさん
22/12/28 10:16:36.58 Pwm0wo/5M.net
知らない人向けに説明すると、この「くんer」というのはプログラマー板の方で特定の競プロerにずっと粘着し誹謗中傷を繰り返していたやつで、IDなしスレだったのをいいことに自演連投していた疑惑が濃厚

980:デフォルトの名無しさん
22/12/28 10:28:57.44 7xHkkVHZ0.net
くんerは結構いるっぽいぞ
twitterですら3‐4人見たことあるし
何が楽しいんかね

981:デフォルトの名無しさん
22/12/28 11:28:34.57 RKKh2wvkr.net
競プロスレで何が楽しいのかねはブーメランすぎるだろ

982:デフォルトの名無しさん
22/12/28 11:38:59.90 Jjpf13Inr.net
スゲー楽しいぞ

983:デフォルトの名無しさん
22/12/28 11:46:30.15 adfqLiPC0.net
知らんけど今ここにいないなら話題にしなくてよくね

984:デフォルトの名無しさん
22/12/28 11:55:15.82 a6/n2za+0.net
そんなこといっても話題にしちゃうやつがいるから、別板の競プロスレでは困ってた
でもここならワッチョイのおかけでそれほど騒がれないだろうから比較的大丈夫かと

985:デフォルトの名無しさん
22/12/28 12:03:12.23 Pwm0wo/5M.net
まあ基本ワッチョイでNGしとけば特に問題ない

986:デフォルトの名無しさん
22/12/28 22:32:17.07 NhN6GB+q0.net
atcoderのABCのBやC問題までの話ですが
提出で他者のコードと違いが無いのにほぼ毎回5ms前後差が付くのは誤差なんでしょうか？
例えば最速の1msのコードをコピペして提出しても差が出ます
特にテストケースの1つ目が極端に遅くて例えば10msで
それ以降は全て1msか2msなのに1つ目が10msなので結果が10msになってしまいます
気にするレベルでは無いと思いますが素朴な疑問です

987:デフォルトの名無しさん
22/12/28 22:51:38.98 wMJvQkVC0.net
競プロの実行時間にはある程度誤差がつくよ
だから時間制限ギリギリのコードが誤差で落ちないように、TLEが出ても内部的には3回ジャッジし直してる
あと最初のケースだけ遅いというのもよくある（立ち上げ時のオーバーヘッド？）

988:デフォルトの名無しさん
22/12/28 23:21:16.62 fZQHMcStr.net
AHCの途中とか1.3倍くらいになったときある

989:デフォルトの名無しさん
22/12/29 03:06:10.71 UML/N/VX0.net
1000ゲット！😎

990:1001
Over 1000 Thread.net
このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 87日 9時間 22分 12秒