競技プログラミング総合スレ 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/03/29(水) 22:42:18.63

近頃のお店の支払いはif文が100個ぐらいありそう
支払い方法が何十通りもあるし
組み合わせて支払えることもあるし
ポイントの付き方とか複雑だし

2023/03/29(水) 23:59:01.26

業務プログラミングの方が大事ってことだね

2023/03/31(金) 14:39:01.38

ABC168C問題について質問
中心角を求めてから余弦定理を使うところまではわかったんだが、肝心な実装ができない
このコードの問題ってどの辺かな
テンプレは省略しています

#include<bits/stdc++.h>
using namespace std;

int main() {
ll A,B,H,M;
cin>>A>>B>>H>>M;
ll m=5*H;
ll l=min(abs(m-M),60-abs(m-M));
if(l==30){
cout<<A+B<<endl;;
return 0;
}
if(l==0){
cout<<abs(A-B)<<endl;
return 0;
}
dl pi=acos(-1);
dl ans=sqrt(A*A+B*B-2*A*B*cos((dl)l/30*pi));
printf("%.12lf\n",ans);
}

2023/03/31(金) 14:42:26.39

結構考えたんだがわからない

2023/03/31(金) 14:43:12.12

計算幾何難しいな

2023/03/31(金) 14:45:49.39

llはlong long
dlはdouble な

2023/03/31(金) 15:07:50.77

短針のズレを考慮できてない

2023/03/31(金) 15:45:13.68

ありがとうございます
短針のずれを考慮して実装し直します
iqが低すぎてそこまで頭が回りませんでした

2023/03/31(金) 15:54:30.84

無事実装できました
やっぱり競プロはIQゲーだと思います

2023/03/31(金) 15:56:10.29

あぁっIQ！(イク)

2023/03/31(金) 16:08:43.15

そうだよ、IQゲーだよ
というか算数のパズルだから、中受してるひとが有利
だから上位者は筑駒や灘だらけだろ

2023/04/01(土) 08:38:04.57

はーい、ガイジのみなさん、こちらに集合してください

2023/04/01(土) 12:15:44.71

ンガガーイ爺爺ジジジジジジwwwww

2023/04/01(土) 12:17:35.88

ガイジは仲間を呼んだ

2023/04/01(土) 13:42:49.55

あ、ガイ

2023/04/01(土) 13:58:41.08

ワクチンは毒ゴリ！

2023/04/01(土) 14:15:52.73

おれも競プロのおかげでイベルメクチンを使ってコロナを乗り越えることができたわ

2023/04/01(土) 23:21:18.83

G問題、凸包の上側と下側を抜き出すのにかなり時間がかかってしまったね
ライブラリ化してもいい気がする

2023/04/02(日) 16:43:56.19

ゴリってワクチン打ってない陰謀論者なのに、飲み会に呼ばれるしオンサイトにも出てるんだ。羨ましーーー！

2023/04/02(日) 19:58:27.80

GPTはそのうち画像や音声データも読み込めるようになるって既に発表されてるぞ

2023/04/03(月) 01:39:44.68

今日のこどふぉで「放物線と直接が共有点を持つかは判別式の正負で判定できる」っていう受験数学典型が出題されたけどこんなものも出るんだ　懐かしい

2023/04/03(月) 19:32:07.17

めちゃくちゃ評判悪そう

2023/04/03(月) 19:53:40.00

下痢　ブリッ

2023/04/03(月) 21:24:06.14

むしろ競プロは受験数学の知識だけで解けるべきじゃない？

2023/04/04(火) 00:10:14.93

ワーキングメモリが足りなくて再帰で複雑なことされると理解に時間かかるんだけど、皆さんなにか工夫してます？

2023/04/04(火) 00:30:09.56

あんなの慣れだろ
まぁ、細かい事言うと描く対象が木の時はこんな感じグラフの時はあんな感じみたいな
数列の漸化式みたいに一定の公式みたいのあるんだけどさ

2023/04/04(火) 01:28:50.00

atcoderでおかしいと思うのは、Dまでで再帰の出現頻度が異常に少ないこと。
最後に見たの半年以上前なような。
アホみたいに単純になりがちなのと、中高生が取り組みにくいのが要因か。

2023/04/04(火) 02:14:13.00

は？先週のeも再帰で解いたんだが

2023/04/04(火) 02:16:15.48

あ、ごめんDまででってことか
わけのわからん制限つけるね

2023/04/04(火) 08:07:40.50

再帰で解けるものは山程あるのに使ってないってだけだろ

2023/04/04(火) 08:54:33.58

ループは再帰じゃん

2023/04/04(火) 09:46:39.09

再帰じゃないよ反復だよ

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

再帰呼び出しじゃないがi++は再帰的な式と言えるかな

2023/04/04(火) 10:51:59.65

むしろ再帰は慣れるとワーキングメモリが少なくても書ける部類のコードになる
関数の引数に対する処理と、終了条件の二つに気をつければいいだけ
全体像を追うんじゃなくて、あくまでもその関数を一回実行したときの処理だけ考える

2023/04/04(火) 12:54:28.83

木がBSTか判定するコードなんですけど、こういうのって頭の中で全部イメージできます？
このロジックも自分で初見では組めなかったんですよね

def validateBST(root):

def isValid(root, minVal, maxVal):
if root is None:
return True
if not (minVal < root.data < maxVal):
return False
return isValid(root.left, minVal, min(maxVal, root.data)) and isValid(root.right, max(minVal, root.data), maxVal)

return True if root is None else isValid(root, -float("inf"), float("inf"))

2023/04/04(火) 13:21:56.47

知的障害とかおありでしょうか？わかりますよ？
<=のほうがよくね、minとかmaxは余計だね、とか

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に聞いたり調べたりしながらやるのも楽しいぞい。解きたくない問題は解かなくても良いし。