競技プログラミング総合スレ 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/08(木) 18:06:46.91

それってデータエンジニアじゃん！
Kaggleじゃん！

2022/12/08(木) 18:15:38.61

kaggle定期的にやりたくなるけど競プロ諸々との両立が難しくて毎回挫折する

2022/12/08(木) 22:15:49.90

健常者スレおやすみ🥱

2022/12/09(金) 07:42:08.88

健常者スレおはよう🥱寒いね

2022/12/09(金) 15:37:29.25

Kaggleって機械学習モデルの精度競争的なイメージが強いけど、AIツールを活用した作業効率化みたいなイメージで話してた

2022/12/10(土) 12:50:59.26

健常者スレおはよう🥱今日はABCだね

2022/12/10(土) 16:56:35.59

ChatGPTをAtCoderのコンテストで使用することが認められるならコンテスト出ないって人を見かけたけど、いまはまだ茶色程度の実力だけど、
仮に暖色程度の実力を備えた競プロAIが登場したとして、AtCoder公式から使用を認められたら、どう反応する人が多いか気になる

2022/12/10(土) 20:31:32.99

まだ未参加なのですが過去問ABCのABまでしか解けないとして参加する意味ありますか？
あとABだけ解けて茶色行けますか？

2022/12/10(土) 20:44:33.79

コンテストになれば普段より集中して問題に取り組めるので参加する意味はあります
また参加回数が少ないとレーティングに補正がかかって低くなる仕組みもあります
ABだけでは茶色にはなれません

2022/12/10(土) 20:45:06.16

>>748
英検とかと違って無料で参加できる実戦だから、練習になるし意味あるよ
強いひとはAtCoder以外にもいろんなコンテストに毎週たくさん参加してたりするよ

ABだけで茶色は無理かな
茶色にいくならCまで余裕もって解いてくださいな

2022/12/10(土) 20:49:39.55

>>747
https://www.businessinsider.jp/post-263042

この前こんな記事読んだんだけど、やっぱりChatGPTは「考えて答えている」んじゃなくて「それっぽい文字列を吐いているだけ」みたいだから、これからよほどのパラダイムシフトがない限り暖色程度の実力を備えた競プロAIは無理じゃないかな
まあそのパラダイムシフトに立ち会ってみたい気もするけど

>>748
本番の時間制限あるなかで考えるのも楽しいし、やってみればいいと思うよ

2022/12/10(土) 20:59:17.91

>>749-750
ありがとうございます
練習で参加してみます

2022/12/10(土) 22:40:05.14

ABしか練習してなかったけどCまで解けて、
DはWAが少し出て時間切れでした残念。
でも緊張感あって楽しかったです。

2022/12/10(土) 22:43:34.37

今日は時間内に6完

2022/12/10(土) 22:49:32.73

普通にE、Fの実装重かったね

2022/12/10(土) 22:51:50.49

D難しくなりすぎ・・・・。もらう方でやってバク取れず。２重dpでうまくいかない事に気づくまで40分。

2022/12/10(土) 22:56:44.55

寝てたら終わってた草

2022/12/10(土) 23:04:25.58

D解けた人の境界見たら、1245位だったのでかなり難解だったんですね。
ダメ元でサンプル通ったから提出したら当然WAでしたが解説見てもさっぱりでした。
少しずつアルゴリズムというものを勉強したいと思います。

2022/12/10(土) 23:04:45.70

editor使わず糞アットコの糞サイトbuiltin editorだけで書いてみた
やっぱり全然だめだな(´・ω・｀)

2022/12/10(土) 23:11:10.88

総和が○○のときの△△を求めよ、みたいな形はナップサックDPであることが多いね

2022/12/11(日) 00:16:52.91

同じ問題のレートが１年で50下がってるんだから、Dは茶色下くらいを目指そう

2022/12/11(日) 01:07:10.13

よかった
俺の調子が悪かったわけじゃないのか

三重ループまでなんとなくわかってたけど実装が複雑になりそうでできなかった

2022/12/11(日) 02:02:20.83

Ex見てるがやっぱり分割統治FFTいつまで経っても慣れんな

2022/12/11(日) 02:54:41.11

愛知ループは三重の三倍難しいと言われてるからな。。

2022/12/11(日) 08:11:02.37

DPや二次元配列などでarray型の生配列を使う例が多いのは慣習的なものですか？
処理が速いとか利点があるのでしょうか？

2022/12/11(日) 08:55:06.62

arrayより楽な選択肢なんかある？
arrayじゃダメなときは当然そっち使うにしても

2022/12/11(日) 09:07:28.08

青安定のために参戦を決めていたのですがぐっすり寝てしまい出れなかったであります🤓

2022/12/11(日) 18:45:09.52

>>766
デバッグしたい時などにあれこれ配列の中身除くのにｖｅｃｔｏｒ配列の方が扱いやすいなと思って使ってました
解説でもDPでvector使ってることもあればarray配列使ってたりと別れるので好みとは思うのですが
何かarray型を選ぶ利点があるのか素朴な疑問でした

>>arrayじゃダメなときは当然そっち使うにしても
array使ってる例が多い気がしたのでvectorからarrayに変更して試してたのですが
vectorに慣れすぎていて逆に使いづらいと思ってvectorに戻しました
ダメな時に結局vectorにするのでそれなら最初からvectorで統一しようかなと
まだ経験少ないので試行錯誤してみます

2022/12/11(日) 20:50:40.50

特に多次元にしたときに顕著だけどarrayの方がvectorより速いし省メモリ

2022/12/11(日) 21:02:26.53

初期値をINFで埋めるとかしたいときは vector でコンストラクタ使うかな　それ以外は生配列
array は使う機会ない

2022/12/11(日) 21:52:54.88

map の key にする時なんかはvectorよりかarrayのが早いパターンが多い気がする

2022/12/11(日) 21:59:28.13

>>769
多次元、速い、省メモリ
試行錯誤する時に意識して使い比べてみます

>>770
int a[100]　例
生配列とarray型を混同してましたが生配列の方です
確かにわざわざarray型を宣言して初期化することは無いですね

ありがとうございました

2022/12/11(日) 22:56:42.06

2次元までの配列ならvector 使うけど3次元以上になると生配列使う
宣言や初期化で文字数が増えるのが嫌

2022/12/11(日) 23:05:39.85

そもそも std::vector と std::array って比較するようなものじゃない気が……

2022/12/11(日) 23:35:42.07

自分はもっぱらvectorで、生配列もstd::arrayも競プロじゃほとんど使ってないけどそれでTLEやMLEしたことはないし自分が使いやすいほうでいいよ

2022/12/11(日) 23:44:16.93

マラソンだと上位人はよくarray使ってる印象

2022/12/12(月) 00:55:20.18

マラソンは定数倍高速化した分だけループ回数増えてスコア伸びるからじゃね
アルゴなら5msのACも1900msのACも変わらんし、AtCoderでC++使っててarrayならギリギリ通るみたいなのはそもそも他の何かが間違ってると思った方がよさそう

2022/12/12(月) 05:57:59.81

定数倍高速化してギリギリ通るの、平方分割的な半分嘘解法など？

2022/12/12(月) 08:27:45.85

ミラー・ラビンとかポラード・ローを使った高速な素因数分解アルゴリズムって競プロでの使用頻度どれくらい？
昨日のこどふぉのCの問題設定が微妙でこの高速な素因数分解アルゴリズムじゃないと計算量的に怪しかった(実際は√nの素因数分解アルゴリズムを定数倍高速化するのでも通るっぽい)んだけど存在を忘れてたせいで解けなかった

2022/12/12(月) 09:29:21.46

自分も解けなかった
自分が解いてきた限りではミラーラビンやロー法じゃないと解けない問題は見たことない
なぜ10^6にしなかったのか謎

2022/12/12(月) 10:59:24.92

高速素因数分解が前提の問題は普通にあるけど AtCoder の rated コンでは出なさそう
Codeforces も基本出さない方針な気がするけど writer の次第だからわからん

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)