競技プログラミング総合スレ 66

1デフォルトの名無しさん (ｱｳｱｳｳｰ Sa77-waiq)
垢版 |
2023/03/22(水) 15:19:42.08ID:9X0hpeOca
!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/22(水) 15:54:09.75ID:AM4tOKKV0
ガイジもこっちこいよおら
2023/03/22(水) 16:12:05.97ID:psQ7vQwG0
スレ立てさんくす
2023/03/23(木) 00:07:52.94ID:Km+XItsNr
IP付けろ
2023/03/23(木) 10:58:36.81ID:o8mgVYSz0
IP出しつつガイジ大集合せよ
2023/03/25(土) 20:15:57.52ID:9huyjCKAa
優勝ですと言いながらSNSに食べ物の写真を上げるのは面白いと思ってやっているのですか
2023/03/25(土) 21:13:54.70ID:a1Ky2GdpM
Twitterってそういうサービスだよ
2023/03/25(土) 23:14:21.96ID:OoIXtbKAa
d問題パリティと言われてみればなるほどだけど
2500人も解けてるの凄いなぁ…
9デフォルトの名無しさん (ﾜｯﾁｮｲ 86ca-SHnl)
垢版 |
2023/03/25(土) 23:37:39.74ID:90xyxOUe0
凄いというより、みんなatcoder特有のノリに慣れてきただけとしか思えない
2023/03/26(日) 00:45:55.97ID:FMK1ABJ40
トップ層で今回作問に携わってないのに「崖ができるのは解けないユーザーが悪い」とか言ってマウント取るのなんなんだろ
ABCでE~F黄diffなら不満出るのは必然だし正当では
2023/03/26(日) 01:02:25.81ID:CrQkGWR30
本当にトップ層かどうかは置いといてTwitterの競プロ界隈()なんてそんなもんだから気にしなくて良いでしょ
2023/03/26(日) 01:04:12.47ID:/aeTeUkmM
崖があるとパフォーマンスの計測が微妙になるから好ましくないことではある
2023/03/26(日) 01:05:06.17ID:TAAza50Z0
こどふぉの米欄でも見る光景だな
2023/03/26(日) 01:11:19.78ID:CrQkGWR30
今回のAのFA gpt使ったコードなんだね
その人1分以内でAとCACしてるしCまでで問題文が簡潔だったら任せても良さそうな感じか
15デフォルトの名無しさん (ﾜｯﾁｮｲ 86ca-SHnl)
垢版 |
2023/03/26(日) 01:29:10.46ID:3yvXzIAi0
Cまではもう諦めるとして、D-FでGPTでACを避ける作問をするとより難しくなるんじゃないだろうか
2023/03/26(日) 08:49:57.32ID:gXBGJV5A0
どうせチョクダイここ見てるんだろ
問題文を画像で提供すればキーボードを叩く時間がかかるからAIの爆速解答は防げる
視力障害の人も防いでしまうから読み上げ音声も同時提供だな
動画ならなお良し
アプリ作成にはアルゴリズムだけじゃなくこういうソリューションも必要だぞ
2023/03/26(日) 09:30:27.35ID:gXBGJV5A0
あと読み上げはすぬけ君がボソボソ言うんじゃなくその辺の安い声優やVtuberに頼むか音声合成な
2023/03/26(日) 13:29:18.49ID:hUryak+J0
無能コンサルってこういう感じなのか
2023/03/26(日) 13:35:03.84ID:CrQkGWR30
自分が有能だと勘違いしてるタイプが一番厄介だわな
2023/03/26(日) 13:46:41.77ID:W7ob2/CIa
何も反論できなくていつもの瀕死の人格攻撃
悔しそうで草
2023/03/26(日) 14:00:40.94ID:pG4dfw0OM
効いてて草
2023/03/26(日) 14:04:01.42ID:W7ob2/CIa
マジで効いてて草
2023/03/26(日) 14:17:25.34ID:W750hvH/a
ちんまんちんまんおちんこ〜♪
2023/03/26(日) 14:23:59.64ID:Cs+yZmPmr
でもすぬけ君のASMRならちょっと見たいかも
2023/03/26(日) 14:55:57.68ID:eSG946WYM
やっぱ自分でも無理筋だと分かっているしょうもない暴言でレスバがしたいだけのやつだったか
2023/03/26(日) 16:01:41.16ID:TsfO1inF0
無理筋じゃなくて裏筋刺激してよ、(*´Д`)ﾊｧﾊｧ
2023/03/26(日) 16:01:46.09ID:/R0vP+6ca
効いてて草
論破されて悔しいのにまったく反論できないってどんな気持ち？w
2023/03/27(月) 14:50:44.04ID:m9bz299oa
AIやばすぎて今のトップレベルはともかく始めたやつとか茶緑あたりはやる気なくなるんじゃないかこれ
29デフォルトの名無しさん (ﾜｯﾁｮｲ 86ca-SHnl)
垢版 |
2023/03/27(月) 15:14:55.29ID:4oR9WOvV0
これからのプログラミングはペアプロになるだろうからatcも許容すると思ったけど、コーディングテストで価値があるのがCくらいまでなのと、そこまでは絶対手動でかけるべきだから、画像とかにするんですかね。
最近、スクショどころかカメラで撮影しても全く映らない動画とかあるし。
2023/03/27(月) 16:04:13.89ID:sDeQZhuqa
その理論だと将棋とか誰もやりたがらない気がするけどそういうのあったんすかねやっぱ
2023/03/27(月) 16:37:29.45ID:jIqJMMmT0
画像になったらここでそれを否定した無能がどう発狂するか楽しみ
2023/03/27(月) 20:37:25.90ID:/QFPO4Z2M
今回のDで緑パフォしかないのレベル高すぎ…
2023/03/27(月) 20:39:13.26ID:shPa1cz80
数え上げ方はかなり典型的だけど一昔前なら水色下位くらいはあった気はする
2023/03/27(月) 22:35:39.05ID:9qPYTfj30
競技プログラミング（主にatcoder）で計算量を問われず無視できるならその問題のレベルどれくらい落ちる？
色一つ下になるくらい？
2023/03/27(月) 22:47:11.54ID:Uu1NkcKK0
計算量無視して良いなら全問題が茶色以下だと思うが、そういう話ではなく？
2023/03/27(月) 22:55:27.75ID:9qPYTfj30
>>35
つまり計算量無視ならatcoderの問題はどれも実装は簡単てこと？
計算量で難しくしてるようなもんてことになんの
2023/03/27(月) 23:07:12.93ID:+lYxKTMv0
>>36
全部愚直に全探索してもいいよってこと？
2023/03/27(月) 23:23:43.68ID:XdQv86Zh0
愚直全探索でいいならほとんどの問題は茶色ぐらいの実装ゲーになりそうだね
2023/03/27(月) 23:25:57.55ID:w6LHc8YX0
他は知らんがatcoderは計算量削減が全てのゲームじゃないの？
2023/03/28(火) 00:35:38.59ID:cr4DmYo80
逆に難易度の重心がほぼ実装の問題とか無いんかな？
2023/03/28(火) 01:07:21.79ID:rDLZ62yyM
実装ゲーもあるが、指数時間や階乗時間計算量許してしまうと大体根底から問題が破壊される気がするな
42デフォルトの名無しさん (ﾜｯﾁｮｲ 86ca-SHnl)
垢版 |
2023/03/28(火) 01:13:44.71ID:6GzNUAUt0
中高大学受験生様の息抜きとしてもアピールしたいから実装系問題が増えるのはNG
2023/03/28(火) 01:32:23.58ID:HytcUhih0
ほぼ愚直全探索で間に合うみたいな実装系メインの問題は基本茶色以下になるけど、再帰とかバックトラックDFSとかが絡んできて問題も面倒だと水色程度にまではなるかな
2023/03/28(火) 11:04:20.30ID:WvnTagyzr
なにいってだこいつ
2023/03/28(火) 13:34:28.55ID:qUy4Ca8ja
無限が出てくる期待値 mod 系はどうしようもないことがありそう
それこそ e とか
2023/03/28(火) 14:53:29.59ID:pBA8OQlO0
確率問題はそれこそモンテカルロで無限の精度を出せないか？
無限の時間がかかるけど、計算量無視していいから余裕だし
2023/03/28(火) 14:56:54.16ID:pBA8OQlO0
よく考えたら無限回の確率 mod 998244353は無理だったわ
そういうのはdiff高いな
2023/03/28(火) 16:40:28.07ID:vDjfaAcMa
まあ答えが単純な有理数で分母の大きささえ評価できればその理屈は成り立つな
e は p+q/e+r/ee とかいう形してるから一筋縄ではいかなさそう
連分数的な計算できたりするのかな
2023/03/29(水) 17:50:24.64ID:POPS3oJ/0
ゴリ～
2023/03/29(水) 18:56:44.24ID:kBGRwrEZ0
ゴリ！？🦍
2023/03/29(水) 19:08:50.79ID:9uutc8gb0
げり！？💩
2023/03/29(水) 19:13:50.87ID:kBGRwrEZ0
単純にif文が100個必要な問題出してくれ
2023/03/29(水) 22:24:59.43ID:EBmgoS++0
ガイジは集合せよ
2023/03/29(水) 22:42:18.63ID:2dimOlTU0
近頃のお店の支払いはif文が100個ぐらいありそう
支払い方法が何十通りもあるし
組み合わせて支払えることもあるし
ポイントの付き方とか複雑だし
2023/03/29(水) 23:59:01.26ID:9uutc8gb0
業務プログラミングの方が大事ってことだね
56デフォルトの名無しさん (ﾜｯﾁｮｲ 450c-JnmT)
垢版 |
2023/03/31(金) 14:39:01.38ID:XH90LCx+0
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);
}
57デフォルトの名無しさん (ﾜｯﾁｮｲ 450c-JnmT)
垢版 |
2023/03/31(金) 14:42:26.39ID:XH90LCx+0
結構考えたんだがわからない
58デフォルトの名無しさん (ﾜｯﾁｮｲ 450c-JnmT)
垢版 |
2023/03/31(金) 14:43:12.12ID:XH90LCx+0
計算幾何難しいな
59デフォルトの名無しさん (ﾜｯﾁｮｲ 450c-JnmT)
垢版 |
2023/03/31(金) 14:45:49.39ID:XH90LCx+0
llはlong long
dlはdouble な
2023/03/31(金) 15:07:50.77ID:fTvY1Xf/r
短針のズレを考慮できてない
61デフォルトの名無しさん (ﾜｯﾁｮｲ 450c-JnmT)
垢版 |
2023/03/31(金) 15:45:13.68ID:XH90LCx+0
ありがとうございます
短針のずれを考慮して実装し直します
iqが低すぎてそこまで頭が回りませんでした
62デフォルトの名無しさん (ﾜｯﾁｮｲ 450c-JnmT)
垢版 |
2023/03/31(金) 15:54:30.84ID:XH90LCx+0
無事実装できました
やっぱり競プロはIQゲーだと思います
2023/03/31(金) 15:56:10.29ID:kOumRh050
あぁっIQ！(イク)
2023/03/31(金) 16:08:43.15ID:t6yfY2Yj0
そうだよ、IQゲーだよ
というか算数のパズルだから、中受してるひとが有利
だから上位者は筑駒や灘だらけだろ
2023/04/01(土) 08:38:04.57ID:zwk1ALmN0
はーい、ガイジのみなさん、こちらに集合してください
2023/04/01(土) 12:15:44.71ID:dkRcJBBh0
ンガガーイ爺爺ジジジジジジwwwww
2023/04/01(土) 12:17:35.88ID:QjynJyA4a
ガイジは仲間を呼んだ
2023/04/01(土) 13:42:49.55ID:BSSJ7Y2r0
あ、ガイ
2023/04/01(土) 13:58:41.08ID:wf8PbLnz0
ワクチンは毒ゴリ！
2023/04/01(土) 14:15:52.73ID:zwk1ALmN0
おれも競プロのおかげでイベルメクチンを使ってコロナを乗り越えることができたわ
2023/04/01(土) 23:21:18.83ID:QCy7MZbH0
G問題、凸包の上側と下側を抜き出すのにかなり時間がかかってしまったね
ライブラリ化してもいい気がする
2023/04/02(日) 16:43:56.19ID:lbh8aSxV0
ゴリってワクチン打ってない陰謀論者なのに、飲み会に呼ばれるしオンサイトにも出てるんだ。羨ましーーー！
2023/04/02(日) 19:58:27.80ID:a1RtyEhB0
GPTはそのうち画像や音声データも読み込めるようになるって既に発表されてるぞ
2023/04/03(月) 01:39:44.68ID:IXS2Ww8n0
今日のこどふぉで「放物線と直接が共有点を持つかは判別式の正負で判定できる」っていう受験数学典型が出題されたけどこんなものも出るんだ　懐かしい
2023/04/03(月) 19:32:07.17ID:FgjSg9ZWa
めちゃくちゃ評判悪そう
2023/04/03(月) 19:53:40.00ID:q+x2Lby/0
下痢　ブリッ
2023/04/03(月) 21:24:06.14ID:SmeNn/jA0
むしろ競プロは受験数学の知識だけで解けるべきじゃない？
2023/04/04(火) 00:10:14.93ID:VOtqbY9Mp
ワーキングメモリが足りなくて再帰で複雑なことされると理解に時間かかるんだけど、皆さんなにか工夫してます？
79デフォルトの名無しさん (ｽｯﾌﾟ Sd1f-2YOk)
垢版 |
2023/04/04(火) 00:30:09.56ID:ynDnusCrd
あんなの慣れだろ
まぁ、細かい事言うと描く対象が木の時はこんな感じグラフの時はあんな感じみたいな
数列の漸化式みたいに一定の公式みたいのあるんだけどさ
80デフォルトの名無しさん (ﾜｯﾁｮｲ ffca-7Vgv)
垢版 |
2023/04/04(火) 01:28:50.00ID:W5rb6s9n0
atcoderでおかしいと思うのは、Dまでで再帰の出現頻度が異常に少ないこと。
最後に見たの半年以上前なような。
アホみたいに単純になりがちなのと、中高生が取り組みにくいのが要因か。
2023/04/04(火) 02:14:13.00ID:TYadsnnda
は？ 先週のeも再帰で解いたんだが
2023/04/04(火) 02:16:15.48ID:TYadsnnda
あ、ごめんDまででってことか
わけのわからん制限つけるね
2023/04/04(火) 08:07:40.50ID:DHwR1ezN0
再帰で解けるものは山程あるのに使ってないってだけだろ
2023/04/04(火) 08:54:33.58ID:qTPfKvwBr
ループは再帰じゃん
2023/04/04(火) 09:46:39.09ID:t/xEUfRa0
再帰じゃないよ反復だよ
2023/04/04(火) 10:18:05.72ID://1NkrQ5a
再帰呼び出しじゃないがi++は再帰的な式と言えるかな
2023/04/04(火) 10:51:59.65ID:QoHW7HWiM
むしろ再帰は慣れるとワーキングメモリが少なくても書ける部類のコードになる
関数の引数に対する処理と、終了条件の二つに気をつければいいだけ
全体像を追うんじゃなくて、あくまでもその関数を一回実行したときの処理だけ考える
2023/04/04(火) 12:54:28.83ID:EY/4cjgwp
木が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.47ID:7WTftjG/M
知的障害とかおありでしょうか？わかりますよ？
<=のほうがよくね、minとかmaxは余計だね、とか
2023/04/04(火) 13:23:54.73ID:PqQnB5Pua
寒色がイキってんなー
2023/04/04(火) 14:09:52.51ID:t/xEUfRa0
ガイジ同士仲良くしようね、ってことだよ
2023/04/04(火) 16:38:00.80ID:Oj3uAFDaM
ある頂点に対して、2つの子それぞれを根とする部分木の情報が定まってれば、その頂点について簡単に判定できる
数学的帰納法の考え方というか、局所的には簡単な処理できるってことがわかるとそんなに大変じゃなくなる
2023/04/04(火) 16:58:58.57ID:lr/sr6Gfp
>>89
より良い書き方があるならコード見たいです
Pythonだと慣れてるので嬉しいです
2023/04/04(火) 17:16:22.71ID:t/xEUfRa0
89でコメントした通りだよ
2023/04/04(火) 17:59:57.64ID:/ayUyQoPa
ガイジ同士仲良くしろよw
仲良くしようと頑張ってそれなのかw
2023/04/04(火) 18:10:30.05ID:Uj7u2nTRp
>>94
minとかmaxって関数のことですよね？
これないと上位ノードより大きい値が左の下位ノードに存在することを許しちゃいませんか？
2023/04/04(火) 18:16:52.31ID:/ayUyQoPa
もしかして自演でやり取りしてるんじゃないかと思うくらいどっちも頭悪いな
2023/04/04(火) 19:37:36.74ID:jf1j38ly0
if not (minVal < root.data < maxVal):
return False
がある時点で明らかにその下の行では
min(maxVal, root.data)) == root.data
じゃない？
2023/04/04(火) 19:51:05.61ID:t/xEUfRa0
そら明らかだよ
2023/04/04(火) 20:15:59.15ID:s5dZ5QHYp
>>98
leetcodeにもそういうコードありました
もう一回やり直してみます
ありがとうございました
2023/04/04(火) 20:17:37.51ID:L6sdRXYAr
BSTって何ンゴ？
新着レスの表示
レスを投稿する

5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況