競技プログラミング総合スレ 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/27(月) 23:07:12.93

>>36
全部愚直に全探索してもいいよってこと？

2023/03/27(月) 23:23:43.68

愚直全探索でいいならほとんどの問題は茶色ぐらいの実装ゲーになりそうだね

2023/03/27(月) 23:25:57.55

他は知らんがatcoderは計算量削減が全てのゲームじゃないの？

2023/03/28(火) 00:35:38.59

逆に難易度の重心がほぼ実装の問題とか無いんかな？

2023/03/28(火) 01:07:21.79

実装ゲーもあるが、指数時間や階乗時間計算量許してしまうと大体根底から問題が破壊される気がするな

2023/03/28(火) 01:13:44.71

中高大学受験生様の息抜きとしてもアピールしたいから実装系問題が増えるのはNG

2023/03/28(火) 01:32:23.58

ほぼ愚直全探索で間に合うみたいな実装系メインの問題は基本茶色以下になるけど、再帰とかバックトラックDFSとかが絡んできて問題も面倒だと水色程度にまではなるかな

2023/03/28(火) 11:04:20.30

なにいってだこいつ

2023/03/28(火) 13:34:28.55

無限が出てくる期待値 mod 系はどうしようもないことがありそう
それこそ e とか

2023/03/28(火) 14:53:29.59

確率問題はそれこそモンテカルロで無限の精度を出せないか？
無限の時間がかかるけど、計算量無視していいから余裕だし

2023/03/28(火) 14:56:54.16

よく考えたら無限回の確率 mod 998244353は無理だったわ
そういうのはdiff高いな

2023/03/28(火) 16:40:28.07

まあ答えが単純な有理数で分母の大きささえ評価できればその理屈は成り立つな
e は p+q/e+r/ee とかいう形してるから一筋縄ではいかなさそう
連分数的な計算できたりするのかな

2023/03/29(水) 17:50:24.64

ゴリ～

2023/03/29(水) 18:56:44.24

ゴリ！？🦍

2023/03/29(水) 19:08:50.79

げり！？💩

2023/03/29(水) 19:13:50.87

単純にif文が100個必要な問題出してくれ

2023/03/29(水) 22:24:59.43

ガイジは集合せよ

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辺のグラフだってあるし