競技プログラミング総合スレ 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/13(火) 05:21:16.73

こどふぉ来週の月曜日までほぼ毎日コンテストあるんだけど過密すぎるでしょ

2022/12/13(火) 09:46:33.18

コドゲやるぞやるぞ

2022/12/16(金) 16:05:11.86

蟻本4.4章の巡回スケジューリング問題(円環上での区間スケジューリング問題)のソートを除いたO(N)解法って何？
円環を切って2つ繋げて区間にして考えるのかなって思ったけど上手くいかない気もするし元の問題が見つからないから確かめることも難しい

2022/12/16(金) 20:10:17.03

各区間を頂点として、蟻本の解法の中で構築してるnextを辺としたグラフを考えると、なもりグラフになっててサイクルをちょうど一つだけ含む
答えはこのグラフ上のパスで表せる

サイクルに含まれない頂点を含む解を考えると、パスの始点と終点を一つ進めたものも有効な解であることが示せるので、
全ての頂点がサイクルに含まれるようなパスだけ考えればいい

あとはサイクルの上でしゃくとり法みたいなことやればできそう
で合ってるかな……？

2022/12/16(金) 21:07:39.53

しゃくとり法しないでもサイクル上の適当な頂点から始めて極大な解を一つ取れば大丈夫か

2022/12/16(金) 22:19:14.38

>>785
確かにグラフ上で考えると求める区間の選び方はサイクルに含まれることが必要で、辺の数=頂点の数と全ての頂点の出次数1から全体としてはなもりグラフ的な感じにはなりそうだからだいたいその方針で良さそうっぽいな
ありがとう

2022/12/17(土) 21:30:59.31

全完出ました

2022/12/17(土) 21:44:36.74

2位と3位が2秒差

2022/12/17(土) 22:41:47.95

Dさぁ、過去問から漁れないと時間的に無理だろ

2022/12/17(土) 22:48:54.79

D通ったけど難易度高すぎ。E,Fの位置にしとけと。

2022/12/17(土) 22:49:30.45

つーか、Dって
連結がない頂点がある場合、答えは0じゃないよね？
追加したら二部グラフになりえると思うんだけど
このケース考えて完全に迷走した

2022/12/17(土) 22:51:41.65

E全域木になるの言われたらそうなんだけど見えなかったし精進が足りて無いのかな
Dは数ヶ月前だったらEに置いてあった気もするしインフレしすぎ

2022/12/17(土) 22:53:14.13

>>792
そうだよ
例えば辺が0個のグラフが与えられたとすると、答えはN*2になる

2022/12/17(土) 22:53:56.18

あ、N*2ではないわ・・・、すまん

2022/12/17(土) 22:54:02.71

D問題
やり方として
・まずは連結グラフに分解する
・連結グラフが3以上だった場合は無理判定をする

・そして各連結グラフ毎に
とりあえず各頂点に黒と白を割り振って、
このグラフそのものが2部グラフになっているかを判定する

2部グラフになっていた場合に、各連結グラフごとに自信が持ってる
反対の色の頂点数-頂点数をanswerに足していく

そして、各連結グラフについては

グラフ1の黒数×グラフ2の黒数
グラフ1の黒数×グラフ2の白数
グラフ1の白数×グラフ2の黒数
グラフ1の白数×グラフ2の白数

の4つを足す

っていう解法を思いついたんだけど、グラフ問題といたことなかったから、各頂点がどの気に属しているかっていう判定ができなかった

俺のやり方、・まずは連結グラフに分解する
さえクリアできテレバこのやり方であっていた？

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

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