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

競技プログラミング総 ..

797:デフォルトの名無しさん
22/12/17 23:44:00.79 ZH4mYY1r0.net
>>795
3つ以上あると駄目じゃない？
連結グラフA,B.Cがあったとして
AとBはつなぐことできてもCは繋がらないから全体として2部にならない
って言おうと思ったけど問題文に「追加して得られるグラフ」は
ってあるね
ここも組み合わせが必要になるのか
20万頂点全部が独立したグラフだったら(M=0と書いてるし）
20万×19万9999/2になりそうだな
その場合どうやって回避してるの？

798:デフォルトの名無しさん
22/12/17 23:48:00.53 st/Rnmpd0.net
>>797
なんか勘違いがありそう
そもそも連結じゃなくても二部グラフと呼ぶよ

799:デフォルトの名無しさん
22/12/17 23:48:21.10 TrtUePRr0.net
みんな当たり前のように解いてて凄えわ
まずは3完出来るようになりたい

800:デフォルトの名無しさん
22/12/18 00:02:11.91 eWCJrp150.net
今回のはDにしては難しかったし、あんまE問題ぐらいの難度だと認識してよさそうではある
2部グラフの特徴を考えつつ、場合の数を立式して計算しないといけないから、
自分で解いてても、「Dでこんなややこしいことしないといけないの？方針ミスったか？」って不安になりながら解いてた

801:デフォルトの名無しさん
22/12/18 00:10:19.26 FIRAaHDO0.net
Cがたまに解ける程度の参加数回の灰色です
全探索とbit全探索はたくさんやったので次に何をやったら良いか
最初に覚えるアルゴリズムのおすすめを１つか２つくらい教えてください
ちなみにDPは10問くらいやってみたのですが理解が進まず一旦保留してます
DPの初見問題だと何を当てはめれば良いのか分からずコピペ出来るようなものしか正解出来ません

802:デフォルトの名無しさん
22/12/18 00:14:22.07 HDBBZBFh0.net
>>801
累積和と二分探索勧めたいです
URLﾘﾝｸ(qiita.com)
こういうの見ながらやると学びやすいかも

803:デフォルトの名無しさん
22/12/18 00:18:22.74 5nfx19Yz0.net
>>798
各独立した連結グラフがあったとして、解き方としてはそれぞれの色のパターン4色かけ合わせた解き方をするじゃない？

その組み合わせ数が、例えば全部20万個の点が全てどれとも連結していなくて独立だった場合、
20万から2つの組み合わせを全て調べるっていうようになると組み合わせ爆発が起きるんじゃないかって思ったんだけど

804:デフォルトの名無しさん
22/12/18 00:21:29.77 FIRAaHDO0.net
>>802
ありがとうございます試してみます
上から順番にやれば難易度的にも徐々に上がってくって認識でOKですか？

805:デフォルトの名無しさん
22/12/18 00:23:25.03 eWCJrp150.net
>>803
>>797 に書かれてるように N=20万、M=0なら 20万×19万9999/2 つまり 19999900000 になる
答えの数値は大きいけど、計算量が大きくなるわけじゃないから問題ない

806:デフォルトの名無しさん
22/12/18 00:26:21.80 eWCJrp150.net
>>803
>20万から2つの組み合わせを全て調べる
ていうか、そんなことしない
組み合わせ数の立式をしてくださいな

807:デフォルトの名無しさん
22/12/18 00:37:00.80 HDBBZBFh0.net
>>804
いや、そんなことはないかもです
Union-Findとか累積和はダイクストラよりも分かりやすいと思うので自分のやりやすい順序で埋めてくといいかなと思います！

808:デフォルトの名無しさん
22/12/18 00:37:33.08 5nfx19Yz0.net
>>805
んんんん？？
だって連結グラフA,B,Cがあったとして、それぞれの黒点白点を4通りかけ合わせるわけじゃん
結局、ab,bc,caのように 20万C２の組み合わせについて調べないといけないことにならない？？

809:デフォルトの名無しさん
22/12/18 01:02:37.00 Un2uABCHM.net
>>808
vector<pair<long long, long long>> v;
に各連結成分の頂点数 {黒, 白} が入ってると思ってくれ
long long ans=0, sum=0;
for (auto [a,b] : v) {
ans += a*b // 同じ連結成分で違う色の2頂点の組の数
ans += (a+b)*sum; // 違う連結成分なら同色の2頂点も可
sum += a+b; // 見終わったやつは足す
}
あとは既に張られてる辺 M 本引けばいい

810:デフォルトの名無しさん
22/12/18 01:10:08.07 FIRAaHDO0.net
>>807
ありがとうございます、上から順番にやってみつつ且つ自分のやりやすい順序で埋めてみます

811:デフォルトの名無しさん
22/12/18 01:23:59.15 VXpf7ZWU0.net
>>809
待ってね
Cプラプラ読んだことないから少し理解に時間がかかりそう
読んでみる

812:デフォルトの名無しさん
22/12/18 01:29:09.60 VXpf7ZWU0.net
>>809
なるほど！！
これすごい

そうか、黒、白で分ける必要がなかったんだね

813:デフォルトの名無しさん
22/12/18 01:37:39.53 VXpf7ZWU0.net
そうか。。普通に感動した
競プロの人たちすごいな

愚直にやるやり方しか思いつかなかった5chやっててよかったって今初めて思ったくらい感動しました
ありがとう

814:デフォルトの名無しさん
22/12/18 01:45:40.04 VXpf7ZWU0.net
>>809
ans+=a*b
ここだけわからない
正方形だったらそれぞれの頂点2だから、その計算だと4になるけど、
繋がっていない頂点数はその計算だと求められなくない？

815:デフォルトの名無しさん
22/12/18 02:04:39.56 Un2uABCHM.net
>>814
「繋がっていない頂点」が何を指してるのか分からない
もう少し厳密に書いてほしい
入力が
4 4
1 2
2 3
3 4
4 1
だとして、連結成分は1つだけで白2黒2
>>809のループは1回だけ回って ans は 4
既に張られてる辺数4を引いて答えは0です

816:デフォルトの名無しさん
22/12/18 02:13:34.94 W2G5o+in0.net
二部グラフか判定
連結成分のペアに対して要素の個数の積出す(累積和使う)
連結成分の内部でいい感じな計算
とかやったけど結構コード長くなってしまった

817:デフォルトの名無しさん
22/12/18 02:13:42.38 8rlMlDEcp.net
>>813
愚直にコードを書いて解けるのはABC-BかCまでで、それ以上の問題は愚直に実装すると問題の制限を超過するからどう工夫するかが問われて応用的になると思っていいよ
ここからアルゴリズムやらデータ構造やらが活躍するんだけど、業務とかで役立つ機会は少ないし(寧ろABC-C以下みたいに愚直に書く機会の方が多い)から役に立たない云々言われることがあるって感じだと思ってる

818:デフォルトの名無しさん
22/12/18 02:33:16.14 9rjazUL60.net
俺も累積和取る感じでやったけど解説の方がスッキリしてるな

819:デフォルトの名無しさん
22/12/18 09:11:43.17 oY6X+UMna.net
>>814
822と計算式違うよ
0だったsumを更新してるだけだよ

820:デフォルトの名無しさん
22/12/18 09:16:03.59 oY6X+UMna.net
>>814
あ、ごめんその前の計算式か
まずは実際にありえる辺の総数を求めて、
最後に繋がってる本数を引くって事
例題の場合
白2,黒3だから2＊3がありえる辺の総数になって、
そこから引かれている4本を引くと答えの2本が出る
重複なしとか前提があるから出来る方法だけど
そう言う私もD解けなかったですけどねw

821:デフォルトの名無しさん (ﾜｯﾁｮｲ db2d-ZR1D)
22/12/18 14:06:43.40 ymgsFwaZ0.net
c問題で水色とか紫とかがTLE出しまくってるの見ると
何やってるんだと思うよね

822:デフォルトの名無しさん
22/12/18 15:01:37.69 MTKzjrMB0.net
C問題って間違えようがないと思うんだけど、
どういうところで間違えるんだろう

823:デフォルトの名無しさん
22/12/18 15:25:33.21 V0HgyU5o0.net
Pythonなら答えの文字列を文字列のまま作るとかすればTLEじゃね

824:デフォルトの名無しさん
22/12/18 15:27:06.21 jOkKJleE0.net
なんとなく多重ループ正規表現でやってTLEしても気にしないくらいの寛容性が必要

825:デフォルトの名無しさん
22/12/18 15:29:13.85 V0HgyU5o0.net
PythonistはListで保持してjoinする癖を叩き込まないといかんのじゃ(´・ω・`)

826:デフォルトの名無しさん (ｻｻｸｯﾃﾛ Spb3-GZpS)
22/12/18 21:15:22.71 7ZxBUPRFp.net
紫ならそもそもこどふぉの話では

827:デフォルトの名無しさん
22/12/19 12:13:17.90 j4becYJFa.net
atcoder probrems をダークテーマにしてると青が紫になるからそれじゃね

828:デフォルトの名無しさん
22/12/19 15:28:31.49 mlNqZ/yUa.net
この競技のレートって絶対評価？相対評価？
レート自体は相対評価に見えるのに、レートに対する評価は絶対評価に見えるのおかしくない？
曲がりなりにもロジックの天才達が作ったシステムなのにこんな欠陥ある？

829:デフォルトの名無しさん
22/12/19 15:33:52.49 umNN1xHI0.net
それは思う。正規分布的なレートの平均が200以下で、プログラマ一般では灰色上でかなり優秀ハズなのに茶色が雑魚という事になっておる。茶色でも一通りのアルゴリズムは使えるハズ。

830:デフォルトの名無しさん
22/12/19 15:42:55.81 j+/VmCNx0.net
社長曰くこんな感じだから、安心していいでしょ
URLﾘﾝｸ(twitter.com)
AtCoderがそのまま役立つ業務ってだいぶ少なくて、
【評価高】は赤まで、
数理最適化・研究開発
【評価中】は青～水まで、（黄もまれに？）
バックエンドエンジニア・機械学習エンジニア
【評価低～評価無】は水～茶色まで、
その他のITエンジニア
くらいがプラス評価になります。関連度が高ければ高いほど高いレートが評価されやすくなり、逆に低いと低いレートですぐカンストしちゃう、って感じ。
評価低に関しては「コードが書けることが保証されてる」くらいのアピールにしかならないです。
(deleted an unsolicited ad)

831:デフォルトの名無しさん
22/12/19 15:46:23.61 j+/VmCNx0.net
青色からはバックエンドエンジニアや機械学習エンジニアの適正としても良い評価もらえるってことだ

832:デフォルトの名無しさん
22/12/19 16:18:03.87 z2IUcPyNM.net
あいつら別にロジックの天才ではないだろ
ガチャガチャパターンマッチしてるだけで嘘投げまくりだし

833:デフォルトの名無しさん
22/12/19 17:19:19.70 umNN1xHI0.net
ABCのFまでで機械学習のスクラッチに関係ありそうな問題を見たことない。なんせ連続量の最適化がほぼ出ない。数理最適化詳しくないけど在庫やポートフォリオの最適化など近いのはヒューリスティックで普通の方は見当違いでは。

834:デフォルトの名無しさん
22/12/19 22:55:51.16 R3+0mHMkM.net
競プロの問題がそのまま何かの業務に役立つと思ってんのかね
もっと根っこのほうの潜在的な適正を測るのにこそ真価を発揮する競技だろ　実際レートが威力を発揮するのは中途より新卒

835:デフォルトの名無しさん
22/12/19 23:00:19.44 TVP15GFUr.net
AtCoder Companions 使ってみたけど便利だな。

836:デフォルトの名無しさん (ｵｯﾍﾟｹ Srb3-58G+)
22/12/20 00:58:20.98 rMM3/RNdr.net
おさわりOK？

837:デフォルトの名無しさん
22/12/20 02:42:22.83 8HBS9cc/0.net
ふと思ったんだけど、全域木の全ての2点間の距離の平均ってどうやって求めたらいい？
全域木が直線だったらめちゃくちゃ簡単だと思うけど、複雑に分岐してたら20万ノードくらいあったら無理かしら？

838:デフォルトの名無しさん
22/12/20 03:06:34.58 qq1PDL7x0.net
全域ってのがよく分からんが、木なら難しくない
総和が分かれば平均は分かるから総和の話をするとして、各辺についてその辺が距離に寄与する分を足せば良い
これはこの辺を消した時にできる2つの木の頂点数の積だから、木DPを1回すれば求まる
O(|V|)

839:デフォルトの名無しさん
22/12/20 08:11:20.58 njbGKqT7a.net
>>830
いや、それを憲法のようにずっと変えないのはおかしくない？って言ってるんだが
全体的な底上げがされてるならその限りではないでしょ
2年前の青と今の青って解ける問題が違うよねって話。

840:デフォルトの名無しさん
22/12/20 09:41:10.31 jE72r9+/H.net
レートに対する評価は絶対評価じゃない
解ける問題が多少変わろうが評価は大して変わらなかったってだけ

841:デフォルトの名無しさん
22/12/20 12:00:03.38 WLUxt4qk0.net
>>837
回答サンクス
木だけど、重み付きなんだよね
計算式がかなり複雑になると思うんだ

842:デフォルトの名無しさん
22/12/20 12:42:02.98 GISGVI8J0.net
重み付きでも難しくないよまず適当に頂点を選んで、根にする
根からdfsをして、各頂点を根とする部分木のサイズを計算する(nums[v]: vを根とする部分木のサイズとする)
辺(u,v,w) (頂点uとvを結ぶ、重みwの辺)
が2点間の距離の総和(=sum(dist(u,v)) (1≤u<v≤N))に寄与する量は、
uとvの内、根から遠い方がvなら、w * (N-nums[v]) * nums[v]
根から遠い方がuなら、w * (N-nums[u]) * nums[u] になる
典型だから、ABCに転がってないか探したけど見当たらないな(CFならありそう)

843:デフォルトの名無しさん
22/12/20 13:25:55.01 qq1PDL7x0.net
とりあえずコード書いてみたわ、こんな感じで合ってるか？
URLﾘﾝｸ(ideone.com)

844:デフォルトの名無しさん
22/12/20 13:39:41.85 GISGVI8J0.net
kotlin読めないけど、合ってると思う
min(subtreeSize[edge.source], subtreeSize[edge.target])のところが場合分け減らせてて良いね

845:デフォルトの名無しさん
22/12/20 15:11:54.66 Nn7CI7yh0.net
>>839
atcoderの立場として発言してるだけかと。
アルゴリズムの研究者が水色とかあるっぽいし、競プロにフィットしなければ緑以下が普通だろうけど、時間で競ってパズル色も強すぎる競技と、アルゴリズム力は結構離れてると思う。

846:デフォルトの名無しさん
22/12/20 16:32:33.88 Q5NLDt+vM.net
>>839
手繋いで皆でゴールとか好きそう

847:デフォルトの名無しさん
22/12/20 18:29:54.55 1VRwiMhX0.net
はてなブックマークのテクノロジーに再帰は遅いって記事が載ってたわ。

848:デフォルトの名無しさん
22/12/20 20:11:04.77 Q316j5h0r.net
そりゃそうだ

849:デフォルトの名無しさん
22/12/20 20:47:10.47 U3UiJpDd0.net
遅いといっても定数倍が遅いだけだし

850:デフォルトの名無しさん
22/12/20 21:04:04.81 j2ePFqjM0.net
なんで遅いの？

851:デフォルトの名無しさん
22/12/20 23:20:27.24 rS70Lc8l0.net
>>842
なるほどおおおお
ただ、理解できそうで理解できない
確かにその式だと、平方完成したときに距離がn/2で最大になることがわかりそう。
ただ、なぜx*(N-x)になるのかがいまだに理解できていない。。
確かに遠い方を選べばx = Nにはならないから、0にはならない、これはわかるが。。
例えば直線だった時に最初の根で中点を選んでしまったとき、
根だから当然部分木のサイズはNになり、N回の寄与しかできない
中点だからもっと大きい数寄与できるはずでは。。
混乱してきた。。

852:デフォルトの名無しさん
22/12/20 23:24:41.27 rS70Lc8l0.net
URLﾘﾝｸ(imgur.com)
まずこれがn=5の場合に中点を選んだ時のツリー

853:デフォルトの名無しさん
22/12/20 23:29:16.90 rS70Lc8l0.net
URLﾘﾝｸ(imgur.com)
cdの辺(４)は遠い方だから、dの部分木サイズ２、
つまり2×3だから6
なるほど、、たしかに6回寄与してる。。。しかしなぜN-nなんだ。。
2項定理の基本がわかってないのかな

854:デフォルトの名無しさん
22/12/20 23:37:55.90 rS70Lc8l0.net
まてよ、なるほど
自分自信を含んだ場合のそれより下の部分と上の部分が何通りあるか、それをどこまで伸ばせるかということか
なるほど、わかりそう

855:デフォルトの名無しさん
22/12/20 23:43:39.65 rS70Lc8l0.net
一人で連投すまない
なるほど！！めっちゃ理解した
木構造であっても直線であっても、そのノードが双方向から挟まれてるとしてどの位置にいるかっていうことが一定になるんだね
いや凄いな、典型っていうけどこういうの当たり前に理解してる人たちなのか。。
感動した

856:デフォルトの名無しさん
22/12/21 00:05:31.28 nWikoW340.net
理解したかおめでとう！
じゃあ次は全ペアのパスの長さの平均じゃなくて中央値を考えてみてね

857:デフォルトの名無しさん
22/12/21 00:08:11.19 ftIf9M8u0.net
>>856
サンクス！！
中央値。。。。。
n(n-1)/2通りある中から実態のある中央値を考えるのか
一晩考えさせてください。

858:デフォルトの名無しさん
22/12/21 00:20:21.60 ftIf9M8u0.net
>>856
最初に聞かせてほしい
いじわる問題じゃなく本当に求まる？

859:デフォルトの名無しさん
22/12/21 00:24:15.31 ftIf9M8u0.net
URLﾘﾝｸ(imgur.com)
この場合は8が中央値
2分探索を使うわけでもないし不可能な気が。。

860:デフォルトの名無しさん
22/12/21 04:04:43.89 ZV6Qma6k0.net
中央値は結構難しいような
中央値だから二分探索を使うというのは良いと思っていて、でも二分探索の判定部分で、
長さx以上のパスの個数を計算する必要があって、これを計算するのは難しい気がする

861:デフォルトの名無しさん
22/12/21 04:29:36.11 c5REgkR40.net
え、中央値解けるん？
考えたこと無かったわ、やってみるか
重み付きだよね？重み無ければ重心分解して畳込めば終わりだし

862:デフォルトの名無しさん
22/12/21 05:22:01.10 ZV6Qma6k0.net
自分はそもそも重心分解を知らなかった正しいか分からないけど、
重心cからbfsをして、各頂点v(1≤v≤N)までの距離d[v]を求めて、各d[v]を座標圧縮してBITに記録する
各d[v]について、d[u]≥x-d[v](1≤u≤N)となるuの数がBITで計算できる (x-d[v]もd[v]とまとめて座標圧縮する)
このままだと重心から見て、同じ部分木に属するパスを含んでしまうから、
重心から見て、vと同じ部分木に属する頂点uについてのみ、d[u]を座標圧縮してBITに記録して、
d[u]≥x-d[v]となるuの数を引く、とかで合ってるかな？

863:デフォルトの名無しさん
22/12/21 05:56:39.59 c5REgkR40.net
URLﾘﾝｸ(judge.yosupo.jp)

864:デフォルトの名無しさん
22/12/21 13:26:19.80 M6bQfxl+0.net
重心からの距離をソートして頭と尻からそれぞれ見ていけばデータ構造使わなくてもカウントはできる
（結局ソートでlogつくが）
二分探索と分割統治の分を合わせてlog3つになるのかな

865:デフォルトの名無しさん (ﾜｯﾁｮｲ ea10-1XWL)
22/12/21 13:55:04.06 ZV6Qma6k0.net
確かに座標圧縮もBITもいらないか
O(N * (log^2)N * log(Nmax(w))) か (重すぎる)

866:デフォルトの名無しさん
22/12/21 16:51:57.69 c5REgkR40.net
あー、なるほど理解した
確かに中央値求まるな……重すぎるけど

867:デフォルトの名無しさん
22/12/21 17:20:24.15 ftIf9M8u0.net
ちょっと待て待てなんかすごいことになってる
重心分解なんか聞いたことないぞ

868:デフォルトの名無しさん
22/12/21 17:48:02.52 ftIf9M8u0.net
重心分解と座標圧縮について調べてみた
重心分解の条件が部分木が全てN/2以下になっているっていうことは、直線の場合が最大でっていう理解であってるよね？(直感的には明らかだけどなぜn/2以下ならといえるのか厳密な定義があれば教えてほしい）

後、画像圧縮も調べてみたけど、これってどういうときに使うものなんだろう

869:デフォルトの名無しさん
22/12/22 00:38:14.06 E11PDpB0M.net
毎回ソートする必要なくてlog1個落ちる？

870:デフォルトの名無しさん
22/12/22 00:44:54.15 zgSSk2yY0.net
競プロ力って言うか、実務とかのプログラミング力ってどうすれば鍛えられるかな
持ってる知識は同じだとして
基礎体力が強い方が勝つんだろうけど、これってワーキングメモリの保持力だったりするんだろうか

871:デフォルトの名無しさん
22/12/22 01:03:51.33 ac9+4gRj0.net
実務とかのプログラミング力、っていわれても環境によって求められるものが違いすぎてなんともだけど、きみがいうプログラミング力ってなんなん？
個人的に「プログラミング力がある」って感じるひとは、それに比例して知識量もあるし、知識が同じなら差がつくとはどうしても思えない
なかには知識は全く同じはずなのにプログラミングすげえ！みたいな天才マンがいるの？
そんな人に出会ったことないし想像できない
というか仮にいたとしても技巧的なコードばかり書いててメンテできなそう

872:デフォルトの名無しさん
22/12/22 02:41:47.06 CW5T8PCf0.net
英語鍛えりゃいいんじゃね
今まで見てきた凄腕はみんな英語が達者で情報を日本語以外で取り入れまくってた

873:デフォルトの名無しさん
22/12/22 03:01:13.83 AAu4e6zFp.net
英語を鍛えれば有能になるんじゃなくて有能人材は元々英語くらいなら余裕だから因果関係が逆な気もする

874:デフォルトの名無しさん
22/12/22 03:05:02.66 AAu4e6zFp.net
競プロでも強い人がこどふぉとかの英語問題文で困ってるの聞いたことないし

875:デフォルトの名無しさん
22/12/22 05:40:46.21 0WpPKX01a.net
例えば高専で、JavaScript, Python をやっていても、
なんだ、Ruby on Rails, Docker, AWS Solution Architect もやっていないのかと、
ウェブ系企業では全く相手にされない
そういう香具師でも、英語さえ出来れば、GAFAM では採用される。
まあ、競技プログラミングもそこそこ出来るし、まあ雇っても良いかという感じ
印象としては、Linux のシステム構築運用できない香具師が、GAFAMに受かる感じ

876:デフォルトの名無しさん
22/12/22 06:18:15.61 zRh15pQp0.net
英語力はchokudaiが既に反例だから違うだろ
英語力がある方が有能だけど
実務とかのプログラミング力はどれだけ色々なことに手を出してきたかだと思うな、凄い奴は経験してる分野が多岐に渡ってて、何聞いてもそれなりに理解してる答えが返ってくる

877:デフォルトの名無しさん
22/12/22 08:53:39.96 gibqUWi2M.net
別にGAFAM受かっているから優秀とは思わないけど、DockerやAWSみたいな個別的な技術の知識より学術的な情報科学に強い人材の方を重視しているから、一見モダンな知識がないように見えるだけなのでは？
そんなの入社後必要に迫られて勉強すればすぐ身につくようなものじゃないか

878:デフォルトの名無しさん
22/12/22 09:04:09.07 gibqUWi2M.net
CodeForcesの問題文は謎の登場人物、ストーリーが面倒くさいだけで、別に競プロの問題を抽出して理解するのにそんなに英語力いらない気がするな
英語圏の中学生向けの小説の方が難しいと思うわ

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