競技プログラミング総合スレ 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(木) 00:20:24.69

>>950

!extend:checked:vvvvv:1000:512
!extend:checked:vvvvv:1000:512

テンプレからコマンド消えてるのでテンプレに追加してください

2022/12/08(木) 00:33:13.01

>>722
ACLにもなってるこの畳み込みは 10⁹+7 だとあまり使い物にならない
このアルゴリズムを使うときはほぼ確実に998244353が指定される
https://atcoder.github.io/ac-library/production/document_ja/convolution.html

2022/12/08(木) 00:34:54.52

>>722
畳み込み演算を高速化するFFTの亜種で、数論変換というのがある
普通のFFTは複素数を使うけど、数論変換はずっとmod pで計算するから精度上の問題が生じないのがメリット
p-1 = 2^m * dみたいな形で書いたときにmが大きいpほど扱いやすく、998244353は大きくて、1000000007は小さいから、そこで数論変換を使うかどうかがバレやすい的な話

2022/12/08(木) 00:38:01.86

>>719
やっぱ一回は思い浮かぶよね
そんなに単純な解だと思わなかったし

2022/12/08(木) 05:37:05.87

そもそも1クエリ固定の場合を解けないと話にならなくて、セグ木やらMoやらを考えるのはそのあとでないか

2022/12/08(木) 10:57:49.64

解既知区間を左右に1伸長したときにまた高速で解を求められれば一クエリでも多クエリでも対応できるから、そこに絞ってまず思考してみるというのも戦術としてはあるだろ
帰納的に考える方が多くの場合少ない思考リソースで問題解けたりするし

2022/12/08(木) 12:32:11.43

言ってることようわからんが結局1クエリ解くことから始めてない？

2022/12/08(木) 13:06:21.88

その1クエリを解くにあたり、Moで多クエリでも高速で処理することを見据えて、1クエリの解を伸長で構成することを試してみるって話
一方、セグ木で解くことを見据えるなら、モノイド性をどこかで見出して区間を併合しながら1クエリの解を構成できないか考えてみるというアプローチになる
メタ的には、多クエリで高速で解ける以上は、1クエリの解き方も限定されてくるだろうって考え方だな
別に数学的知見じゃなくて、ただの問題解く手順のお気持ちみたいなもんだから、わからないんならわからんでいいよ

2022/12/08(木) 13:14:19.81

前回のAも、「多クエリを高速で処理できるんだから簡単な区間の特徴で1クエリ分解けるだろう（そもそもAGC-Aだし）」で想定解に至った人も割といるんじゃないか思っているが、発想的にはそれと似たようなものだと思うわ

2022/12/08(木) 14:18:33.85

区間の伸長が高速にできるなら、解が自明な長さ0や1の区間から始めるだけでは

2022/12/08(木) 14:28:51.79

自分がMoを考えたと言ったのは、1クエリ解くにしてもDPみたいに漸化式作れたらやりやすそうだからと思ったからかな
もちろん最初のクエリの答えは自明な区間から出発するよ

2022/12/08(木) 16:31:38.77

なおだいブログ曰くchatGPT使っていいらしいな
Cまでしか解けないしなんか問題文を変換しなきゃいけないらしいから茶以上だと意味ないけど

2022/12/08(木) 16:37:54.78

適当に自動化してA、B、CをChatGPTに瞬殺してもらって良いってことなの？

2022/12/08(木) 16:46:31.91

3問目まで自動で解いてくれるなら5分ぐらいは節約できるし多少はパフォ上がるかな

2022/12/08(木) 17:27:26.68

twitterから拾ってきたやつだけど
・英語版の問題文を与える
・数式等をTeXで書く(A_i, 10^2など)
・入力と出力の例を与える
・AtCoderの問題であることを教える
・Pythonで書かせる
必要があるっぽいから普通に解いたほうがいい気がするな

2022/12/08(木) 17:31:25.35

まだ発展途上とは言えイラストAIもあっちゅう間だったしな。
もう俺みたいな底辺は解く楽しさしか残らねーわ。

2022/12/08(木) 17:49:40.32

>>737
TeXへの変換規則さえちゃんと考えてコーディングしておけば、後は自動化できそうな感じもするな

2022/12/08(木) 17:54:32.49

これからはAIをうまく使う力が重要なのであれば、練習としてそういう解き方を研究するのもありだと思ってるわ

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プラプラ読んだことないから少し理解に時間がかかりそう
読んでみる