競技プログラミング総合スレ 66 (478ﾚｽ)
上下前次1-新
39: (ﾜｯﾁｮｲ c6d7-487i) 2023/03/27(月)23:25 ID:w6LHc8YX0(1) AAS
他は知らんがatcoderは計算量削減が全てのゲームじゃないの？
40: (ﾜｯﾁｮｲ 4910-wXJE) 2023/03/28(火)00:35 ID:cr4DmYo80(1) AAS
逆に難易度の重心がほぼ実装の問題とか無いんかな？
41: (ﾃﾃﾝﾃﾝﾃﾝ MM26-/edl) 2023/03/28(火)01:07 ID:rDLZ62yyM(1) AAS
実装ゲーもあるが、指数時間や階乗時間計算量許してしまうと大体根底から問題が破壊される気がするな
42: (ﾜｯﾁｮｲ 86ca-SHnl) 2023/03/28(火)01:13 ID:6GzNUAUt0(1) AAS
中高大学受験生様の息抜きとしてもアピールしたいから実装系問題が増えるのはNG
43: (ﾜｯﾁｮｲ 8101-JE21) 2023/03/28(火)01:32 ID:HytcUhih0(1) AAS
ほぼ愚直全探索で間に合うみたいな実装系メインの問題は基本茶色以下になるけど、再帰とかバックトラックDFSとかが絡んできて問題も面倒だと水色程度にまではなるかな
44: (ｵｯﾍﾟｹ Srf1-EJv0) 2023/03/28(火)11:04 ID:WvnTagyzr(1) AAS
なにいってだこいつ
45: (ｱｳｱｳｳｰ Saa5-OQny) 2023/03/28(火)13:34 ID:qUy4Ca8ja(1) AAS
無限が出てくる期待値 mod 系はどうしようもないことがありそう
それこそ e とか
46: (ﾜｯﾁｮｲ 3143-0wRU) 2023/03/28(火)14:53 ID:pBA8OQlO0(1/2) AAS
確率問題はそれこそモンテカルロで無限の精度を出せないか？
無限の時間がかかるけど、計算量無視していいから余裕だし
47: (ﾜｯﾁｮｲ 3143-0wRU) 2023/03/28(火)14:56 ID:pBA8OQlO0(2/2) AAS
よく考えたら無限回の確率 mod 998244353は無理だったわ
そういうのはdiff高いな
48: (ｱｳｱｳｳｰ Saa5-OQny) 2023/03/28(火)16:40 ID:vDjfaAcMa(1) AAS
まあ答えが単純な有理数で分母の大きささえ評価できればその理屈は成り立つな
e は p+q/e+r/ee とかいう形してるから一筋縄ではいかなさそう
連分数的な計算できたりするのかな
49: (ﾜｯﾁｮｲ aebb-Hkjr) 2023/03/29(水)17:50 ID:POPS3oJ/0(1) AAS
ゴリ～
50: (ﾜｯﾁｮｲ 4910-wXJE) 2023/03/29(水)18:56 ID:kBGRwrEZ0(1/2) AAS
ゴリ！？🦍
51: (ﾜｯﾁｮｲ c6d7-487i) 2023/03/29(水)19:08 ID:9uutc8gb0(1/2) AAS
げり！？💩
52: (ﾜｯﾁｮｲ 4910-wXJE) 2023/03/29(水)19:13 ID:kBGRwrEZ0(2/2) AAS
単純にif文が100個必要な問題出してくれ
53: (ﾜｯﾁｮｲ a5a4-SHnl) 2023/03/29(水)22:24 ID:EBmgoS++0(1) AAS
ガイジは集合せよ
54: (ﾜｯﾁｮｲ c202-uluY) 2023/03/29(水)22:42 ID:2dimOlTU0(1) AAS
近頃のお店の支払いはif文が100個ぐらいありそう
支払い方法が何十通りもあるし
組み合わせて支払えることもあるし
ポイントの付き方とか複雑だし
55: (ﾜｯﾁｮｲ c6d7-487i) 2023/03/29(水)23:59 ID:9uutc8gb0(2/2) AAS
業務プログラミングの方が大事ってことだね
56: (ﾜｯﾁｮｲ 450c-JnmT) 2023/03/31(金)14:39 ID:XH90LCx+0(1/6) AAS
ABC168C問題について質問
中心角を求めてから余弦定理を使うところまではわかったんだが、肝心な実装ができない
このコードの問題ってどの辺かな
テンプレは省略しています
#include<bits/stdc++.h>
using namespace std;
int main() {
省16
57: (ﾜｯﾁｮｲ 450c-JnmT) 2023/03/31(金)14:42 ID:XH90LCx+0(2/6) AAS
結構考えたんだがわからない
58: (ﾜｯﾁｮｲ 450c-JnmT) 2023/03/31(金)14:43 ID:XH90LCx+0(3/6) AAS
計算幾何難しいな
59: (ﾜｯﾁｮｲ 450c-JnmT) 2023/03/31(金)14:45 ID:XH90LCx+0(4/6) AAS
llはlong long
dlはdouble な
60: (ｵｯﾍﾟｹ Srf1-CXWr) 2023/03/31(金)15:07 ID:fTvY1Xf/r(1) AAS
短針のズレを考慮できてない
61: (ﾜｯﾁｮｲ 450c-JnmT) 2023/03/31(金)15:45 ID:XH90LCx+0(5/6) AAS
ありがとうございます
短針のずれを考慮して実装し直します
iqが低すぎてそこまで頭が回りませんでした
62: (ﾜｯﾁｮｲ 450c-JnmT) 2023/03/31(金)15:54 ID:XH90LCx+0(6/6) AAS
無事実装できました
やっぱり競プロはIQゲーだと思います
63: (ﾜｯﾁｮｲ 4910-wXJE) 2023/03/31(金)15:56 ID:kOumRh050(1) AAS
あぁっIQ！(イク)
64: (ﾜｯﾁｮｲ 8905-EZ7z) 2023/03/31(金)16:08 ID:t6yfY2Yj0(1) AAS
そうだよ、IQゲーだよ
というか算数のパズルだから、中受してるひとが有利
だから上位者は筑駒や灘だらけだろ
65: (ﾜｯﾁｮｲ dfa4-RhFY) 2023/04/01(土)08:38 ID:zwk1ALmN0(1/2) AAS
はーい、ガイジのみなさん、こちらに集合してください
66: (ﾜｯﾁｮｲ ffd7-7kGg) 2023/04/01(土)12:15 ID:dkRcJBBh0(1) AAS
ンガガーイ爺爺ジジジジジジwwwww
67: (ｱｳｱｳｳｰ Sa23-VQD5) 2023/04/01(土)12:17 ID:QjynJyA4a(1) AAS
ガイジは仲間を呼んだ
68: (ﾜｯﾁｮｲ 5f10-GKj5) 2023/04/01(土)13:42 ID:BSSJ7Y2r0(1) AAS
あ、ガイ
69: (ﾜｯﾁｮｲ ffbb-6Sa5) 2023/04/01(土)13:58 ID:wf8PbLnz0(1) AAS
ワクチンは毒ゴリ！
70: (ﾜｯﾁｮｲ dfa4-RhFY) 2023/04/01(土)14:15 ID:zwk1ALmN0(2/2) AAS
おれも競プロのおかげでイベルメクチンを使ってコロナを乗り越えることができたわ
71: (ﾜｯﾁｮｲ 5fbd-qTPE) 2023/04/01(土)23:21 ID:QCy7MZbH0(1) AAS
G問題、凸包の上側と下側を抜き出すのにかなり時間がかかってしまったね
ライブラリ化してもいい気がする
72: (ﾜｯﾁｮｲ ffbb-6Sa5) 2023/04/02(日)16:43 ID:lbh8aSxV0(1) AAS
ゴリってワクチン打ってない陰謀論者なのに、飲み会に呼ばれるしオンサイトにも出てるんだ。羨ましーーー！
73: (ﾜｯﾁｮｲ 5f01-4c3z) 2023/04/02(日)19:58 ID:a1RtyEhB0(1) AAS
GPTはそのうち画像や音声データも読み込めるようになるって既に発表されてるぞ
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
マジで寒いノリだな
上下前次1-新書関写板覧索設栞歴
あと 359 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.017s