競技プログラミング総合スレ 64
- 1 :デフォルトの名無しさん (ラクッペペ MM7f-osoq):[ここ壊れてます] .net
- ↑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
- 941 :デフォルトの名無しさん :2022/12/26(月) 14:12:14.71 ID:oDvkMIGt0.net
- >>940
これは実務赤、有能
- 942 :デフォルトの名無しさん :2022/12/26(月) 17:56:28.72 ID:5LxkM09pa.net
- >>937
スパルタにすると諦めるからどのみちだめ
- 943 :デフォルトの名無しさん :2022/12/26(月) 18:18:11.69 ID:CkzYHyzir.net
- くん、ICPCメンバーと何かあったんか?
- 944 :デフォルトの名無しさん :2022/12/26(月) 18:49:12.07 ID:KxFT/wbk0.net
- >>943
詳しい経緯は話してないけど、少し前のツイートで「ICPCのメンバーとは決別した」って言ってたでしょ
今日も練習すっぽかしたって自分で言ってるしチーム内でうまく言ってないんじゃないの
- 945 :デフォルトの名無しさん :2022/12/26(月) 18:57:58.08 ID:qC77tL+z0.net
- 初心者なのですが
ABC262BをACLのDSUを使って解くことは出来ますか?
解説などでは全く使ってなかったので
そもそもの方針が間違ってるのか知りたいです
https://atcoder.jp/contests/abc262/tasks/abc262_b
- 946 :デフォルトの名無しさん :2022/12/26(月) 19:08:08.06 ID:CkzYHyzir.net
- 路じゃなくて辺が存在すればいいからDSUを使う意味がない
- 947 :デフォルトの名無しさん :2022/12/26(月) 19:20:29.16 ID:BJooufdOr.net
- >>944
うーんこの
- 948 :デフォルトの名無しさん :2022/12/26(月) 19:22:13.79 ID:89yBpVXU0.net
- >>946
くんer、偏見だけど水色くらいそう
- 949 :デフォルトの名無しさん :2022/12/26(月) 19:25:08.31 ID:TDmnxh2KM.net
- さっき考えついた問題
はじめ、頂点1つの根付き木(当然その頂点が根)がある。これからN-1の頂点をこのグラフに以下の手順で一つずつ追加する:
・P/Qの確率で新たに加える頂点を根とした新たな根付き木を追加する。辺は加えない。
・1-P/Qの確率で、既にグラフに存在している頂点の一つを一様ランダムに選び、その頂点の子として新たに頂点を加える。
なお、帰納的にこのグラフは根付き木の森になる。このとき、以下の期待値を求めよ。
・根付き木の頂点数の平均値
・根付き木の頂点数の最大値
・根付き木の高さの平均値
・根付き木の高さの最大値
それぞれどの程度の制約でできるか。
- 950 :デフォルトの名無しさん (ワッチョイ 7bd7-CvDm):2022/12/26(月) 19:54:14.04 ID:45xsZ8H/0.net
- >>948
まあちょっと下のやつを見るのが1番楽しいからな
- 951 :デフォルトの名無しさん (ワッチョイ 17e6-dxp0):2022/12/26(月) 20:12:21.63 ID:qC77tL+z0.net
- >>946
グラフやDSUなど全く理解出来ていない質問でしたすみません
- 952 :デフォルトの名無しさん :2022/12/26(月) 20:18:45.79 ID:CkzYHyzir.net
- いえいえ!全く問題ないです!
色んな解法の解き方を考えると理解が深まるのでいいと思いますよ
- 953 :デフォルトの名無しさん :2022/12/26(月) 21:33:49.83 ID:0EESOEy50.net
- >>949
これ、できた森ごとに平均とったり最大取ったりするって話だよね?
例えば、頂点数が3の木が2つ、頂点数が2の木が1つの森ができたという状況なら、平均は8/3、最大は3みたいな
一番上はO(N)だけど、他はすぐにはよさげな方法が思いつかないね
- 954 :デフォルトの名無しさん :2022/12/26(月) 21:35:18.96 ID: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 :デフォルトの名無しさん :2022/12/26(月) 22:11:29.09 ID:A4uXrTBpH.net
- 高さの方はさらにむずいな
- 956 :デフォルトの名無しさん :2022/12/26(月) 22:32:21.55 ID:89yBpVXU0.net
- 1つ目の問題、操作後の木の数の期待値が1+((N-1)P/Q)個で頂点数がN個だから木の頂点数の平均はNQ/((N-1)P+Q)じゃね?って思ったけどもしかして俺トンチンカンな事言ってる?
- 957 :デフォルトの名無しさん :2022/12/26(月) 22:38:07.30 ID:lgGpVqEr0.net
- オッペケ Sr1f-v7Gx
ワッチョイ 477c-It8h
金玉民はネットWatchにでもスレ立てて勝手にやっててくれ
- 958 :デフォルトの名無しさん :2022/12/26(月) 22:49:50.80 ID: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 :デフォルトの名無しさん :2022/12/26(月) 23:02:59.61 ID:89yBpVXU0.net
- NGでいいでしょ
結局前の板でもネトスト辞めさせられなかったし
- 960 :デフォルトの名無しさん :2022/12/26(月) 23:05:37.69 ID: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 :デフォルトの名無しさん :2022/12/26(月) 23:10:06.86 ID:0EESOEy50.net
- まあNGしてスルーしとけばいいんじゃないかな
ありスレは考えようによっていろいろな荒らし対策ができるので
- 962 :デフォルトの名無しさん :2022/12/26(月) 23:11:27.69 ID:0EESOEy50.net
- >>960
二行目Σが抜けてる
- 963 :デフォルトの名無しさん :2022/12/26(月) 23:13:00.30 ID:DjfcghMN0.net
- こいつ俺と考えることが全く同じで気持ち悪いな 黄溜りだろ
- 964 :デフォルトの名無しさん :2022/12/26(月) 23:15:08.45 ID:0EESOEy50.net
- 典型性高めの話なので、レベルが近かったら自ずと似たようなこと考えるんじゃないかな
- 965 :デフォルトの名無しさん :2022/12/26(月) 23:17:26.16 ID:DjfcghMN0.net
- いなすのが上手
- 966 :デフォルトの名無しさん :2022/12/26(月) 23:34:21.03 ID:0neW5JWbM.net
- >>953
>これ、できた森ごとに平均とったり最大取ったりするって話だよね?
>例えば、頂点数が3の木が2つ、頂点数が2の木が1つの森ができたという状況なら、平均は8/3、最大は3みたいな
その認識であってる
- 967 :デフォルトの名無しさん :2022/12/26(月) 23:41:02.76 ID:0EESOEy50.net
- ありがとう
てかO(logN)だね、普通にlogは定数をやらかしてた
- 968 :デフォルトの名無しさん :2022/12/27(火) 00:59:43.64 ID:q4+xdjXF0.net
- 自分もこの前問題思いついた(既出かもしれない)んだけど、
N個の区間が与えられて、Q個の区間変更クエリに対して毎回区間スケジューリング問題を考える(重ならない区間の数の最大値を答える)って感じの問題なんだけど、これってN、Q≦2×10^5でも出来るかな?
区間に重みが無い場合は差分考えればいけそうな感じもするけど重みがつくと流石に厳しい?
- 969 :デフォルトの名無しさん :2022/12/27(火) 04:13:23.69 ID:Dyt+8YEa0.net
- 重み無しでも10^5は無理だと思う
- 970 :デフォルトの名無しさん :2022/12/27(火) 07:21:55.50 ID:4MTJolmy0.net
- どういう更新をするのか分からないけど、重み無しは解けない?
左からの区間スケジューリングと右からの区間スケジューリングを前計算しておけばいけると思う
重み有りの区間スケジューリングは自分は初めて聞いた 更新無しだとセグ木+DPとか?
重み有りでも左と右から前計算しておけば解けそうだけどなあ
- 971 :デフォルトの名無しさん :2022/12/27(火) 07:30:35.83 ID:4MTJolmy0.net
- あーでも、更新クエリで区間が全然違う場所に移動することを考えると、前計算の意味ないか
嘘解法だった
- 972 :デフォルトの名無しさん :2022/12/27(火) 07:53:19.24 ID:q4+xdjXF0.net
- 重みありの区間スケジューリングは端点で座標圧縮してイベントソートした上でDPすれば解ける(蟻本のintervalsっていう問題のk=1の場合でも紹介されている)
一応クエリはオフラインでも可能なものを考えてたんだけどどうだろう
- 973 :デフォルトの名無しさん (オッペケ Sref-1V6l):2022/12/27(火) 08:40:43.45 ID:04KLziRpr.net
- ここに業務で詰まってる課題を投げれば解いてくれるって聞いたんですが本当ですか?
- 974 :デフォルトの名無しさん :2022/12/27(火) 09:08:16.53 ID:ImJeuIiNr.net
- 競プロ風に形成すれば解いてくれそう
- 975 :デフォルトの名無しさん :2022/12/27(火) 11:19:54.22 ID:8jh3A4jF0.net
- chatGPTに投げるとあと一歩で動きそうに見えるコードを書いてくれる
- 976 :デフォルトの名無しさん :2022/12/27(火) 22:55:47.95 ID:v6hw5ZGxr.net
- あっち荒されてるからやっぱこっちでくんの話題します😭
- 977 :デフォルトの名無しさん :2022/12/27(火) 23:59:27.38 ID:wEYGAABC0.net
- >>976
ネトストガイジはネットWatch板に自分で巣を作ってどうぞ
- 978 :デフォルトの名無しさん (ワッチョイ 7bd7-pcZM):2022/12/28(水) 00:32:52.20 ID:3WFyEPkg0.net
- ガイジスレも政治スレになったから避難所としてここにいるしかないな
自治erもこのスレに移住させたがってたししばらくはここでいいんじゃないか?
- 979 :デフォルトの名無しさん :2022/12/28(水) 10:16:36.58 ID:Pwm0wo/5M.net
- 知らない人向けに説明すると、この「くんer」というのはプログラマー板の方で特定の競プロerにずっと粘着し誹謗中傷を繰り返していたやつで、IDなしスレだったのをいいことに自演連投していた疑惑が濃厚
- 980 :デフォルトの名無しさん :2022/12/28(水) 10:28:57.44 ID:7xHkkVHZ0.net
- くんerは結構いるっぽいぞ
twitterですら3‐4人見たことあるし
何が楽しいんかね
- 981 :デフォルトの名無しさん :2022/12/28(水) 11:28:34.57 ID:RKKh2wvkr.net
- 競プロスレで何が楽しいのかねはブーメランすぎるだろ
- 982 :デフォルトの名無しさん :2022/12/28(水) 11:38:59.90 ID:Jjpf13Inr.net
- スゲー楽しいぞ
- 983 :デフォルトの名無しさん :2022/12/28(水) 11:46:30.15 ID:adfqLiPC0.net
- 知らんけど今ここにいないなら話題にしなくてよくね
- 984 :デフォルトの名無しさん :2022/12/28(水) 11:55:15.82 ID:a6/n2za+0.net
- そんなこといっても話題にしちゃうやつがいるから、別板の競プロスレでは困ってた
でもここならワッチョイのおかけでそれほど騒がれないだろうから比較的大丈夫かと
- 985 :デフォルトの名無しさん :2022/12/28(水) 12:03:12.23 ID:Pwm0wo/5M.net
- まあ基本ワッチョイでNGしとけば特に問題ない
- 986 :デフォルトの名無しさん :2022/12/28(水) 22:32:17.07 ID:NhN6GB+q0.net
- atcoderのABCのBやC問題までの話ですが
提出で他者のコードと違いが無いのにほぼ毎回5ms前後差が付くのは誤差なんでしょうか?
例えば最速の1msのコードをコピペして提出しても差が出ます
特にテストケースの1つ目が極端に遅くて例えば10msで
それ以降は全て1msか2msなのに1つ目が10msなので結果が10msになってしまいます
気にするレベルでは無いと思いますが素朴な疑問です
- 987 :デフォルトの名無しさん :2022/12/28(水) 22:51:38.98 ID:wMJvQkVC0.net
- 競プロの実行時間にはある程度誤差がつくよ
だから時間制限ギリギリのコードが誤差で落ちないように、TLEが出ても内部的には3回ジャッジし直してる
あと最初のケースだけ遅いというのもよくある(立ち上げ時のオーバーヘッド?)
- 988 :デフォルトの名無しさん :2022/12/28(水) 23:21:16.62 ID:fZQHMcStr.net
- AHCの途中とか1.3倍くらいになったときある
- 989 :デフォルトの名無しさん :2022/12/29(木) 03:06:10.71 ID:UML/N/VX0.net
- 1000ゲット!😎
- 990 :2ch.net投稿限界:Over 1000 Thread
- 2ch.netからのレス数が1000に到達しました。
230 KB
新着レスの表示
掲示板に戻る
全部
前100
次100
最新50
read.cgi ver 2014.07.20.01.SC 2014/07/20 D ★