23/03/22 15:54:09.75 AM4tOKKV0.net
ガイジもこっちこいよおら
3:デフォルトの名無しさん
23/03/22 16:12:05.97 psQ7vQwG0.net
スレ立てさんくす
4:デフォルトの名無しさん
23/03/23 00:07:52.94 Km+XItsNr.net
IP付けろ
5:デフォルトの名無しさん
23/03/23 10:58:36.81 o8mgVYSz0.net
IP出しつつガイジ大集合せよ
6:デフォルトの名無しさん
23/03/25 20:15:57.52 9huyjCKAa.net
優勝ですと言いながらSNSに食べ物の写真を上げるのは面白いと思ってやっているのですか
7:デフォルトの名無しさん
23/03/25 21:13:54.70 a1Ky2GdpM.net
Twitterってそういうサービスだよ
8:デフォルトの名無しさん
23/03/25 23:14:21.96 OoIXtbKAa.net
d問題パリティと言われてみればなるほどだけど
2500人も解けてるの凄いなぁ…
9:デフォルトの名無しさん
23/03/25 23:37:39.74 90xyxOUe0.net
凄いというより、みんなatcoder特有のノリに慣れてきただけとしか思えない
10:デフォルトの名無しさん
23/03/26 00:45:55.97 FMK1ABJ40.net
トップ層で今回作問に携わってないのに「崖ができるのは解けないユーザーが悪い」とか言ってマウント取るのなんなんだろ
ABCでE~F黄diffなら不満出るのは必然だし正当では
11:デフォルトの名無しさん
23/03/26 01:02:25.81 CrQkGWR30.net
本当にトップ層かどうかは置いといてTwitterの競プロ界隈()なんてそんなもんだから気にしなくて良いでしょ
12:デフォルトの名無しさん
23/03/26 01:04:12.47 /aeTeUkmM.net
崖があるとパフォーマンスの計測が微妙になるから好ましくないことではある
13:デフォルトの名無しさん
23/03/26 01:05:06.17 TAAza50Z0.net
こどふぉの米欄でも見る光景だな
14:デフォルトの名無しさん
23/03/26 01:11:19.78 CrQkGWR30.net
今回のAのFA gpt使ったコードなんだね
その人1分以内でAとCACしてるしCまでで問題文が簡潔だったら任せても良さそうな感じか
15:デフォルトの名無しさん
23/03/26 01:29:10.46 3yvXzIAi0.net
Cまではもう諦めるとして、D-FでGPTでACを避ける作問をするとより難しくなるんじゃないだろうか
16:デフォルトの名無しさん
23/03/26 08:49:57.32 gXBGJV5A0.net
どうせチョクダイここ見てるんだろ
問題文を画像で提供すればキーボードを叩く時間がかかるからAIの爆速解答は防げる
視力障害の人も防いでしまうから読み上げ音声も同時提供だな
動画ならなお良し
アプリ作成にはアルゴリズムだけじゃなくこういうソリューションも必要だぞ
17:デフォルトの名無しさん
23/03/26 09:30:27.35 gXBGJV5A0.net
あと読み上げはすぬけ君がボソボソ言うんじゃなくその辺の安い声優やVtuberに頼むか音声合成な
18:デフォルトの名無しさん
23/03/26 13:29:18.49 hUryak+J0.net
無能コンサルってこういう感じなのか
19:デフォルトの名無しさん
23/03/26 13:35:03.84 CrQkGWR30.net
自分が有能だと勘違いしてるタイプが一番厄介だわな
20:デフォルトの名無しさん
23/03/26 13:46:41.77 W7ob2/CIa.net
何も反論できなくていつもの瀕死の人格攻撃
悔しそうで草
21:デフォルトの名無しさん
23/03/26 14:00:40.94 pG4dfw0OM.net
効いてて草
22:デフォルトの名無しさん
23/03/26 14:04:01.42 W7ob2/CIa.net
マジで効いてて草
23:デフォルトの名無しさん
23/03/26 14:17:25.34 W750hvH/a.net
ちんまんちんまんおちんこ～♪
24:デフォルトの名無しさん
23/03/26 14:23:59.64 Cs+yZmPmr.net
でもすぬけ君のASMRならちょっと見たいかも
25:デフォルトの名無しさん
23/03/26 14:55:57.68 eSG946WYM.net
やっぱ自分でも無理筋だと分かっているしょうもない暴言でレスバがしたいだけのやつだったか
26:デフォルトの名無しさん
23/03/26 16:01:41.16 TsfO1inF0.net
無理筋じゃなくて裏筋刺激してよ、(*´Д`)ﾊｧﾊｧ
27:デフォルトの名無しさん
23/03/26 16:01:46.09 /R0vP+6ca.net
効いてて草
論破されて悔しいのにまったく反論できないってどんな気持ち？w
28:デフォルトの名無しさん
23/03/27 14:50:44.04 m9bz299oa.net
AIやばすぎて今のトップレベルはともかく始めたやつとか茶緑あたりはやる気なくなるんじゃないかこれ
29:デフォルトの名無しさん
23/03/27 15:14:55.29 4oR9WOvV0.net
これからのプログラミングはペアプロになるだろうからatcも許容すると思ったけど、コーディングテストで価値があるのがCくらいまでなのと、そこまでは絶対手動でかけるべきだから、画像とかにするんですかね。
最近、スクショどころかカメラで撮影しても全く映らない動画とかあるし。
30:デフォルトの名無しさん
23/03/27 16:04:13.89 sDeQZhuqa.net
その理論だと将棋とか誰もやりたがらない気がするけどそういうのあったんすかねやっぱ
31:デフォルトの名無しさん
23/03/27 16:37:29.45 jIqJMMmT0.net
画像になったらここでそれを否定した無能がどう発狂するか楽しみ
32:デフォルトの名無しさん
23/03/27 20:37:25.90 /QFPO4Z2M.net
今回のDで緑パフォしかないのレベル高すぎ…
33:デフォルトの名無しさん
23/03/27 20:39:13.26 shPa1cz80.net
数え上げ方はかなり典型的だけど一昔前なら水色下位くらいはあった気はする
34:デフォルトの名無しさん
23/03/27 22:35:39.05 9qPYTfj30.net
競技プログラミング（主にatcoder）で計算量を問われず無視できるならその問題のレベルどれくらい落ちる？
色一つ下になるくらい？
35:デフォルトの名無しさん
23/03/27 22:47:11.54 Uu1NkcKK0.net
計算量無視して良いなら全問題が茶色以下だと思うが、そういう話ではなく？
36:デフォルトの名無しさん
23/03/27 22:55:27.75 9qPYTfj30.net
>>35
つまり計算量無視ならatcoderの問題はどれも実装は簡単てこと？
計算量で難しくしてるようなもんてことになんの
37:デフォルトの名無しさん
23/03/27 23:07:12.93 +lYxKTMv0.net
>>36
全部愚直に全探索してもいいよってこと？
38:デフォルトの名無しさん
23/03/27 23:23:43.68 XdQv86Zh0.net
愚直全探索でいいならほとんどの問題は茶色ぐらいの実装ゲーになりそうだね
39:デフォルトの名無しさん
23/03/27 23:25:57.55 w6LHc8YX0.net
他は知らんがatcoderは計算量削減が全てのゲームじゃないの？
40:デフォルトの名無しさん
23/03/28 00:35:38.59 cr4DmYo80.net
逆に難易度の重心がほぼ実装の問題とか無いんかな？
41:デフォルトの名無しさん
23/03/28 01:07:21.79 rDLZ62yyM.net
実装ゲーもあるが、指数時間や階乗時間計算量許してしまうと大体根底から問題が破壊される気がするな
42:デフォルトの名無しさん
23/03/28 01:13:44.71 6GzNUAUt0.net
中高大学受験生様の息抜きとしてもアピールしたいから実装系問題が増えるのはNG
43:デフォルトの名無しさん
23/03/28 01:32:23.58 HytcUhih0.net
ほぼ愚直全探索で間に合うみたいな実装系メインの問題は基本茶色以下になるけど、再帰とかバックトラックDFSとかが絡んできて問題も面倒だと水色程度にまではなるかな
44:デフォルトの名無しさん
23/03/28 11:04:20.30 WvnTagyzr.net
なにいってだこいつ
45:デフォルトの名無しさん (ｱｳｱｳｳｰ Saa5-OQny)
23/03/28 13:34:28.55 qUy4Ca8ja.net
無限が出てくる期待値 mod 系はどうしようもないことがありそう
それこそ e とか
46:デフォルトの名無しさん (ﾜｯﾁｮｲ 3143-0wRU)
23/03/28 14:53:29.59 pBA8OQlO0.net
確率問題はそれこそモンテカルロで無限の精度を出せないか？
無限の時間がかかるけど、計算量無視していいから余裕だし
47:デフォルトの名無しさん (ﾜｯﾁｮｲ 3143-0wRU)
23/03/28 14:56:54.16 pBA8OQlO0.net
よく考えたら無限回の確率 mod 998244353は無理だったわ
そういうのはdiff高いな
48:デフォルトの名無しさん (ｱｳｱｳｳｰ Saa5-OQny)
23/03/28 16:40:28.07 vDjfaAcMa.net
まあ答えが単純な有理数で分母の大きささえ評価できればその理屈は成り立つな
e は p+q/e+r/ee とかいう形してるから一筋縄ではいかなさそう
連分数的な計算できたりするのかな
49:デフォルトの名無しさん
23/03/29 17:50:24.64 POPS3oJ/0.net
ゴリ～
50:デフォルトの名無しさん
23/03/29 18:56:44.24 kBGRwrEZ0.net
ゴリ！？🦍
51:デフォルトの名無しさん
23/03/29 19:08:50.79 9uutc8gb0.net
げり！？💩
52:デフォルトの名無しさん
23/03/29 19:13:50.87 kBGRwrEZ0.net
単純にif文が100個必要な問題出してくれ
53:デフォルトの名無しさん
23/03/29 22:24:59.43 EBmgoS++0.net
ガイジは集合せよ
54:デフォルトの名無しさん
23/03/29 22:42:18.63 2dimOlTU0.net
近頃のお店の支払いはif文が100個ぐらいありそう
支払い方法が何十通りもあるし
組み合わせて支払えることもあるし
ポイントの付き方とか複雑だし
55:デフォルトの名無しさん
23/03/29 23:59:01.26 9uutc8gb0.net
業務プログラミングの方が大事ってことだね
56:デフォルトの名無しさん (ﾜｯﾁｮｲ 450c-JnmT)
23/03/31 14:39:01.38 XH90LCx+0.net
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)
23/03/31 14:42:26.39 XH90LCx+0.net
結構考えたんだがわからない
58:デフォルトの名無しさん (ﾜｯﾁｮｲ 450c-JnmT)
23/03/31 14:43:12.12 XH90LCx+0.net
計算幾何難しいな
59:デフォルトの名無しさん (ﾜｯﾁｮｲ 450c-JnmT)
23/03/31 14:45:49.39 XH90LCx+0.net
llはlong long
dlはdouble な
60:デフォルトの名無しさん (ｵｯﾍﾟｹ Srf1-CXWr)
23/03/31 15:07:50.77 fTvY1Xf/r.net
短針のズレを考慮できてない
61:デフォルトの名無しさん (ﾜｯﾁｮｲ 450c-JnmT)
23/03/31 15:45:13.68 XH90LCx+0.net
ありがとうございます
短針のずれを考慮して実装し直します
iqが低すぎてそこまで頭が回りませんでした
62:デフォルトの名無しさん (ﾜｯﾁｮｲ 450c-JnmT)
23/03/31 15:54:30.84 XH90LCx+0.net
無事実装できました
やっぱり競プロはIQゲーだと思います
63:デフォルトの名無しさん (ﾜｯﾁｮｲ 4910-wXJE)
23/03/31 15:56:10.29 kOumRh050.net
あぁっIQ！(イク)
64:デフォルトの名無しさん (ﾜｯﾁｮｲ 8905-EZ7z)
23/03/31 16:08:43.15 t6yfY2Yj0.net
そうだよ、IQゲーだよ
というか算数のパズルだから、中受してるひとが有利
だから上位者は筑駒や灘だらけだろ
65:デフォルトの名無しさん (ﾜｯﾁｮｲ dfa4-RhFY)
23/04/01 08:38:04.57 zwk1ALmN0.net
はーい、ガイジのみなさん、こちらに集合してください
66:デフォルトの名無しさん (ﾜｯﾁｮｲ ffd7-7kGg)
23/04/01 12:15:44.71 dkRcJBBh0.net
ンガガーイ爺爺ジジジジジジwwwww
67:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa23-VQD5)
23/04/01 12:17:35.88 QjynJyA4a.net
ガイジは仲間を呼んだ
68:デフォルトの名無しさん (ﾜｯﾁｮｲ 5f10-GKj5)
23/04/01 13:42:49.55 BSSJ7Y2r0.net
あ、ガイ
69:デフォルトの名無しさん (ﾜｯﾁｮｲ ffbb-6Sa5)
23/04/01 13:58:41.08 wf8PbLnz0.net
ワクチンは毒ゴリ！
70:デフォルトの名無しさん (ﾜｯﾁｮｲ dfa4-RhFY)
23/04/01 14:15:52.73 zwk1ALmN0.net
おれも競プロのおかげでイベルメクチンを使ってコロナを乗り越えることができたわ
71:デフォルトの名無しさん
23/04/01 23:21:18.83 QCy7MZbH0.net
G問題、凸包の上側と下側を抜き出すのにかなり時間がかかってしまったね
ライブラリ化してもいい気がする
72:デフォルトの名無しさん
23/04/02 16:43:56.19 lbh8aSxV0.net
ゴリってワクチン打ってない陰謀論者なのに、飲み会に呼ばれるしオンサイトにも出てるんだ。羨ましーーー！
73:デフォルトの名無しさん
23/04/02 19:58:27.80 a1RtyEhB0.net
GPTはそのうち画像や音声データも読み込めるようになるって既に発表されてるぞ
74:デフォルトの名無しさん (ﾜｯﾁｮｲ 5f01-/O8Q)
23/04/03 01:39:44.68 IXS2Ww8n0.net
今日のこどふぉで「放物線と直接が共有点を持つかは判別式の正負で判定できる」っていう受験数学典型が出題されたけどこんなものも出るんだ 懐かしい
75:デフォルトの名無しさん
23/04/03 19:32:07.17 FgjSg9ZWa.net
めちゃくちゃ評判悪そう
76:デフォルトの名無しさん
23/04/03 19:53:40.00 q+x2Lby/0.net
下痢 ブリッ
77:デフォルトの名無しさん
23/04/03 21:24:06.14 SmeNn/jA0.net
むしろ競プロは受験数学の知識だけで解けるべきじゃない？
78:デフォルトの名無しさん (ｻｻｸｯﾃﾛﾚ Sp33-A7Yb)
23/04/04 00:10:14.93 VOtqbY9Mp.net
ワーキングメモリが足りなくて再帰で複雑なことされると理解に時間かかるんだけど、皆さんなにか工夫してます？
79:デフォルトの名無しさん (ｽｯﾌﾟ Sd1f-2YOk)
23/04/04 00:30:09.56 ynDnusCrd.net
あんなの慣れだろ
まぁ、細かい事言うと描く対象が木の時はこんな感じグラフの時はあんな感じみたいな
数列の漸化式みたいに一定の公式みたいのあるんだけどさ
80:デフォルトの名無しさん (ﾜｯﾁｮｲ ffca-7Vgv)
23/04/04 01:28:50.00 W5rb6s9n0.net
atcoderでおかしいと思うのは、Dまでで再帰の出現頻度が異常に少ないこと。
最後に見たの半年以上前なような。
アホみたいに単純になりがちなのと、中高生が取り組みにくいのが要因か。
81:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa23-+nBq)
23/04/04 02:14:13.00 TYadsnnda.net
は？ 先週のeも再帰で解いたんだが
82:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa23-+nBq)
23/04/04 02:16:15.48 TYadsnnda.net
あ、ごめんDまででってことか
わけのわからん制限つけるね
83:デフォルトの名無しさん
23/04/04 08:07:40.50 DHwR1ezN0.net
再帰で解けるものは山程あるのに使ってないってだけだろ
84:デフォルトの名無しさん
23/04/04 08:54:33.58 qTPfKvwBr.net
ループは再帰じゃん
85:デフォルトの名無しさん
23/04/04 09:46:39.09 t/xEUfRa0.net
再帰じゃないよ反復だよ
86:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa23-VQD5)
23/04/04 10:18:05.72 //1NkrQ5a.net
再帰呼び出しじゃないがi++は再帰的な式と言えるかな
87:デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM4f-Qm86)
23/04/04 10:51:59.65 QoHW7HWiM.net
むしろ再帰は慣れるとワーキングメモリが少なくても書ける部類のコードになる
関数の引数に対する処理と、終了条件の二つに気をつければいいだけ
全体像を追うんじゃなくて、あくまでもその関数を一回実行したときの処理だけ考える
88:デフォルトの名無しさん (ｻｻｸｯﾃﾛﾚ Sp33-A7Yb)
23/04/04 12:54:28.83 EY/4cjgwp.net
木が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"))
89:デフォルトの名無しさん (ﾍﾞｰｲﾓ MM8f-RhFY)
23/04/04 13:21:56.47 7WTftjG/M.net
知的障害とかおありでしょうか？わかりますよ？
<=のほうがよくね、minとかmaxは余計だね、とか
90:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa23-VQD5)
23/04/04 13:23:54.73 PqQnB5Pua.net
寒色がイキってんなー
91:デフォルトの名無しさん (ﾜｯﾁｮｲ 5f05-RhFY)
23/04/04 14:09:52.51 t/xEUfRa0.net
ガイジ同士仲良くしようね、ってことだよ
92:デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM4f-Qm86)
23/04/04 16:38:00.80 Oj3uAFDaM.net
ある頂点に対して、2つの子それぞれを根とする部分木の情報が定まってれば、その頂点について簡単に判定できる
数学的帰納法の考え方というか、局所的には簡単な処理できるってことがわかるとそんなに大変じゃなくなる
93:デフォルトの名無しさん (ｻｻｸｯﾃﾛﾚ Sp33-A7Yb)
23/04/04 16:58:58.57 lr/sr6Gfp.net
>>89
より良い書き方があるならコード見たいです
Pythonだと慣れてるので嬉しいです
94:デフォルトの名無しさん (ﾜｯﾁｮｲ 5f05-RhFY)
23/04/04 17:16:22.71 t/xEUfRa0.net
89でコメントした通りだよ
95:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa23-VQD5)
23/04/04 17:59:57.64 /ayUyQoPa.net
ガイジ同士仲良くしろよw
仲良くしようと頑張ってそれなのかw
96:デフォルトの名無しさん (ｻｻｸｯﾃﾛﾚ Sp33-A7Yb)
23/04/04 18:10:30.05 Uj7u2nTRp.net
>>94
minとかmaxって関数のことですよね？
これないと上位ノードより大きい値が左の下位ノードに存在することを許しちゃいませんか？
97:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa23-VQD5)
23/04/04 18:16:52.31 /ayUyQoPa.net
もしかして自演でやり取りしてるんじゃないかと思うくらいどっちも頭悪いな
98:デフォルトの名無しさん (ﾜｯﾁｮｲ df5f-vkwt)
23/04/04 19:37:36.74 jf1j38ly0.net
if not (minVal < root.data < maxVal):
return False
がある時点で明らかにその下の行では
min(maxVal, root.data)) == root.data
じゃない？
99:デフォルトの名無しさん (ﾜｯﾁｮｲ 5f05-RhFY)
23/04/04 19:51:05.61 t/xEUfRa0.net
そら明らかだよ
100:デフォルトの名無しさん (ｻｻｸｯﾃﾛﾚ Sp33-A7Yb)
23/04/04 20:15:59.15 s5dZ5QHYp.net
>>98
leetcodeにもそういうコードありました
もう一回やり直してみます
ありがとうございました
101:デフォルトの名無しさん (ｵｯﾍﾟｹ Sr33-eXH4)
23/04/04 20:17:37.51 L6sdRXYAr.net
BSTって何ンゴ？
102:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa23-VQD5)
23/04/04 20:19:04.15 /ayUyQoPa.net
余計なものの中に最後の一行についての言及がないということは二人()ともあのif文は要ると思ってるんだろうな
103:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa23-VQD5)
23/04/04 20:19:51.59 /ayUyQoPa.net
>>101
二分探索木
104:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa23-VQD5)
23/04/04 20:21:24.74 /ayUyQoPa.net
if文じゃなくif式か
105:デフォルトの名無しさん
23/04/04 20:25:46.72 jf1j38ly0.net
確かに そんなちゃんと読んでねえ
106:デフォルトの名無しさん
23/04/04 20:39:40.28 L6sdRXYAr.net
>>103
あっそっかぁ……
二分探索木判定とかしたいときあるか？
107:デフォルトの名無しさん
23/04/04 20:43:03.69 /ayUyQoPa.net
>>106
平衡二分木の実装をデバッグする時くらいかな
108:デフォルトの名無しさん
23/04/04 21:14:56.40 t/xEUfRa0.net
たしかに最後のifもいらねーじゃん
ガイジが集まれば強力なガイジになれそうだな
109:デフォルトの名無しさん (ﾜｯﾁｮｲ 5f07-VQD5)
23/04/05 07:32:45.91 xDsMBQrA0.net
ガイジは低レベルなところでワヤワヤやってただけだろw
110:デフォルトの名無しさん (ﾜｯﾁｮｲ dfa4-RhFY)
23/04/05 07:51:29.52 V9g+Im060.net
きみはもしかして高レベルなガイジなの？
111:デフォルトの名無しさん (ﾜｯﾁｮｲ 5f07-VQD5)
23/04/05 08:33:49.11 xDsMBQrA0.net
一人前にカチンときたか
112:デフォルトの名無しさん (JP 0H83-RhFY)
23/04/05 08:39:59.26 YYcedFeHH.net
みんなガイジなんだから仲良くしようね
113:デフォルトの名無しさん (ﾜｯﾁｮｲ 5f07-VQD5)
23/04/05 08:40:53.22 xDsMBQrA0.net
まずお前は素人の質問を見てマウント取らないようにするところから始めたらいいと思うぞガイジw
114:デフォルトの名無しさん (ﾜｯﾁｮｲ 5f07-VQD5)
23/04/05 08:42:54.34 xDsMBQrA0.net
誰でも見た瞬間わかることをさも有能ムーブで語るのは流石に見てるだけでイタいから
115:デフォルトの名無しさん (ﾜｯﾁｮｲ 5f05-RhFY)
23/04/05 09:11:39.70 kAD3is4b0.net
効いてて草
116:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa23-VQD5)
23/04/05 09:13:29.61 jU3TV3ZDa.net
毎日壊れたレコードみたいに戯言つぶやいてないでガイジスレに帰れよw
117:デフォルトの名無しさん (ｵｯﾍﾟｹ Sr33-GKj5)
23/04/05 10:36:55.94 ZG/fEbXfr.net
お前らもこっちきな😘
あっちは何を書き込んでもいいぞ🤗
118:デフォルトの名無しさん (ﾜｯﾁｮｲ ffd7-7kGg)
23/04/05 11:41:26.97 PMDplXIF0.net
こっちも何書き込んでも大丈夫だぞ😉
119:デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM4f-Qm86)
23/04/05 17:58:38.15 RPvbx/wwM.net
マジで寒いノリだな
120:デフォルトの名無しさん (ﾜｯﾁｮｲ 5f07-VQD5)
23/04/05 18:27:04.88 sB818/CP0.net
効いてるガイジ君ってずっといるんだなって
121:デフォルトの名無しさん (ﾜｯﾁｮｲ df2c-7kGg)
23/04/05 21:21:21.09 ez4hA7yb0.net
みんな効かないように頑張ろう
122:デフォルトの名無しさん (ﾜｯﾁｮｲ 7f55-EYsv)
23/04/06 17:29:09.91 AU30dZob0.net
幅優先探索の計算量が O(N + M)（N は頂点数, M は辺数）ですが、
N と M は異なる種類の変数です。
計算量は、 O(N + M) ですと言われてもピンときません。
普通は、 N << M だと思うので、 O(M) でいいような気がします。
例えば、連結グラフの場合、 N - 1 ≦ M ですよね。
123:デフォルトの名無しさん (ﾜｯﾁｮｲ 5f05-RhFY)
23/04/06 17:42:27.24 bgS53p4B0.net
辺が重複しない、という前提を入れるならそうですよね
124:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa23-VQD5)
23/04/06 17:42:52.77 SUeW78Oka.net
ウィキペディアにはO(M)と書いてあるぞ
125:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa23-AjAb)
23/04/06 17:49:53.74 2uDXGWIaa.net
普通は、と言ったって例外はあるやろ
126:デフォルトの名無しさん (ﾜｯﾁｮｲ 7f55-EYsv)
23/04/06 17:51:04.74 AU30dZob0.net
O(N + M) ですと教えてもらって何が嬉しいですか？
この情報をどう利用しますか？
127:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa23-VQD5)
23/04/06 17:56:13.19 SUeW78Oka.net
計算量の話をする時って何も断りを入れなければ最悪計算量か平均計算量に決まってるのに普通じゃない時の話を持ち出してるのはどういう人種なんだ
128:デフォルトの名無しさん (ﾜｯﾁｮｲ 5f05-RhFY)
23/04/06 18:01:17.36 bgS53p4B0.net
すまん、明らかに間違ったことかいてたわ
辺が重複しないじゃなくて、連結グラフという前提ならそうですよね
129:デフォルトの名無しさん (ｵｯﾍﾟｹ Sr33-eXH4)
23/04/06 18:52:38.27 T+lwLVXUr.net
うるせーバカ
130:デフォルトの名無しさん (ﾜｯﾁｮｲ 5f05-RhFY)
23/04/06 19:04:02.38 bgS53p4B0.net
サンキューガイジ！
131:デフォルトの名無しさん (ﾜｯﾁｮｲ 5f07-VQD5)
23/04/06 19:06:12.21 O4MLKnYM0.net
自演失敗してて草
132:デフォルトの名無しさん (ﾜｯﾁｮｲ 5f05-RhFY)
23/04/06 19:07:23.88 bgS53p4B0.net
自演ガイジも仲良くしようね
133:デフォルトの名無しさん (ﾜｯﾁｮｲ 5f07-VQD5)
23/04/06 19:10:39.31 O4MLKnYM0.net
効いてて草
134:デフォルトの名無しさん (ﾜｯﾁｮｲ 7f02-icd+)
23/04/06 19:18:25.49 ejh7i/EB0.net
計算量の話って
満足な時間内にできるかどうかの議論でしか役に立たないよね
135:デフォルトの名無しさん (ﾜｯﾁｮｲ df5f-vkwt)
23/04/06 19:29:21.38 aDW8E5OM0.net
かかる時間が見積もれると嬉しいだろ
O(M)でないものをO(M)って書いていいことにはならないけど
136:デフォルトの名無しさん (ｽﾌﾟｰﾌﾟ Sd9f-PuAn)
23/04/06 19:53:45.59 Ej/MkqD7d.net
幅優先探索はそもそもΩ(N+M)なケースが無いと思うからO(M)って書いて欲しいが、N=O(M)は自明じゃないと思うぞ
N頂点0辺のグラフだってあるし
137:デフォルトの名無しさん (ﾜｯﾁｮｲ 5f43-PuAn)
23/04/06 22:06:07.24 qiEKlOzd0.net
すまん嘘書いた
幅優先探索って最初に距離配列を作るからO(N+M)で合ってたわ
138:デフォルトの名無しさん
23/04/07 18:56:18.33 koL6xQVKa.net
チョクダイ毎日AI下げしてるな、これくらい上流層でも脅威なんだな
139:デフォルトの名無しさん
23/04/07 19:05:30.59 PbTiq3Mq0.net
高橋直大さんの実力は世界トップレベルなんですか？
140:デフォルトの名無しさん
23/04/07 19:50:49.14 4NY4d7fE0.net
いいえ
141:デフォルトの名無しさん
23/04/07 20:14:15.12 Jyfuc8w80.net
赤レベルが解けるようになるのは10年以上かかるだろうけど、
コーディングテストとして売り物になる層はすでにほぼ終了だし、E,Fまで解けるようになったらほとんどの参加者の自力解答は無意味ということに。
GPT前提の問題作りか、時間をかけた試行錯誤は苦手だろうからヒューリスティック重視とかになっていくんじゃないだろうか。
142:デフォルトの名無しさん (ﾜｯﾁｮｲ fe7c-UY1G)
23/04/08 00:54:27.43 NWI0hhIl0.net
ヒューリスティックもある程度のレベルまでは行きそうだけどな
24時間コードを書かせ続けることもできるし
143:デフォルトの名無しさん (ﾜｯﾁｮｲ a9b1-Q90w)
23/04/08 14:37:32.42 d9UfkEh40.net
始めて一年の茶色のおっさんだけどAIに負けるレベルになったと聞いてモチベだだ下がり。俺みたいなやつ多いと思うよ。
そりゃ参加者減ったら焦るわな
144:デフォルトの名無しさん (ﾜｯﾁｮｲ d907-NO7/)
23/04/08 14:48:17.63 dzO9pS9o0.net
AIに負けるって言うがChatGPTは競プロ用にチューニングしたプログラミングAIじゃないぞ
こいつができるのは問題を読むことと何を求められてるかを把握すること
つまり日本語(あるいは英語)を読解するAIだ
要するに人類が負けてるのはプログラミング能力じゃなく読解力と記憶力なんだよ
今に見てろこいつらあらゆる分野でゲームと動画に浸かったお前らに国語力の差を見せつけてくるから
145:デフォルトの名無しさん (ﾜｯﾁｮｲ e101-x1gv)
23/04/08 15:13:43.63 H0kArwlU0.net
暖色レベルへの到達はあったとしてもかなり先だろうし競技としては成立するだろうけど緑～水色くらいなら近い将来到達しそうだし新規参入と寒色停滞勢の参加率は減るかもね
146:デフォルトの名無しさん (ｻｻｸｯﾃﾛﾙ Spd1-42TY)
23/04/08 15:15:38.10 obJbbgz0p.net
競プロってゲームでやってるのかと思ってたからAIに負けてやる気なくなるってのはよくわからん
147:デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM66-rOwk)
23/04/08 15:21:45.60 YDsW15QlM.net
ARC/AGCの中盤以降に競プロの本当の楽しさがあるという主張は否定しないが、ABCの前半も競技として楽しんでいた層の方がマジョリティで、そういう層が競プロの裾野を広げていた側面もあるから、コンテンツとしてダメージを受けざるを得ないと思うわ
企業もスポンサーをするのは基本ABCだし、Jobsで見られているのもレベル的にABCでの実力がメイン
148:デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM66-rOwk)
23/04/08 15:23:40.74 YDsW15QlM.net
>>146
競技を楽しんでるのに競技そのものが成立しなくなったら嫌だろ？
Project Eulerみたいな感覚で問題に取り組んでいるんなら大丈夫だが、そういう人は初心者層ほど少ない
149:デフォルトの名無しさん (ｻｻｸｯﾃﾛﾙ Spd1-42TY)
23/04/08 15:26:53.49 obJbbgz0p.net
>>148
他の人らがAI使って解答してるかもしれないと思ってしまうってこと？
150:デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM66-rOwk)
23/04/08 15:34:11.41 YDsW15QlM.net
>>149
バレる可能性が低く対策不能なチートが蔓延ったオンラインゲームは壊れるやろ
ただのオンラインゲームでさえそうなのに、一応AtCoderはJobsみたいな実利的に意味のあるものと繋がってるから、みんな使うようになるんじゃねーの
開き直ってAIバトルにしても、投稿速度ゲームになりそうだし
151:デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM66-rOwk)
23/04/08 15:35:24.79 YDsW15QlM.net
みんな使わないにしても、使ってるやつにレートを吸われることでモチベの減退はあるだろうな
152:デフォルトの名無しさん (ｻｻｸｯﾃﾛﾙ Spd1-42TY)
23/04/08 15:36:44.41 obJbbgz0p.net
>>150
まあそういう人はスポーツすればいいよ
アルゴリズム解くのが好きとか純粋に知識欲の高い人が残るんだろうね
153:デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM66-rOwk)
23/04/08 15:43:15.50 YDsW15QlM.net
>>152
その辺の人でも楽しめる競技になる道は閉ざされそうで悲しいな
元々運営にそういうモチベなさそうだったが（金のために仕方なくやってる感満載だった）
154:デフォルトの名無しさん (ﾜｯﾁｮｲ c6ca-HjNm)
23/04/08 19:32:52.09 jzMk6Pp80.net
ノーレートで、食事したり飲みながら今までほぼ開かなかったF,GとかをchatGTPに聞いたり調べたりしながらやるのも楽しいぞい。解きたくない問題は解かなくても良いし。
155:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/08 20:03:48.77 RgGs2QbX0.net
ワーシャル・フロイドアルゴリズムについて質問です。
最終的に任意の2点間の最短距離を入れるための2次元配列は、
代入演算子の左右で共通のものが使われています。
それでも、問題がないのはなぜですか？
156:デフォルトの名無しさん (ﾜｯﾁｮｲ 85a4-5f+B)
23/04/08 20:09:47.90 8rEHJkBb0.net
ワーシャル・フロイドアルゴリズムは、全ての頂点間の最短距離を求めるためのアルゴリズムです。このアルゴリズムは、動的計画法の一種であり、一度計算された結果を再利用することで、計算量を減らすことができます。
具体的には、アルゴリズムの初期段階で、すべての頂点の間の距離を表す2次元配列を作成します。この配列は、アルゴリズムの途中で更新されますが、代入演算子の左右で共通のものが使われるため、問題はありません。
なぜなら、アルゴリズムの途中で更新される値は、それ以前の値に依存しているため、代入演算子の左右で共通の2次元配列を使用していることによって、更新された値が正しく計算され、以前に計算された値が失われることはありません。
つまり、更新された値は、以前に計算された値に基づいて正確に計算され、以前に計算された値が配列内に保持され続けるため、代入演算子の左右で共通の2次元配列を使用することは、アルゴリズムの正しい動作に影響を与えないということです。
157:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/08 21:36:51.70 RgGs2QbX0.net
>>155
大丈夫な理由が分かりました。
158:デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb)
23/04/08 22:06:19.33 8FTHKj1c0.net
chatGPT便利だろ
こういう風に答えてくれる
159:デフォルトの名無しさん (ﾜｯﾁｮｲ d907-NO7/)
23/04/08 22:12:19.75 dzO9pS9o0.net
ものすごくもっともらしい嘘つくから知らないことを聞くのはおすすめしないぞ
160:デフォルトの名無しさん (ﾜｯﾁｮｲ d907-NO7/)
23/04/08 22:16:56.23 dzO9pS9o0.net
ワルシャワ・フローラル法を知ってる？
はい、ワルシャワ・フローラル法は、グラフの最大マッチングを求めるアルゴリズムの一種です。このアルゴリズムは、ハンガリー人数学者であるエドモンド・ワルシャワと、ポーランド人数学者であるタデウシュ・フローラルによって開発されました。
ワルシャワ・フローラル法は、ハンガリー法と同様に、最大マッチング問題を解決するために使用されます。このアルゴリズムは、二部グラフに適用されます。アルゴリズムの基本的な考え方は、各未マッチング頂点について、その頂点を始点とする増加路を探し、その増加路に属する辺のマッチングを反転させることです。
ワルシャワ・フローラル法は、ハンガリー法よりも効率的であることが知られていますが、完全グラフでは最悪の場合の計算量がO(n^4)であるため、実用的ではありません。しかし、一般のグラフに対しては、最大マッチングを高速に計算することができるため、実際には広く使用されています。
161:デフォルトの名無しさん (ﾜｯﾁｮｲ 85a4-Az6A)
23/04/09 02:49:15.65 3zzmmMIO0.net
正確なことを答えさせるために、プロンプトエンジニアリングをがんばりましょうね
162:デフォルトの名無しさん (ﾜｯﾁｮｲ c69a-RdFw)
23/04/09 06:48:28.69 /c2XAn9L0.net
素朴な整数演算のコードを書いたため、特定のテストケースのときにコードの途中で
整数がオーバーフローするような場合、一般的なコードの書き方の処方箋みたいなものは
ありますかね
例えば「整数の配列から適切な要素を取り出して期待される和を作れ、そういう要素が
ない場合はエラー値を返せ」みたいので、配列要素はどれもオーバーフローに近い整数、
和は配列内の最小要素よりちょっとだけ大きい値（なのでエラー値の場合）、とか....
163:デフォルトの名無しさん (ﾜｯﾁｮｲ d907-NO7/)
23/04/09 10:26:45.20 /OFxiXOD0.net
競プロならlong longを使うだけ
実務ならオーバーフローした時に例外が発生するようにしてそれをキャッチ
164:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/09 13:54:07.28 l3qXUMY00.net
『アルゴリズム実技検定公式テキストエントリー～中級編』
最小全域木を求める、「プリムのアルゴリズム」について説明があります。
こうすれば、求まるという説明はあるのですが、なぜ求まるのかの説明がありません。
みなさんは、こうすれば求まるという情報だけで十分で、それで満足しますか？
それとも、ちゃんと証明まで自分で考えるか、誰かが書いた証明を読みますか？
165:デフォルトの名無しさん (ﾜｯﾁｮｲ ae2b-RdFw)
23/04/09 14:45:06.26 dl/B18nt0.net
>>163
なるほど。確かに例えば入力がintならlong longを使えばとりあえず大丈夫そう
ちなみにC++ですが、例えばintのオーバーフローを例外で処理するのはどうしたら....
166:デフォルトの名無しさん (ﾜｯﾁｮｲ 85a4-5f+B)
23/04/09 14:49:24.80 3zzmmMIO0.net
C++でオーバーフローを検出する方法はいくつかありますが、一般的なものは以下のようになります¹²³。
- 演算前に範囲チェックを行う。例えば、a + b がオーバーフローするかどうかは、a > INT_MAX - b か a < INT_MIN - b で判定できる。
- 符号なし整数を使う。符号なし整数のオーバーフローは定義されているので、演算後に結果が元の値より小さくなっていないかチェックすればよい。
- boostライブラリのsafe_numericsを使う。これはオーバーフローを検出するための特別な型を提供しており、オーバーフローが発生した場合に例外を投げる。
(1) Detecting signed overflow in C/C++ - Stack Overflow. URLﾘﾝｸ(stackoverflow.com) アクセス日時 4/9/2023.
(2) c++ - How do I detect unsigned integer overflow? - Stack Overflow. URLﾘﾝｸ(stackoverflow.com) アクセス日時 4/9/2023.
(3) c - How to check if overflow occured? - Stack Overflow. URLﾘﾝｸ(stackoverflow.com) アクセス日時 4/9/2023.
167:デフォルトの名無しさん (ﾜｯﾁｮｲ bd5f-EL/2)
23/04/09 16:13:00.47 sd0zf58N0.net
gccの__builtin_add_overflowとか__builtin_mul_overflowを使う
168:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/09 18:08:06.26 l3qXUMY00.net
github.com/kenkoooo/pastbook-source-code/blob/master/chukyu/python/chapter06/section11/6-11-1.py
169:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/09 18:11:31.29 l3qXUMY00.net
↑のファイルはプリムのアルゴリズムで最小全域木問題を解くコードです。
ファイル中の以下の箇所がなぜ必要なのかが分かりません。
一見すると、キューの中には、marked の値がFalseのノードしか入っていないように思うのですが、
実際には、Falseのノードも入ることがあるようです。（以下の箇所をコメントアウトすると
パスしません。）
# 辺につながる頂点 i もすでにマークされていた場合、
# 操作をスキップする
if marked[i]:
■■■■continue
170:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/09 18:16:05.03 l3qXUMY00.net
一部、間違えましたので訂正します。↓
↑のファイルはプリムのアルゴリズムで最小全域木問題を解くコードです。
ファイル中の以下の箇所がなぜ必要なのかが分かりません。
一見すると、キューの中には、marked の値がFalseのノードしか入っていないように思うのですが、
実際には、Trueのノードも入ることがあるようです。（以下の箇所をコメントアウトすると
パスしません。）
# 辺につながる頂点 i もすでにマークされていた場合、
# 操作をスキップする
if marked[i]:
■■■■continue
171:デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb)
23/04/09 18:19:09.47 fcL4nlHr0.net
この部分は、既にマークされた頂点に対応する辺をスキップするために必要です。
確かに、キューには基本的にmarkedの値がFalseのノードしか入らないように見えますが、
実際には同じノードに対して複数の辺がキューに入ることがあります。
例えば、次のようなグラフを考えてみましょう。
1 -- 2
| /
| /
3
各辺の重みはすべて1とします。最初に頂点1を選び、marked[1]=Trueとします。
次に、頂点1に隣接する辺をキューに追加します。
この時点でキューの状態は以下のようになります。
(1, 2), (1, 3)
次に、キューから最小の重みの辺を取り出し、それに接続されている頂点2をマークします。
頂点2に隣接する辺をキューに追加します。
この時点でキューの状態は以下のようになります。
(1, 3), (1, 1), (1, 3)
ここで、次にキューから取り出す辺が(1, 1)であることに注意してください。
ただし、頂点1はすでにマークされているため、この辺を使ってしまうと、最小全域木の条件を満たさなくなります。
これが、以下のコード部分が必要とされる理由です。
if marked[i]:
continue
この部分によって、既にマークされた頂点に対応する辺をスキップし、
正しい最小全域木を構築することができます。
172:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/09 18:19:33.94 l3qXUMY00.net
ヒープにプッシュする前に、そのノードがマークされていないことをチェックしています。
ですので、ヒープ内には、マークされていないノードしか入れないと思うのですが。
173:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/09 18:25:07.45 l3qXUMY00.net
>>171
あまり参考にならないだろうと思って読んでいたらなぜか理由が分かりました。
マークされていない状態で、同じノードが複数個ヒープに入ることがあるわけですね。
174:デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb)
23/04/09 18:28:01.90 fcL4nlHr0.net
>>172
確かに、ヒープにプッシュする前にそのノードがマークされていないことをチェックしています。
ただし、ヒープにプッシュされた後で、そのノードが他の辺を経由してマークされる可能性があります。
そのため、ヒープから辺を取り出す前にもう一度マークされているかどうかをチェックする必要があります。
先程のグラフで考えてみましょう。キューがこの様になったところから解説します。
(1, 3), (1, 1), (1, 3)
ここで、最初に(1, 3)をキューから取り出し、頂点3をマークします。この時点で、キューには以下のような状態が残っています。
(1, 1), (1, 3)
次にキューから取り出す辺は(1, 1)です。この辺は、頂点1と頂点2の間にありますが、頂点1はすでにマークされています。
しかし、この辺をヒープにプッシュした時点では、頂点1はまだマークされていませんでした。
それが、例のコード部分が必要とされる理由です。
あの部分によって、既にマークされた頂点に対応する辺をスキップし、正しい最小全域木を構築することができます。
175:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/09 18:28:12.80 l3qXUMY00.net
>>171
この場合でいうとノード3が2回ヒープに入るわけですね。
176:デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb)
23/04/09 18:31:35.09 fcL4nlHr0.net
>>175
はい、その通りです。
最初にノード1からノード3への辺がヒープに追加され、次にノード2からノード3への辺がヒープに追加されます。
(1, 3) <-- 1から3への辺
(1, 1)
(1, 3) <-- 2から3への辺
このように、同じノードが複数回ヒープに入ることがあります。プリムのアルゴリズムでは、
すでにマークされた頂点に対応する辺を無視する必要があります。
そのため、ヒープから辺を取り出す前にマークされているかどうかをチェックする必要があるのです。
177:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa05-IjNm)
23/04/09 19:43:48.36 O0uaasVha.net
おんちぽまんぽげろろろり？
178:デフォルトの名無しさん (ﾌﾞｰｲﾓ MMf6-tIu7)
23/04/09 22:42:46.25 fJZ93dkaM.net
序盤からムズすぎ
179:デフォルトの名無しさん (ﾜｯﾁｮｲ d9b0-OQ9P)
23/04/09 22:44:46.28 0uKKY8S80.net
Eむずい
setとpriority queueいじくってたら通った
180:デフォルトの名無しさん
23/04/09 22:47:55.78 DKklNxRop.net
E二分探索でやろうとしたらハマって普通にsetで順番にみるだけだった
F解けたのに今回も解いてる人の数がF<Gなせいであまり順位伸びてないの配点何とかして欲しいわ
181:デフォルトの名無しさん
23/04/09 23:58:26.29 BvehXBT4d.net
整数式の倍数判定のプログラム作りたいんだけどできる？
nは自然数
例1
入力:n(n+1)(n+2)
出力:6
(入力した式の倍数判定。6の倍数)
2の倍数でも3の倍数でもあるが、最も大きい数を出力
例2
入力:n^9-n^3
出力:504
182:デフォルトの名無しさん
23/04/10 02:32:34.26 Gn/yyThB0.net
>>181
nに素数をいくつか突っ込んだ値(0以外)で最大公約数とればいいんでない？
という気はするけど万年茶色脳には正しいか証明するなんてムリ
183:デフォルトの名無しさん
23/04/10 02:49:14.21 zrtbja+Y0.net
素数pの倍数かどうかはmod pが整域だから多項式は根を高々次数d個しかもたないのでp≤dだけ調べればいいよね
p^kはわからん
184:デフォルトの名無しさん
23/04/10 03:22:55.78 zrtbja+Y0.net
fが零因子⇔あるa≠0が存在してaf=0らしいから、最初にfを係数のgcdで割っとけば零因子じゃなくなって、p^k≤dだけ調べればいいと思う
185:デフォルトの名無しさん
23/04/10 03:46:52.88 zrtbja+Y0.net
>>184
これ全部嘘です 寝るか
186:デフォルトの名無しさん (ﾌﾞｰｲﾓ MMf6-tIu7)
23/04/10 13:12:10.43 Sbe/ma/bM.net
mod p で何代入しても0になる多項式は例えば x(x-1)...(x-p+1) でp次を達成できて最適
mod p^n だとこれをn乗すると構成できるので（最適かは知らんが）pn次以下と評価できる
だからpnがd以下の範囲を探索すれば良いが計算量は悪いな
187:デフォルトの名無しさん (ﾌﾞｰｲﾓ MMf6-tIu7)
23/04/10 13:16:20.11 Sbe/ma/bM.net
>>186
馬鹿すぎ、評価すべき方向が逆
188:デフォルトの名無しさん (ﾜｯﾁｮｲ d9b0-OQ9P)
23/04/10 15:49:54.60 1oGpX4FF0.net
Fはやってみたら簡単に解けた
Gはgrundy数求めるとき単純な勘違いしてた
むー悔しい
189:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/10 16:05:58.27 /Pv3NVQa0.net
DAGの最長パスを求める問題について質問があります。
『アルゴリズム実技検定公式テキストエントリー～中級編』に
「トポロジカルソート」の考え方が重要と書いてあります。
ですが、DAGがトポロジカルソートできるということを使っている
箇所が見当たりません。
載っている解法は、indegreeが0である頂点からの最長パスをDPにより求めるというものです。
190:デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb)
23/04/10 16:12:48.08 GqegRxcS0.net
確かに、その解法ではトポロジカルソートを明示的に実行していないように見えますが、
実際にはトポロジカルソートの考え方が含まれています。DAGの最長パスを求める際、
トポロジカルソートの概念が重要なのは、頂点の順序付けによって依存関係を解決することができるからです。
その解法で、indegree（入次数）が0の頂点からDPを用いて最長パスを求めています。これは、各頂点について、
その頂点に入ってくる辺がなくなる（依存関係が解決される）順序で処理を行っていることを意味します。
この順序付けがトポロジカルソートの結果と同じです。
indegreeが0になる頂点から処理を行い、その後、処理された頂点から出る辺を削除することで、
indegreeが0になる頂点が次々と現れます。この手順は、トポロジカルソートを実行する手順と同じです。
したがって、トポロジカルソートを明示的に行わなくても、その考え方が解法に含まれているため、
問題を解決することができます。トポロジカルソートの概念は、DAGの最長パス問題を解く際の重要な考え方であることがわかります。
191:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/10 16:13:37.24 /Pv3NVQa0.net
DAGであれば、最長パスが存在し、それはDPで求められる。
ただそれだけのことではないでしょうか？
192:デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb)
23/04/10 16:19:57.68 GqegRxcS0.net
はい、おっしゃる通りです。DAGであれば、最長パスが存在し、動的計画法（DP）を用いて求めることができます。
繰り返しになりますが、トポロジカルソートの概念を用いることで、DAG内の頂点の順序付けが可能であり、
この順序付けに従ってDPを適用することで、最長パスを求めることができます。
193:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/10 16:20:04.87 /Pv3NVQa0.net
DAGにoutdegreeおよびindegreeが0の点が両方とも存在することは、自明です。
もしそのような点がなければ、閉路が存在することになるからです。
トポロジカルソートなどという考え方を持ち出すまでもありません。
194:デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb)
23/04/10 16:26:05.43 GqegRxcS0.net
トポロジカルソートを明示的に実行しなくても、DAGの最長パス問題をDPで解くことは可能です。
ただし、その際に頂点の処理順序や依存関係の解決が重要となるため、トポロジカルソートの考え方が役立ちます。
トポロジカルソートを適用したDPでは、頂点の依存関係が効率的に解決されるため、計算量はO(V+E)です。
ここで、Vは頂点数、Eは辺数です。トポロジカルソートによって得られた頂点の順序に従ってDPを行うことで、
各頂点と辺に対して一度だけ計算が行われます。
一方、トポロジカルソートを適用しないDPでは、無駄な計算が発生する可能性があります。
例えば、メモ化再帰を用いたDPの場合、計算量は最悪O(2^V)になることがあります。
これは、全ての頂点に対して、それぞれを含むか含まないかの選択肢があるためです。
195:デフォルトの名無しさん (ﾜｯﾁｮｲ 417c-g1pj)
23/04/10 19:58:08.22 6t40mDb70.net
>>181
多項式 f(n) について計算したい
calc(f) で求めたい値を返す関数として
f が定数ならそれを返す
定数でないなら g(n)=f(n+1)-f(n)
とgを定めて
calc(f) = gcd(f(1), calc(g))
を計算すればいい、再帰の深さはfの次数で抑えられる
196:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/10 20:30:41.82 /Pv3NVQa0.net
『アルゴリズム実技検定公式テキストエントリー～中級編』に載っている
DAGの最長パスを求めるコードでは、トポロジカルソートを陽には使っていないです。
197:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa05-ynyP)
23/04/10 21:31:52.04 Qr60KJ2xa.net
その本持ってないからその本の解法教えて
そしたら質問の回答するよ
198:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/10 21:57:16.12 /Pv3NVQa0.net
>>197
ソースコードは以下です：
github.com/kenkoooo/pastbook-source-code/blob/master/chukyu/python/chapter06/section04/6-4-8.py
199:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa05-ynyP)
23/04/10 22:22:43.61 Qr60KJ2xa.net
確かに陽にトポロジカルソートはしてないね
値が確定する順序がトポロジカルソート順の逆順にはなってるけど
多分、以下のようなことを言いたいんじゃないかな
・各頂点の値を一つずつ順に確定していって、
・一度確定した頂点を再度訪れる必要がない
・そのようなことが可能な確定順が存在する
確かに考え方によっては自明とも思えるかもしれないけど、逆にそれくらいのことしか言ってないということでは
200:デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb)
23/04/10 22:32:19.30 GqegRxcS0.net
この問題の場合はメモ化再帰でトポロジカルソートを使わなくても計算量はO(N+M)です。
頂点間に循環がないため、再帰の深さが頂点数Nを超えることがなく、
各頂点に対して rec 関数が最大1回しか呼び出されないからです。
トポロジカルソートを使ってそのコードを書き換えるとこうなります。
URLﾘﾝｸ(ideone.com)
201:デフォルトの名無しさん (ﾜｯﾁｮｲ 06d7-IjNm)
23/04/11 00:50:14.84 AEAouguL0.net
んげりいいいいいいいwwwwww
202:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/11 10:56:16.23 KVT1yw8N0.net
>>199-200
ありがとうございました。
>>200
コードを見たのですが、
# トポロジカルソートで得られた順序に沿って最長経路を更新
for u in order:
for v in edges[u]:
length[v] = max(length[v], length[u] + 1)
の「for u in order:」でなぜ良いのかが分かりません。orderの要素を後ろから見ていかなければ
ならないように思ったのですが、そうではないのはなぜでしょうか？
203:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/11 11:11:09.23 KVT1yw8N0.net
for u in order:
■■■■print(u)
とすると自分が思っている順序とちょうど逆順で表示されます。
order.append(u)
を実行すると order の最大インデックスの要素の次に u が挿入されますよね。
そうだとすると、 order[0], order[1], … は queue から出てきた順に並べたものになりますよね。
204:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/11 11:15:16.38 KVT1yw8N0.net
多分、単純な勘違いなんですが、どこを勘違いしているのかが分かりません。
205:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/11 11:16:45.70 KVT1yw8N0.net
あ、分かりました。
与えられた有向グラフの辺の向きをすべて逆にしても、最長パスの長さは変わりませんね。
206:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/11 11:35:54.50 KVT1yw8N0.net
以下のコードは全く無駄なことをやっていますが、自分の理解通りなのはこちらのコードです：
ideone.com/gMUZDZ
207:デフォルトの名無しさん (ﾌﾞｰｲﾓ MM66-NK+R)
23/04/11 13:43:59.54 FMwVbediM.net
すまん初めてこのスレ来たんだけど連投してるやつはネームド？
208:デフォルトの名無しさん (ｵｯﾍﾟｹ Srd1-Ofdo)
23/04/11 14:46:33.78 vCEpO63Mr.net
ネームド志望
209:デフォルトの名無しさん (ﾌﾞｰｲﾓ MM66-tIu7)
23/04/11 15:09:56.33 F0CC9LzbM.net
>>195
天才か
gcd(f(1),f(2),...)
=gcd(f(1),f(2)-f(1),f(3)-f(2),...)
ということか
確かに典型だが無限で思考がストップしてしまっていた
210:デフォルトの名無しさん
23/04/11 18:39:41.18 KVT1yw8N0.net
pythonで2分探索を行う bisect というものがあります。
bisect.bisect(l, a)
としたとき、 a in l であるかどうかも判定したいのですが、そのような関数は用意されていませんか？
自分で作るしかないですかね？
211:デフォルトの名無しさん
23/04/11 18:42:16.72 KVT1yw8N0.net
Pythonに2分探索で整列済みのリスト l に要素 a が含まれるかどうかを調べる関数はありますか？
212:デフォルトの名無しさん
23/04/11 18:44:52.56 KVT1yw8N0.net
もちろん、 bisect を使って、簡単に実装できますが、用意されている関数はないですか？
213:デフォルトの名無しさん
23/04/11 19:14:39.91 AEAouguL0.net
がんばれ
214:デフォルトの名無しさん
23/04/11 19:20:22.62 KVT1yw8N0.net
まあ、以下のコードでいいと思うのですが、車輪の再発明はしたくないですよね。
i = bisect.bisect_left(l, a)
if l[i] == a:
return True
else:
return False
215:デフォルトの名無しさん
23/04/11 23:36:07.25 HQTQbeZV0.net
車輪の再発明はしたくないですよ
216:デフォルトの名無しさん
23/04/12 00:15:56.65 9s1XLAQx0.net
公式を読めと言いたいが
URLﾘﾝｸ(docs.python.org)
集合でも管理してinで判定すれば良いのでは(´・ω・`)
217:デフォルトの名無しさん
23/04/12 09:07:44.12 tXIe9h+KM.net
今IT系とは全く別の職種だから転職したくてAtCoder始めたけど楽しいな
未経験で他職種に転職出来るのか分からんけど
218:デフォルトの名無しさん
23/04/12 09:21:22.65 g9fBg21da.net
>>216
2分探索することは確定でそこで発見できるのにそれに加えてわざわざ他の集合を使う意味とは？
219:デフォルトの名無しさん
23/04/12 09:24:04.21 g9fBg21da.net
>>217
最低緑以上になればJobsで転職できる可能性はあるが緑っていっぱいいるので年齢や運が絡むかもな
220:デフォルトの名無しさん
23/04/12 09:48:33.24 VY8vydj+M.net
>>219
ありがとう
数学好きでアルゴリズムも昔やったことあったから緑まではすんなりいけたわ
今は水色目指して色々やってるけどアルゴリズム的要素より数学要素のほうが多く感じるな
年齢は25だからあと3年位がギリギリかなあと思ってる
221:デフォルトの名無しさん
23/04/12 10:00:29.60 e73VjvEsa.net
水より緑の方が採用しやすい
ほんとに転職したいなら水まで行ったらとか思わない方がいい
222:デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM66-NK+R)
23/04/12 12:09:52.88 SHZyHyDIM.net
>>221
今年色々あって復職したてだから転職活動するなら来年以降かもしれんわ、一応ビズリーチとか登録はしたけど
水色より緑のほうが採用しやすいのはなぜ？
223:デフォルトの名無しさん (ｽｯﾌﾟﾌﾟ Sd22-QZiB)
23/04/12 17:15:55.13 d+uvLod6d.net
今から狂気プログラミング始めるならPythonでいいかな、
224:デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb)
23/04/12 18:22:04.45 7SV2gFKB0.net
brainfuckがいいと思うよ
225:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/12 20:36:03.56 AXD/P1A20.net
以下の問題ですが、パスするまでに1日かかりました。
atcoder.jp/contests/past202004-open/tasks/past202004_g
こういうアイディアはほとんど必要がないけれども、実装するのが大変という
問題の対処方法を教えてください。
1日かかって作成したコードは以下です：
ideone.com/NY8mNY
226:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/12 20:42:57.91 AXD/P1A20.net
あ、模範解答を見たら、実装するのも実は大変じゃないんですね。
227:デフォルトの名無しさん (ﾜｯﾁｮｲ d907-NO7/)
23/04/13 14:51:21.47 YZ8/Xbx00.net
>>225
> こういうアイディアはほとんど必要がないけれども、実装するのが大変という
> 問題の対処方法を教えてください。
「アイデアを出すか頑張って実装する」以外の答えが思いつかんのだが真面目に聞いてるのか？
228:デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
23/04/13 16:57:11.93 lV5klkX+0.net
実装大変だなーと思ったら、自分のアイディアが悪いと思ってまず間違いないですか？
というのも、模範解答を見ると実装もシンプルな場合ばかりなので。
229:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa05-NO7/)
23/04/13 17:03:32.55 UbSfQqvCa.net
風向風速とかの簡単で面倒な問題も初期の頃はあったなあ
最近見ないけど無いと言い切る材料もない
230:デフォルトの名無しさん (ﾜｯﾁｮｲ e101-ynyP)
23/04/14 00:49:29.86 PKpPv7DW0.net
土曜夕方にコドフォdiv1あるじゃん
231:デフォルトの名無しさん (ｵｯﾍﾟｹ Srd1-Ofdo)
23/04/14 00:57:35.22 iX1MRsL1r.net
普通デートするよね
232:デフォルトの名無しさん
23/04/15 15:22:24.86 J7EhpH7h0.net
中国にウクライナ侵攻関連で厚い助力を求めるようだな
台湾侵攻の際には、米軍を混乱させるためにロシアは北海道に、北朝鮮は南に牽制するという話もあったしそりゃそうだよな
URLﾘﾝｸ(www.bloomberg.co.jp)
中国は、プーチン大統領が１年以上前にウクライナ侵攻を命じて以来初めて、国防相をロシアに派遣する。中ロの緊密な関係があらためて示唆される。
中国の李尚福国防相はロシアのショイグ国防相の招きに応じ、16日からロシア訪問を開始する。
ショイグ氏は李氏と軍事協力および世界や地域の安全保障について議論すると語ったと、ロシアの国営タス通信は報じた。
233:デフォルトの名無しさん
23/04/15 18:34:37.16 YgeZYNMw0.net
そうですか。中国やロシア、北朝鮮の動向は世界の平和や安全に影響を与える可能性がありますね。
最新のニュースによると、米国が中国の台湾侵攻を確実視しており、日本も中国と戦火を交える可能性があるという記事がありました。¹
また、安保理が18日に北朝鮮のICBM発射について緊急会合を開催することになりました。²
ロシアはウクライナ侵攻で敗色濃厚であり、北朝鮮の核ミサイル開発にも深刻な影響を受けているという記事もありました。³
これらの情報はあなたの興味に沿っていますか？
(1) 米国が確実視する中国の台湾侵攻、そうなれば日本も中国と戦火を .... URLﾘﾝｸ(jbpress.ismedia.jp) アクセス日時 4/15/2023.
(2) 安保理が18日に北朝鮮会合 ICBM発射で日米欧要請. URLﾘﾝｸ(www.nikkei.com) アクセス日時 4/15/2023.
(3) 敗色濃厚のロシア、北朝鮮の核ミサイル開発にも深刻な影響. URLﾘﾝｸ(jbpress.ismedia.jp) アクセス日時 4/15/2023.
(4) [FT]北朝鮮、ロシアに急接近 中国の思惑から離反 - 日本経済新聞. URLﾘﾝｸ(www.nikkei.com) アクセス日時 4/15/2023.
(5) ロシアと中国、北朝鮮情勢巡り緊密に連携 | ロイター. URLﾘﾝｸ(jp.reuters.com) アクセス日時 4/15/2023.
(6) 「中露と北朝鮮がサイバー攻撃」初の名指し…自衛隊の防衛 .... URLﾘﾝｸ(www.yomiuri.co.jp) アクセス日時 4/15/2023.
234:デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM8f-H/xe)
23/04/15 22:26:08.62 KbvfxJ7qM.net
今回のABCレート不具合で変動なしらしいな
苦手分野過ぎてAとBしか解けなかったからありがたいわ
235:デフォルトの名無しさん (ﾜｯﾁｮｲ 47b0-AIBz)
23/04/15 22:42:31.24 hxYUx3pC0.net
5完
バグりまくるし止まりまくるし散々だった
236:デフォルトの名無しさん (ﾜｯﾁｮｲ c7ad-/dh0)
23/04/15 22:45:28.79 2lW0lXjE0.net
>>218
調子良かったのにunratedかよ☹
237:デフォルトの名無しさん (ﾜｯﾁｮｲ c7ad-/dh0)
23/04/15 22:55:38.71 2lW0lXjE0.net
のんびり解いてた割には暖まるなあと思ってたけどこれDDoSの影響で普段速く解く人が遅れたってことか🥶
238:デフォルトの名無しさん (ﾜｯﾁｮｲ 47b0-AIBz)
23/04/15 23:06:02.45 hxYUx3pC0.net
あと5分あったらF修正して解けてた…
239:デフォルトの名無しさん (ﾜｯﾁｮｲ 4707-uZLY)
23/04/16 16:50:33.05 +7pzCas80.net
URLﾘﾝｸ(twitter.com)
マルチchokudaiサーチがダサくないと思ってるところに草生える
(deleted an unsolicited ad)
240:デフォルトの名無しさん (ﾜｯﾁｮｲ 67a4-ws6F)
23/04/16 18:18:14.06 iQzJN3tu0.net
研究者が自分の名前を手法に付けることは、研究コミュニティで一般的には推奨されていません。ただし、研究者が特定の手法やアルゴリズムを開発した場合、その手法が他の研究者や専門家によって引用されることがあります。この場合、研究者の名前が手法に関連付けられることがあります。
241:デフォルトの名無しさん (ﾜｯﾁｮｲ 072d-7nfa)
23/04/16 18:55:38.54 uh3dAZwl0.net
今回のCでどうしても3つTLEが潰せない
242:デフォルトの名無しさん (ｱｳｱｳｳｰ Sacb-uZLY)
23/04/16 19:06:04.93 Ke39kkrTa.net
どうしても自力で解けないなら解説読んでいいんじゃね
243:デフォルトの名無しさん (ｵｯﾍﾟｹ Srfb-g0sp)
23/04/16 22:30:54.90 SVYFRHN6r.net
もし自分でアルゴリズム開発したらかっこいい略称付けたいよね
244:デフォルトの名無しさん (ｱｳｱｳｳｰ Sacb-4m2x)
23/04/16 22:32:11.67 XfEQvCuWa.net
>>241
俺かよ
PriorityqueやSortedSetを使わずに普通の配列やSetを使って出力時に都度ソートしたら行けた
自前のライブラリだと重すぎるみたいだな
245:デフォルトの名無しさん
23/04/17 08:58:02.89 5c7uVWzN0.net
Aho, Hopcroft and UllmanのThe Design and Analysis of Computer Algorithmsという
非常に古い本はもうゴミのような本でしょうか？
246:デフォルトの名無しさん
23/04/17 12:28:12.67 WWhqmq79r.net
今アホって言った？
247:デフォルトの名無しさん (ﾜｯﾁｮｲ 07da-vbZL)
23/04/17 22:20:09.89 5e6VxUA80.net
最近は自分で判断できない輩が増えてきたな。
248:デフォルトの名無しさん (ﾜｯﾁｮｲ c705-9i6p)
23/04/17 22:52:26.54 LKkslgOL0.net
>>245
Aho, Hopcroft, and UllmanのThe Design and Analysis of Computer Algorithmsという本は、1974年に初版が出版された古いテキストですが、ゴミのような本とまで言うのは必ずしも適切ではありません。この本は、コンピュータアルゴリズムの設計と解析に関する初期の基本的な理論と概念をカバーしており、多くの現代のアルゴリズムの基礎となっています。しかし、この本が初版が出版されてから約半世紀が経過し、その間にコンピュータ科学やアルゴリズムに関する研究は大幅に進歩しています。例えば、機械学習、データマイニング、並列化、分散システムなどのトピックが現代のアルゴリズム研究の重要な分野となっていますが、これらはこの本では扱われていません。
この本は古典的なアルゴリズムの理解には役立ちますが、より新しいアルゴリズムや技術の発展を学ぶためには、最近出版された書籍やオンラインリソースを利用することが望ましいです。例えば、Cormen, Leiserson, Rivest, and SteinによるIntroduction to AlgorithmsやKleinberg and TardosのAlgorithm Designといった現代のテキストは、最新の研究や技術を含んでおり、現在の学習者に適した教材です。
つまり、Aho, Hopcroft, and UllmanのThe Design and Analysis of Computer Algorithmsは、歴史的な価値があるという点でゴミのような本とは言えませんが、現代のアルゴリズム研究や技術を学ぶ上で最も適切な教材ではないかもしれません。学ぶ内容に応じて、より新しいリソースや書籍を利用することを検討してみてください。
249:デフォルトの名無しさん (ﾜｯﾁｮｲ 7fd6-GSlL)
23/04/17 23:36:48.58 y8gbGQlA0.net
アルゴリズムデザイン、重版されて書店に並んでて嬉しかった
250:デフォルトの名無しさん (ｱｳｱｳｳｰ Sacb-J8Vk)
23/04/20 19:31:49.09 f2njLhGLa.net
URLﾘﾝｸ(mathlog.info)
今までにない斬新なセグ木の解説記事
251:デフォルトの名無しさん (ｱｳｱｳｳｰ Sacb-uZLY)
23/04/20 19:42:54.89 mhtgTGfFa.net
>>250
その下のスーパー某もすごいな
252:デフォルトの名無しさん (ｵｯﾍﾟｹ Srfb-Lcwe)
23/04/21 12:31:14.61 Oi9Mt79Gr.net
レートは？書いた人の
253:デフォルトの名無しさん (ｱｳｱｳｳｰ Sacb-uZLY)
23/04/21 13:07:22.60 /VhDvdfwa.net
正確な数値はともかく灰色以外の何に見えるんだ？
254:デフォルトの名無しさん (ｵｯﾍﾟｹ Srfb-Lcwe)
23/04/21 13:16:18.21 wvR7tFMwr.net
読む価値があるか確認するために聞いたんだけど
255:デフォルトの名無しさん (ｱｳｱｳｳｰ Sacb-uZLY)
23/04/21 13:19:22.09 /VhDvdfwa.net
ないよ
256:デフォルトの名無しさん (ﾜｯﾁｮｲ bfd7-KgtD)
23/04/21 13:20:36.38 Va2XyxIX0.net
ないアルヨ
257:デフォルトの名無しさん (ｱｳｱｳｳｰ Sacb-uZLY)
23/04/21 13:23:56.80 /VhDvdfwa.net
ないのかあるのかどっちだと突っ込んでほしいジジイおるな
258:デフォルトの名無しさん (ﾜｯﾁｮｲ bfd7-KgtD)
23/04/21 13:26:33.33 Va2XyxIX0.net
ツッコんでほしいアルヨ
259:デフォルトの名無しさん (ﾜｯﾁｮｲ c75f-icHo)
23/04/21 17:05:10.19 k2duIDVm0.net
関数型しか触ったことないに1ペソ
260:デフォルトの名無しさん (ﾌﾞｰｲﾓ MM3e-Zf+n)
23/04/22 21:46:10.29 5GqLc7RXM.net
またUnratedやないか
誰やねんDDoSしてるやつ
こんなサイトにしても意味ないやろ
261:デフォルトの名無しさん (ﾜｯﾁｮｲ 15b0-8fVP)
23/04/22 22:42:13.57 /cmb/FVj0.net
久しぶりにABCDEG6完😤
262:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa21-m1As)
23/04/22 23:12:42.60 rVcI1++Da.net
中国かロシアやろな
国がらみの可能性もあるから犯人探しは無意味
263:デフォルトの名無しさん
23/04/23 01:27:17.24 moyGSSduM.net
意図的に狙われてるのは確かだけどなんの目的で狙ってるんやろ
264:デフォルトの名無しさん (ﾜｯﾁｮｲ 5d2d-YWDm)
23/04/23 15:36:40.71 60YTymnP0.net
C問題なんだけど解説みたいに反転させる必要ある？
一つでも-が含まれてたらoの最大長答えるだけじゃない？
つまりn未満のoの最大長答えるだけでしょ
265:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa21-m1As)
23/04/23 15:44:39.80 QD8bkyZga.net
解答例のやり方だと反転の必要あるな
串が出てきて初めてansに入るから
266:デフォルトの名無しさん (ﾜｯﾁｮｲ e5ad-8MXh)
23/04/23 18:46:05.86 MZTwl0QJ0.net
反転させて2回チェックすれば団子判定をシンプルにできるって意図じゃないかな
267:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa21-ZiWf)
23/04/23 18:54:15.92 LpJKh+XVa.net
出題者は反転してない
どっちでもいいんじゃね
268:デフォルトの名無しさん (ﾌﾞｰｲﾓ MM3e-oS25)
23/04/23 20:08:08.02 PWijjkXzM.net
-が入っていれば、oと-しかないのだからoは-と接してるわけで、oと-どちらかなければ-1、両方あれば連続したoの長さでいいんじゃないの？
269:デフォルトの名無しさん (ﾌﾞｰｲﾓ MM3e-oS25)
23/04/23 20:10:50.67 PWijjkXzM.net
久し振りにやったんだけど、
rated選んだつもりなのにunratedになってたんだけど、自分が選び間違えたの？
成績よくなかったからいいんだけど
270:デフォルトの名無しさん (ﾜｯﾁｮｲ 1507-ZiWf)
23/04/23 20:17:55.91 5yiVxLP00.net
質問タブに書いてあるけどDDOSのせいで全員unratedの無効試合になってる
271:デフォルトの名無しさん (ﾜｯﾁｮｲ 1507-ZiWf)
23/04/23 20:18:35.89 5yiVxLP00.net
>>268
それでもいいし解けさえすればそれでなくてもいいというだけの話
272:デフォルトの名無しさん (ﾌﾞｰｲﾓ MM3e-oS25)
23/04/23 20:39:44.51 PWijjkXzM.net
>>270
ありがと。
別にお酒に酔ってたわけじゃないのに、
なんで間違えたのかずっと悩んでたの
273:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa21-ZiWf)
23/04/23 20:43:02.12 LpJKh+XVa.net
Cは正規表現で解けるな
肯定的先読み言明を使えば一回のマッチでいける
274:デフォルトの名無しさん (ﾜｯﾁｮｲ 7d01-8Z+s)
23/04/23 21:48:22.47 kV4uegyh0.net
質問タブでアナウンス送るの、知らない人にとっては分かりづらい
275:デフォルトの名無しさん (ｽﾌｯ Sd0a-hie5)
23/04/25 18:22:04.22 NfKxocHyd.net
Chatgptの影響ですでにレート出にくくなってるとかある？
276:デフォルトの名無しさん (ﾜｯﾁｮｲ e505-2JcT)
23/04/25 18:32:28.97 aoA2LcV80.net
GPTのおかげで誰でもCくらいまでは瞬殺できるし、緑茶らへんの人にとっては影響あるんじゃない？
277:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa21-9VOY)
23/04/25 20:23:26.21 Nhg6f6DZa.net
インタラクティブ問題なら回避できるんかな
278:デフォルトの名無しさん (ｽｯﾌﾟ Sd0a-PPLO)
23/04/25 22:48:32.00 8h60ybjNd.net
茶色中盤くらいまではCまで早解きゲーだしまあ初心者は萎えるかもな
279:デフォルトの名無しさん (ﾜｯﾁｮｲ 5d2d-YWDm)
23/04/26 00:39:41.99 v/InlOgJ0.net
D - Find by Query
この問題の意味がわからない、運が悪いとACできないとか無いの？
280:デフォルトの名無しさん (ﾜｯﾁｮｲ 5d2d-YWDm)
23/04/26 00:44:09.42 v/InlOgJ0.net
ああ、境界を探すのか
281:デフォルトの名無しさん
23/04/26 04:47:13.13 CtDSQpU90.net
10 ^ 6で試せる回数が20回だから二分探索しかないんだけどこういうメタ読み辞めたいんだよな
282:デフォルトの名無しさん
23/04/26 04:53:12.19 dFoBwinZp.net
何なら序盤で出てくるインタラクティブ問題っていう時点でパターンが限られすぎてて8、9割二分探索(の類型)であることが推測出来る
283:デフォルトの名無しさん
23/04/26 14:19:57.84 pZKGmWvba.net
>>276
必ず正しい答えを出すわけじゃないから自分で直せないとペナルティ食らうぞ
284:デフォルトの名無しさん (ﾜｯﾁｮｲ 7d01-8Z+s)
23/04/26 18:10:09.71 hY8jXU1C0.net
問題公開されてても提出できなかったらどうすんの
285:デフォルトの名無しさん (ﾌﾞｰｲﾓ MM3e-Zf+n)
23/04/26 18:32:26.54 PpfAVk7MM.net
茶色だけみんなchatgptで序盤の問題解いてたのか
俺もそうしようかな
286:デフォルトの名無しさん (ﾜｯﾁｮｲ e505-2JcT)
23/04/27 13:25:15.77 N5pXZR7+0.net
GPT使ってないからレートが低い、みたいなセルフハンディキャップはカッコ悪すぎるからGPTくらいは賢く利用しようね
287:デフォルトの名無しさん (ﾜｯﾁｮｲ 5d2d-YWDm)
23/04/28 04:45:15.96 9dah9Cbv0.net
A,Bの問題文を整形してChatGPTに貼り付けて反応もどってくるの待つより自分で解いたほうが速いわけ
更に投稿前にチェックも必要だし
嫁にそのやり方を教えてA,B問題の投稿を担当してもらってる間に自分はCあたりから手を付けるのほうがいいかも
288:デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-/HYv)
23/04/28 08:08:18.98 Qu9Tu4Uo0.net
>>287
そんな姑息なことをするほど、競技プログラミングで良い成績をおさめることにメリットはあるんですね。
289:デフォルトの名無しさん (ﾜｯﾁｮｲ d1a4-2JcT)
23/04/28 08:22:56.44 39Dn9gJ30.net
>>287
APIあるんだから全部自動化するにきまってんだろ
290:デフォルトの名無しさん (ﾜｯﾁｮｲ 17b0-NOa+)
23/04/29 23:10:27.33 yZQ+uKse0.net
5完しかできなかった
Dみたいなのが地味にめんどくさい
291:デフォルトの名無しさん (ﾌﾞｰｲﾓ MM8f-ia05)
23/04/29 23:17:20.22 BBFLtm1nM.net
D問題昨日勉強した内容が出てきてめっちゃ嬉しかった
これ進研ゼミでやったことある状態だったわ
292:デフォルトの名無しさん (ﾜｯﾁｮｲ 5701-MUOW)
23/04/30 00:03:32.63 VtRKwrnb0.net
Gで解説と違う方針で通したから解説書こうと思ったが、一応C++でも通るか確認したらC++だとTLEだったのでやめた
C++遅いね
293:デフォルトの名無しさん (ｽﾌｯ Sdbf-TsFU)
23/04/30 01:19:01.58 WQH2sNqzd.net
Patisserie ABC 3 出るかと思って過去問見直したけど全然出なかった
294:デフォルトの名無しさん (ﾜｯﾁｮｲ f7db-YI8Y)
23/05/03 00:51:23.91 83koBp/d0.net
ngtkanaって男性？
295:デフォルトの名無しさん (ﾜｯﾁｮｲ 97ad-muTB)
23/05/03 04:10:47.45 k35m8F9T0.net
黄色だから野郎じゃない
296:デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf)
23/05/03 17:06:24.93 aKUbjdKi0.net
n次元直方体とは I = [a_1, b_1] × [a_2, b_2] × … × [a_n, b_n] の形の集合である。
n次元空間 R^n の部分集合 B で、有限個のn次元直方体の和集合であるようなもの全体の集合を C とする。
B1, B2 ∈ C であるときに、 B1 = B2 であるかそうでないかを判定してください。
↑自作の問題です。
この問題って効率的なアルゴリズムが存在しますか？
297:デフォルトの名無しさん (ﾜｯﾁｮｲ 577c-9aVW)
23/05/03 17:43:05.99 C+dlbD9Z0.net
日本語で書いてくれ
298:デフォルトの名無しさん (ﾜｯﾁｮｲ 572d-wHlW)
23/05/03 19:29:13.60 ElyXadep0.net
B1とB2の直方体の数が異なる場合、B1とB2は等しくない
B1とB2の直方体の数が同じ場合、B1とB2に含まれる直方体の番号を並べ替える
各直方体の対応する要素が等しくない場合、B1とB2は等しくない
すべての直方体の対応する要素が等しい場合、B1とB2は等しい
299:デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf)
23/05/03 19:40:48.41 aKUbjdKi0.net
B1 が1個のn次元直方体からなる集合とします。
それを2つに分けた2つのn次元直方体の和集合を B2 とします。
B1 を構成する直方体の数は 1 です。
B2 を構成する直方体の数は 2 です。
ですが、B1 = B2 です。
300:デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf)
23/05/03 19:43:42.25 aKUbjdKi0.net
B1 = [0, 1] × [0, 1]
B2 = [0, 1/2] × [0, 1/2] ∪ [1/2, 1] × [0, 1/2] ∪ [0, 1/2] × [1/2, 1] ∪ [1/2, 1] × [1/2, 1]
が入力として与えられた場合、 B1 = B2 です。
301:デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf)
23/05/03 19:48:56.95 aKUbjdKi0.net
B1 = [0, 5] × [0, 5]
B2 = [0, 2] × [0, 1] ∪ [1, 4] × [2, 3] ∪ [2, 4] × [3, 4] ∪ [0, 1] × [2, 4] ∪ [2, 4] × [0, 2] ∪ [0, 2] × [1, 2]
B1 ≠ B2 です。
302:デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf)
23/05/03 19:49:22.48 aKUbjdKi0.net
>>301
訂正します：
B1 = [0, 4] × [0, 4]
B2 = [0, 2] × [0, 1] ∪ [1, 4] × [2, 3] ∪ [2, 4] × [3, 4] ∪ [0, 1] × [2, 4] ∪ [2, 4] × [0, 2] ∪ [0, 2] × [1, 2]
B1 ≠ B2 です。
303:デフォルトの名無しさん (ｵｯﾍﾟｹ Sr8b-siYD)
23/05/03 21:06:39.53 MtXxv88er.net
うんち！w
304:デフォルトの名無しさん (ﾜｯﾁｮｲ 5701-MUOW)
23/05/04 00:35:43.31 FFDpqzE90.net
併合していって無駄のない表現にできればいける？
305:デフォルトの名無しさん (ﾜｯﾁｮｲ 375f-k3Rv)
23/05/04 01:33:09.74 Pbw0n2Gt0.net
そんなことよりn乗で増えていくのを抑えないと無理なんでは
306:デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf)
23/05/04 02:26:58.39 iR6EpWdh0.net
2次元限定、座標は有理数限定にしたら、競プロの問題として成立しますか？
307:デフォルトの名無しさん (ﾜｯﾁｮｲ 572d-wHlW)
23/05/04 04:20:04.21 W+5O3yqN0.net
>>306
yukicoderで出題してみれば？
308:デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf)
23/05/05 10:56:46.77 xYbtWehf0.net
>>307
そういうサイトがあるんですか。
a, b を実数とする。
a ≦ b とする。
[a, b], [a, b), (a, b], (a, b) を区間という。
d 個の区間 I_1, …, I_d の直積 B := I_1 × … × I_d を R^d の直方体という。
B_1, …, B_k を互いに共通部分のない R^d の直方体とする。
E = B_1 ∪ … ∪ B_k
とする。
i ∈ {1, …, k} とする。
B_i を含む E の部分集合の中で最大の直方体を求めよ。
この効率的な解法はありますか？
309:デフォルトの名無しさん (ﾜｯﾁｮｲ bfd7-E7B+)
23/05/05 13:25:13.43 CuujTRH+0.net
あるよ
310:デフォルトの名無しさん (ﾌﾞｰｲﾓ MMab-8WUk)
23/05/05 18:31:53.93 zrOWQZW0M.net
自分で解けてなければ自作の問題とは言わん
311:デフォルトの名無しさん (ﾜｯﾁｮｲ 375f-67at)
23/05/05 21:17:04.26 0zwWrX/A0.net
よくわからないけど [0, 1) の最大の区間は存在しないんだけど大丈夫そ？
312:デフォルトの名無しさん
23/05/14 13:25:49.39 0RYyu89NT
曰本に原爆落とした世界最悪のならす゛者ヒステリ一國家の犬コ口ジャップと違って世界中に氣球飛ばしてる習近平を全面的に支持しようぜ
都心まて゛数珠つなき゛て゛クソ航空機飛は゛しまくって，クソポリ公は威力業務妨害へリ飛は゛しまくって仕事に勉強にと妨害して住民の神経破壞
して犯罪惹起してるし，温室効果ガスに騒音にコ□ナにとまき散らして氣侯変動させて災害連發させて國土に國力にと破壊して人殺して
私権侵害して私腹を肥やす史上最悪の強盜殺人の首魁齊藤鉄夫ら殺人腐敗テ口リストに乗っ取られたクソ曰本全國と゛こからでも２４時間
必す゛クソシナの気球が見えるくらいに飛は゛しまくってクソ航空機を根絶やしにしてくれたら、離島全部クソシナの領土ってことでいいよな
何が領空侵犯だ、撃墜すへ゛きは何も住民に危害を加えていない氣球て゛はなく，四六時中グ儿ク゛ル私権侵害しまくってるクソポリ公へリた゛ろ
専制主義と民主主義の対立た゛の言ってるハ゛力か゛いるが，地球破壞して私権侵害して私腹を肥やす強盜殺人テ口國家との対立というのか゛正解
民主主義とは銃刀法などなく個人がスティンカ゛－を所持して，平穏な生活を妨害するテ□リス├から身を守る権利か゛住民にある社會た゛ボケ
創価学会員は、何百萬人も殺傷して損害を与えて私腹を肥やし続けて逮捕者まで出てる世界最悪の殺人腐敗組織公明党を
池田センセ―が□をきけて容認するとか本氣て゛思ってるとしたら侮辱にもほどがあるぞ！
ｈＴТрｓ：／／ｉ．ｉｍｇｕｒ，сοｍ／hnli1ga.jpeg
313:デフォルトの名無しさん
23/05/13 22:41:38.39 WJe+G9hta.net
5分延長か
面白い対応するね
314:デフォルトの名無しさん
23/05/14 00:45:51.21 KvQ47IR30.net
攻撃を受けてもratedという前例ができたのはよかった
315:デフォルトの名無しさん
23/05/14 06:52:48.64 NgHJ91w50.net
コンテストモードの敗北
316:デフォルトの名無しさん (ﾜｯﾁｮｲ f37c-ECSL)
23/05/17 05:36:16.93 UaIMjrrs0.net
>>294
女性だよ
検索したら本名とか出て来ると思うけど
317:デフォルトの名無しさん (ﾜｯﾁｮｲ a32d-+/XS)
23/05/17 09:19:32.53 tRah0iPS0.net
>>316
Youtubeで本人の歌声も聴けるしな
318:デフォルトの名無しさん (ﾜｯﾁｮｲ d3b0-SwK+)
23/05/20 22:48:05.22 IbXAPdJ/0.net
６完…
今回は７完したかった…
319:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa2f-o1RM)
23/05/20 23:12:12.63 +EVZ8y+Ka.net
配点割とその通りだったな
320:デフォルトの名無しさん (ﾜｯﾁｮｲ 57db-3XON)
23/05/22 00:56:46.44 mBh1GEMi0.net
パフォーマンスがinfinityになった回って61以前にあった？
321:デフォルトの名無しさん (ﾜｯﾁｮｲ abb0-IOpb)
23/05/27 22:44:08.16 DM47Hxe/0.net
難しすぎるよ
322:デフォルトの名無しさん
23/05/27 23:33:38.14 DM47Hxe/0.net
コドフォもないし
323:デフォルトの名無しさん (ﾜｯﾁｮｲ 99b0-AV1S)
23/06/03 23:01:24.39 i1emxrQn0.net
6完
mod入力ミスってたのがアホすぎる
324:デフォルトの名無しさん
23/06/04 16:31:49.86 VEMViUBd0.net
やっとE問題解けるようになってきた
E問題って一個一個の実行時間が長いんだな
325:デフォルトの名無しさん
23/06/04 17:44:29.58 0q9gSB9x0.net
競プロ有段者(強い人)に質問
Atcoderで一段階上に行くためには解説を何も見ずとも解けるレベルの一段階上を同じように解けるレベルになるまでその問題を解説だけ見て実装は全て自分で、っていう感じでひたすら練習していくっていうやり方は有効？
自分の場合はD問題は9割ガタ解けて、Eがまだ実戦では歯が立たないレベル
326:デフォルトの名無しさん
23/06/04 17:53:24.73 AGQzq0Q+0.net
うん
327:デフォルトの名無しさん
23/06/04 20:29:27.17 z/tZxQvT0.net
E問題思ったより簡単だな
食わず嫌いしてた
328:デフォルトの名無しさん
23/06/06 11:53:03.19 MhCqkbZk0.net
某所で「左右がバランスした括弧の列を生成する」という問題があり、解答が
void parenthesis(int l, int r, string& s, vector<string>& ans) {
if (l + r == 0) {
ans.push_back(s); return;
}
if (r < l) return;
if (l > 0) {
s.push_back('(');
parenthesis(l - 1, r, s, ans);
s.pop_back();
}
if (r > 0) {
s.push_back(')');
parenthesis(l, r - 1, s, ans);
s.pop_back();
}
}
（呼出の例） vector<string> ans; string s; parenthesis(4, 4, s, ans);
この if (r < l) return; が左右のバランス（単に'('と')'の数が同じというだけでなく）の条件に
効いているようですが、ピンとこないのです... 確かに正しい括弧の列のとき、それが成り
立つのはわかりますが、逆にそれがバランス条件を満たすのに十分であるというのが
どなたかわかりやすい説明はないでしょうか
329:デフォルトの名無しさん
23/06/06 12:29:54.00 GQVo4dJ/a.net
しょーもない処理を複雑に描いてるだけのクソプログラムやな
この関数は最初の呼び出しでlとrが同じ数字なるよう入れるのが前提で
r<lの条件は例外処理みたいなもんやろ
330:デフォルトの名無しさん
23/06/06 12:35:33.96 UncR9VmG0.net
このコードの一部 `if (r < l) return;` について説明します。
ここで `l` と `r` はそれぞれまだ追加できる '(' の数と ')' の数を表しています。なので、このチェック `if (r < l) return;` は、')' の数が '(' の数より少なくなる場合、すなわち、開き括弧より閉じ括弧が少なくなる場合を防いでいます。
正しい括弧の列を生成するためには、2つの重要なルールを守らなければなりません：
1. 左括弧と右括弧の数が等しいこと
2. 任意の時点で、右括弧の数が左括弧の数を超えないこと
1つ目のルールは、左括弧と右括弧を同数だけ生成すれば満たされます。しかし、2つ目のルールはもう少し注意が必要です。それは、どの時点でも、閉じ括弧の数が開き括弧の数を超えてはならないからです。これを超えてしまうと、括弧の列が無効になってしまいます。
例えば、"())(" のような列は、開き括弧と閉じ括弧の数は同じでも、2番目の閉じ括弧が開き括弧を超えているため、無効な括弧の列となります。
だからこそ、`if (r < l) return;` のチェックが必要なのです。これにより、閉じ括弧の数が開き括弧を超えるような状況を防いでいます。これは、まだ追加できる閉じ括弧の数 `r` が、開き括弧 `l` より少なくなる場合、すなわち、閉じ括弧が開き括弧を超える可能性がある場合に、そのパスをすぐに終了させることで実現されています。
331:デフォルトの名無しさん
23/06/06 12:49:04.77 FRsr3KcUH.net
(を+1)を-1と対応させて累積和が常に非負っていうのがバランスしていることの必要十分条件であることを認めれば if(r < l)return; がそれの言い換えなことは明らか
証明したければ累積和が0になるところで文字列を分割して、それぞれの文字列の一番外側の括弧を取り外すとネストが一つ浅いものに帰着できるからネストの深さで帰納法を回すみたいなことを気をつけてやるといいんじゃないか
332:デフォルトの名無しさん
23/06/07 08:00:55.26 nPOLblkw0.net
>>330はChatGPTなのかな? すごいな
>>331 どうもありがとうございます
このコードの場合、再帰時に常に右側に括弧を追加することが if (r < l) return; で
必要十分になることの前提だと思うんですが.... >>330はそのことがうやむやのような
333:デフォルトの名無しさん
23/06/07 08:33:42.08 nPOLblkw0.net
>>328のコードとは別に、
(と)をそれぞれn個使う正当な括弧列をレベルn(L=n)の括弧列と呼んだとき、L=nの括弧列から
L=n+1の括弧列はどう生成されるのかを考えてみたのですが
例えばL=2の()()はL=1の()の右か左に()を追加した、考えてみます
L=3の((()))はL=2の(())に ( + (()) + ) とした、と考えてみます
このように「全体を()で囲むか()を追加するかのルール」でいけるのかと思いきや
L=4の(())(())がL=3のどれからどう作られるのか、がよくわからず
( + ())(() + )ができたらいいのですが ())(() はL=3の正しい括弧列ではない
例えばL=3の (())() に (()) ( + () + ) と、括弧を割り込ませる? なんだかおかしい?
あるいはこれはL=2の(())を二つ並べた、と考えるべき?
要は、正しい括弧の追加操作のみをして再帰的に括弧列を生成することは可能なのか?
あるいは単にすべてのパターンを生成して正当でないのを刈り取ることしかできないのか?
などということが気になったのですが
334:デフォルトの名無しさん
23/06/07 09:49:06.82 Bta2HQ7X0.net
>>333
結論から言うと、それは難しい問題であり、一般的なアプローチでは、「全てのパターンを生成し、
それがバランスの取れた括弧列であるかどうかを判定する」という方法が用いられます。
しかし、バランスの取れた括弧列を生成するための一種の再帰的なパターンは存在します。
それは、大きさnの全てのバランスの取れた括弧列を生成した後で、その各々に対して以下の操作を行うことです：
1. '(' + P + ')' を追加する
2. P + '()' を追加する
3. '()' + P を追加する
ここで P は大きさnの任意のバランスの取れた括弧列です。
この操作を行うと、全ての大きさn+1のバランスの取れた括弧列を生成することができます。
ただし、これは重複する列を生成する可能性があるため、生成された列は一意であることを保証するために
何らかの方法で重複を除去する必要があります。
したがって、厳密には「全てのパターンを生成し、それがバランスの取れた括弧列であるかどうかを判定する」
という方法とは異なりますが、これは一種の再帰的なアプローチと言えます。
しかし、これらのアプローチは計算時間やメモリ使用量の観点から見ると、>>328に示されたDFSを用いたアプローチに比べて
効率的ではないかもしれません。また、DFSを用いたアプローチは明確に「正しい括弧の追加操作のみ」を行っていると言えます。
なぜなら、すべての括弧列を生成する過程で、同時にその列が正しい括弧列であるかどうかをチェックすることが可能だからです。
335:デフォルトの名無しさん
23/06/07 10:10:41.04 WomvMCD50.net
>>333
>>334 は嘘
バランスした括弧列の定義は全体を括弧で囲む操作と括弧列2つの結合で生成される集合だから、その()を追加するっていうのを右か左に追加するって意味だとするとレベル2以上の文字列同士の結合が考慮されていないの
で、(())(())が作れない
中に()を挿入することを許すとすると、今度は全体を括弧で囲む操作はいらなくなる
というのも、どんな空でないバランスした括弧列にも()の部分があるから、それを取り除くことを繰り返すことで空にできるから、逆に空文字列に()を追加していくことで任意のバランスした括弧列が作れるし、バランスした括弧列の任意の箇所に()を挿入した文字列もまたバランスした括弧列になっている
336:デフォルトの名無しさん
23/06/07 11:08:01.09 DYKBdUd80.net
>>332
ご指摘の通り、このコードでは再帰的に右側に括弧を追加しています。具体的には、まず左括弧を追加し、その後で右括弧を追加しています。
この if (r < l) return; の制約は、この追加の順序に基づいています。開始時点では、開き括弧と閉じ括弧の数が等しく（つまり、l == r）、左括弧を先に追加します。そのため、追加の過程では一時的に l が r より小さくなります。しかし、その後すぐに右括弧を追加することでバランスを保ちます。
if (r < l) return; のチェックにより、右括弧が先に追加される（つまり、r < l となる）状況を防いでいます。これは、左括弧を追加した後でのみ右括弧を追加するという、このコードの括弧の追加の順序を反映しています。そのため、この制約が満たされない場合（つまり、右括弧が先に追加される場合）、そのパスは無効となり、すぐに終了します。
したがって、この if (r < l) return; の制約は、このコードの括弧の追加の順序に基づいて、左括弧と右括弧が正しくバランスを保つことを保証しています。
337:デフォルトの名無しさん
23/06/07 14:48:36.26 w+aRYGw/r.net
非負のランダムウォーク書いて+1-1を()に対応させるだけだろ
338:デフォルトの名無しさん
23/06/10 17:29:19.24 0oQUevmP0.net
>>328
閉じ括弧が開き括弧より少なかったら、ダメってことなだけでは。
開き括弧と閉じ括弧の数が同じって条件は最初の呼び出しではlとrが同じでなければならないって制約があると思う
339:デフォルトの名無しさん (ﾜｯﾁｮｲ 89b0-SVCw)
23/06/10 22:46:50.51 sqwX2ns70.net
6完…
途中まではいいペースもFで帰りがけにも頂点集合受け取るの忘れて時間ギリギリに
340:デフォルトの名無しさん
23/06/11 20:43:12.18 Fc1cWZtx0.net
>>338
例えば())(()は閉じ開きの括弧数だけでいうとおkだけど実際にはおkじゃない
では何故これが生成されないか、他の駄目パターンもなぜ生成されないか気になった
というのを既に考察したつもり
341:デフォルトの名無しさん
23/06/11 20:59:44.70 Fc1cWZtx0.net
しかし、解く時間が限られている場合にグダグダ悩んでいる暇はないよなあ
そういう場合パターンを覚えておくしかない?
342:デフォルトの名無しさん (ﾜｯﾁｮｲ 61b0-8SEE)
23/06/17 22:47:22.26 /YYtpwSS0.net
ジャッジが終わらないよ
343:デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM96-/52B)
23/06/17 23:10:07.92 dXHH06bsM.net
unratedおおすぎ
344:デフォルトの名無しさん (ﾜｯﾁｮｲ 92ad-zFGp)
23/06/17 23:16:56.58 re9nMjXH0.net
アーロンジャッジたすけて
345:デフォルトの名無しさん (ﾜｯﾁｮｲ 092d-dYQK)
23/06/18 04:25:23.41 KT9X3u120.net
atcoderがddos受けてるとして、潰して得をするのは誰だ？
346:デフォルトの名無しさん (ｱｳｱｳｳｰ Sacd-c3fv)
23/06/18 11:57:26.20 zhu3s9uha.net
ロシア中国
347:デフォルトの名無しさん (ﾜｯﾁｮｲ a325-p5N0)
23/06/24 17:44:41.70 SdmUsAHw0.net
ガイジのみんなこっちおいで😆
怖がる必要ないよ✌
348:デフォルトの名無しさん (ｵｯﾍﾟｹ Sr81-g5c7)
23/06/24 18:57:52.69 JQRvym1Fr.net
うおおおおおおおお🤓
349:デフォルトの名無しさん (ﾜｯﾁｮｲ a325-p5N0)
23/06/24 19:30:32.53 SdmUsAHw0.net
他のガイジもこっちおいで！
350:デフォルトの名無しさん (ﾜｯﾁｮｲ a3bd-/B6M)
23/06/24 22:23:51.32 +O4dPU7T0.net
攻撃されてね？
351:デフォルトの名無しさん (ﾜｯﾁｮｲ a325-cli0)
23/06/24 22:28:05.07 SdmUsAHw0.net
落ちてる！クソすぎ！！！
352:デフォルトの名無しさん (ﾜｯﾁｮｲ 75b0-GDjS)
23/06/24 22:42:50.37 ZtOuHWP80.net
せっかくG解けたのに1分遅れになってしまった…
353:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa69-Auuh)
23/06/24 22:55:29.87 gDpwuzMxa.net
アンレでしょ、ね？ね？
354:デフォルトの名無しさん (ﾜｯﾁｮｲ 75b0-GDjS)
23/06/24 22:56:49.69 ZtOuHWP80.net
ところでC正解者少なすぎ
355:デフォルトの名無しさん (ﾜｯﾁｮｲ a325-cli0)
23/06/24 23:12:14.22 SdmUsAHw0.net
10:10くらい？から今(10:50)までずっとatcoder開けませんが、同じ人いるかな
なんてツイートしてるひともいるね
356:デフォルトの名無しさん (ﾜｯﾁｮｲ 9dda-0drY)
23/06/25 01:40:55.82 9o2+M89H0.net
このコードがaws環境でsegmentationfaultになる原因わかる人いる？
ちなみにatcoderではこのコードでACを取れたので致命的な間違いがあるわけでは無さそう
int main(){
ll n, q, dp[39][100009], A[100009];
cin >> n >> q;
rep(i, 1, n) {
cin >> A[i];
dp[0][i] = A[i];
}
rep(i, 1, 29){
rep(j, 1, n){
dp[i][j] = dp[i-1][dp[i-1][j]];
}
}
rrep(i, q){
ll x, y;
cin >> x >> y;
ll cur = x;
Rep(j, 29, 0){
if((y & (1 << j)) != 0) cur = dp[j][cur];
}
cout << cur << endl;
}
}
357:デフォルトの名無しさん (ﾜｯﾁｮｲ 9dda-0drY)
23/06/25 01:41:11.75 9o2+M89H0.net
どこかおかしい部分あるかな
358:デフォルトの名無しさん (ﾜｯﾁｮｲ 4bd6-1Bpn)
23/06/25 02:14:14.53 0IEJDuKo0.net
スタックサイズ
359:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa69-Auuh)
23/06/25 02:15:11.19 3TXiYfiya.net
>>356
マルチは市ね
360:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa69-yAbC)
23/06/29 15:31:24.42 wEpX0/Cla.net
Twitterのpaizaの広告とかに必ず現れる
「入力値をチェックしていない」
という返信をつける人は、具体的に何をチェックして、どう処理するの？
361:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa69-yAbC)
23/06/29 15:35:22.33 wEpX0/Cla.net
たとえば、
・Nは偶数
・AとBの合計はN未満
といった制約は、実際のプログラムならチェックして例外をスローする
しかし、
「nが整数値じゃない場合をチェックしていない」
みたいなよくわからない難癖をつける人もいる
整数値じゃなければint型にパースするときに、ほとんどの言語で例外になるからいいのでは
362:デフォルトの名無しさん (ｽﾌﾟﾌﾟ Sd43-2HPs)
23/06/29 15:50:34.59 WjHgY0Cmd.net
>>356
ll で dp[39][100009], A[100009];
何バイトあるん
363:デフォルトの名無しさん (ﾜｯﾁｮｲ 7fb0-+Ydp)
23/07/01 22:45:27.97 rC0kSH/20.net
今回は簡単めでしたね
G解けなかったけど
364:デフォルトの名無しさん (ﾜｯﾁｮｲ e2da-l2Kc)
23/07/01 23:33:06.19 x6PMIr/p0.net
コンテスト初参加
C問題があまりにも酷いと思った
20分くらいかけて、priorityqueue<pair<double、int>> に値をプッシュする時にpairのsecondの方にマイナスを付ければ良いことに気がついたもののWA
何を試してもWAで、doubleの精度に問題があるんじゃないかと思って、ネット検索をしたら、long doubleという型があることを知り、試してみたら無事AC
Ｃ問題で時間とメンタルを削られてD問題は諦めた
初参加とはいえ茶パフォはあまりに脳障害すぎるだろ
365:デフォルトの名無しさん (ﾜｯﾁｮｲ e2da-l2Kc)
23/07/01 23:39:31.52 x6PMIr/p0.net
今回のＣ問題でpriorityqueueを使ったんだけど、priorityqueue<pair<double、int>> に値をプッシュする時、pairのsecondの方に-をつけて取り出す順番を工夫するのって典型？
ちょっとした閃きだけど思いついた時は俺ちょっと頭いいんじゃねって思っちゃった
その後ものの見事に脳障害っぷりを晒してしまったけど
366:デフォルトの名無しさん (ﾜｯﾁｮｲ a225-+ypZ)
23/07/01 23:43:47.83 L7MIkgdg0.net
その発想は天才だよ、才能あるね
367:デフォルトの名無しさん (ｻｻｸｯﾃﾛﾗ Sp5f-RHsg)
23/07/01 23:50:30.60 wjWc9sXDp.net
マジレスすると符号付けて逆順にすることで実装をシンプルにするのはかなりの典型です
368:デフォルトの名無しさん (ｱｳｱｳｳｰ Sabb-zrhl)
23/07/01 23:53:37.30 6JFt9TARa.net
むしろそのマイナスにするのが主題と言ってもいいくらい
369:デフォルトの名無しさん (ｱｳｱｳｳｰ Sabb-DX8j)
23/07/01 23:57:08.30 CM44ThHXa.net
C++ってFraction無いんだっけ？
まあ無くても自分で通分すれば済む話だが
370:デフォルトの名無しさん (ﾜｯﾁｮｲ e2da-l2Kc)
23/07/02 00:35:29.46 sYDH7cmq0.net
なるほど、ただの典型だったか…
ただ、その典型を自分で思いついたのはちょっと嬉しい
371:デフォルトの名無しさん (ﾜｯﾁｮｲ e2da-l2Kc)
23/07/02 00:39:10.97 sYDH7cmq0.net
先程 D問題をACしてきた
結構簡単だし、C問題を普通に解けていたら多分四完出来た
今回のC問題みたいに本質的じゃない部分(long doubleという型を知っているかどうかみたいな)を問うのは本当にやめた方が良いと思う 問題の質がシンプルに低い
372:デフォルトの名無しさん (ｱｳｱｳｳｰ Sabb-zrhl)
23/07/02 01:16:07.96 3YsXAzA4a.net
小数の精度についての理解を問うなかなかの良問だと思ったけどね
373:デフォルトの名無しさん (ﾜｯﾁｮｲ cb5f-5Jqn)
23/07/02 01:33:02.66 K/v1SCuX0.net
浮動小数点数での出力を求められていない場合に浮動小数点数を使うのはアンチパターン
分数を管理する構造体を持ち出したり適切な比較関数を書いたりして対処するべき
374:デフォルトの名無しさん (ｻｻｸｯﾃﾛﾗ Sp5f-RHsg)
23/07/02 03:53:32.35 FFIcTLPjp.net
前回のC問題はただめちゃくちゃ面倒なだけでアレだったけど今週のC問題は何も悪くないし非本質的でもないだろ
浮動小数点数は誤差に気をつけるべきなんて競プロでは身につけておくべき典型知識だし競プロ外でも浮動小数点数の仕組みは知っておくべきだしm
375:デフォルトの名無しさん (ｻｻｸｯﾃﾛﾗ Sp5f-RHsg)
23/07/02 03:56:07.16 FFIcTLPjp.net
強いて言うならlong double型で無理矢理通すような解答を弾けるような設定にして比較関数やら有理数型を表す構造体やらの整数しか登場しなくて誤差の心配がない解答のみが通るようにしてほしかったがCでそれは酷かもしれない
376:デフォルトの名無しさん (ﾜｯﾁｮｲ d701-OYD+)
23/07/02 04:23:31.59 vN/hop9Q0.net
long double使わなくても解けるし、それ知らないと解けないと言ってる人のレベルが低すぎるだけ
377:デフォルトの名無しさん (ﾜｯﾁｮｲ 12bd-+Mc8)
23/07/02 08:45:23.44 TDPjDhzP0.net
E問題の意味が分からないんだが。
俺の考えたアルゴリズムは、
Mが0,1,2になる数、
Eが0,1,2になる数、
Xが0,1,2になる数、
を全て数えて
各組み合わせ27通りについて、
mex×場合分けの数
っていうやり方をしたんだがサンプル3の問題からしてそもそも合わない
日本語下手で説明難しいからコードを見てほしい。
URLﾘﾝｸ(atcoder.jp)
このやり方がなぜいけないのかわからない
コンテスト中「E問題いけるやん！」と思ってただけに絶望だったわ、はぁ。。
378:デフォルトの名無しさん (ﾜｯﾁｮｲ 12bd-+Mc8)
23/07/02 08:51:37.04 TDPjDhzP0.net
関係ないけど、dictのkeyで回せば
if k not in dic["X"]:
continue
みたいなのいらなかったな
379:デフォルトの名無しさん (ﾜｯﾁｮｲ 6710-GKTn)
23/07/02 08:52:36.78 IX/DQMpQ0.net
i<j<k
380:デフォルトの名無しさん (ﾜｯﾁｮｲ 12bd-+Mc8)
23/07/02 08:55:34.57 TDPjDhzP0.net
>>379
ないてもいい？
381:デフォルトの名無しさん (ﾜｯﾁｮｲ 12bd-+Mc8)
23/07/02 09:02:55.87 TDPjDhzP0.net
雑なやり方だけど、
「E」に来た時点で、それより前のMの各012の数と
それより後のXの「012」の数を保持しておけば簡単に解けたわけか
382:デフォルトの名無しさん (ﾜｯﾁｮｲ ceca-Sjvf)
23/07/02 10:28:08.37 ZqX35jN50.net
Cみたいなのが普通に小数にしてソートして解けないとか、現実的に不要な精度を求めてるからじゃ。工夫して分数を比較とか一般的なプログラミングではあり得ない。
383:デフォルトの名無しさん (ﾜｯﾁｮｲ d701-runv)
23/07/02 11:00:12.04 zHWl+4BQ0.net
一切の誤差が許容できないケースは業プロでもあり得ると思う
384:デフォルトの名無しさん (ﾜｯﾁｮｲ e2ad-P14V)
23/07/02 11:08:00.56 KeYtCxoR0.net
COBOL使われてそう
385:デフォルトの名無しさん (ﾜｯﾁｮｲ 6743-usyi)
23/07/02 11:14:00.32 w7ISOQF/0.net
普通に業プロでも浮動小数点の誤差でやらかすのあるあるだけどな
とくに一致判定しだすと大抵はテストを通って後でトラブる
386:デフォルトの名無しさん (ﾜｯﾁｮｲ a225-+ypZ)
23/07/02 11:34:46.41 13GYnxJn0.net
むしろ業プロはバグだらけで運用でカバーするのが当たり前だか？
バグなくなるまでQAとデバッグしてたらいつまでたっても終わらない
387:デフォルトの名無しさん (ﾜｯﾁｮｲ a225-+ypZ)
23/07/02 11:37:01.69 13GYnxJn0.net
当たり前だが？
388:デフォルトの名無しさん (ｱｳｱｳｳｰ Sabb-DX8j)
23/07/02 11:40:04.07 uPRSXMfXa.net
>>382
あり得ないのは誤差があることを知りながらdoubleを使うことだぞ
誤差が許容できないとわかってて整数で誤差のない計算ができることもわかってるんだから整数で計算するべき
わかってないお前が無能というだけ
389:デフォルトの名無しさん (ﾜｯﾁｮｲ ceca-Sjvf)
23/07/02 11:40:34.10 ZqX35jN50.net
しかし、スポーツとかゲームの勝率を管理するシステムがあったとして、
小数点以下6桁以上の精度のために内部的に分子分母を整数で別々に保存してるとは思えないのだがｗｗｗ
390:デフォルトの名無しさん (ｱｳｱｳｳｰ Sabb-DX8j)
23/07/02 11:56:01.97 uPRSXMfXa.net
思えよw
勝ち数と試合数を保存してるに決まってるだろw
391:デフォルトの名無しさん (ｱｳｱｳｳｰ Sabb-DX8j)
23/07/02 11:57:10.10 uPRSXMfXa.net
逆に勝率だけ保存してその後の試合の結果どうすんの？w
過去の勝率からどうやって現在の勝率を計算するんだよw
392:デフォルトの名無しさん (ﾜｯﾁｮｲ ceca-Sjvf)
23/07/02 12:04:01.86 ZqX35jN50.net
それは当然してるけど、orderbyで引き出すときに、勝率をatcoder流でソートするとか多分ないｗ
ワテが知らないだけで分数流ベイズ統計学とかあるのかｗ
393:デフォルトの名無しさん (ｱｳｱｳｳｰ Sabb-DX8j)
23/07/02 12:04:59.74 762mJONda.net
お前の我流が間違ってるだけだぞ
394:デフォルトの名無しさん (ｱｳｱｳｳｰ Sabb-zrhl)
23/07/02 12:50:39.91 3YsXAzA4a.net
普通に業務でもあり得るんだよなぁ
395:デフォルトの名無しさん (ｽﾌﾟｯｯ Sd7a-Tn1R)
23/07/02 15:00:00.77 Kiw2FHRVd.net
>>391
n 試合後に
現在の勝率 R(n)「だけ」が判っている場合
n+1 試合後の勝率 R(n+1) は
n+1 試合目の勝ち負けが r (勝ちなら 1 負けなら 0) とすると
R(n+1) = (R(n) x n + r) / (n + 1)
で良いんじゃね
もちろん誤差は蓄積するよ
こんなこと一々描くのも恥ずかしいレベル
396:デフォルトの名無しさん (ｱｳｱｳｳｰ Sabb-DX8j)
23/07/02 15:20:20.64 762mJONda.net
>>395
そのnは試合数じゃないのかw
こんなこといちいち書かせるなよw
397:デフォルトの名無しさん (ﾜｯﾁｮｲ d701-+Mc8)
23/07/02 15:24:37.03 vW9xhJCj0.net
もう少し比較条件が複雑化されて
operator<なりstd::sortに渡すラムダ式をちゃんと定義しないと駄目なら一転して教育的とかいいそう
398:デフォルトの名無しさん (ﾜｯﾁｮｲ 23da-l2Kc)
23/07/02 23:05:02.47 CGuiBJy50.net
ARCゼロ完 地頭悪すぎる ガチで死にたい
399:デフォルトの名無しさん (ﾜｯﾁｮｲ 23da-l2Kc)
23/07/02 23:07:06.37 CGuiBJy50.net
昨日はABC三完
今日はARCゼロ完
A問題は解けそうだったけど結局最後までAC出来ず
頭が悪すぎる
IQ1しか無いよ俺は
400:デフォルトの名無しさん (ﾜｯﾁｮｲ 23da-l2Kc)
23/07/02 23:13:24.16 CGuiBJy50.net
数理能力皆無の知的障害者です
401:デフォルトの名無しさん (ﾜｯﾁｮｲ 230d-+Mc8)
23/07/03 01:30:24.77 OPBRIWzz0.net
・解説開くとTwitterに飛ぶやつあるが、アカウント持ってないから見れない。
・今日のARC出題者はPCT。何千人の大人が高校生の手の上で転がされていると思うと笑える。
402:デフォルトの名無しさん (ｱｳｱｳｳｰ Sabb-DX8j)
23/07/03 09:36:39.54 NXhRhmBta.net
大人は経験を積んでるから対応力があるわけで素の能力的には筋力でも記憶力でも計算力でも高校生くらいがピークだろ
ずっと数学に取り組んできた高校生が年食ったにわかより数学力高いのは何もおかしくない