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

2023/03/22(水) 15:19:42.08

!extend:checked:vvvvv:1000:512
!extend:checked:vvvvv:1000:512
!extend:checked:vvvvv:1000:512
↑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/

※前スレ
競技プログラミング総合スレ 65
https://mevius.5ch.net/test/read.cgi/tech/1672026457/ VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

2023/04/04(火) 13:23:54.73

寒色がイキってんなー

2023/04/04(火) 14:09:52.51

ガイジ同士仲良くしようね、ってことだよ

2023/04/04(火) 16:38:00.80

ある頂点に対して、2つの子それぞれを根とする部分木の情報が定まってれば、その頂点について簡単に判定できる
数学的帰納法の考え方というか、局所的には簡単な処理できるってことがわかるとそんなに大変じゃなくなる

2023/04/04(火) 16:58:58.57

>>89
より良い書き方があるならコード見たいです
Pythonだと慣れてるので嬉しいです

2023/04/04(火) 17:16:22.71

89でコメントした通りだよ

2023/04/04(火) 17:59:57.64

ガイジ同士仲良くしろよw
仲良くしようと頑張ってそれなのかw

2023/04/04(火) 18:10:30.05

>>94
minとかmaxって関数のことですよね？
これないと上位ノードより大きい値が左の下位ノードに存在することを許しちゃいませんか？

2023/04/04(火) 18:16:52.31

もしかして自演でやり取りしてるんじゃないかと思うくらいどっちも頭悪いな

2023/04/04(火) 19:37:36.74

if not (minVal < root.data < maxVal):
return False
がある時点で明らかにその下の行では
min(maxVal, root.data)) == root.data
じゃない？

2023/04/04(火) 19:51:05.61

そら明らかだよ

2023/04/04(火) 20:15:59.15

>>98
leetcodeにもそういうコードありました
もう一回やり直してみます
ありがとうございました

2023/04/04(火) 20:17:37.51

BSTって何ンゴ？

2023/04/04(火) 20:19:04.15

余計なものの中に最後の一行についての言及がないということは二人()ともあのif文は要ると思ってるんだろうな

2023/04/04(火) 20:19:51.59

>>101
二分探索木

2023/04/04(火) 20:21:24.74

if文じゃなくif式か

2023/04/04(火) 20:25:46.72

確かにそんなちゃんと読んでねえ

2023/04/04(火) 20:39:40.28

>>103
あっそっかぁ……
二分探索木判定とかしたいときあるか？

2023/04/04(火) 20:43:03.69

>>106
平衡二分木の実装をデバッグする時くらいかな

2023/04/04(火) 21:14:56.40

たしかに最後のifもいらねーじゃん
ガイジが集まれば強力なガイジになれそうだな

2023/04/05(水) 07:32:45.91

ガイジは低レベルなところでワヤワヤやってただけだろw

2023/04/05(水) 07:51:29.52

きみはもしかして高レベルなガイジなの？

2023/04/05(水) 08:33:49.11

一人前にカチンときたか

**デフォルトの名無しさん** (JP 0H83-RhFY) · 2023/04/05(水) 08:39:59.26

みんなガイジなんだから仲良くしようね

2023/04/05(水) 08:40:53.22

まずお前は素人の質問を見てマウント取らないようにするところから始めたらいいと思うぞガイジw

2023/04/05(水) 08:42:54.34

誰でも見た瞬間わかることをさも有能ムーブで語るのは流石に見てるだけでイタいから

2023/04/05(水) 09:11:39.70

効いてて草

2023/04/05(水) 09:13:29.61

毎日壊れたレコードみたいに戯言つぶやいてないでガイジスレに帰れよw

2023/04/05(水) 10:36:55.94

お前らもこっちきな😘
あっちは何を書き込んでもいいぞ🤗

2023/04/05(水) 11:41:26.97

こっちも何書き込んでも大丈夫だぞ😉

2023/04/05(水) 17:58:38.15

マジで寒いノリだな

2023/04/05(水) 18:27:04.88

効いてるガイジ君ってずっといるんだなって

2023/04/05(水) 21:21:21.09

みんな効かないように頑張ろう

2023/04/06(木) 17:29:09.91

幅優先探索の計算量が O(N + M)（N は頂点数, M は辺数）ですが、
N と M は異なる種類の変数です。

計算量は、 O(N + M) ですと言われてもピンときません。

普通は、 N << M だと思うので、 O(M) でいいような気がします。

例えば、連結グラフの場合、 N - 1 ≦ M ですよね。

2023/04/06(木) 17:42:27.24

辺が重複しない、という前提を入れるならそうですよね

2023/04/06(木) 17:42:52.77

ウィキペディアにはO(M)と書いてあるぞ

2023/04/06(木) 17:49:53.74

普通は、と言ったって例外はあるやろ

2023/04/06(木) 17:51:04.74

O(N + M) ですと教えてもらって何が嬉しいですか？
この情報をどう利用しますか？

2023/04/06(木) 17:56:13.19

計算量の話をする時って何も断りを入れなければ最悪計算量か平均計算量に決まってるのに普通じゃない時の話を持ち出してるのはどういう人種なんだ

2023/04/06(木) 18:01:17.36

すまん、明らかに間違ったことかいてたわ
辺が重複しないじゃなくて、連結グラフという前提ならそうですよね

2023/04/06(木) 18:52:38.27

うるせーバカ

2023/04/06(木) 19:04:02.38

サンキューガイジ！

2023/04/06(木) 19:06:12.21

自演失敗してて草

2023/04/06(木) 19:07:23.88

自演ガイジも仲良くしようね

2023/04/06(木) 19:10:39.31

効いてて草

2023/04/06(木) 19:18:25.49

計算量の話って
満足な時間内にできるかどうかの議論でしか役に立たないよね

2023/04/06(木) 19:29:21.38

かかる時間が見積もれると嬉しいだろ
O(M)でないものをO(M)って書いていいことにはならないけど

2023/04/06(木) 19:53:45.59

幅優先探索はそもそもΩ(N+M)なケースが無いと思うからO(M)って書いて欲しいが、N=O(M)は自明じゃないと思うぞ
N頂点0辺のグラフだってあるし

2023/04/06(木) 22:06:07.24

すまん嘘書いた
幅優先探索って最初に距離配列を作るからO(N+M)で合ってたわ

2023/04/07(金) 18:56:18.33

チョクダイ毎日AI下げしてるな、これくらい上流層でも脅威なんだな

2023/04/07(金) 19:05:30.59

高橋直大さんの実力は世界トップレベルなんですか？

2023/04/07(金) 19:50:49.14

いいえ

2023/04/07(金) 20:14:15.12

赤レベルが解けるようになるのは10年以上かかるだろうけど、
コーディングテストとして売り物になる層はすでにほぼ終了だし、E,Fまで解けるようになったらほとんどの参加者の自力解答は無意味ということに。
GPT前提の問題作りか、時間をかけた試行錯誤は苦手だろうからヒューリスティック重視とかになっていくんじゃないだろうか。

2023/04/08(土) 00:54:27.43

ヒューリスティックもある程度のレベルまでは行きそうだけどな
24時間コードを書かせ続けることもできるし

2023/04/08(土) 14:37:32.42

始めて一年の茶色のおっさんだけどAIに負けるレベルになったと聞いてモチベだだ下がり。俺みたいなやつ多いと思うよ。
そりゃ参加者減ったら焦るわな

2023/04/08(土) 14:48:17.63

AIに負けるって言うがChatGPTは競プロ用にチューニングしたプログラミングAIじゃないぞ
こいつができるのは問題を読むことと何を求められてるかを把握すること
つまり日本語(あるいは英語)を読解するAIだ
要するに人類が負けてるのはプログラミング能力じゃなく読解力と記憶力なんだよ
今に見てろこいつらあらゆる分野でゲームと動画に浸かったお前らに国語力の差を見せつけてくるから

2023/04/08(土) 15:13:43.63

暖色レベルへの到達はあったとしてもかなり先だろうし競技としては成立するだろうけど緑～水色くらいなら近い将来到達しそうだし新規参入と寒色停滞勢の参加率は減るかもね

2023/04/08(土) 15:15:38.10

競プロってゲームでやってるのかと思ってたからAIに負けてやる気なくなるってのはよくわからん

2023/04/08(土) 15:21:45.60

ARC/AGCの中盤以降に競プロの本当の楽しさがあるという主張は否定しないが、ABCの前半も競技として楽しんでいた層の方がマジョリティで、そういう層が競プロの裾野を広げていた側面もあるから、コンテンツとしてダメージを受けざるを得ないと思うわ
企業もスポンサーをするのは基本ABCだし、Jobsで見られているのもレベル的にABCでの実力がメイン

2023/04/08(土) 15:23:40.74

>>146
競技を楽しんでるのに競技そのものが成立しなくなったら嫌だろ？
Project Eulerみたいな感覚で問題に取り組んでいるんなら大丈夫だが、そういう人は初心者層ほど少ない

2023/04/08(土) 15:26:53.49

>>148
他の人らがAI使って解答してるかもしれないと思ってしまうってこと？

2023/04/08(土) 15:34:11.41

>>149
バレる可能性が低く対策不能なチートが蔓延ったオンラインゲームは壊れるやろ
ただのオンラインゲームでさえそうなのに、一応AtCoderはJobsみたいな実利的に意味のあるものと繋がってるから、みんな使うようになるんじゃねーの
開き直ってAIバトルにしても、投稿速度ゲームになりそうだし

2023/04/08(土) 15:35:24.79

みんな使わないにしても、使ってるやつにレートを吸われることでモチベの減退はあるだろうな

2023/04/08(土) 15:36:44.41

>>150
まあそういう人はスポーツすればいいよ
アルゴリズム解くのが好きとか純粋に知識欲の高い人が残るんだろうね

2023/04/08(土) 15:43:15.50

>>152
その辺の人でも楽しめる競技になる道は閉ざされそうで悲しいな
元々運営にそういうモチベなさそうだったが（金のために仕方なくやってる感満載だった）

2023/04/08(土) 19:32:52.09

ノーレートで、食事したり飲みながら今までほぼ開かなかったF,GとかをchatGTPに聞いたり調べたりしながらやるのも楽しいぞい。解きたくない問題は解かなくても良いし。

2023/04/08(土) 20:03:48.77

ワーシャル・フロイドアルゴリズムについて質問です。

最終的に任意の2点間の最短距離を入れるための2次元配列は、
代入演算子の左右で共通のものが使われています。
それでも、問題がないのはなぜですか？

2023/04/08(土) 20:09:47.90

ワーシャル・フロイドアルゴリズムは、全ての頂点間の最短距離を求めるためのアルゴリズムです。このアルゴリズムは、動的計画法の一種であり、一度計算された結果を再利用することで、計算量を減らすことができます。

具体的には、アルゴリズムの初期段階で、すべての頂点の間の距離を表す2次元配列を作成します。この配列は、アルゴリズムの途中で更新されますが、代入演算子の左右で共通のものが使われるため、問題はありません。

なぜなら、アルゴリズムの途中で更新される値は、それ以前の値に依存しているため、代入演算子の左右で共通の2次元配列を使用していることによって、更新された値が正しく計算され、以前に計算された値が失われることはありません。

つまり、更新された値は、以前に計算された値に基づいて正確に計算され、以前に計算された値が配列内に保持され続けるため、代入演算子の左右で共通の2次元配列を使用することは、アルゴリズムの正しい動作に影響を与えないということです。

2023/04/08(土) 21:36:51.70

>>155

大丈夫な理由が分かりました。

2023/04/08(土) 22:06:19.33

chatGPT便利だろ
こういう風に答えてくれる

2023/04/08(土) 22:12:19.75

ものすごくもっともらしい嘘つくから知らないことを聞くのはおすすめしないぞ

2023/04/08(土) 22:16:56.23

ワルシャワ・フローラル法を知ってる？

はい、ワルシャワ・フローラル法は、グラフの最大マッチングを求めるアルゴリズムの一種です。このアルゴリズムは、ハンガリー人数学者であるエドモンド・ワルシャワと、ポーランド人数学者であるタデウシュ・フローラルによって開発されました。

ワルシャワ・フローラル法は、ハンガリー法と同様に、最大マッチング問題を解決するために使用されます。このアルゴリズムは、二部グラフに適用されます。アルゴリズムの基本的な考え方は、各未マッチング頂点について、その頂点を始点とする増加路を探し、その増加路に属する辺のマッチングを反転させることです。

ワルシャワ・フローラル法は、ハンガリー法よりも効率的であることが知られていますが、完全グラフでは最悪の場合の計算量がO(n^4)であるため、実用的ではありません。しかし、一般のグラフに対しては、最大マッチングを高速に計算することができるため、実際には広く使用されています。

2023/04/09(日) 02:49:15.65

正確なことを答えさせるために、プロンプトエンジニアリングをがんばりましょうね

2023/04/09(日) 06:48:28.69

素朴な整数演算のコードを書いたため、特定のテストケースのときにコードの途中で
整数がオーバーフローするような場合、一般的なコードの書き方の処方箋みたいなものは
ありますかね

例えば「整数の配列から適切な要素を取り出して期待される和を作れ、そういう要素が
ない場合はエラー値を返せ」みたいので、配列要素はどれもオーバーフローに近い整数、
和は配列内の最小要素よりちょっとだけ大きい値（なのでエラー値の場合）、とか....

2023/04/09(日) 10:26:45.20

競プロならlong longを使うだけ
実務ならオーバーフローした時に例外が発生するようにしてそれをキャッチ

2023/04/09(日) 13:54:07.28

『アルゴリズム実技検定公式テキストエントリー～中級編』

最小全域木を求める、「プリムのアルゴリズム」について説明があります。
こうすれば、求まるという説明はあるのですが、なぜ求まるのかの説明がありません。

みなさんは、こうすれば求まるという情報だけで十分で、それで満足しますか？

それとも、ちゃんと証明まで自分で考えるか、誰かが書いた証明を読みますか？

2023/04/09(日) 14:45:06.26

>>163
なるほど。確かに例えば入力がintならlong longを使えばとりあえず大丈夫そう
ちなみにC++ですが、例えばintのオーバーフローを例外で処理するのはどうしたら....

2023/04/09(日) 14:49:24.80

C++でオーバーフローを検出する方法はいくつかありますが、一般的なものは以下のようになります¹²³。

- 演算前に範囲チェックを行う。例えば、a + b がオーバーフローするかどうかは、a > INT_MAX - b か a < INT_MIN - b で判定できる。
- 符号なし整数を使う。符号なし整数のオーバーフローは定義されているので、演算後に結果が元の値より小さくなっていないかチェックすればよい。
- boostライブラリのsafe_numericsを使う。これはオーバーフローを検出するための特別な型を提供しており、オーバーフローが発生した場合に例外を投げる。

(1) Detecting signed overflow in C/C++ - Stack Overflow. https://stackoverflow.com/questions/3944505/detecting-signed-overflow-in-c-c アクセス日時 4/9/2023.
(2) c++ - How do I detect unsigned integer overflow? - Stack Overflow. https://stackoverflow.com/questions/199333/how-do-i-detect-unsigned-integer-overflow アクセス日時 4/9/2023.
(3) c - How to check if overflow occured? - Stack Overflow. https://stackoverflow.com/questions/7683685/how-to-check-if-overflow-occured アクセス日時 4/9/2023.

2023/04/09(日) 16:13:00.47

gccの__builtin_add_overflowとか__builtin_mul_overflowを使う

2023/04/09(日) 18:08:06.26

github.com/kenkoooo/pastbook-source-code/blob/master/chukyu/python/chapter06/section11/6-11-1.py

2023/04/09(日) 18:11:31.29

↑のファイルはプリムのアルゴリズムで最小全域木問題を解くコードです。
ファイル中の以下の箇所がなぜ必要なのかが分かりません。
一見すると、キューの中には、marked の値がFalseのノードしか入っていないように思うのですが、
実際には、Falseのノードも入ることがあるようです。（以下の箇所をコメントアウトすると
パスしません。）

# 辺につながる頂点 i もすでにマークされていた場合、
# 操作をスキップする
if marked[i]:
■■■■continue

2023/04/09(日) 18:16:05.03

一部、間違えましたので訂正します。↓

↑のファイルはプリムのアルゴリズムで最小全域木問題を解くコードです。
ファイル中の以下の箇所がなぜ必要なのかが分かりません。
一見すると、キューの中には、marked の値がFalseのノードしか入っていないように思うのですが、
実際には、Trueのノードも入ることがあるようです。（以下の箇所をコメントアウトすると
パスしません。）

# 辺につながる頂点 i もすでにマークされていた場合、
# 操作をスキップする
if marked[i]:
■■■■continue

2023/04/09(日) 18:19:09.47

この部分は、既にマークされた頂点に対応する辺をスキップするために必要です。
確かに、キューには基本的にmarkedの値がFalseのノードしか入らないように見えますが、
実際には同じノードに対して複数の辺がキューに入ることがあります。

例えば、次のようなグラフを考えてみましょう。
1 -- 2
| /
| /
3
各辺の重みはすべて1とします。最初に頂点1を選び、marked[1]=Trueとします。
次に、頂点1に隣接する辺をキューに追加します。

この時点でキューの状態は以下のようになります。
(1, 2), (1, 3)

次に、キューから最小の重みの辺を取り出し、それに接続されている頂点2をマークします。
頂点2に隣接する辺をキューに追加します。

この時点でキューの状態は以下のようになります。
(1, 3), (1, 1), (1, 3)

ここで、次にキューから取り出す辺が(1, 1)であることに注意してください。
ただし、頂点1はすでにマークされているため、この辺を使ってしまうと、最小全域木の条件を満たさなくなります。
これが、以下のコード部分が必要とされる理由です。

if marked[i]:
continue
この部分によって、既にマークされた頂点に対応する辺をスキップし、
正しい最小全域木を構築することができます。

2023/04/09(日) 18:19:33.94

ヒープにプッシュする前に、そのノードがマークされていないことをチェックしています。
ですので、ヒープ内には、マークされていないノードしか入れないと思うのですが。

2023/04/09(日) 18:25:07.45

>>171
あまり参考にならないだろうと思って読んでいたらなぜか理由が分かりました。
マークされていない状態で、同じノードが複数個ヒープに入ることがあるわけですね。

2023/04/09(日) 18:28:01.90

>>172
確かに、ヒープにプッシュする前にそのノードがマークされていないことをチェックしています。
ただし、ヒープにプッシュされた後で、そのノードが他の辺を経由してマークされる可能性があります。
そのため、ヒープから辺を取り出す前にもう一度マークされているかどうかをチェックする必要があります。

先程のグラフで考えてみましょう。キューがこの様になったところから解説します。
(1, 3), (1, 1), (1, 3)

ここで、最初に(1, 3)をキューから取り出し、頂点3をマークします。この時点で、キューには以下のような状態が残っています。
(1, 1), (1, 3)

次にキューから取り出す辺は(1, 1)です。この辺は、頂点1と頂点2の間にありますが、頂点1はすでにマークされています。
しかし、この辺をヒープにプッシュした時点では、頂点1はまだマークされていませんでした。
それが、例のコード部分が必要とされる理由です。

あの部分によって、既にマークされた頂点に対応する辺をスキップし、正しい最小全域木を構築することができます。

2023/04/09(日) 18:28:12.80

>>171
この場合でいうとノード3が2回ヒープに入るわけですね。

2023/04/09(日) 18:31:35.09

>>175
はい、その通りです。
最初にノード1からノード3への辺がヒープに追加され、次にノード2からノード3への辺がヒープに追加されます。

(1, 3) <-- 1から3への辺
(1, 1)
(1, 3) <-- 2から3への辺

このように、同じノードが複数回ヒープに入ることがあります。プリムのアルゴリズムでは、
すでにマークされた頂点に対応する辺を無視する必要があります。
そのため、ヒープから辺を取り出す前にマークされているかどうかをチェックする必要があるのです。

2023/04/09(日) 19:43:48.36

おんちぽまんぽげろろろり？

2023/04/09(日) 22:42:46.25

序盤からムズすぎ

2023/04/09(日) 22:44:46.28

Eむずい
setとpriority queueいじくってたら通った

2023/04/09(日) 22:47:55.78

E二分探索でやろうとしたらハマって普通にsetで順番にみるだけだった
F解けたのに今回も解いてる人の数がF<Gなせいであまり順位伸びてないの配点何とかして欲しいわ

2023/04/09(日) 23:58:26.29

整数式の倍数判定のプログラム作りたいんだけどできる？
nは自然数

例1

入力:n(n+1)(n+2)
出力:6

(入力した式の倍数判定。6の倍数)
2の倍数でも3の倍数でもあるが、最も大きい数を出力

例2
入力:n^9-n^3
出力:504

2023/04/10(月) 02:32:34.26

>>181
nに素数をいくつか突っ込んだ値(0以外)で最大公約数とればいいんでない？
という気はするけど万年茶色脳には正しいか証明するなんてムリ

2023/04/10(月) 02:49:14.21

素数pの倍数かどうかはmod pが整域だから多項式は根を高々次数d個しかもたないのでp≤dだけ調べればいいよね
p^kはわからん

2023/04/10(月) 03:22:55.78

fが零因子⇔あるa≠0が存在してaf=0らしいから、最初にfを係数のgcdで割っとけば零因子じゃなくなって、p^k≤dだけ調べればいいと思う

2023/04/10(月) 03:46:52.88

>>184
これ全部嘘です寝るか

2023/04/10(月) 13:12:10.43

mod p で何代入しても0になる多項式は例えば x(x-1)...(x-p+1) でp次を達成できて最適
mod p^n だとこれをn乗すると構成できるので（最適かは知らんが）pn次以下と評価できる
だからpnがd以下の範囲を探索すれば良いが計算量は悪いな

2023/04/10(月) 13:16:20.11

>>186
馬鹿すぎ、評価すべき方向が逆

2023/04/10(月) 15:49:54.60

Fはやってみたら簡単に解けた
Gはgrundy数求めるとき単純な勘違いしてた
むー悔しい

2023/04/10(月) 16:05:58.27

DAGの最長パスを求める問題について質問があります。

『アルゴリズム実技検定公式テキストエントリー～中級編』に
「トポロジカルソート」の考え方が重要と書いてあります。
ですが、DAGがトポロジカルソートできるということを使っている
箇所が見当たりません。

載っている解法は、indegreeが0である頂点からの最長パスをDPにより求めるというものです。