競技プログラミング総合スレ 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/24(土) 12:37:53.51

プログラムで活躍としては
センスのみ<知識のみ<<<知識+センス
なんだよ
これで勘違いが起きることが多い

知識のみしかもってないと一見最上なんだけど、実は何も産み出さない

知識のみでも誰かがセンスを持ってると一気に有益なものが産み出される
つまりピースを埋められる存在になれるかどうかで活躍は変わってくる

2022/12/24(土) 18:09:57.90

今日のコンテストはどうなるんですか

2022/12/24(土) 22:41:01.66

ギリギリ解けたけどEムズいよ

2022/12/24(土) 22:46:01.54

E解けないからFから解いたんだけどFもFで計算量的に大丈夫なのか？って疑ってた最初の方に思いついた解法(ユーザー解説の奴)が他の解法で悩んだ挙句普通に通ったからあまりスッキリしない

2022/12/24(土) 22:55:16.29

D計算時間を解決できなかった
配列とコンテナで管理するのが速いのかー。
アイデアはあったけどどれが最適かわかんなかった

2022/12/24(土) 23:18:12.92

Eのdp複雑すぎて草

2022/12/24(土) 23:24:36.98

最近のE難しい気がする

2022/12/24(土) 23:30:32.81

D、問題文誤読して違うことやってたのにACになってた
（誤答になる入力が存在することは確認済み）

2022/12/24(土) 23:35:14.60

(a(b)a)がyesでも通るって話題になってるね

2022/12/25(日) 10:23:23.93

yesでも通るというかNoが通らず不正解になると言う方が状況を誤解なく伝えられるんじゃね

2022/12/25(日) 10:47:58.50

ABC283
そもそもの難度調整が下手すぎないか？よく考えて作ってるのか疑問

2022/12/25(日) 10:54:07.27

難易度言うならそもそもABCでD以上出さなくていんじゃね
D以上はARCに回せばいい
レーティングも400まででいいよ

2022/12/25(日) 12:35:37.19

黄色以上は解答できなくして賞金も貰えないようにすればいいよ

2022/12/25(日) 13:12:05.09

昔青だった人が水色なんだからビギナーコンテストはmax水色~緑下で十分すぎる

2022/12/25(日) 14:00:20.35

AGCって1200無くても受けて良いの？
暇だし受けてみようかな

2022/12/25(日) 15:04:24.59

レートつかないだけで参加できると思うよ

2022/12/25(日) 15:41:34.02

ABC上位中国勢ばかりやんけ
少し前より青→黄の難易度かなり上がってそう

2022/12/25(日) 19:32:07.15

>>912
あー、レートつかないのか。なら後日でも良いか

2022/12/25(日) 19:34:29.29

人類の5人に一人が中国人だから。
石を5個投げれば一つは中国人に当たる。

2022/12/25(日) 19:45:56.78

rated上位はマジで中国人がほとんど

2022/12/25(日) 19:48:23.57

理由はしらんけど、どうやら中国勢は現在のレートが実際の実力に追いついてないひとが多すぎるから
だから中国人がたくさん参加するとパフォがちょっと渋くなるかもしれんなあ

2022/12/25(日) 19:49:02.80

中国って中高生くらいで強い人多いけど競プロの塾とか競プロの中国語の参考書とかもあるのかな

2022/12/25(日) 19:52:07.11

この前2012年生まれの中国人の赤いたぞ
年齢詐称じゃなかったらすごいな

2022/12/25(日) 19:56:16.55

>>918
塾はあるらしい
情報オリンピックで活躍できたら、好きな大学に入れるから高校生ががんばるらしい

参考書については、おれたしか2008年くらいにICPC対策の英語の参考書みたいなの買ったことあるんだけど、たしかそのオリジナルが中国語だったはず（俺が買ったのは英語に翻訳されたバージョン）
まあ今ならきっとかなりたくさんあるでしょ

2022/12/25(日) 20:13:44.45

なんだ塾があるのか。
勉強したらできて当たり前だな。
中国人はしょせん中国人にすぎないな。

↑って、ネトウヨが言い出しそう。

2022/12/25(日) 20:23:10.79

中国なら有り得そうとも思うが同時に詐称も沢山いるしなあ

2022/12/25(日) 20:40:15.68

ネトウヨって結局、清和会のために統一教会を支持してる奴らだろ？
国益だの愛国だの言ってるけど、その国というのは韓国のことだろう。

2022/12/25(日) 21:12:16.73

ITは超左だからそういうのはないんじゃ

2022/12/25(日) 22:10:30.90

>>923
頭が悪いからパヨクになっちゃうの？
それともパヨクだから頭悪くなるの？

2022/12/25(日) 22:17:25.74

>>925
いまは社会科で習わないのか？
ネトウヨは自民党清和会、つまり韓国朴正煕派閥。
パヨクは社会党、つまり朝鮮総連派閥。

2022/12/25(日) 22:39:50.62

>>926
最近のネトウヨは嫌韓じゃないのか・・・
清和会のせいでややこしいな

2022/12/25(日) 22:43:35.02

>>927
金大中暗殺未遂事件とかも習わないのか？

2022/12/25(日) 23:25:15.62

>>927
元々ネトウヨを作ったのが韓国人だろ。
いいように操られやがって。

2022/12/25(日) 23:27:58.85

私を貶しても何もでないよ🥺

2022/12/25(日) 23:32:02.62

>>930
なんか出せよ。

2022/12/25(日) 23:45:09.06

統一教会は日本で、ゆとりある教育を提唱しているが、韓国では全く逆のことを言ってるからな。
騙されるなよ。

2022/12/25(日) 23:46:50.19

三角関数は高度な数学じゃないぞ。
全員が知っていなければならない基本的な算数だからな。
統一教会派の国会議員に騙されるなよ。

2022/12/26(月) 00:01:23.73

snukeさん滑り込んだな
にしても中国が多い

2022/12/26(月) 00:03:13.58

tourist敗れるのも日常風景になってきた

2022/12/26(月) 00:06:51.77

前の二つの状態を持つDP、前日のABCでもあったのにDPしなくても掛けていけば求まると迷走して1完遅解きだからダメダメだ
Bもどう実験すれば思いつけるのか

2022/12/26(月) 00:07:49.33

タイムリーだね
すぬけさんやtouristいなかったら本当に中国勢が強い
横綱さんもかなりすごい

2022/12/26(月) 00:11:02.93

chokudaiも3000の実力ないとか言いながらしっかり34位か

2022/12/26(月) 01:50:16.22

すみません、くんerですけど明日からこっち書き込みます

2022/12/26(月) 01:57:43.17

ワスも本格的にこっちに進出じゃい(´・ω・`)

2022/12/26(月) 02:03:28.25

もしngしたかったら
1週間毎にｵｯﾍﾟｹ Sr1f-v7GxのｵｯﾍﾟｹSr以外の部分をngお願いします(前2桁はよく変わるので)

2022/12/26(月) 02:07:40.38

こんな感じで

2022/12/26(月) 02:07:53.69

変わってねぇ...

2022/12/26(月) 02:07:56.66

くんer真面目かよ

2022/12/26(月) 02:46:07.41

うんち！w

2022/12/26(月) 03:47:58.81

誰

2022/12/26(月) 08:20:22.77

今の日本の若い人って頑張らないし甘やかされてるしそりゃ全体的な競争力低くもなるわ

2022/12/26(月) 12:27:01.64

競争力を上げるためにはもっとスパルタにせねば、とお考えなのですね

2022/12/26(月) 12:45:34.28

暇だからスレ立てる

2022/12/26(月) 12:45:46.11

950

2022/12/26(月) 12:47:59.32

競技プログラミング総合スレ 65
https://mevius.5ch.net/test/read.cgi/tech/1672026457/

建てたにょ

2022/12/26(月) 14:12:14.71

>>951
これは実務赤、有能

2022/12/26(月) 17:56:28.72

>>948
スパルタにすると諦めるからどのみちだめ

2022/12/26(月) 18:18:11.69

くん、ICPCメンバーと何かあったんか？

2022/12/26(月) 18:49:12.07

>>954
詳しい経緯は話してないけど、少し前のツイートで「ICPCのメンバーとは決別した」って言ってたでしょ
今日も練習すっぽかしたって自分で言ってるしチーム内でうまく言ってないんじゃないの

2022/12/26(月) 18:57:58.08

初心者なのですが
ABC262BをACLのDSUを使って解くことは出来ますか？
解説などでは全く使ってなかったので
そもそもの方針が間違ってるのか知りたいです
https://atcoder.jp/contests/abc262/tasks/abc262_b

2022/12/26(月) 19:08:08.06

路じゃなくて辺が存在すればいいからDSUを使う意味がない

2022/12/26(月) 19:20:29.16

>>955
うーんこの

2022/12/26(月) 19:22:13.79

>>957
くんer、偏見だけど水色くらいそう

2022/12/26(月) 19:25:08.31

さっき考えついた問題

はじめ、頂点1つの根付き木（当然その頂点が根）がある。これからN-1の頂点をこのグラフに以下の手順で一つずつ追加する：

・P/Qの確率で新たに加える頂点を根とした新たな根付き木を追加する。辺は加えない。
・1-P/Qの確率で、既にグラフに存在している頂点の一つを一様ランダムに選び、その頂点の子として新たに頂点を加える。

なお、帰納的にこのグラフは根付き木の森になる。このとき、以下の期待値を求めよ。

・根付き木の頂点数の平均値
・根付き木の頂点数の最大値
・根付き木の高さの平均値
・根付き木の高さの最大値

それぞれどの程度の制約でできるか。

2022/12/26(月) 19:54:14.04

>>959
まあちょっと下のやつを見るのが1番楽しいからな

2022/12/26(月) 20:12:21.63

>>957
グラフやDSUなど全く理解出来ていない質問でしたすみません

2022/12/26(月) 20:18:45.79

いえいえ！全く問題ないです！
色んな解法の解き方を考えると理解が深まるのでいいと思いますよ

2022/12/26(月) 21:33:49.83

>>960
これ、できた森ごとに平均とったり最大取ったりするって話だよね？
例えば、頂点数が3の木が2つ、頂点数が2の木が1つの森ができたという状況なら、平均は8/3、最大は3みたいな
一番上はO(N)だけど、他はすぐにはよさげな方法が思いつかないね

2022/12/26(月) 21:35:18.96

例えば二個目だけど、f(n,m,k)をN=n、最大頂点数m、根付き木数kである確率として、f(n,m,k) = Σ_{i<n/m} Σ_{j<n} 何かの係数 * f(n-im,j,k-i)みたいな風なDPだったりするかね？

**デフォルトの名無しさん** (JP 0Hfd-s0Sd) · 2022/12/26(月) 22:11:29.09

高さの方はさらにむずいな

2022/12/26(月) 22:32:21.55

1つ目の問題、操作後の木の数の期待値が1+((N-1)P/Q)個で頂点数がN個だから木の頂点数の平均はNQ/((N-1)P+Q)じゃね？って思ったけどもしかして俺トンチンカンな事言ってる？

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しとけば特に問題ない