競技プログラミング総合スレ 66 (478ﾚｽ)
競技プログラミング総合スレ 66 http://mevius.5ch.net/test/read.cgi/tech/1679465982/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
126: デフォルトの名無しさん (ﾜｯﾁｮｲ 7f55-EYsv) [] 2023/04/06(木) 17:51:04.74 ID:AU30dZob0 O(N + M) ですと教えてもらって何が嬉しいですか？ この情報をどう利用しますか？ http://mevius.5ch.net/test/read.cgi/tech/1679465982/126
127: デフォルトの名無しさん (ｱｳｱｳｳｰ Sa23-VQD5) [sage] 2023/04/06(木) 17:56:13.19 ID:SUeW78Oka 計算量の話をする時って何も断りを入れなければ最悪計算量か平均計算量に決まってるのに普通じゃない時の話を持ち出してるのはどういう人種なんだ http://mevius.5ch.net/test/read.cgi/tech/1679465982/127
128: デフォルトの名無しさん (ﾜｯﾁｮｲ 5f05-RhFY) [sage] 2023/04/06(木) 18:01:17.36 ID:bgS53p4B0 すまん、明らかに間違ったことかいてたわ 辺が重複しないじゃなくて、連結グラフという前提ならそうですよね http://mevius.5ch.net/test/read.cgi/tech/1679465982/128
129: デフォルトの名無しさん (ｵｯﾍﾟｹ Sr33-eXH4) [sage] 2023/04/06(木) 18:52:38.27 ID:T+lwLVXUr うるせーバカ http://mevius.5ch.net/test/read.cgi/tech/1679465982/129
130: デフォルトの名無しさん (ﾜｯﾁｮｲ 5f05-RhFY) [sage] 2023/04/06(木) 19:04:02.38 ID:bgS53p4B0 サンキューガイジ！ http://mevius.5ch.net/test/read.cgi/tech/1679465982/130
131: デフォルトの名無しさん (ﾜｯﾁｮｲ 5f07-VQD5) [sage] 2023/04/06(木) 19:06:12.21 ID:O4MLKnYM0 自演失敗してて草 http://mevius.5ch.net/test/read.cgi/tech/1679465982/131
132: デフォルトの名無しさん (ﾜｯﾁｮｲ 5f05-RhFY) [sage] 2023/04/06(木) 19:07:23.88 ID:bgS53p4B0 自演ガイジも仲良くしようね http://mevius.5ch.net/test/read.cgi/tech/1679465982/132
133: デフォルトの名無しさん (ﾜｯﾁｮｲ 5f07-VQD5) [sage] 2023/04/06(木) 19:10:39.31 ID:O4MLKnYM0 効いてて草 http://mevius.5ch.net/test/read.cgi/tech/1679465982/133
134: デフォルトの名無しさん (ﾜｯﾁｮｲ 7f02-icd+) [sage] 2023/04/06(木) 19:18:25.49 ID:ejh7i/EB0 計算量の話って 満足な時間内にできるかどうかの議論でしか役に立たないよね http://mevius.5ch.net/test/read.cgi/tech/1679465982/134
135: デフォルトの名無しさん (ﾜｯﾁｮｲ df5f-vkwt) [sage] 2023/04/06(木) 19:29:21.38 ID:aDW8E5OM0 かかる時間が見積もれると嬉しいだろ O(M)でないものをO(M)って書いていいことにはならないけど http://mevius.5ch.net/test/read.cgi/tech/1679465982/135
136: デフォルトの名無しさん (ｽﾌﾟｰﾌﾟ Sd9f-PuAn) [sage] 2023/04/06(木) 19:53:45.59 ID:Ej/MkqD7d 幅優先探索はそもそもΩ(N+M)なケースが無いと思うからO(M)って書いて欲しいが、N=O(M)は自明じゃないと思うぞ N頂点0辺のグラフだってあるし http://mevius.5ch.net/test/read.cgi/tech/1679465982/136
137: デフォルトの名無しさん (ﾜｯﾁｮｲ 5f43-PuAn) [sage] 2023/04/06(木) 22:06:07.24 ID:qiEKlOzd0 すまん嘘書いた 幅優先探索って最初に距離配列を作るからO(N+M)で合ってたわ http://mevius.5ch.net/test/read.cgi/tech/1679465982/137
138: デフォルトの名無しさん (ｱｳｱｳｳｰ Sa23-bNUo) [sage] 2023/04/07(金) 18:56:18.33 ID:koL6xQVKa チョクダイ毎日AI下げしてるな、これくらい上流層でも脅威なんだな http://mevius.5ch.net/test/read.cgi/tech/1679465982/138
139: デフォルトの名無しさん (ﾜｯﾁｮｲ 7f55-EYsv) [] 2023/04/07(金) 19:05:30.59 ID:PbTiq3Mq0 高橋直大さんの実力は世界トップレベルなんですか？ http://mevius.5ch.net/test/read.cgi/tech/1679465982/139
140: デフォルトの名無しさん (ﾜｯﾁｮｲ 5f05-RhFY) [sage] 2023/04/07(金) 19:50:49.14 ID:4NY4d7fE0 いいえ http://mevius.5ch.net/test/read.cgi/tech/1679465982/140
141: デフォルトの名無しさん (ﾜｯﾁｮｲ ffca-7Vgv) [] 2023/04/07(金) 20:14:15.12 ID:Jyfuc8w80 赤レベルが解けるようになるのは10年以上かかるだろうけど、 コーディングテストとして売り物になる層はすでにほぼ終了だし、E,Fまで解けるようになったらほとんどの参加者の自力解答は無意味ということに。 GPT前提の問題作りか、時間をかけた試行錯誤は苦手だろうからヒューリスティック重視とかになっていくんじゃないだろうか。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/141
142: デフォルトの名無しさん (ﾜｯﾁｮｲ fe7c-UY1G) [sage] 2023/04/08(土) 00:54:27.43 ID:NWI0hhIl0 ヒューリスティックもある程度のレベルまでは行きそうだけどな 24時間コードを書かせ続けることもできるし http://mevius.5ch.net/test/read.cgi/tech/1679465982/142
143: デフォルトの名無しさん (ﾜｯﾁｮｲ a9b1-Q90w) [sage] 2023/04/08(土) 14:37:32.42 ID:d9UfkEh40 始めて一年の茶色のおっさんだけどAIに負けるレベルになったと聞いてモチベだだ下がり。俺みたいなやつ多いと思うよ。 そりゃ参加者減ったら焦るわな http://mevius.5ch.net/test/read.cgi/tech/1679465982/143
144: デフォルトの名無しさん (ﾜｯﾁｮｲ d907-NO7/) [sage] 2023/04/08(土) 14:48:17.63 ID:dzO9pS9o0 AIに負けるって言うがChatGPTは競プロ用にチューニングしたプログラミングAIじゃないぞ こいつができるのは問題を読むことと何を求められてるかを把握すること つまり日本語(あるいは英語)を読解するAIだ 要するに人類が負けてるのはプログラミング能力じゃなく読解力と記憶力なんだよ 今に見てろこいつらあらゆる分野でゲームと動画に浸かったお前らに国語力の差を見せつけてくるから http://mevius.5ch.net/test/read.cgi/tech/1679465982/144
145: デフォルトの名無しさん (ﾜｯﾁｮｲ e101-x1gv) [sage] 2023/04/08(土) 15:13:43.63 ID:H0kArwlU0 暖色レベルへの到達はあったとしてもかなり先だろうし競技としては成立するだろうけど緑〜水色くらいなら近い将来到達しそうだし新規参入と寒色停滞勢の参加率は減るかもね http://mevius.5ch.net/test/read.cgi/tech/1679465982/145
146: デフォルトの名無しさん (ｻｻｸｯﾃﾛﾙ Spd1-42TY) [sage] 2023/04/08(土) 15:15:38.10 ID:obJbbgz0p 競プロってゲームでやってるのかと思ってたからAIに負けてやる気なくなるってのはよくわからん http://mevius.5ch.net/test/read.cgi/tech/1679465982/146
147: デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM66-rOwk) [sage] 2023/04/08(土) 15:21:45.60 ID:YDsW15QlM ARC/AGCの中盤以降に競プロの本当の楽しさがあるという主張は否定しないが、ABCの前半も競技として楽しんでいた層の方がマジョリティで、そういう層が競プロの裾野を広げていた側面もあるから、コンテンツとしてダメージを受けざるを得ないと思うわ 企業もスポンサーをするのは基本ABCだし、Jobsで見られているのもレベル的にABCでの実力がメイン http://mevius.5ch.net/test/read.cgi/tech/1679465982/147
148: デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM66-rOwk) [sage] 2023/04/08(土) 15:23:40.74 ID:YDsW15QlM >>146 競技を楽しんでるのに競技そのものが成立しなくなったら嫌だろ？ Project Eulerみたいな感覚で問題に取り組んでいるんなら大丈夫だが、そういう人は初心者層ほど少ない http://mevius.5ch.net/test/read.cgi/tech/1679465982/148
149: デフォルトの名無しさん (ｻｻｸｯﾃﾛﾙ Spd1-42TY) [sage] 2023/04/08(土) 15:26:53.49 ID:obJbbgz0p >>148 他の人らがAI使って解答してるかもしれないと思ってしまうってこと？ http://mevius.5ch.net/test/read.cgi/tech/1679465982/149
150: デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM66-rOwk) [sage] 2023/04/08(土) 15:34:11.41 ID:YDsW15QlM >>149 バレる可能性が低く対策不能なチートが蔓延ったオンラインゲームは壊れるやろ ただのオンラインゲームでさえそうなのに、一応AtCoderはJobsみたいな実利的に意味のあるものと繋がってるから、みんな使うようになるんじゃねーの 開き直ってAIバトルにしても、投稿速度ゲームになりそうだし http://mevius.5ch.net/test/read.cgi/tech/1679465982/150
151: デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM66-rOwk) [sage] 2023/04/08(土) 15:35:24.79 ID:YDsW15QlM みんな使わないにしても、使ってるやつにレートを吸われることでモチベの減退はあるだろうな http://mevius.5ch.net/test/read.cgi/tech/1679465982/151
152: デフォルトの名無しさん (ｻｻｸｯﾃﾛﾙ Spd1-42TY) [sage] 2023/04/08(土) 15:36:44.41 ID:obJbbgz0p >>150 まあそういう人はスポーツすればいいよ アルゴリズム解くのが好きとか純粋に知識欲の高い人が残るんだろうね http://mevius.5ch.net/test/read.cgi/tech/1679465982/152
153: デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM66-rOwk) [sage] 2023/04/08(土) 15:43:15.50 ID:YDsW15QlM >>152 その辺の人でも楽しめる競技になる道は閉ざされそうで悲しいな 元々運営にそういうモチベなさそうだったが（金のために仕方なくやってる感満載だった） http://mevius.5ch.net/test/read.cgi/tech/1679465982/153
154: デフォルトの名無しさん (ﾜｯﾁｮｲ c6ca-HjNm) [] 2023/04/08(土) 19:32:52.09 ID:jzMk6Pp80 ノーレートで、食事したり飲みながら今までほぼ開かなかったF,GとかをchatGTPに聞いたり調べたりしながらやるのも楽しいぞい。解きたくない問題は解かなくても良いし。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/154
155: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/08(土) 20:03:48.77 ID:RgGs2QbX0 ワーシャル・フロイドアルゴリズムについて質問です。 最終的に任意の2点間の最短距離を入れるための2次元配列は、 代入演算子の左右で共通のものが使われています。 それでも、問題がないのはなぜですか？ http://mevius.5ch.net/test/read.cgi/tech/1679465982/155
156: デフォルトの名無しさん (ﾜｯﾁｮｲ 85a4-5f+B) [sage] 2023/04/08(土) 20:09:47.90 ID:8rEHJkBb0 ワーシャル・フロイドアルゴリズムは、全ての頂点間の最短距離を求めるためのアルゴリズムです。このアルゴリズムは、動的計画法の一種であり、一度計算された結果を再利用することで、計算量を減らすことができます。 具体的には、アルゴリズムの初期段階で、すべての頂点の間の距離を表す2次元配列を作成します。この配列は、アルゴリズムの途中で更新されますが、代入演算子の左右で共通のものが使われるため、問題はありません。 なぜなら、ア
ルゴリズムの途中で更新される値は、それ以前の値に依存しているため、代入演算子の左右で共通の2次元配列を使用していることによって、更新された値が正しく計算され、以前に計算された値が失われることはありません。 つまり、更新された値は、以前に計算された値に基づいて正確に計算され、以前に計算された値が配列内に保持され続けるため、代入演算子の左右で共通の2次元配列を使用することは、アルゴリズムの正しい動作に影響を与えないということです。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/156
157: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/08(土) 21:36:51.70 ID:RgGs2QbX0 >>155 大丈夫な理由が分かりました。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/157
158: デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb) [sage] 2023/04/08(土) 22:06:19.33 ID:8FTHKj1c0 chatGPT便利だろ こういう風に答えてくれる http://mevius.5ch.net/test/read.cgi/tech/1679465982/158
159: デフォルトの名無しさん (ﾜｯﾁｮｲ d907-NO7/) [sage] 2023/04/08(土) 22:12:19.75 ID:dzO9pS9o0 ものすごくもっともらしい嘘つくから知らないことを聞くのはおすすめしないぞ http://mevius.5ch.net/test/read.cgi/tech/1679465982/159
160: デフォルトの名無しさん (ﾜｯﾁｮｲ d907-NO7/) [sage] 2023/04/08(土) 22:16:56.23 ID:dzO9pS9o0 ワルシャワ・フローラル法を知ってる？ はい、ワルシャワ・フローラル法は、グラフの最大マッチングを求めるアルゴリズムの一種です。このアルゴリズムは、ハンガリー人数学者であるエドモンド・ワルシャワと、ポーランド人数学者であるタデウシュ・フローラルによって開発されました。 ワルシャワ・フローラル法は、ハンガリー法と同様に、最大マッチング問題を解決するために使用されます。このアルゴリズムは、二部グラフに適用されます。アルゴ
リズムの基本的な考え方は、各未マッチング頂点について、その頂点を始点とする増加路を探し、その増加路に属する辺のマッチングを反転させることです。 ワルシャワ・フローラル法は、ハンガリー法よりも効率的であることが知られていますが、完全グラフでは最悪の場合の計算量がO(n^4)であるため、実用的ではありません。しかし、一般のグラフに対しては、最大マッチングを高速に計算することができるため、実際には広く使用されています。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/160
161: デフォルトの名無しさん (ﾜｯﾁｮｲ 85a4-Az6A) [sage] 2023/04/09(日) 02:49:15.65 ID:3zzmmMIO0 正確なことを答えさせるために、プロンプトエンジニアリングをがんばりましょうね http://mevius.5ch.net/test/read.cgi/tech/1679465982/161
162: デフォルトの名無しさん (ﾜｯﾁｮｲ c69a-RdFw) [sage] 2023/04/09(日) 06:48:28.69 ID:/c2XAn9L0 素朴な整数演算のコードを書いたため、特定のテストケースのときにコードの途中で 整数がオーバーフローするような場合、一般的なコードの書き方の処方箋みたいなものは ありますかね 例えば「整数の配列から適切な要素を取り出して期待される和を作れ、そういう要素が ない場合はエラー値を返せ」みたいので、配列要素はどれもオーバーフローに近い整数、 和は配列内の最小要素よりちょっとだけ大きい値（なのでエラー値の場合）、とか.... http:/
/mevius.5ch.net/test/read.cgi/tech/1679465982/162
163: デフォルトの名無しさん (ﾜｯﾁｮｲ d907-NO7/) [sage] 2023/04/09(日) 10:26:45.20 ID:/OFxiXOD0 競プロならlong longを使うだけ 実務ならオーバーフローした時に例外が発生するようにしてそれをキャッチ http://mevius.5ch.net/test/read.cgi/tech/1679465982/163
164: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/09(日) 13:54:07.28 ID:l3qXUMY00 『アルゴリズム実技検定公式テキストエントリー〜中級編』 最小全域木を求める、「プリムのアルゴリズム」について説明があります。 こうすれば、求まるという説明はあるのですが、なぜ求まるのかの説明がありません。 みなさんは、こうすれば求まるという情報だけで十分で、それで満足しますか？ それとも、ちゃんと証明まで自分で考えるか、誰かが書いた証明を読みますか？ http://mevius.5ch.net/test/read.cgi/tech/1679465982/164
165: デフォルトの名無しさん (ﾜｯﾁｮｲ ae2b-RdFw) [sage] 2023/04/09(日) 14:45:06.26 ID:dl/B18nt0 >>163 なるほど。確かに例えば入力がintならlong longを使えばとりあえず大丈夫そう ちなみにC++ですが、例えばintのオーバーフローを例外で処理するのはどうしたら.... http://mevius.5ch.net/test/read.cgi/tech/1679465982/165
166: デフォルトの名無しさん (ﾜｯﾁｮｲ 85a4-5f+B) [sage] 2023/04/09(日) 14:49:24.80 ID:3zzmmMIO0 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. http://mevius.5ch.net/test/read.cgi/tech/1679465982/166
167: デフォルトの名無しさん (ﾜｯﾁｮｲ bd5f-EL/2) [sage] 2023/04/09(日) 16:13:00.47 ID:sd0zf58N0 gccの__builtin_add_overflowとか__builtin_mul_overflowを使う http://mevius.5ch.net/test/read.cgi/tech/1679465982/167
168: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/09(日) 18:08:06.26 ID:l3qXUMY00 github.com/kenkoooo/pastbook-source-code/blob/master/chukyu/python/chapter06/section11/6-11-1.py http://mevius.5ch.net/test/read.cgi/tech/1679465982/168
169: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/09(日) 18:11:31.29 ID:l3qXUMY00 ↑のファイルはプリムのアルゴリズムで最小全域木問題を解くコードです。 ファイル中の以下の箇所がなぜ必要なのかが分かりません。 一見すると、キューの中には、marked の値がFalseのノードしか入っていないように思うのですが、 実際には、Falseのノードも入ることがあるようです。（以下の箇所をコメントアウトすると パスしません。） # 辺につながる頂点 i もすでにマークされていた場合、 # 操作をスキップする if marked[i]: ■■■■continue
http://mevius.5ch.net/test/read.cgi/tech/1679465982/169
170: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/09(日) 18:16:05.03 ID:l3qXUMY00 一部、間違えましたので訂正します。↓ ↑のファイルはプリムのアルゴリズムで最小全域木問題を解くコードです。 ファイル中の以下の箇所がなぜ必要なのかが分かりません。 一見すると、キューの中には、marked の値がFalseのノードしか入っていないように思うのですが、 実際には、Trueのノードも入ることがあるようです。（以下の箇所をコメントアウトすると パスしません。） # 辺につながる頂点 i もすでにマークされていた場合、 # 操作をスキップ
する if marked[i]: ■■■■continue http://mevius.5ch.net/test/read.cgi/tech/1679465982/170
171: デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb) [sage] 2023/04/09(日) 18:19:09.47 ID:fcL4nlHr0 この部分は、既にマークされた頂点に対応する辺をスキップするために必要です。 確かに、キューには基本的に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 この部分に
よって、既にマークされた頂点に対応する辺をスキップし、 正しい最小全域木を構築することができます。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/171
172: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/09(日) 18:19:33.94 ID:l3qXUMY00 ヒープにプッシュする前に、そのノードがマークされていないことをチェックしています。 ですので、ヒープ内には、マークされていないノードしか入れないと思うのですが。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/172
173: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/09(日) 18:25:07.45 ID:l3qXUMY00 >>171 あまり参考にならないだろうと思って読んでいたらなぜか理由が分かりました。 マークされていない状態で、同じノードが複数個ヒープに入ることがあるわけですね。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/173
174: デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb) [sage] 2023/04/09(日) 18:28:01.90 ID:fcL4nlHr0 >>172 確かに、ヒープにプッシュする前にそのノードがマークされていないことをチェックしています。 ただし、ヒープにプッシュされた後で、そのノードが他の辺を経由してマークされる可能性があります。 そのため、ヒープから辺を取り出す前にもう一度マークされているかどうかをチェックする必要があります。 先程のグラフで考えてみましょう。キューがこの様になったところから解説します。 (1, 3), (1, 1), (1, 3) ここで、最初に(1, 3)
をキューから取り出し、頂点3をマークします。この時点で、キューには以下のような状態が残っています。 (1, 1), (1, 3) 次にキューから取り出す辺は(1, 1)です。この辺は、頂点1と頂点2の間にありますが、頂点1はすでにマークされています。 しかし、この辺をヒープにプッシュした時点では、頂点1はまだマークされていませんでした。 それが、例のコード部分が必要とされる理由です。 あの部分によって、既にマークされた頂点に対応する辺をスキップし、正しい最小全域木を構築することができます。 http://mevius.5ch.net/test/read.cgi/tech/167
9465982/174
175: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/09(日) 18:28:12.80 ID:l3qXUMY00 >>171 この場合でいうとノード3が2回ヒープに入るわけですね。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/175
176: デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb) [sage] 2023/04/09(日) 18:31:35.09 ID:fcL4nlHr0 >>175 はい、その通りです。 最初にノード1からノード3への辺がヒープに追加され、次にノード2からノード3への辺がヒープに追加されます。 (1, 3) <-- 1から3への辺 (1, 1) (1, 3) <-- 2から3への辺 このように、同じノードが複数回ヒープに入ることがあります。プリムのアルゴリズムでは、 すでにマークされた頂点に対応する辺を無視する必要があります。 そのため、ヒープから辺を取り出す前にマークされているかどうかをチェックす
る必要があるのです。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/176
177: デフォルトの名無しさん (ｱｳｱｳｳｰ Sa05-IjNm) [sage] 2023/04/09(日) 19:43:48.36 ID:O0uaasVha おんちぽまんぽげろろろり？ http://mevius.5ch.net/test/read.cgi/tech/1679465982/177
178: デフォルトの名無しさん (ﾌﾞｰｲﾓ MMf6-tIu7) [sage] 2023/04/09(日) 22:42:46.25 ID:fJZ93dkaM 序盤からムズすぎ http://mevius.5ch.net/test/read.cgi/tech/1679465982/178
179: デフォルトの名無しさん (ﾜｯﾁｮｲ d9b0-OQ9P) [sage] 2023/04/09(日) 22:44:46.28 ID:0uKKY8S80 Eむずい setとpriority queueいじくってたら通った http://mevius.5ch.net/test/read.cgi/tech/1679465982/179
180: デフォルトの名無しさん (ｻｻｸｯﾃﾛﾗ Spd1-x1gv) [sage] 2023/04/09(日) 22:47:55.78 ID:DKklNxRop E二分探索でやろうとしたらハマって普通にsetで順番にみるだけだった F解けたのに今回も解いてる人の数がF<Gなせいであまり順位伸びてないの配点何とかして欲しいわ http://mevius.5ch.net/test/read.cgi/tech/1679465982/180
181: デフォルトの名無しさん (ｽｯｯﾌﾟ Sd22-QZiB) [] 2023/04/09(日) 23:58:26.29 ID:BvehXBT4d 整数式の倍数判定のプログラム作りたいんだけどできる？ nは自然数 例1 入力:n(n+1)(n+2) 出力:6 (入力した式の倍数判定。6の倍数) 2の倍数でも3の倍数でもあるが、最も大きい数を出力 例2 入力:n^9-n^3 出力:504 http://mevius.5ch.net/test/read.cgi/tech/1679465982/181
182: デフォルトの名無しさん (ﾜｯﾁｮｲ eebb-Sq7r) [sage] 2023/04/10(月) 02:32:34.26 ID:Gn/yyThB0 >>181 nに素数をいくつか突っ込んだ値(0以外)で最大公約数とればいいんでない？ という気はするけど万年茶色脳には正しいか証明するなんてムリ http://mevius.5ch.net/test/read.cgi/tech/1679465982/182
183: デフォルトの名無しさん (ﾜｯﾁｮｲ bd5f-EL/2) [sage] 2023/04/10(月) 02:49:14.21 ID:zrtbja+Y0 素数pの倍数かどうかはmod pが整域だから多項式は根を高々次数d個しかもたないのでp≤dだけ調べればいいよね p^kはわからん http://mevius.5ch.net/test/read.cgi/tech/1679465982/183
184: デフォルトの名無しさん (ﾜｯﾁｮｲ bd5f-EL/2) [sage] 2023/04/10(月) 03:22:55.78 ID:zrtbja+Y0 fが零因子⇔あるa≠0が存在してaf=0らしいから、最初にfを係数のgcdで割っとけば零因子じゃなくなって、p^k≤dだけ調べればいいと思う http://mevius.5ch.net/test/read.cgi/tech/1679465982/184
185: デフォルトの名無しさん (ﾜｯﾁｮｲ bd5f-EL/2) [sage] 2023/04/10(月) 03:46:52.88 ID:zrtbja+Y0 >>184 これ全部嘘です 寝るか http://mevius.5ch.net/test/read.cgi/tech/1679465982/185
186: デフォルトの名無しさん (ﾌﾞｰｲﾓ MMf6-tIu7) [sage] 2023/04/10(月) 13:12:10.43 ID:Sbe/ma/bM mod p で何代入しても0になる多項式は例えば x(x-1)...(x-p+1) でp次を達成できて最適 mod p^n だとこれをn乗すると構成できるので（最適かは知らんが）pn次以下と評価できる だからpnがd以下の範囲を探索すれば良いが計算量は悪いな http://mevius.5ch.net/test/read.cgi/tech/1679465982/186
187: デフォルトの名無しさん (ﾌﾞｰｲﾓ MMf6-tIu7) [sage] 2023/04/10(月) 13:16:20.11 ID:Sbe/ma/bM >>186 馬鹿すぎ、評価すべき方向が逆 http://mevius.5ch.net/test/read.cgi/tech/1679465982/187
188: デフォルトの名無しさん (ﾜｯﾁｮｲ d9b0-OQ9P) [sage] 2023/04/10(月) 15:49:54.60 ID:1oGpX4FF0 Fはやってみたら簡単に解けた Gはgrundy数求めるとき単純な勘違いしてた むー悔しい http://mevius.5ch.net/test/read.cgi/tech/1679465982/188
189: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/10(月) 16:05:58.27 ID:/Pv3NVQa0 DAGの最長パスを求める問題について質問があります。 『アルゴリズム実技検定公式テキストエントリー〜中級編』に 「トポロジカルソート」の考え方が重要と書いてあります。 ですが、DAGがトポロジカルソートできるということを使っている 箇所が見当たりません。 載っている解法は、indegreeが0である頂点からの最長パスをDPにより求めるというものです。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/189
190: デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb) [sage] 2023/04/10(月) 16:12:48.08 ID:GqegRxcS0 確かに、その解法ではトポロジカルソートを明示的に実行していないように見えますが、 実際にはトポロジカルソートの考え方が含まれています。DAGの最長パスを求める際、 トポロジカルソートの概念が重要なのは、頂点の順序付けによって依存関係を解決することができるからです。 その解法で、indegree（入次数）が0の頂点からDPを用いて最長パスを求めています。これは、各頂点について、 その頂点に入ってくる辺がなくなる（依存関係が解決される
）順序で処理を行っていることを意味します。 この順序付けがトポロジカルソートの結果と同じです。 indegreeが0になる頂点から処理を行い、その後、処理された頂点から出る辺を削除することで、 indegreeが0になる頂点が次々と現れます。この手順は、トポロジカルソートを実行する手順と同じです。 したがって、トポロジカルソートを明示的に行わなくても、その考え方が解法に含まれているため、 問題を解決することができます。トポロジカルソートの概念は、DAGの最長パス問題を解く際の重要な考え方であることがわかります。 http://mevius.5ch.
net/test/read.cgi/tech/1679465982/190
191: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/10(月) 16:13:37.24 ID:/Pv3NVQa0 DAGであれば、最長パスが存在し、それはDPで求められる。 ただそれだけのことではないでしょうか？ http://mevius.5ch.net/test/read.cgi/tech/1679465982/191
192: デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb) [sage] 2023/04/10(月) 16:19:57.68 ID:GqegRxcS0 はい、おっしゃる通りです。DAGであれば、最長パスが存在し、動的計画法（DP）を用いて求めることができます。 繰り返しになりますが、トポロジカルソートの概念を用いることで、DAG内の頂点の順序付けが可能であり、 この順序付けに従ってDPを適用することで、最長パスを求めることができます。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/192
193: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/10(月) 16:20:04.87 ID:/Pv3NVQa0 DAGにoutdegreeおよびindegreeが0の点が両方とも存在することは、自明です。 もしそのような点がなければ、閉路が存在することになるからです。 トポロジカルソートなどという考え方を持ち出すまでもありません。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/193
194: デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb) [sage] 2023/04/10(月) 16:26:05.43 ID:GqegRxcS0 トポロジカルソートを明示的に実行しなくても、DAGの最長パス問題をDPで解くことは可能です。 ただし、その際に頂点の処理順序や依存関係の解決が重要となるため、トポロジカルソートの考え方が役立ちます。 トポロジカルソートを適用したDPでは、頂点の依存関係が効率的に解決されるため、計算量はO(V+E)です。 ここで、Vは頂点数、Eは辺数です。トポロジカルソートによって得られた頂点の順序に従ってDPを行うことで、 各頂点と辺に対して一度だけ
計算が行われます。 一方、トポロジカルソートを適用しないDPでは、無駄な計算が発生する可能性があります。 例えば、メモ化再帰を用いたDPの場合、計算量は最悪O(2^V)になることがあります。 これは、全ての頂点に対して、それぞれを含むか含まないかの選択肢があるためです。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/194
195: デフォルトの名無しさん (ﾜｯﾁｮｲ 417c-g1pj) [sage] 2023/04/10(月) 19:58:08.22 ID:6t40mDb70 >>181 多項式 f(n) について計算したい calc(f) で求めたい値を返す関数として f が定数ならそれを返す 定数でないなら g(n)=f(n+1)-f(n) とgを定めて calc(f) = gcd(f(1), calc(g)) を計算すればいい、再帰の深さはfの次数で抑えられる http://mevius.5ch.net/test/read.cgi/tech/1679465982/195
196: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/10(月) 20:30:41.82 ID:/Pv3NVQa0 『アルゴリズム実技検定公式テキストエントリー〜中級編』に載っている DAGの最長パスを求めるコードでは、トポロジカルソートを陽には使っていないです。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/196
197: デフォルトの名無しさん (ｱｳｱｳｳｰ Sa05-ynyP) [sage] 2023/04/10(月) 21:31:52.04 ID:Qr60KJ2xa その本持ってないからその本の解法教えて そしたら質問の回答するよ http://mevius.5ch.net/test/read.cgi/tech/1679465982/197
198: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/10(月) 21:57:16.12 ID:/Pv3NVQa0 >>197 ソースコードは以下です： github.com/kenkoooo/pastbook-source-code/blob/master/chukyu/python/chapter06/section04/6-4-8.py http://mevius.5ch.net/test/read.cgi/tech/1679465982/198
199: デフォルトの名無しさん (ｱｳｱｳｳｰ Sa05-ynyP) [sage] 2023/04/10(月) 22:22:43.61 ID:Qr60KJ2xa 確かに陽にトポロジカルソートはしてないね 値が確定する順序がトポロジカルソート順の逆順にはなってるけど 多分、以下のようなことを言いたいんじゃないかな ・各頂点の値を一つずつ順に確定していって、 ・一度確定した頂点を再度訪れる必要がない ・そのようなことが可能な確定順が存在する 確かに考え方によっては自明とも思えるかもしれないけど、逆にそれくらいのことしか言ってないということでは http://mevius.5ch.net/test/read.cgi/
tech/1679465982/199
200: デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb) [sage] 2023/04/10(月) 22:32:19.30 ID:GqegRxcS0 この問題の場合はメモ化再帰でトポロジカルソートを使わなくても計算量はO(N+M)です。 頂点間に循環がないため、再帰の深さが頂点数Nを超えることがなく、 各頂点に対して rec 関数が最大1回しか呼び出されないからです。 トポロジカルソートを使ってそのコードを書き換えるとこうなります。 https://ideone.com/1NbHIf http://mevius.5ch.net/test/read.cgi/tech/1679465982/200
201: デフォルトの名無しさん (ﾜｯﾁｮｲ 06d7-IjNm) [sage] 2023/04/11(火) 00:50:14.84 ID:AEAouguL0 んげりいいいいいいいwwwwww http://mevius.5ch.net/test/read.cgi/tech/1679465982/201
202: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/11(火) 10:56:16.23 ID:KVT1yw8N0 >>199-200 ありがとうございました。 >>200 コードを見たのですが、 # トポロジカルソートで得られた順序に沿って最長経路を更新 for u in order: for v in edges[u]: length[v] = max(length[v], length[u] + 1) の「for u in order:」でなぜ良いのかが分かりません。orderの要素を後ろから見ていかなければ ならないように思ったのですが、そうではないのはなぜでしょうか？ http://mevius.5ch.net/test/read.cgi/tech/1679465982/202
203: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/11(火) 11:11:09.23 ID:KVT1yw8N0 for u in order: ■■■■print(u) とすると自分が思っている順序とちょうど逆順で表示されます。 order.append(u) を実行すると order の最大インデックスの要素の次に u が挿入されますよね。 そうだとすると、 order[0], order[1], … は queue から出てきた順に並べたものになりますよね。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/203
204: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/11(火) 11:15:16.38 ID:KVT1yw8N0 多分、単純な勘違いなんですが、どこを勘違いしているのかが分かりません。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/204
205: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/11(火) 11:16:45.70 ID:KVT1yw8N0 あ、分かりました。 与えられた有向グラフの辺の向きをすべて逆にしても、最長パスの長さは変わりませんね。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/205
206: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/11(火) 11:35:54.50 ID:KVT1yw8N0 以下のコードは全く無駄なことをやっていますが、自分の理解通りなのはこちらのコードです： ideone.com/gMUZDZ http://mevius.5ch.net/test/read.cgi/tech/1679465982/206
ﾒﾓ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 272 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.026s