競技プログラミング総合スレ 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/17(土) 22:55:32.46

cまでは10分ちょっとでクリアできるようになったけど、
ｄがここ一か月難しい気がする
酒のみすぎかしら

2022/12/17(土) 22:57:13.17

>>796
そう思ったけど、解説にはその点が触れられてない

2022/12/17(土) 22:59:39.92

いや、それがあのBとWの入れ替え関数式か。
D解けた人良くここまで計算し切ったね
グラフの計算に二部グラフの計算加えて、
さらに計算式も考えるとかやりきれんよ。

2022/12/17(土) 23:02:27.38

自分は余事象じゃなくて普通に足し合わせたけど、二頂点が異なる連結成分にある場合は後から色を合わせられるから全通りOKっていうのを最初は見逃してた

2022/12/17(土) 23:05:00.09

グラフの分解ってどうやるのがいいの？
普通はdfsでグラフは見ていくんだろうけど、

for分で回すのも違うと思うし、unionFindとかで調べることになるの？

2022/12/17(土) 23:13:31.41

おれはUnionFindつかってないよ
まあ使ったほうが見通しが良いなら使ってもいい 
2部グラフとして考え、連結成分ごとに2色に塗り分けて、色ごとの頂点の数を数えて、組み合わせを計算して足し合わせた
これだけ

2022/12/17(土) 23:23:39.77

青の人が３完だったらしーからD解けなくても全く問題ない気がする

2022/12/17(土) 23:28:22.91

グラフの分解は、
visited[v]: 頂点vを訪問したか
を用意して、for (int v=0; v<N; v++) で visited[v]がFalseなら、
そのvからbfsをして、visitedを更新しながら、色々やる
という方法でやってる
二部グラフ判定なら、visitedは頂点の色の配列で代用できる

2022/12/17(土) 23:31:28.58

Nが最大で2*10^5だから、たぶん解法はO(N)だろうとあたりをつける

つまり、おそらく「頂点iから伸ばしてもいい辺の本数」を定数時間で求めさせるのが想定解だろうと予想できる

色々考えると「頂点iから伸ばしてもいい辺の本数」は

(頂点iと同じ連結成分に属している、頂点iと違う色の頂点の数) - (頂点iの次数) + (頂点iが属していない全連結成分の頂点数)

だと求まるから、この総和が答えって感じで解けた

2022/12/17(土) 23:39:16.37

>>796
連結成分は3つ以上あってもいいよ

2022/12/17(土) 23:39:58.72

>>804
なるほど！サンクス

2022/12/17(土) 23:44:00.79

>>806
3つ以上あると駄目じゃない？

連結グラフA,B.Cがあったとして
AとBはつなぐことできてもCは繋がらないから全体として2部にならない

って言おうと思ったけど問題文に「追加して得られるグラフ」は
ってあるね
ここも組み合わせが必要になるのか

20万頂点全部が独立したグラフだったら(M=0と書いてるし）
20万×19万9999/2になりそうだな

その場合どうやって回避してるの？

2022/12/17(土) 23:48:00.53

>>808
なんか勘違いがありそう
そもそも連結じゃなくても二部グラフと呼ぶよ

2022/12/17(土) 23:48:21.10

みんな当たり前のように解いてて凄えわ
まずは3完出来るようになりたい

2022/12/18(日) 00:02:11.91

今回のはDにしては難しかったし、あんまE問題ぐらいの難度だと認識してよさそうではある
2部グラフの特徴を考えつつ、場合の数を立式して計算しないといけないから、
自分で解いてても、「Dでこんなややこしいことしないといけないの？方針ミスったか？」って不安になりながら解いてた

2022/12/18(日) 00:10:19.26

Cがたまに解ける程度の参加数回の灰色です
全探索とbit全探索はたくさんやったので次に何をやったら良いか
最初に覚えるアルゴリズムのおすすめを１つか２つくらい教えてください

ちなみにDPは10問くらいやってみたのですが理解が進まず一旦保留してます
DPの初見問題だと何を当てはめれば良いのか分からずコピペ出来るようなものしか正解出来ません

2022/12/18(日) 00:14:22.07

>>812
累積和と二分探索勧めたいです
https://qiita.com/e869120/items/eb50fdaece12be418faa#%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95%E5%8C%BA%E9%96%93-dp
こういうの見ながらやると学びやすいかも

2022/12/18(日) 00:18:22.74

>>809
各独立した連結グラフがあったとして、解き方としてはそれぞれの色のパターン4色かけ合わせた解き方をするじゃない？

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

2022/12/18(日) 00:21:29.77

>>813
ありがとうございます試してみます

上から順番にやれば難易度的にも徐々に上がってくって認識でOKですか？

2022/12/18(日) 00:23:25.03

>>814
>>808 に書かれてるように N=20万、M=0なら 20万×19万9999/2 つまり 19999900000 になる
答えの数値は大きいけど、計算量が大きくなるわけじゃないから問題ない

2022/12/18(日) 00:26:21.80

>>814
>20万から2つの組み合わせを全て調べる
ていうか、そんなことしない
組み合わせ数の立式をしてくださいな

2022/12/18(日) 00:37:00.80

>>815
いや、そんなことはないかもです
Union-Findとか累積和はダイクストラよりも分かりやすいと思うので自分のやりやすい順序で埋めてくといいかなと思います！

2022/12/18(日) 00:37:33.08

>>816

んんんん？？
だって連結グラフA,B,Cがあったとして、それぞれの黒点白点を4通りかけ合わせるわけじゃん

結局、ab,bc,caのように 20万C２の組み合わせについて調べないといけないことにならない？？

2022/12/18(日) 01:02:37.00

>>819
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 本引けばいい

2022/12/18(日) 01:10:08.07

>>818
ありがとうございます、上から順番にやってみつつ且つ自分のやりやすい順序で埋めてみます

2022/12/18(日) 01:23:59.15

>>820
待ってね
Cプラプラ読んだことないから少し理解に時間がかかりそう
読んでみる

2022/12/18(日) 01:29:09.60

>>820
なるほど！！
これすごい

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

2022/12/18(日) 01:37:39.53

そうか。。普通に感動した
競プロの人たちすごいな

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

2022/12/18(日) 01:45:40.04

>>820

ans+=a*b

ここだけわからない

正方形だったらそれぞれの頂点2だから、その計算だと4になるけど、
繋がっていない頂点数はその計算だと求められなくない？

2022/12/18(日) 02:04:39.56

>>825
「繋がっていない頂点」が何を指してるのか分からない
もう少し厳密に書いてほしい

入力が
4 4
1 2
2 3
3 4
4 1
だとして、連結成分は1つだけで白2黒2
>>820のループは1回だけ回って ans は 4
既に張られてる辺数4を引いて答えは0です

2022/12/18(日) 02:13:34.94

二部グラフか判定
連結成分のペアに対して要素の個数の積出す(累積和使う)
連結成分の内部でいい感じな計算
とかやったけど結構コード長くなってしまった

2022/12/18(日) 02:13:42.38

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

2022/12/18(日) 02:33:16.14

俺も累積和取る感じでやったけど解説の方がスッキリしてるな

2022/12/18(日) 09:11:43.17

>>825
822と計算式違うよ
0だったsumを更新してるだけだよ

2022/12/18(日) 09:16:03.59

>>825
あ、ごめんその前の計算式か
まずは実際にありえる辺の総数を求めて、
最後に繋がってる本数を引くって事

例題の場合
白2,黒3だから2＊3がありえる辺の総数になって、
そこから引かれている4本を引くと答えの2本が出る
重複なしとか前提があるから出来る方法だけど

そう言う私もD解けなかったですけどねw

2022/12/18(日) 14:06:43.40

c問題で水色とか紫とかがTLE出しまくってるの見ると
何やってるんだと思うよね

2022/12/18(日) 15:01:37.69

C問題って間違えようがないと思うんだけど、
どういうところで間違えるんだろう

2022/12/18(日) 15:25:33.21

Pythonなら答えの文字列を文字列のまま作るとかすればTLEじゃね

2022/12/18(日) 15:27:06.21

なんとなく多重ループ正規表現でやってTLEしても気にしないくらいの寛容性が必要

2022/12/18(日) 15:29:13.85

PythonistはListで保持してjoinする癖を叩き込まないといかんのじゃ(´・ω・`)

2022/12/18(日) 21:15:22.71

紫ならそもそもこどふぉの話では

2022/12/19(月) 12:13:17.90

atcoder probrems をダークテーマにしてると青が紫になるからそれじゃね

2022/12/19(月) 15:28:31.49

この競技のレートって絶対評価？相対評価？
レート自体は相対評価に見えるのに、レートに対する評価は絶対評価に見えるのおかしくない？

曲がりなりにもロジックの天才達が作ったシステムなのにこんな欠陥ある？

2022/12/19(月) 15:33:52.49

それは思う。正規分布的なレートの平均が200以下で、プログラマ一般では灰色上でかなり優秀ハズなのに茶色が雑魚という事になっておる。茶色でも一通りのアルゴリズムは使えるハズ。

2022/12/19(月) 15:42:55.81

社長曰くこんな感じだから、安心していいでしょ
https://twitter.com/chokudai/status/1474258242452987907

AtCoderがそのまま役立つ業務ってだいぶ少なくて、
【評価高】は赤まで、
数理最適化・研究開発
【評価中】は青～水まで、（黄もまれに？）
バックエンドエンジニア・機械学習エンジニア
【評価低～評価無】は水～茶色まで、
その他のITエンジニア

くらいがプラス評価になります。関連度が高ければ高いほど高いレートが評価されやすくなり、逆に低いと低いレートですぐカンストしちゃう、って感じ。

評価低に関しては「コードが書けることが保証されてる」くらいのアピールにしかならないです。
https://twitter.com/5chan_nel (5ch newer account)

2022/12/19(月) 15:46:23.61

青色からはバックエンドエンジニアや機械学習エンジニアの適正としても良い評価もらえるってことだ

2022/12/19(月) 16:18:03.87

あいつら別にロジックの天才ではないだろ
ガチャガチャパターンマッチしてるだけで嘘投げまくりだし

2022/12/19(月) 17:19:19.70

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

2022/12/19(月) 22:55:51.16

競プロの問題がそのまま何かの業務に役立つと思ってんのかね
もっと根っこのほうの潜在的な適正を測るのにこそ真価を発揮する競技だろ　実際レートが威力を発揮するのは中途より新卒

2022/12/19(月) 23:00:19.44

AtCoder Companions 使ってみたけど便利だな。

2022/12/20(火) 00:58:20.98

おさわりOK？

2022/12/20(火) 02:42:22.83

ふと思ったんだけど、全域木の全ての2点間の距離の平均ってどうやって求めたらいい？
全域木が直線だったらめちゃくちゃ簡単だと思うけど、複雑に分岐してたら20万ノードくらいあったら無理かしら？

2022/12/20(火) 03:06:34.58

全域ってのがよく分からんが、木なら難しくない
総和が分かれば平均は分かるから総和の話をするとして、各辺についてその辺が距離に寄与する分を足せば良い
これはこの辺を消した時にできる2つの木の頂点数の積だから、木DPを1回すれば求まる
O(|V|)

2022/12/20(火) 08:11:20.58

>>841
いや、それを憲法のようにずっと変えないのはおかしくない？って言ってるんだが
全体的な底上げがされてるならその限りではないでしょ
2年前の青と今の青って解ける問題が違うよねって話。

**デフォルトの名無しさん** (JP 0Hf6-3jwL) · 2022/12/20(火) 09:41:10.31

レートに対する評価は絶対評価じゃない
解ける問題が多少変わろうが評価は大して変わらなかったってだけ

2022/12/20(火) 12:00:03.38

>>848
回答サンクス
木だけど、重み付きなんだよね

計算式がかなり複雑になると思うんだ

2022/12/20(火) 12:42:02.98

重み付きでも難しくないよまず適当に頂点を選んで、根にする
根から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ならありそう)

2022/12/20(火) 13:25:55.01

とりあえずコード書いてみたわ、こんな感じで合ってるか？
https://ideone.com/oTWtMA

2022/12/20(火) 13:39:41.85

kotlin読めないけど、合ってると思う
min(subtreeSize[edge.source], subtreeSize[edge.target])のところが場合分け減らせてて良いね

2022/12/20(火) 15:11:54.66

>>850
atcoderの立場として発言してるだけかと。
アルゴリズムの研究者が水色とかあるっぽいし、競プロにフィットしなければ緑以下が普通だろうけど、時間で競ってパズル色も強すぎる競技と、アルゴリズム力は結構離れてると思う。

2022/12/20(火) 16:32:33.88

>>850
手繋いで皆でゴールとか好きそう

2022/12/20(火) 18:29:54.55

はてなブックマークのテクノロジーに再帰は遅いって記事が載ってたわ。

2022/12/20(火) 20:11:04.77

そりゃそうだ

2022/12/20(火) 20:47:10.47

遅いといっても定数倍が遅いだけだし

2022/12/20(火) 21:04:04.81

なんで遅いの？

2022/12/20(火) 23:20:27.24

>>853
なるほどおおおお
ただ、理解できそうで理解できない
確かにその式だと、平方完成したときに距離がn/2で最大になることがわかりそう。
ただ、なぜx*(N-x)になるのかがいまだに理解できていない。。

確かに遠い方を選べばx = Nにはならないから、0にはならない、これはわかるが。。
例えば直線だった時に最初の根で中点を選んでしまったとき、
根だから当然部分木のサイズはNになり、N回の寄与しかできない
中点だからもっと大きい数寄与できるはずでは。。
混乱してきた。。

2022/12/20(火) 23:24:41.27

https://imgur.com/a/7XCo1vG
まずこれがn=5の場合に中点を選んだ時のツリー

2022/12/20(火) 23:29:16.90

https://imgur.com/a/urLR8OE
cdの辺(４)は遠い方だから、dの部分木サイズ２、
つまり2×3だから6
なるほど、、たしかに6回寄与してる。。。しかしなぜN-nなんだ。。
2項定理の基本がわかってないのかな

2022/12/20(火) 23:37:55.90

まてよ、なるほど
自分自信を含んだ場合のそれより下の部分と上の部分が何通りあるか、それをどこまで伸ばせるかということか
なるほど、わかりそう

2022/12/20(火) 23:43:39.65

一人で連投すまない
なるほど！！めっちゃ理解した
木構造であっても直線であっても、そのノードが双方向から挟まれてるとしてどの位置にいるかっていうことが一定になるんだね

いや凄いな、典型っていうけどこういうの当たり前に理解してる人たちなのか。。
感動した

2022/12/21(水) 00:05:31.28

理解したかおめでとう！
じゃあ次は全ペアのパスの長さの平均じゃなくて中央値を考えてみてね

2022/12/21(水) 00:08:11.19

>>867
サンクス！！
中央値。。。。。
n(n-1)/2通りある中から実態のある中央値を考えるのか

一晩考えさせてください。

2022/12/21(水) 00:20:21.60

>>867
最初に聞かせてほしい
いじわる問題じゃなく本当に求まる？

2022/12/21(水) 00:24:15.31

https://imgur.com/a/kHjv6cK
この場合は8が中央値
2分探索を使うわけでもないし不可能な気が。。

2022/12/21(水) 04:04:43.89

中央値は結構難しいような
中央値だから二分探索を使うというのは良いと思っていて、でも二分探索の判定部分で、
長さx以上のパスの個数を計算する必要があって、これを計算するのは難しい気がする

2022/12/21(水) 04:29:36.11

え、中央値解けるん？
考えたこと無かったわ、やってみるか
重み付きだよね？重み無ければ重心分解して畳込めば終わりだし

2022/12/21(水) 05:22:01.10

自分はそもそも重心分解を知らなかった正しいか分からないけど、
重心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の数を引く、とかで合ってるかな？

2022/12/21(水) 05:56:39.59

https://judge.yosupo.jp/problem/frequency_table_of_tree_distance

2022/12/21(水) 13:26:19.80

重心からの距離をソートして頭と尻からそれぞれ見ていけばデータ構造使わなくてもカウントはできる
（結局ソートでlogつくが）

二分探索と分割統治の分を合わせてlog3つになるのかな

2022/12/21(水) 13:55:04.06

確かに座標圧縮もBITもいらないか
O(N * (log^2)N * log(Nmax(w))) か (重すぎる)

2022/12/21(水) 16:51:57.69

あー、なるほど理解した
確かに中央値求まるな……重すぎるけど

2022/12/21(水) 17:20:24.15

ちょっと待て待てなんかすごいことになってる
重心分解なんか聞いたことないぞ

2022/12/21(水) 17:48:02.52

重心分解と座標圧縮について調べてみた

重心分解の条件が部分木が全てN/2以下になっているっていうことは、直線の場合が最大でっていう理解であってるよね？(直感的には明らかだけどなぜn/2以下ならといえるのか厳密な定義があれば教えてほしい）

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

2022/12/22(木) 00:38:14.06

毎回ソートする必要なくてlog1個落ちる？

2022/12/22(木) 00:44:54.15

競プロ力って言うか、実務とかのプログラミング力ってどうすれば鍛えられるかな
持ってる知識は同じだとして
基礎体力が強い方が勝つんだろうけど、これってワーキングメモリの保持力だったりするんだろうか

2022/12/22(木) 01:03:51.33

実務とかのプログラミング力、っていわれても環境によって求められるものが違いすぎてなんともだけど、きみがいうプログラミング力ってなんなん？
個人的に「プログラミング力がある」って感じるひとは、それに比例して知識量もあるし、知識が同じなら差がつくとはどうしても思えない

なかには知識は全く同じはずなのにプログラミングすげえ！みたいな天才マンがいるの？
そんな人に出会ったことないし想像できない
というか仮にいたとしても技巧的なコードばかり書いててメンテできなそう

2022/12/22(木) 02:41:47.06

英語鍛えりゃいいんじゃね
今まで見てきた凄腕はみんな英語が達者で情報を日本語以外で取り入れまくってた

2022/12/22(木) 03:01:13.83

英語を鍛えれば有能になるんじゃなくて有能人材は元々英語くらいなら余裕だから因果関係が逆な気もする

2022/12/22(木) 03:05:02.66

競プロでも強い人がこどふぉとかの英語問題文で困ってるの聞いたことないし

2022/12/22(木) 05:40:46.21

例えば高専で、JavaScript, Python をやっていても、
なんだ、Ruby on Rails, Docker, AWS Solution Architect もやっていないのかと、
ウェブ系企業では全く相手にされない

そういう香具師でも、英語さえ出来れば、GAFAM では採用される。
まあ、競技プログラミングもそこそこ出来るし、まあ雇っても良いかという感じ

印象としては、Linux のシステム構築運用できない香具師が、GAFAMに受かる感じ

2022/12/22(木) 06:18:15.61

英語力はchokudaiが既に反例だから違うだろ
英語力がある方が有能だけど
実務とかのプログラミング力はどれだけ色々なことに手を出してきたかだと思うな、凄い奴は経験してる分野が多岐に渡ってて、何聞いてもそれなりに理解してる答えが返ってくる

2022/12/22(木) 08:53:39.96

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

2022/12/22(木) 09:04:09.07

CodeForcesの問題文は謎の登場人物、ストーリーが面倒くさいだけで、別に競プロの問題を抽出して理解するのにそんなに英語力いらない気がするな
英語圏の中学生向けの小説の方が難しいと思うわ

2022/12/22(木) 09:48:19.57

>>879
重心探索のアルゴリズムで重心が定まったとき、重心とされた頂点の親の方の連結成分の成分数がn/2以下と言えるのか？という疑問かな？
であれば、重心を根とした部分木の頂点数はn/2より大きいから、親の方の連結成分＝重心を根とした部分木の頂点数はn/2以下になるって感じかな？（全然違う疑問だったら言ってくれ）

あと、画像圧縮と座標圧縮は別物だね
座標圧縮の方が簡単で競プロで頻出

2022/12/22(木) 09:54:55.85

座標圧縮って競プロだと当然のように使われるけど実際に業務とかでも活用されてるのかな(まあ大した実装量じゃないからわざわざ名前をつけてないだけなのかもしれないけど)

2022/12/22(木) 09:55:19.15

>>890
あ、
×親の方の連結成分＝重心を根とした部分木の頂点数
〇親の方の連結成分＝重心を根とした部分木を元の木から取り除いた連結成分の頂点数
ね

2022/12/22(木) 11:36:03.34

>>891
画像、科学計算分野とかゲーム開発では使うかもしれない
勤怠管理ソフトで使ってるのは聞いたことない

2022/12/22(木) 11:53:21.34

普通はハッシュマップかマップをまずは使いそう

2022/12/22(木) 13:07:07.73

座標圧縮っぽいことは思い出してみると業務で使ったことあるけど座標圧縮だと意識してはいなかった気がする

2022/12/24(土) 10:36:20.69

クリスマスイブだけど今日も競プロ参戦するぜ