競技プログラミング総合スレ 66 (478ﾚｽ)
上下前次1-新
103(1): (ｱｳｱｳｳｰ Sa23-VQD5) 2023/04/04(火)20:19 ID:/ayUyQoPa(4/6) AAS
>>101
二分探索木
104: (ｱｳｱｳｳｰ Sa23-VQD5) 2023/04/04(火)20:21 ID:/ayUyQoPa(5/6) AAS
if文じゃなくif式か
105: (ﾜｯﾁｮｲ df5f-vkwt) 2023/04/04(火)20:25 ID:jf1j38ly0(2/2) AAS
確かに そんなちゃんと読んでねえ
106(1): (ｵｯﾍﾟｹ Sr33-eXH4) 2023/04/04(火)20:39 ID:L6sdRXYAr(2/2) AAS
>>103
あっそっかぁ……
二分探索木判定とかしたいときあるか？
107: (ｱｳｱｳｳｰ Sa23-VQD5) 2023/04/04(火)20:43 ID:/ayUyQoPa(6/6) AAS
>>106
平衡二分木の実装をデバッグする時くらいかな
108: (ﾜｯﾁｮｲ 5f05-RhFY) 2023/04/04(火)21:14 ID:t/xEUfRa0(5/5) AAS
たしかに最後のifもいらねーじゃん
ガイジが集まれば強力なガイジになれそうだな
109: (ﾜｯﾁｮｲ 5f07-VQD5) 2023/04/05(水)07:32 ID:xDsMBQrA0(1/4) AAS
ガイジは低レベルなところでワヤワヤやってただけだろw
110: (ﾜｯﾁｮｲ dfa4-RhFY) 2023/04/05(水)07:51 ID:V9g+Im060(1) AAS
きみはもしかして高レベルなガイジなの？
111: (ﾜｯﾁｮｲ 5f07-VQD5) 2023/04/05(水)08:33 ID:xDsMBQrA0(2/4) AAS
一人前にカチンときたか
112: (JP 0H83-RhFY) 2023/04/05(水)08:39 ID:YYcedFeHH(1) AAS
みんなガイジなんだから仲良くしようね
113: (ﾜｯﾁｮｲ 5f07-VQD5) 2023/04/05(水)08:40 ID:xDsMBQrA0(3/4) AAS
まずお前は素人の質問を見てマウント取らないようにするところから始めたらいいと思うぞガイジw
114: (ﾜｯﾁｮｲ 5f07-VQD5) 2023/04/05(水)08:42 ID:xDsMBQrA0(4/4) AAS
誰でも見た瞬間わかることをさも有能ムーブで語るのは流石に見てるだけでイタいから
115: (ﾜｯﾁｮｲ 5f05-RhFY) 2023/04/05(水)09:11 ID:kAD3is4b0(1) AAS
効いてて草
116: (ｱｳｱｳｳｰ Sa23-VQD5) 2023/04/05(水)09:13 ID:jU3TV3ZDa(1) AAS
毎日壊れたレコードみたいに戯言つぶやいてないでガイジスレに帰れよw
117: (ｵｯﾍﾟｹ Sr33-GKj5) 2023/04/05(水)10:36 ID:ZG/fEbXfr(1) AAS
お前らもこっちきな😘
あっちは何を書き込んでもいいぞ🤗
118: (ﾜｯﾁｮｲ ffd7-7kGg) 2023/04/05(水)11:41 ID:PMDplXIF0(1) AAS
こっちも何書き込んでも大丈夫だぞ😉
119: (ﾃﾃﾝﾃﾝﾃﾝ MM4f-Qm86) 2023/04/05(水)17:58 ID:RPvbx/wwM(1) AAS
マジで寒いノリだな
120: (ﾜｯﾁｮｲ 5f07-VQD5) 2023/04/05(水)18:27 ID:sB818/CP0(1) AAS
効いてるガイジ君ってずっといるんだなって
121: (ﾜｯﾁｮｲ df2c-7kGg) 2023/04/05(水)21:21 ID:ez4hA7yb0(1) AAS
みんな効かないように頑張ろう
122: (ﾜｯﾁｮｲ 7f55-EYsv) 2023/04/06(木)17:29 ID:AU30dZob0(1/2) AAS
幅優先探索の計算量が O(N + M)（N は頂点数, M は辺数）ですが、
N と M は異なる種類の変数です。
計算量は、 O(N + M) ですと言われてもピンときません。
普通は、 N << M だと思うので、 O(M) でいいような気がします。
例えば、連結グラフの場合、 N - 1 ≦ M ですよね。
123: (ﾜｯﾁｮｲ 5f05-RhFY) 2023/04/06(木)17:42 ID:bgS53p4B0(1/4) AAS
辺が重複しない、という前提を入れるならそうですよね
124: (ｱｳｱｳｳｰ Sa23-VQD5) 2023/04/06(木)17:42 ID:SUeW78Oka(1/2) AAS
ウィキペディアにはO(M)と書いてあるぞ
125: (ｱｳｱｳｳｰ Sa23-AjAb) 2023/04/06(木)17:49 ID:2uDXGWIaa(1) AAS
普通は、と言ったって例外はあるやろ
126: (ﾜｯﾁｮｲ 7f55-EYsv) 2023/04/06(木)17:51 ID:AU30dZob0(2/2) AAS
O(N + M) ですと教えてもらって何が嬉しいですか？
この情報をどう利用しますか？
127: (ｱｳｱｳｳｰ Sa23-VQD5) 2023/04/06(木)17:56 ID:SUeW78Oka(2/2) AAS
計算量の話をする時って何も断りを入れなければ最悪計算量か平均計算量に決まってるのに普通じゃない時の話を持ち出してるのはどういう人種なんだ
128: (ﾜｯﾁｮｲ 5f05-RhFY) 2023/04/06(木)18:01 ID:bgS53p4B0(2/4) AAS
すまん、明らかに間違ったことかいてたわ
辺が重複しないじゃなくて、連結グラフという前提ならそうですよね
129: (ｵｯﾍﾟｹ Sr33-eXH4) 2023/04/06(木)18:52 ID:T+lwLVXUr(1) AAS
うるせーバカ
130: (ﾜｯﾁｮｲ 5f05-RhFY) 2023/04/06(木)19:04 ID:bgS53p4B0(3/4) AAS
サンキューガイジ！
131: (ﾜｯﾁｮｲ 5f07-VQD5) 2023/04/06(木)19:06 ID:O4MLKnYM0(1/2) AAS
自演失敗してて草
132: (ﾜｯﾁｮｲ 5f05-RhFY) 2023/04/06(木)19:07 ID:bgS53p4B0(4/4) AAS
自演ガイジも仲良くしようね
133: (ﾜｯﾁｮｲ 5f07-VQD5) 2023/04/06(木)19:10 ID:O4MLKnYM0(2/2) AAS
効いてて草
134: (ﾜｯﾁｮｲ 7f02-icd+) 2023/04/06(木)19:18 ID:ejh7i/EB0(1) AAS
計算量の話って
満足な時間内にできるかどうかの議論でしか役に立たないよね
135: (ﾜｯﾁｮｲ df5f-vkwt) 2023/04/06(木)19:29 ID:aDW8E5OM0(1) AAS
かかる時間が見積もれると嬉しいだろ
O(M)でないものをO(M)って書いていいことにはならないけど
136: (ｽﾌﾟｰﾌﾟ Sd9f-PuAn) 2023/04/06(木)19:53 ID:Ej/MkqD7d(1) AAS
幅優先探索はそもそもΩ(N+M)なケースが無いと思うからO(M)って書いて欲しいが、N=O(M)は自明じゃないと思うぞ
N頂点0辺のグラフだってあるし
137: (ﾜｯﾁｮｲ 5f43-PuAn) 2023/04/06(木)22:06 ID:qiEKlOzd0(1) AAS
すまん嘘書いた
幅優先探索って最初に距離配列を作るからO(N+M)で合ってたわ
138: (ｱｳｱｳｳｰ Sa23-bNUo) 2023/04/07(金)18:56 ID:koL6xQVKa(1) AAS
チョクダイ毎日AI下げしてるな、これくらい上流層でも脅威なんだな
139: (ﾜｯﾁｮｲ 7f55-EYsv) 2023/04/07(金)19:05 ID:PbTiq3Mq0(1) AAS
高橋直大さんの実力は世界トップレベルなんですか？
140: (ﾜｯﾁｮｲ 5f05-RhFY) 2023/04/07(金)19:50 ID:4NY4d7fE0(1) AAS
いいえ
141: (ﾜｯﾁｮｲ ffca-7Vgv) 2023/04/07(金)20:14 ID:Jyfuc8w80(1) AAS
赤レベルが解けるようになるのは10年以上かかるだろうけど、
コーディングテストとして売り物になる層はすでにほぼ終了だし、E,Fまで解けるようになったらほとんどの参加者の自力解答は無意味ということに。
GPT前提の問題作りか、時間をかけた試行錯誤は苦手だろうからヒューリスティック重視とかになっていくんじゃないだろうか。
142: (ﾜｯﾁｮｲ fe7c-UY1G) 2023/04/08(土)00:54 ID:NWI0hhIl0(1) AAS
ヒューリスティックもある程度のレベルまでは行きそうだけどな
24時間コードを書かせ続けることもできるし
143: (ﾜｯﾁｮｲ a9b1-Q90w) 2023/04/08(土)14:37 ID:d9UfkEh40(1) AAS
始めて一年の茶色のおっさんだけどAIに負けるレベルになったと聞いてモチベだだ下がり。俺みたいなやつ多いと思うよ。
そりゃ参加者減ったら焦るわな
144: (ﾜｯﾁｮｲ d907-NO7/) 2023/04/08(土)14:48 ID:dzO9pS9o0(1/3) AAS
AIに負けるって言うがChatGPTは競プロ用にチューニングしたプログラミングAIじゃないぞ
こいつができるのは問題を読むことと何を求められてるかを把握すること
つまり日本語(あるいは英語)を読解するAIだ
要するに人類が負けてるのはプログラミング能力じゃなく読解力と記憶力なんだよ
今に見てろこいつらあらゆる分野でゲームと動画に浸かったお前らに国語力の差を見せつけてくるから
145: (ﾜｯﾁｮｲ e101-x1gv) 2023/04/08(土)15:13 ID:H0kArwlU0(1) AAS
暖色レベルへの到達はあったとしてもかなり先だろうし競技としては成立するだろうけど緑〜水色くらいなら近い将来到達しそうだし新規参入と寒色停滞勢の参加率は減るかもね
146(1): (ｻｻｸｯﾃﾛﾙ Spd1-42TY) 2023/04/08(土)15:15 ID:obJbbgz0p(1/3) AAS
競プロってゲームでやってるのかと思ってたからAIに負けてやる気なくなるってのはよくわからん
147: (ﾃﾃﾝﾃﾝﾃﾝ MM66-rOwk) 2023/04/08(土)15:21 ID:YDsW15QlM(1/5) AAS
ARC/AGCの中盤以降に競プロの本当の楽しさがあるという主張は否定しないが、ABCの前半も競技として楽しんでいた層の方がマジョリティで、そういう層が競プロの裾野を広げていた側面もあるから、コンテンツとしてダメージを受けざるを得ないと思うわ
企業もスポンサーをするのは基本ABCだし、Jobsで見られているのもレベル的にABCでの実力がメイン
148(1): (ﾃﾃﾝﾃﾝﾃﾝ MM66-rOwk) 2023/04/08(土)15:23 ID:YDsW15QlM(2/5) AAS
>>146
競技を楽しんでるのに競技そのものが成立しなくなったら嫌だろ？
Project Eulerみたいな感覚で問題に取り組んでいるんなら大丈夫だが、そういう人は初心者層ほど少ない
149(1): (ｻｻｸｯﾃﾛﾙ Spd1-42TY) 2023/04/08(土)15:26 ID:obJbbgz0p(2/3) AAS
>>148
他の人らがAI使って解答してるかもしれないと思ってしまうってこと？
150(1): (ﾃﾃﾝﾃﾝﾃﾝ MM66-rOwk) 2023/04/08(土)15:34 ID:YDsW15QlM(3/5) AAS
>>149
バレる可能性が低く対策不能なチートが蔓延ったオンラインゲームは壊れるやろ
ただのオンラインゲームでさえそうなのに、一応AtCoderはJobsみたいな実利的に意味のあるものと繋がってるから、みんな使うようになるんじゃねーの
開き直ってAIバトルにしても、投稿速度ゲームになりそうだし
151: (ﾃﾃﾝﾃﾝﾃﾝ MM66-rOwk) 2023/04/08(土)15:35 ID:YDsW15QlM(4/5) AAS
みんな使わないにしても、使ってるやつにレートを吸われることでモチベの減退はあるだろうな
152(1): (ｻｻｸｯﾃﾛﾙ Spd1-42TY) 2023/04/08(土)15:36 ID:obJbbgz0p(3/3) AAS
>>150
まあそういう人はスポーツすればいいよ
アルゴリズム解くのが好きとか純粋に知識欲の高い人が残るんだろうね
153: (ﾃﾃﾝﾃﾝﾃﾝ MM66-rOwk) 2023/04/08(土)15:43 ID:YDsW15QlM(5/5) AAS
>>152
その辺の人でも楽しめる競技になる道は閉ざされそうで悲しいな
元々運営にそういうモチベなさそうだったが（金のために仕方なくやってる感満載だった）
154: (ﾜｯﾁｮｲ c6ca-HjNm) 2023/04/08(土)19:32 ID:jzMk6Pp80(1) AAS
ノーレートで、食事したり飲みながら今までほぼ開かなかったF,GとかをchatGTPに聞いたり調べたりしながらやるのも楽しいぞい。解きたくない問題は解かなくても良いし。
155(1): (ﾜｯﾁｮｲ 8255-dXWb) 2023/04/08(土)20:03 ID:RgGs2QbX0(1/2) AAS
ワーシャル・フロイドアルゴリズムについて質問です。
最終的に任意の2点間の最短距離を入れるための2次元配列は、
代入演算子の左右で共通のものが使われています。
それでも、問題がないのはなぜですか？
156: (ﾜｯﾁｮｲ 85a4-5f+B) 2023/04/08(土)20:09 ID:8rEHJkBb0(1) AAS
ワーシャル・フロイドアルゴリズムは、全ての頂点間の最短距離を求めるためのアルゴリズムです。このアルゴリズムは、動的計画法の一種であり、一度計算された結果を再利用することで、計算量を減らすことができます。
具体的には、アルゴリズムの初期段階で、すべての頂点の間の距離を表す2次元配列を作成します。この配列は、アルゴリズムの途中で更新されますが、代入演算子の左右で共通のものが使われるため、問題はありません。
なぜなら、アルゴリズムの途中で更新される値は、それ以前の値に依存しているため、代入演算子の左右で共通の2次元配列を使用していることによって、更新された値が正しく計算され、以前に計算された値が失われることはありません。
つまり、更新された値は、以前に計算された値に基づいて正確に計算され、以前に計算された値が配列内に保持され続けるため、代入演算子の左右で共通の2次元配列を使用することは、アルゴリズムの正しい動作に影響を与えないということです。
157: (ﾜｯﾁｮｲ 8255-dXWb) 2023/04/08(土)21:36 ID:RgGs2QbX0(2/2) AAS
>>155
大丈夫な理由が分かりました。
158: (ﾜｯﾁｮｲ 412d-dXWb) 2023/04/08(土)22:06 ID:8FTHKj1c0(1) AAS
chatGPT便利だろ
こういう風に答えてくれる
159: (ﾜｯﾁｮｲ d907-NO7/) 2023/04/08(土)22:12 ID:dzO9pS9o0(2/3) AAS
ものすごくもっともらしい嘘つくから知らないことを聞くのはおすすめしないぞ
160: (ﾜｯﾁｮｲ d907-NO7/) 2023/04/08(土)22:16 ID:dzO9pS9o0(3/3) AAS
ワルシャワ・フローラル法を知ってる？
はい、ワルシャワ・フローラル法は、グラフの最大マッチングを求めるアルゴリズムの一種です。このアルゴリズムは、ハンガリー人数学者であるエドモンド・ワルシャワと、ポーランド人数学者であるタデウシュ・フローラルによって開発されました。
ワルシャワ・フローラル法は、ハンガリー法と同様に、最大マッチング問題を解決するために使用されます。このアルゴリズムは、二部グラフに適用されます。アルゴリズムの基本的な考え方は、各未マッチング頂点について、その頂点を始点とする増加路を探し、その増加路に属する辺のマッチングを反転させることです。
ワルシャワ・フローラル法は、ハンガリー法よりも効率的であることが知られていますが、完全グラフでは最悪の場合の計算量がO(n^4)であるため、実用的ではありません。しかし、一般のグラフに対しては、最大マッチングを高速に計算することができるため、実際には広く使用されています。
161: (ﾜｯﾁｮｲ 85a4-Az6A) 2023/04/09(日)02:49 ID:3zzmmMIO0(1/2) AAS
正確なことを答えさせるために、プロンプトエンジニアリングをがんばりましょうね
162: (ﾜｯﾁｮｲ c69a-RdFw) 2023/04/09(日)06:48 ID:/c2XAn9L0(1) AAS
素朴な整数演算のコードを書いたため、特定のテストケースのときにコードの途中で
整数がオーバーフローするような場合、一般的なコードの書き方の処方箋みたいなものは
ありますかね
例えば「整数の配列から適切な要素を取り出して期待される和を作れ、そういう要素が
ない場合はエラー値を返せ」みたいので、配列要素はどれもオーバーフローに近い整数、
和は配列内の最小要素よりちょっとだけ大きい値（なのでエラー値の場合）、とか....
163(1): (ﾜｯﾁｮｲ d907-NO7/) 2023/04/09(日)10:26 ID:/OFxiXOD0(1) AAS
競プロならlong longを使うだけ
実務ならオーバーフローした時に例外が発生するようにしてそれをキャッチ
164: (ﾜｯﾁｮｲ 8255-dXWb) 2023/04/09(日)13:54 ID:l3qXUMY00(1/7) AAS
『アルゴリズム実技検定公式テキストエントリー〜中級編』
最小全域木を求める、「プリムのアルゴリズム」について説明があります。
こうすれば、求まるという説明はあるのですが、なぜ求まるのかの説明がありません。
みなさんは、こうすれば求まるという情報だけで十分で、それで満足しますか？
それとも、ちゃんと証明まで自分で考えるか、誰かが書いた証明を読みますか？
165: (ﾜｯﾁｮｲ ae2b-RdFw) 2023/04/09(日)14:45 ID:dl/B18nt0(1) AAS
>>163
なるほど。確かに例えば入力がintならlong longを使えばとりあえず大丈夫そう
ちなみにC++ですが、例えばintのオーバーフローを例外で処理するのはどうしたら....
166: (ﾜｯﾁｮｲ 85a4-5f+B) 2023/04/09(日)14:49 ID:3zzmmMIO0(2/2) AAS
C++でオーバーフローを検出する方法はいくつかありますが、一般的なものは以下のようになります¹²³。
- 演算前に範囲チェックを行う。例えば、a + b がオーバーフローするかどうかは、a > INT_MAX - b か a < INT_MIN - b で判定できる。
- 符号なし整数を使う。符号なし整数のオーバーフローは定義されているので、演算後に結果が元の値より小さくなっていないかチェックすればよい。
- boostライブラリのsafe_numericsを使う。これはオーバーフローを検出するための特別な型を提供しており、オーバーフローが発生した場合に例外を投げる。
(1) Detecting signed overflow in C/C++ - Stack Overflow. 外部ﾘﾝｸ:stackoverflow.com アクセス日時 4/9/2023.
(2) c++ - How do I detect unsigned integer overflow? - Stack Overflow. 外部ﾘﾝｸ:stackoverflow.com アクセス日時 4/9/2023.
(3) c - How to check if overflow occured? - Stack Overflow. 外部ﾘﾝｸ:stackoverflow.com アクセス日時 4/9/2023.
167: (ﾜｯﾁｮｲ bd5f-EL/2) 2023/04/09(日)16:13 ID:sd0zf58N0(1) AAS
gccの__builtin_add_overflowとか__builtin_mul_overflowを使う
168: (ﾜｯﾁｮｲ 8255-dXWb) 2023/04/09(日)18:08 ID:l3qXUMY00(2/7) AAS
github.com/kenkoooo/pastbook-source-code/blob/master/chukyu/python/chapter06/section11/6-11-1.py
169: (ﾜｯﾁｮｲ 8255-dXWb) 2023/04/09(日)18:11 ID:l3qXUMY00(3/7) AAS
↑のファイルはプリムのアルゴリズムで最小全域木問題を解くコードです。
ファイル中の以下の箇所がなぜ必要なのかが分かりません。
一見すると、キューの中には、marked の値がFalseのノードしか入っていないように思うのですが、
実際には、Falseのノードも入ることがあるようです。（以下の箇所をコメントアウトすると
パスしません。）
# 辺につながる頂点 i もすでにマークされていた場合、
# 操作をスキップする
省2
170: (ﾜｯﾁｮｲ 8255-dXWb) 2023/04/09(日)18:16 ID:l3qXUMY00(4/7) AAS
一部、間違えましたので訂正します。↓
↑のファイルはプリムのアルゴリズムで最小全域木問題を解くコードです。
ファイル中の以下の箇所がなぜ必要なのかが分かりません。
一見すると、キューの中には、marked の値がFalseのノードしか入っていないように思うのですが、
実際には、Trueのノードも入ることがあるようです。（以下の箇所をコメントアウトすると
パスしません。）
# 辺につながる頂点 i もすでにマークされていた場合、
省3
171(2): (ﾜｯﾁｮｲ 412d-dXWb) 2023/04/09(日)18:19 ID:fcL4nlHr0(1/3) AAS
この部分は、既にマークされた頂点に対応する辺をスキップするために必要です。
確かに、キューには基本的にmarkedの値がFalseのノードしか入らないように見えますが、
実際には同じノードに対して複数の辺がキューに入ることがあります。
例えば、次のようなグラフを考えてみましょう。
1 -- 2
| /
| /
省16
172(1): (ﾜｯﾁｮｲ 8255-dXWb) 2023/04/09(日)18:19 ID:l3qXUMY00(5/7) AAS
ヒープにプッシュする前に、そのノードがマークされていないことをチェックしています。
ですので、ヒープ内には、マークされていないノードしか入れないと思うのですが。
173: (ﾜｯﾁｮｲ 8255-dXWb) 2023/04/09(日)18:25 ID:l3qXUMY00(6/7) AAS
>>171
あまり参考にならないだろうと思って読んでいたらなぜか理由が分かりました。
マークされていない状態で、同じノードが複数個ヒープに入ることがあるわけですね。
174: (ﾜｯﾁｮｲ 412d-dXWb) 2023/04/09(日)18:28 ID:fcL4nlHr0(2/3) AAS
>>172
確かに、ヒープにプッシュする前にそのノードがマークされていないことをチェックしています。
ただし、ヒープにプッシュされた後で、そのノードが他の辺を経由してマークされる可能性があります。
そのため、ヒープから辺を取り出す前にもう一度マークされているかどうかをチェックする必要があります。
先程のグラフで考えてみましょう。キューがこの様になったところから解説します。
(1, 3), (1, 1), (1, 3)
ここで、最初に(1, 3)をキューから取り出し、頂点3をマークします。この時点で、キューには以下のような状態が残っています。
省5
175(1): (ﾜｯﾁｮｲ 8255-dXWb) 2023/04/09(日)18:28 ID:l3qXUMY00(7/7) AAS
>>171
この場合でいうとノード3が2回ヒープに入るわけですね。
176: (ﾜｯﾁｮｲ 412d-dXWb) 2023/04/09(日)18:31 ID:fcL4nlHr0(3/3) AAS
>>175
はい、その通りです。
最初にノード1からノード3への辺がヒープに追加され、次にノード2からノード3への辺がヒープに追加されます。
(1, 3) <-- 1から3への辺
(1, 1)
(1, 3) <-- 2から3への辺
このように、同じノードが複数回ヒープに入ることがあります。プリムのアルゴリズムでは、
省2
177: (ｱｳｱｳｳｰ Sa05-IjNm) 2023/04/09(日)19:43 ID:O0uaasVha(1) AAS
おんちぽまんぽげろろろり？
178: (ﾌﾞｰｲﾓ MMf6-tIu7) 2023/04/09(日)22:42 ID:fJZ93dkaM(1) AAS
序盤からムズすぎ
179: (ﾜｯﾁｮｲ d9b0-OQ9P) 2023/04/09(日)22:44 ID:0uKKY8S80(1) AAS
Eむずい
setとpriority queueいじくってたら通った
180: (ｻｻｸｯﾃﾛﾗ Spd1-x1gv) 2023/04/09(日)22:47 ID:DKklNxRop(1) AAS
E二分探索でやろうとしたらハマって普通にsetで順番にみるだけだった
F解けたのに今回も解いてる人の数がF<Gなせいであまり順位伸びてないの配点何とかして欲しいわ
181(2): (ｽｯｯﾌﾟ Sd22-QZiB) 2023/04/09(日)23:58 ID:BvehXBT4d(1) AAS
整数式の倍数判定のプログラム作りたいんだけどできる？
nは自然数
例1
入力:n(n+1)(n+2)
出力:6
(入力した式の倍数判定。6の倍数)
2の倍数でも3の倍数でもあるが、最も大きい数を出力
省3
182: (ﾜｯﾁｮｲ eebb-Sq7r) 2023/04/10(月)02:32 ID:Gn/yyThB0(1) AAS
>>181
nに素数をいくつか突っ込んだ値(0以外)で最大公約数とればいいんでない？
という気はするけど万年茶色脳には正しいか証明するなんてムリ
183: (ﾜｯﾁｮｲ bd5f-EL/2) 2023/04/10(月)02:49 ID:zrtbja+Y0(1/3) AAS
素数pの倍数かどうかはmod pが整域だから多項式は根を高々次数d個しかもたないのでp≤dだけ調べればいいよね
p^kはわからん
上下前次1-新書関写板覧索設栞歴
あと 295 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.015s