競技プログラミング総合スレ 66 (478ﾚｽ)
上下前次1-新
74: (ﾜｯﾁｮｲ 5f01-/O8Q) 2023/04/03(月)01:39 ID:IXS2Ww8n0(1) AAS
今日のこどふぉで「放物線と直接が共有点を持つかは判別式の正負で判定できる」っていう受験数学典型が出題されたけどこんなものも出るんだ 懐かしい
75: (ｱｳｱｳｳｰ Sa23-c96Y) 2023/04/03(月)19:32 ID:FgjSg9ZWa(1) AAS
めちゃくちゃ評判悪そう
76: (ﾜｯﾁｮｲ ffd7-7kGg) 2023/04/03(月)19:53 ID:q+x2Lby/0(1) AAS
下痢 ブリッ
77: (ﾜｯﾁｮｲ 5f05-RhFY) 2023/04/03(月)21:24 ID:SmeNn/jA0(1) AAS
むしろ競プロは受験数学の知識だけで解けるべきじゃない？
78: (ｻｻｸｯﾃﾛﾚ Sp33-A7Yb) 2023/04/04(火)00:10 ID:VOtqbY9Mp(1) AAS
ワーキングメモリが足りなくて再帰で複雑なことされると理解に時間かかるんだけど、皆さんなにか工夫してます？
79: (ｽｯﾌﾟ Sd1f-2YOk) 2023/04/04(火)00:30 ID:ynDnusCrd(1) AAS
あんなの慣れだろ
まぁ、細かい事言うと描く対象が木の時はこんな感じグラフの時はあんな感じみたいな
数列の漸化式みたいに一定の公式みたいのあるんだけどさ
80: (ﾜｯﾁｮｲ ffca-7Vgv) 2023/04/04(火)01:28 ID:W5rb6s9n0(1) AAS
atcoderでおかしいと思うのは、Dまでで再帰の出現頻度が異常に少ないこと。
最後に見たの半年以上前なような。
アホみたいに単純になりがちなのと、中高生が取り組みにくいのが要因か。
81: (ｱｳｱｳｳｰ Sa23-+nBq) 2023/04/04(火)02:14 ID:TYadsnnda(1/2) AAS
は？ 先週のeも再帰で解いたんだが
82: (ｱｳｱｳｳｰ Sa23-+nBq) 2023/04/04(火)02:16 ID:TYadsnnda(2/2) AAS
あ、ごめんDまででってことか
わけのわからん制限つけるね
83: (ﾜｯﾁｮｲ 5f07-VQD5) 2023/04/04(火)08:07 ID:DHwR1ezN0(1) AAS
再帰で解けるものは山程あるのに使ってないってだけだろ
84: (ｵｯﾍﾟｹ Sr33-eXH4) 2023/04/04(火)08:54 ID:qTPfKvwBr(1) AAS
ループは再帰じゃん
85: (ﾜｯﾁｮｲ 5f05-RhFY) 2023/04/04(火)09:46 ID:t/xEUfRa0(1/5) AAS
再帰じゃないよ反復だよ
86: (ｱｳｱｳｳｰ Sa23-VQD5) 2023/04/04(火)10:18 ID://1NkrQ5a(1) AAS
再帰呼び出しじゃないがi++は再帰的な式と言えるかな
87: (ﾃﾃﾝﾃﾝﾃﾝ MM4f-Qm86) 2023/04/04(火)10:51 ID:QoHW7HWiM(1) AAS
むしろ再帰は慣れるとワーキングメモリが少なくても書ける部類のコードになる
関数の引数に対する処理と、終了条件の二つに気をつければいいだけ
全体像を追うんじゃなくて、あくまでもその関数を一回実行したときの処理だけ考える
88: (ｻｻｸｯﾃﾛﾚ Sp33-A7Yb) 2023/04/04(火)12:54 ID:EY/4cjgwp(1) AAS
木がBSTか判定するコードなんですけど、こういうのって頭の中で全部イメージできます？
このロジックも自分で初見では組めなかったんですよね
def validateBST(root):
def isValid(root, minVal, maxVal):
if root is None:
return True
if not (minVal < root.data < maxVal):
省3
89(1): (ﾍﾞｰｲﾓ MM8f-RhFY) 2023/04/04(火)13:21 ID:7WTftjG/M(1) AAS
知的障害とかおありでしょうか？わかりますよ？
<=のほうがよくね、minとかmaxは余計だね、とか
90: (ｱｳｱｳｳｰ Sa23-VQD5) 2023/04/04(火)13:23 ID:PqQnB5Pua(1) AAS
寒色がイキってんなー
91: (ﾜｯﾁｮｲ 5f05-RhFY) 2023/04/04(火)14:09 ID:t/xEUfRa0(2/5) AAS
ガイジ同士仲良くしようね、ってことだよ
92: (ﾃﾃﾝﾃﾝﾃﾝ MM4f-Qm86) 2023/04/04(火)16:38 ID:Oj3uAFDaM(1) AAS
ある頂点に対して、2つの子それぞれを根とする部分木の情報が定まってれば、その頂点について簡単に判定できる
数学的帰納法の考え方というか、局所的には簡単な処理できるってことがわかるとそんなに大変じゃなくなる
93: (ｻｻｸｯﾃﾛﾚ Sp33-A7Yb) 2023/04/04(火)16:58 ID:lr/sr6Gfp(1) AAS
>>89
より良い書き方があるならコード見たいです
Pythonだと慣れてるので嬉しいです
94(1): (ﾜｯﾁｮｲ 5f05-RhFY) 2023/04/04(火)17:16 ID:t/xEUfRa0(3/5) AAS
89でコメントした通りだよ
95: (ｱｳｱｳｳｰ Sa23-VQD5) 2023/04/04(火)17:59 ID:/ayUyQoPa(1/6) AAS
ガイジ同士仲良くしろよw
仲良くしようと頑張ってそれなのかw
96: (ｻｻｸｯﾃﾛﾚ Sp33-A7Yb) 2023/04/04(火)18:10 ID:Uj7u2nTRp(1) AAS
>>94
minとかmaxって関数のことですよね？
これないと上位ノードより大きい値が左の下位ノードに存在することを許しちゃいませんか？
97: (ｱｳｱｳｳｰ Sa23-VQD5) 2023/04/04(火)18:16 ID:/ayUyQoPa(2/6) AAS
もしかして自演でやり取りしてるんじゃないかと思うくらいどっちも頭悪いな
98(1): (ﾜｯﾁｮｲ df5f-vkwt) 2023/04/04(火)19:37 ID:jf1j38ly0(1/2) AAS
if not (minVal < root.data < maxVal):
return False
がある時点で明らかにその下の行では
min(maxVal, root.data)) == root.data
じゃない？
99: (ﾜｯﾁｮｲ 5f05-RhFY) 2023/04/04(火)19:51 ID:t/xEUfRa0(4/5) AAS
そら明らかだよ
100: (ｻｻｸｯﾃﾛﾚ Sp33-A7Yb) 2023/04/04(火)20:15 ID:s5dZ5QHYp(1) AAS
>>98
leetcodeにもそういうコードありました
もう一回やり直してみます
ありがとうございました
101(1): (ｵｯﾍﾟｹ Sr33-eXH4) 2023/04/04(火)20:17 ID:L6sdRXYAr(1/2) AAS
BSTって何ンゴ？
102: (ｱｳｱｳｳｰ Sa23-VQD5) 2023/04/04(火)20:19 ID:/ayUyQoPa(3/6) AAS
余計なものの中に最後の一行についての言及がないということは二人()ともあのif文は要ると思ってるんだろうな
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に聞いたり調べたりしながらやるのも楽しいぞい。解きたくない問題は解かなくても良いし。
上下前次1-新書関写板覧索設栞歴
あと 324 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.017s