競技プログラミング総 ..
[2ch|▼Menu]
879:デフォルトの名無しさん
22/12/22 09:48:19.57 lVkIDQyd0.net
>>868
重心探索のアルゴリズムで重心が定まったとき、重心とされた頂点の親の方の連結成分の成分数がn/2以下と言えるのか?という疑問かな?
であれば、重心を根とした部分木の頂点数はn/2より大きいから、親の方の連結成分=重心を根とした部分木の頂点数はn/2以下になるって感じかな?(全然違う疑問だったら言ってくれ)
あと、画像圧縮と座標圧縮は別物だね
座標圧縮の方が簡単で競プロで頻出

880:デフォルトの名無しさん
22/12/22 09:54:55.85 Xj8jM7zP0.net
座標圧縮って競プロだと当然のように使われるけど実際に業務とかでも活用されてるのかな(まあ大した実装量じゃないからわざわざ名前をつけてないだけなのかもしれないけど)

881:デフォルトの名無しさん
22/12/22 09:55:19.15 lVkIDQyd0.net
>>879
あ、
×親の方の連結成分=重心を根とした部分木の頂点数
〇親の方の連結成分=重心を根とした部分木を元の木から取り除いた連結成分の頂点数


882:デフォルトの名無しさん
22/12/22 11:36:03.34 CW5T8PCf0.net
>>880
画像、科学計算分野とかゲーム開発では使うかもしれない
勤怠管理ソフトで使ってるのは聞いたことない

883:デフォルトの名無しさん
22/12/22 11:53:21.34 InE00bnxM.net
普通はハッシュマップかマップをまずは使いそう

884:デフォルトの名無しさん
22/12/22 13:07:07.73 b/+SXENfa.net
座標圧縮っぽいことは思い出してみると業務で使ったことあるけど座標圧縮だと意識してはいなかった気がする

885:デフォルトの名無しさん
22/12/24 10:36:20.69 cLKr3UoH0.net
クリスマスイブだけど今日も競プロ参戦するぜ

886:デフォルトの名無しさん
22/12/24 12:37:53.51 kMNz+jCza.net
プログラムで活躍としては
センスのみ<知識のみ<<<知識+センス
なんだよ
これで勘違いが起きることが多い
知識のみしかもってないと一見最上なんだけど、実は何も産み出さない
知識のみでも誰かがセンスを持ってると一気に有益なものが産み出される
つまりピースを埋められる存在になれるかどうかで活躍は変わってくる

887:デフォルトの名無しさん
22/12/24 18:09:57.90 kSkjk9Mz0.net
今日のコンテストはどうなるんですか

888:デフォルトの名無しさん
22/12/24 22:41:01.66 jJWHRZm50.net
ギリギリ解けたけどEムズいよ

889:デフォルトの名無しさん
22/12/24 22:46:01.54 xqB/wOMj0.net
E解けないからFから解いたんだけどFもFで計算量的に大丈夫なのか?って疑ってた最初の方に思いついた解法(ユーザー解説の奴)が他の解法で悩んだ挙句普通に通ったからあまりスッキリしない

890:デフォルトの名無しさん
22/12/24 22:55:16.29 EtphqWYEa.net
D計算時間を解決できなかった
配列とコンテナで管理するのが速いのかー。
アイデアはあったけどどれが最適かわかんなかった

891:デフォルトの名無しさん
22/12/24 23:18:12.92 FlOHVYkZ0.net
Eのdp複雑すぎて草

892:デフォルトの名無しさん
22/12/24 23:24:36.98 xqB/wOMj0.net
最近のE難しい気がする

893:デフォルトの名無しさん
22/12/24 23:30:32.81 2UD54AXs0.net
D、問題文誤読して違うことやってたのにACになってた
(誤答になる入力が存在することは確認済み)

894:デフォルトの名無しさん
22/12/24 23:35:14.60 K9GUlR1pa.net
(a(b)a)がyesでも通るって話題になってるね

895:デフォルトの名無しさん
22/12/25 10:23:23.93 NJW41kMTa.net
yesでも通るというかNoが通らず不正解になると言う方が状況を誤解なく伝えられるんじゃね

896:デフォルトの名無しさん
22/12/25 10:47:58.50 kS5NHk/h0.net
ABC283
そもそもの難度調整が下手すぎないか?よく考えて作ってるのか疑問

897:デフォルトの名無しさん
22/12/25 10:54:07.27 5/A96Duc0.net
難易度言うならそもそもABCでD以上出さなくていんじゃね
D以上はARCに回せばいい
レーティングも400まででいいよ

898:デフォルトの名無しさん
22/12/25 12:35:37.19 czJqHKZW0.net
黄色以上は解答できなくして賞金も貰えないようにすればいいよ

899:デフォルトの名無しさん
22/12/25 13:12:05.09 RXfOQg060.net
昔青だった人が水色なんだからビギナーコンテストはmax水色~緑下で十分すぎる

900:デフォルトの名無しさん
22/12/25 14:00:20.35 Rt4BkDBba.net
AGCって1200無くても受けて良いの?
暇だし受けてみようかな

901:デフォルトの名無しさん
22/12/25 15:04:24.59 k0QXLRtM0.net
レートつかないだけで参加できると思うよ

902:デフォルトの名無しさん
22/12/25 15:41:34.02 dPtGXdEed.net
ABC上位中国勢ばかりやんけ
少し前より青→黄の難易度かなり上がってそう

903:デフォルトの名無しさん
22/12/25 19:32:07.15 90srlnYwa.net
>>901
あー、レートつかないのか。なら後日でも良いか

904:デフォルトの名無しさん
22/12/25 19:34:29.29 pw/2PAh60.net
人類の5人に一人が中国人だから。
石を5個投げれば一つは中国人に当たる。

905:デフォルトの名無しさん
22/12/25 19:45:56.78 xnbiQd6b0.net
rated上位はマジで中国人がほとんど

906:デフォルトの名無しさん
22/12/25 19:48:23.57 X45g+HJH0.net
理由はしらんけど、どうやら中国勢は現在のレートが実際の実力に追いついてないひとが多すぎるから
だから中国人がたくさん参加するとパフォがちょっと渋くなるかもしれんなあ

907:デフォルトの名無しさん
22/12/25 19:49:02.80 3snFXch40.net
中国って中高生くらいで強い人多いけど競プロの塾とか競プロの中国語の参考書とかもあるのかな

908:デフォルトの名無しさん
22/12/25 19:52:07.11 c5tpuwy60.net
この前2012年生まれの中国人の赤いたぞ
年齢詐称じゃなかったらすごいな

909:デフォルトの名無しさん
22/12/25 19:56:16.55 X45g+HJH0.net
>>907
塾はあるらしい
情報オリンピックで活躍できたら、好きな大学に入れるから高校生ががんばるらしい
参考書については、おれたしか2008年くらいにICPC対策の英語の参考書みたいなの買ったことあるんだけど、たしかそのオリジナルが中国語だったはず(俺が買ったのは英語に翻訳されたバージョン)
まあ今ならきっとかなりたくさんあるでしょ

910:デフォルトの名無しさん
22/12/25 20:13:44.45 pw/2PAh60.net
なんだ塾があるのか。
勉強したらできて当たり前だな。
中国人はしょせん中国人にすぎないな。
↑って、ネトウヨが言い出しそう。

911:デフォルトの名無しさん
22/12/25 20:23:10.79 dZ1hIi2mM.net
中国なら有り得そうとも思うが同時に詐称も沢山いるしなあ

912:デフォルトの名無しさん
22/12/25 20:40:15.68 pw/2PAh60.net
ネトウヨって結局、清和会のために統一教会を支持してる奴らだろ?
国益だの愛国だの言ってるけど、その国というのは韓国のことだろう。

913:デフォルトの名無しさん
22/12/25 21:12:16.73 RXfOQg060.net
ITは超左だからそういうのはないんじゃ

914:デフォルトの名無しさん
22/12/25 22:10:30.90 c5tpuwy60.net
>>912
頭が悪いからパヨクになっちゃうの?
それともパヨクだから頭悪くなるの?

915:デフォルトの名無しさん
22/12/25 22:17:25.74 pw/2PAh60.net
>>914
いまは社会科で習わないのか?
ネトウヨは自民党清和会、つまり韓国朴正煕派閥。
パヨクは社会党、つまり朝鮮総連派閥。

916:デフォルトの名無しさん
22/12/25 22:39:50.62 XWdxnRqI0.net
>>915
最近のネトウヨは嫌韓じゃないのか・・・
清和会のせいでややこしいな

917:デフォルトの名無しさん
22/12/25 22:43:35.02 pw/2PAh60.net
>>916
金大中暗殺未遂事件とかも習わないのか?

918:デフォルトの名無しさん
22/12/25 23:25:15.62 pw/2PAh60.net
>>916
元々ネトウヨを作ったのが韓国人だろ。
いいように操られやがって。

919:デフォルトの名無しさん
22/12/25 23:27:58.85 XWdxnRqI0.net
私を貶しても何もでないよ🥺

920:デフォルトの名無しさん
22/12/25 23:32:02.62 pw/2PAh60.net
>>919
なんか出せよ。

921:デフォルトの名無しさん
22/12/25 23:45:09.06 pw/2PAh60.net
統一教会は日本で、ゆとりある教育を提唱しているが、韓国では全く逆のことを言ってるからな。
騙されるなよ。

922:デフォルトの名無しさん
22/12/25 23:46:50.19 pw/2PAh60.net
三角関数は高度な数学じゃないぞ。
全員が知っていなければならない基本的な算数だからな。
統一教会派の国会議員に騙されるなよ。

923:デフォルトの名無しさん (ワッチョイ c305-dxp0)
22/12/26 00:01:23.73 FjUIzguJ0.net
snukeさん滑り込んだな
にしても中国が多い

924:デフォルトの名無しさん (アウアウウー Sab3-8rxy)
22/12/26 00:03:13.58 2k0I0Okna.net
tourist敗れるのも日常風景になってきた

925:デフォルトの名無しさん (ササクッテロ Sp1f-JTql)
22/12/26 00:06:51.77 NJmVt5wpp.net
前の二つの状態を持つDP、前日のABCでもあったのにDPしなくても掛けていけば求まると迷走して1完遅解きだからダメダメだ
Bもどう実験すれば思いつけるのか

926:デフォルトの名無しさん (ワッチョイ adbd-IDYW)
22/12/26 00:07:49.33 0EESOEy50.net
タイムリーだね
すぬけさんやtouristいなかったら本当に中国勢が強い
横綱さんもかなりすごい

927:デフォルトの名無しさん
22/12/26 00:11:02.93 2k0I0Okna.net
chokudaiも3000の実力ないとか言いながらしっかり34位か

928:デフォルトの名無しさん (オッペケ Sr1f-v7Gx)
22/12/26 01:50:16.22 bsJyc2OPr.net
すみません、くんerですけど明日からこっち書き込みます

929:デフォルトの名無しさん
22/12/26 01:57:43.17 UwIL/0u/0.net
ワスも本格的にこっちに進出じゃい(´・ω・`)

930:デフォルトの名無しさん
22/12/26 02:03:28.25 bsJyc2OPr.net
もしngしたかったら
1週間毎にオッペケ Sr1f-v7GxのオッペケSr以外の部分をngお願いします(前2桁はよく変わるので)

931:デフォルトの名無しさん
22/12/26 02:07:40.38 VOvNKiQ1r.net
こんな感じで

932:デフォルトの名無しさん
22/12/26 02:07:53.69 VOvNKiQ1r.net
変わってねぇ...

933:デフォルトの名無しさん
22/12/26 02:07:56.66 UwIL/0u/0.net
くんer真面目かよ

934:デフォルトの名無しさん
22/12/26 02:46:07.41 oqCp9wYlr.net
うんち!w

935:デフォルトの名無しさん
22/12/26 03:47:58.81 n//AvpiG0.net


936:デフォルトの名無しさん
22/12/26 08:20:22.77 tmqxSKGS0.net
今の日本の若い人って頑張らないし甘やかされてるしそりゃ全体的な競争力低くもなるわ

937:デフォルトの名無しさん
22/12/26 12:27:01.64 O2R1XPjG0.net
競争力を上げるためにはもっとスパルタにせねば、とお考えなのですね

938:デフォルトの名無しさん
22/12/26 12:45:34.28 CkzYHyzir.net
暇だからスレ立てる

939:デフォルトの名無しさん
22/12/26 12:45:46.11 CkzYHyzir.net
950

940:デフォルトの名無しさん
22/12/26 12:47:59.32 CkzYHyzir.net
競技プログラミング総合スレ 65
スレリンク(tech板)
建てたにょ

941:デフォルトの名無しさん
22/12/26 14:12:14.71 oDvkMIGt0.net
>>940
これは実務赤、有能

942:デフォルトの名無しさん
22/12/26 17:56:28.72 5LxkM09pa.net
>>937
スパルタにすると諦めるからどのみちだめ

943:デフォルトの名無しさん
22/12/26 18:18:11.69 CkzYHyzir.net
くん、ICPCメンバーと何かあったんか?

944:デフォルトの名無しさん
22/12/26 18:49:12.07 KxFT/wbk0.net
>>943
詳しい経緯は話してないけど、少し前のツイートで「ICPCのメンバーとは決別した」って言ってたでしょ
今日も練習すっぽかしたって自分で言ってるしチーム内でうまく言ってないんじゃないの

945:デフォルトの名無しさん
22/12/26 18:57:58.08 qC77tL+z0.net
初心者なのですが
ABC262BをACLのDSUを使って解くことは出来ますか?
解説などでは全く使ってなかったので
そもそもの方針が間違ってるのか知りたいです
URLリンク(atcoder.jp)

946:デフォルトの名無しさん
22/12/26 19:08:08.06 CkzYHyzir.net
路じゃなくて辺が存在すればいいからDSUを使う意味がない

947:デフォルトの名無しさん
22/12/26 19:20:29.16 BJooufdOr.net
>>944
うーんこの

948:デフォルトの名無しさん
22/12/26 19:22:13.79 89yBpVXU0.net
>>946
くんer、偏見だけど水色くらいそう

949:デフォルトの名無しさん
22/12/26 19:25:08.31 TDmnxh2KM.net
さっき考えついた問題
はじめ、頂点1つの根付き木(当然その頂点が根)がある。これからN-1の頂点をこのグラフに以下の手順で一つずつ追加する:
・P/Qの確率で新たに加える頂点を根とした新たな根付き木を追加する。辺は加えない。
・1-P/Qの確率で、既にグラフに存在している頂点の一つを一様ランダムに選び、その頂点の子として新たに頂点を加える。
なお、帰納的にこのグラフは根付き木の森になる。このとき、以下の期待値を求めよ。
・根付き木の頂点数の平均値
・根付き木の頂点数の最大値
・根付き木の高さの平均値
・根付き木の高さの最大値
それぞれどの程度の制約でできるか。

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
このスレッドは1000を超えました。
新しいスレッドを立ててください。
life time: 87日 9時間 22分 12秒


最新レス表示
スレッドの検索
類似スレ一覧
話題のニュース
おまかせリスト
▼オプションを表示
暇つぶし2ch

408日前に更新/229 KB
担当:undef