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

2022/10/02(日) 17:43:58.66

↑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

2022/12/26(月) 22:38:07.30

ｵｯﾍﾟｹ Sr1f-v7Gx
ﾜｯﾁｮｲ 477c-It8h
金玉民はネットWatchにでもスレ立てて勝手にやっててくれ

2022/12/26(月) 22:49:50.80

>>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)でもできそうだね

2022/12/26(月) 23:02:59.61

NGでいいでしょ
結局前の板でもネトスト辞めさせられなかったし

2022/12/26(月) 23:05:37.69

てか、積分がどうのみたいな話もいらなくて、
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
かね
なんかすごく有名な話から自明に導かれる気がするけど思いだせない

2022/12/26(月) 23:10:06.86

まあNGしてスルーしとけばいいんじゃないかな
ありスレは考えようによっていろいろな荒らし対策ができるので

2022/12/26(月) 23:11:27.69

>>971
二行目Σが抜けてる

2022/12/26(月) 23:13:00.30

こいつ俺と考えることが全く同じで気持ち悪いな黄溜りだろ

2022/12/26(月) 23:15:08.45

典型性高めの話なので、レベルが近かったら自ずと似たようなこと考えるんじゃないかな

2022/12/26(月) 23:17:26.16

いなすのが上手

2022/12/26(月) 23:34:21.03

>>964
>これ、できた森ごとに平均とったり最大取ったりするって話だよね？
>例えば、頂点数が3の木が2つ、頂点数が2の木が1つの森ができたという状況なら、平均は8/3、最大は3みたいな

その認識であってる

2022/12/26(月) 23:41:02.76

ありがとう
てかO(logN)だね、普通にlogは定数をやらかしてた

2022/12/27(火) 00:59:43.64

自分もこの前問題思いついた(既出かもしれない)んだけど、
N個の区間が与えられて、Q個の区間変更クエリに対して毎回区間スケジューリング問題を考える(重ならない区間の数の最大値を答える)って感じの問題なんだけど、これってN、Q≦2×10^5でも出来るかな？

区間に重みが無い場合は差分考えればいけそうな感じもするけど重みがつくと流石に厳しい？

2022/12/27(火) 04:13:23.69

重み無しでも10^5は無理だと思う

2022/12/27(火) 07:21:55.50

どういう更新をするのか分からないけど、重み無しは解けない？
左からの区間スケジューリングと右からの区間スケジューリングを前計算しておけばいけると思う
重み有りの区間スケジューリングは自分は初めて聞いた更新無しだとセグ木+DPとか？
重み有りでも左と右から前計算しておけば解けそうだけどなあ

2022/12/27(火) 07:30:35.83

あーでも、更新クエリで区間が全然違う場所に移動することを考えると、前計算の意味ないか
嘘解法だった

2022/12/27(火) 07:53:19.24

重みありの区間スケジューリングは端点で座標圧縮してイベントソートした上でDPすれば解ける(蟻本のintervalsっていう問題のk=1の場合でも紹介されている)
一応クエリはオフラインでも可能なものを考えてたんだけどどうだろう

2022/12/27(火) 08:40:43.45

ここに業務で詰まってる課題を投げれば解いてくれるって聞いたんですが本当ですか？

2022/12/27(火) 09:08:16.53

競プロ風に形成すれば解いてくれそう

2022/12/27(火) 11:19:54.22

chatGPTに投げるとあと一歩で動きそうに見えるコードを書いてくれる

2022/12/27(火) 22:55:47.95

あっち荒されてるからやっぱこっちでくんの話題します😭

2022/12/27(火) 23:59:27.38

>>987
ネトストガイジはネットWatch板に自分で巣を作ってどうぞ

2022/12/28(水) 00:32:52.20

ガイジスレも政治スレになったから避難所としてここにいるしかないな
自治erもこのスレに移住させたがってたししばらくはここでいいんじゃないか？

2022/12/28(水) 10:16:36.58

知らない人向けに説明すると、この「くんer」というのはプログラマー板の方で特定の競プロerにずっと粘着し誹謗中傷を繰り返していたやつで、IDなしスレだったのをいいことに自演連投していた疑惑が濃厚

2022/12/28(水) 10:28:57.44

くんerは結構いるっぽいぞ
twitterですら3‐4人見たことあるし
何が楽しいんかね

2022/12/28(水) 11:28:34.57

競プロスレで何が楽しいのかねはブーメランすぎるだろ

2022/12/28(水) 11:38:59.90

スゲー楽しいぞ

2022/12/28(水) 11:46:30.15

知らんけど今ここにいないなら話題にしなくてよくね

2022/12/28(水) 11:55:15.82

そんなこといっても話題にしちゃうやつがいるから、別板の競プロスレでは困ってた
でもここならワッチョイのおかけでそれほど騒がれないだろうから比較的大丈夫かと

2022/12/28(水) 12:03:12.23

まあ基本ワッチョイでNGしとけば特に問題ない

2022/12/28(水) 22:32:17.07

atcoderのABCのBやC問題までの話ですが
提出で他者のコードと違いが無いのにほぼ毎回5ms前後差が付くのは誤差なんでしょうか？

例えば最速の1msのコードをコピペして提出しても差が出ます
特にテストケースの1つ目が極端に遅くて例えば10msで
それ以降は全て1msか2msなのに1つ目が10msなので結果が10msになってしまいます
気にするレベルでは無いと思いますが素朴な疑問です

2022/12/28(水) 22:51:38.98

競プロの実行時間にはある程度誤差がつくよ
だから時間制限ギリギリのコードが誤差で落ちないように、TLEが出ても内部的には3回ジャッジし直してる
あと最初のケースだけ遅いというのもよくある（立ち上げ時のオーバーヘッド？）

2022/12/28(水) 23:21:16.62

AHCの途中とか1.3倍くらいになったときある

2022/12/29(木) 03:06:10.71

1000ゲット！😎

**1001** · Over 1000

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