競技プログラミング総合スレ 66 (478レス)
上下前次1-新
317: (ワッチョイ d3b0-SwK+) 2023/05/20(土)22:48 ID:IbXAPdJ/0(1) AAS
6完…
今回は7完したかった…
318: (アウアウウー Sa2f-o1RM) 2023/05/20(土)23:12 ID:+EVZ8y+Ka(1) AAS
配点割とその通りだったな
319: (ワッチョイ 57db-3XON) 2023/05/22(月)00:56 ID:mBh1GEMi0(1) AAS
パフォーマンスがinfinityになった回って61以前にあった?
320: (ワッチョイ abb0-IOpb) 2023/05/27(土)22:44 ID:DM47Hxe/0(1/2) AAS
難しすぎるよ
321: (ワッチョイ abb0-IOpb) 2023/05/27(土)23:33 ID:DM47Hxe/0(2/2) AAS
コドフォもないし
322: (ワッチョイ 99b0-AV1S) 2023/06/03(土)23:01 ID:i1emxrQn0(1) AAS
6完
mod入力ミスってたのがアホすぎる
323: (ワッチョイ c6bd-2a7c) 2023/06/04(日)16:31 ID:VEMViUBd0(1) AAS
やっとE問題解けるようになってきた
E問題って一個一個の実行時間が長いんだな
324: (ワッチョイ c2bd-2a7c) 2023/06/04(日)17:44 ID:0q9gSB9x0(1) AAS
競プロ有段者(強い人)に質問
Atcoderで一段階上に行くためには解説を何も見ずとも解けるレベルの一段階上を同じように解けるレベルになるまでその問題を解説だけ見て実装は全て自分で、っていう感じでひたすら練習していくっていうやり方は有効?
自分の場合はD問題は9割ガタ解けて、Eがまだ実戦では歯が立たないレベル
325: (ワッチョイ 45a4-Ya2I) 2023/06/04(日)17:53 ID:AGQzq0Q+0(1) AAS
うん
326: (ワッチョイ 02bd-2a7c) 2023/06/04(日)20:29 ID:z/tZxQvT0(1) AAS
E問題思ったより簡単だな
食わず嫌いしてた
327(3): (ワッチョイ 469a-dFNS) 2023/06/06(火)11:53 ID:MhCqkbZk0(1) AAS
某所で「左右がバランスした括弧の列を生成する」という問題があり、解答が
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) {
省15
328: (アウアウウー Sac5-l0ym) 2023/06/06(火)12:29 ID:GQVo4dJ/a(1) AAS
しょーもない処理を複雑に描いてるだけのクソプログラムやな
この関数は最初の呼び出しでlとrが同じ数字なるよう入れるのが前提で
r<lの条件は例外処理みたいなもんやろ
329(1): (ワッチョイ 45a4-4Uvu) 2023/06/06(火)12:35 ID:UncR9VmG0(1) AAS
このコードの一部 `if (r < l) return;` について説明します。
ここで `l` と `r` はそれぞれまだ追加できる '(' の数と ')' の数を表しています。なので、このチェック `if (r < l) return;` は、')' の数が '(' の数より少なくなる場合、すなわち、開き括弧より閉じ括弧が少なくなる場合を防いでいます。
正しい括弧の列を生成するためには、2つの重要なルールを守らなければなりません:
1. 左括弧と右括弧の数が等しいこと
2. 任意の時点で、右括弧の数が左括弧の数を超えないこと
1つ目のルールは、左括弧と右括弧を同数だけ生成すれば満たされます。しかし、2つ目のルールはもう少し注意が必要です。それは、どの時点でも、閉じ括弧の数が開き括弧の数を超えてはならないからです。これを超えてしまうと、括弧の列が無効になってしまいます。
省2
330(1): (JP 0H56-RtFh) 2023/06/06(火)12:49 ID:FRsr3KcUH(1) AAS
(を+1)を-1と対応させて累積和が常に非負っていうのがバランスしていることの必要十分条件であることを認めれば if(r < l)return; がそれの言い換えなことは明らか
証明したければ累積和が0になるところで文字列を分割して、それぞれの文字列の一番外側の括弧を取り外すとネストが一つ浅いものに帰着できるからネストの深さで帰納法を回すみたいなことを気をつけてやるといいんじゃないか
331(1): (ワッチョイ 469a-dFNS) 2023/06/07(水)08:00 ID:nPOLblkw0(1/2) AAS
>>329はChatGPTなのかな? すごいな
>>330 どうもありがとうございます
このコードの場合、再帰時に常に右側に括弧を追加することが if (r < l) return; で
必要十分になることの前提だと思うんですが.... >>329はそのことがうやむやのような
332(2): (ワッチョイ 469a-dFNS) 2023/06/07(水)08:33 ID:nPOLblkw0(2/2) AAS
>>327のコードとは別に、
(と)をそれぞれn個使う正当な括弧列をレベルn(L=n)の括弧列と呼んだとき、L=nの括弧列から
L=n+1の括弧列はどう生成されるのかを考えてみたのですが
例えばL=2の()()はL=1の()の右か左に()を追加した、考えてみます
L=3の((()))はL=2の(())に ( + (()) + ) とした、と考えてみます
このように「全体を()で囲むか()を追加するかのルール」でいけるのかと思いきや
L=4の(())(())がL=3のどれからどう作られるのか、がよくわからず
省6
333(1): (ワッチョイ 012d-UlWg) 2023/06/07(水)09:49 ID:Bta2HQ7X0(1) AAS
>>332
結論から言うと、それは難しい問題であり、一般的なアプローチでは、「全てのパターンを生成し、
それがバランスの取れた括弧列であるかどうかを判定する」という方法が用いられます。
しかし、バランスの取れた括弧列を生成するための一種の再帰的なパターンは存在します。
それは、大きさnの全てのバランスの取れた括弧列を生成した後で、その各々に対して以下の操作を行うことです:
1. '(' + P + ')' を追加する
2. P + '()' を追加する
省10
334: (ワッチョイ 7d5f-RtFh) 2023/06/07(水)10:10 ID:WomvMCD50(1) AAS
>>332
>>333 は嘘
バランスした括弧列の定義は全体を括弧で囲む操作と括弧列2つの結合で生成される集合だから、その()を追加するっていうのを右か左に追加するって意味だとするとレベル2以上の文字列同士の結合が考慮されていないの
で、(())(())が作れない
中に()を挿入することを許すとすると、今度は全体を括弧で囲む操作はいらなくなる
というのも、どんな空でないバランスした括弧列にも()の部分があるから、それを取り除くことを繰り返すことで空にできるから、逆に空文字列に()を追加していくことで任意のバランスした括弧列が作れるし、バランスした括弧列の任意の箇所に()を挿入した文字列もまたバランスした括弧列になっている
335: (ワッチョイ a905-4Uvu) 2023/06/07(水)11:08 ID:DYKBdUd80(1) AAS
>>331
ご指摘の通り、このコードでは再帰的に右側に括弧を追加しています。具体的には、まず左括弧を追加し、その後で右括弧を追加しています。
この if (r < l) return; の制約は、この追加の順序に基づいています。開始時点では、開き括弧と閉じ括弧の数が等しく(つまり、l == r)、左括弧を先に追加します。そのため、追加の過程では一時的に l が r より小さくなります。しかし、その後すぐに右括弧を追加することでバランスを保ちます。
if (r < l) return; のチェックにより、右括弧が先に追加される(つまり、r < l となる)状況を防いでいます。これは、左括弧を追加した後でのみ右括弧を追加するという、このコードの括弧の追加の順序を反映しています。そのため、この制約が満たされない場合(つまり、右括弧が先に追加される場合)、そのパスは無効となり、すぐに終了します。
したがって、この if (r < l) return; の制約は、このコードの括弧の追加の順序に基づいて、左括弧と右括弧が正しくバランスを保つことを保証しています。
336: (オッペケ Sr91-BHVC) 2023/06/07(水)14:48 ID:w+aRYGw/r(1) AAS
非負のランダムウォーク書いて+1-1を()に対応させるだけだろ
337(1): (ワッチョイ 797f-Ydfh) 2023/06/10(土)17:29 ID:0oQUevmP0(1) AAS
>>327
閉じ括弧が開き括弧より少なかったら、ダメってことなだけでは。
開き括弧と閉じ括弧の数が同じって条件は最初の呼び出しではlとrが同じでなければならないって制約があると思う
338: (ワッチョイ 89b0-SVCw) 2023/06/10(土)22:46 ID:sqwX2ns70(1) AAS
6完…
途中まではいいペースもFで帰りがけにも頂点集合受け取るの忘れて時間ギリギリに
339: (ワッチョイ 7b9a-D1r1) 2023/06/11(日)20:43 ID:Fc1cWZtx0(1/2) AAS
>>337
例えば())(()は閉じ開きの括弧数だけでいうとおkだけど実際にはおkじゃない
では何故これが生成されないか、他の駄目パターンもなぜ生成されないか気になった
というのを既に考察したつもり
340: (ワッチョイ 7b9a-D1r1) 2023/06/11(日)20:59 ID:Fc1cWZtx0(2/2) AAS
しかし、解く時間が限られている場合にグダグダ悩んでいる暇はないよなあ
そういう場合パターンを覚えておくしかない?
341: (ワッチョイ 61b0-8SEE) 2023/06/17(土)22:47 ID:/YYtpwSS0(1) AAS
ジャッジが終わらないよ
342: (テテンテンテン MM96-/52B) 2023/06/17(土)23:10 ID:dXHH06bsM(1) AAS
unratedおおすぎ
343: (ワッチョイ 92ad-zFGp) 2023/06/17(土)23:16 ID:re9nMjXH0(1) AAS
アーロンジャッジたすけて
344: (ワッチョイ 092d-dYQK) 2023/06/18(日)04:25 ID:KT9X3u120(1) AAS
atcoderがddos受けてるとして、潰して得をするのは誰だ?
345: (アウアウウー Sacd-c3fv) 2023/06/18(日)11:57 ID:zhu3s9uha(1) AAS
ロシア中国
346: (ワッチョイ a325-p5N0) 2023/06/24(土)17:44 ID:SdmUsAHw0(1/4) AAS
ガイジのみんなこっちおいで😆
怖がる必要ないよ✌
347: (オッペケ Sr81-g5c7) 2023/06/24(土)18:57 ID:JQRvym1Fr(1) AAS
うおおおおおおおお🤓
348: (ワッチョイ a325-p5N0) 2023/06/24(土)19:30 ID:SdmUsAHw0(2/4) AAS
他のガイジもこっちおいで!
349: (ワッチョイ a3bd-/B6M) 2023/06/24(土)22:23 ID:+O4dPU7T0(1) AAS
攻撃されてね?
350: (ワッチョイ a325-cli0) 2023/06/24(土)22:28 ID:SdmUsAHw0(3/4) AAS
落ちてる!クソすぎ!!!
351: (ワッチョイ 75b0-GDjS) 2023/06/24(土)22:42 ID:ZtOuHWP80(1/2) AAS
せっかくG解けたのに1分遅れになってしまった…
352: (アウアウウー Sa69-Auuh) 2023/06/24(土)22:55 ID:gDpwuzMxa(1) AAS
アンレでしょ、ね?ね?
353: (ワッチョイ 75b0-GDjS) 2023/06/24(土)22:56 ID:ZtOuHWP80(2/2) AAS
ところでC正解者少なすぎ
354: (ワッチョイ a325-cli0) 2023/06/24(土)23:12 ID:SdmUsAHw0(4/4) AAS
10:10くらい?から今(10:50)までずっとatcoder開けませんが、同じ人いるかな
なんてツイートしてるひともいるね
355(2): (ワッチョイ 9dda-0drY) 2023/06/25(日)01:40 ID:9o2+M89H0(1/2) AAS
このコードがaws環境でsegmentationfaultになる原因わかる人いる?
ちなみにatcoderではこのコードでACを取れたので致命的な間違いがあるわけでは無さそう
int main(){
ll n, q, dp[39][100009], A[100009];
cin >> n >> q;
rep(i, 1, n) {
cin >> A[i];
省17
356: (ワッチョイ 9dda-0drY) 2023/06/25(日)01:41 ID:9o2+M89H0(2/2) AAS
どこかおかしい部分あるかな
357: (ワッチョイ 4bd6-1Bpn) 2023/06/25(日)02:14 ID:0IEJDuKo0(1) AAS
スタックサイズ
358: (アウアウウー Sa69-Auuh) 2023/06/25(日)02:15 ID:3TXiYfiya(1) AAS
>>355
マルチは市ね
359: (アウアウウー Sa69-yAbC) 2023/06/29(木)15:31 ID:wEpX0/Cla(1/2) AAS
Twitterのpaizaの広告とかに必ず現れる
「入力値をチェックしていない」
という返信をつける人は、具体的に何をチェックして、どう処理するの?
360: (アウアウウー Sa69-yAbC) 2023/06/29(木)15:35 ID:wEpX0/Cla(2/2) AAS
たとえば、
・Nは偶数
・AとBの合計はN未満
といった制約は、実際のプログラムならチェックして例外をスローする
しかし、
「nが整数値じゃない場合をチェックしていない」
みたいなよくわからない難癖をつける人もいる
省1
361: (スププ Sd43-2HPs) 2023/06/29(木)15:50 ID:WjHgY0Cmd(1) AAS
>>355
ll で dp[39][100009], A[100009];
何バイトあるん
362: (ワッチョイ 7fb0-+Ydp) 2023/07/01(土)22:45 ID:rC0kSH/20(1) AAS
今回は簡単めでしたね
G解けなかったけど
363: (ワッチョイ e2da-l2Kc) 2023/07/01(土)23:33 ID:x6PMIr/p0(1/2) AAS
コンテスト初参加
C問題があまりにも酷いと思った
20分くらいかけて、priorityqueue<pair<double、int>> に値をプッシュする時にpairのsecondの方にマイナスを付ければ良いことに気がついたもののWA
何を試してもWAで、doubleの精度に問題があるんじゃないかと思って、ネット検索をしたら、long doubleという型があることを知り、試してみたら無事AC
C問題で時間とメンタルを削られてD問題は諦めた
初参加とはいえ茶パフォはあまりに脳障害すぎるだろ
364: (ワッチョイ e2da-l2Kc) 2023/07/01(土)23:39 ID:x6PMIr/p0(2/2) AAS
今回のC問題でpriorityqueueを使ったんだけど、priorityqueue<pair<double、int>> に値をプッシュする時、pairのsecondの方に-をつけて取り出す順番を工夫するのって典型?
ちょっとした閃きだけど思いついた時は俺ちょっと頭いいんじゃねって思っちゃった
その後ものの見事に脳障害っぷりを晒してしまったけど
365: (ワッチョイ a225-+ypZ) 2023/07/01(土)23:43 ID:L7MIkgdg0(1) AAS
その発想は天才だよ、才能あるね
366: (ササクッテロラ Sp5f-RHsg) 2023/07/01(土)23:50 ID:wjWc9sXDp(1) AAS
マジレスすると符号付けて逆順にすることで実装をシンプルにするのはかなりの典型です
367: (アウアウウー Sabb-zrhl) 2023/07/01(土)23:53 ID:6JFt9TARa(1) AAS
むしろそのマイナスにするのが主題と言ってもいいくらい
368: (アウアウウー Sabb-DX8j) 2023/07/01(土)23:57 ID:CM44ThHXa(1) AAS
C++ってFraction無いんだっけ?
まあ無くても自分で通分すれば済む話だが
369: (ワッチョイ e2da-l2Kc) 2023/07/02(日)00:35 ID:sYDH7cmq0(1/2) AAS
なるほど、ただの典型だったか…
ただ、その典型を自分で思いついたのはちょっと嬉しい
370: (ワッチョイ e2da-l2Kc) 2023/07/02(日)00:39 ID:sYDH7cmq0(2/2) AAS
先程 D問題をACしてきた
結構簡単だし、C問題を普通に解けていたら多分四完出来た
今回のC問題みたいに本質的じゃない部分(long doubleという型を知っているかどうかみたいな)を問うのは本当にやめた方が良いと思う 問題の質がシンプルに低い
371: (アウアウウー Sabb-zrhl) 2023/07/02(日)01:16 ID:3YsXAzA4a(1/2) AAS
小数の精度についての理解を問うなかなかの良問だと思ったけどね
372: (ワッチョイ cb5f-5Jqn) 2023/07/02(日)01:33 ID:K/v1SCuX0(1) AAS
浮動小数点数での出力を求められていない場合に浮動小数点数を使うのはアンチパターン
分数を管理する構造体を持ち出したり適切な比較関数を書いたりして対処するべき
373: (ササクッテロラ Sp5f-RHsg) 2023/07/02(日)03:53 ID:FFIcTLPjp(1/2) AAS
前回のC問題はただめちゃくちゃ面倒なだけでアレだったけど今週のC問題は何も悪くないし非本質的でもないだろ
浮動小数点数は誤差に気をつけるべきなんて競プロでは身につけておくべき典型知識だし競プロ外でも浮動小数点数の仕組みは知っておくべきだしm
374: (ササクッテロラ Sp5f-RHsg) 2023/07/02(日)03:56 ID:FFIcTLPjp(2/2) AAS
強いて言うならlong double型で無理矢理通すような解答を弾けるような設定にして比較関数やら有理数型を表す構造体やらの整数しか登場しなくて誤差の心配がない解答のみが通るようにしてほしかったがCでそれは酷かもしれない
375: (ワッチョイ d701-OYD+) 2023/07/02(日)04:23 ID:vN/hop9Q0(1) AAS
long double使わなくても解けるし、それ知らないと解けないと言ってる人のレベルが低すぎるだけ
376: (ワッチョイ 12bd-+Mc8) 2023/07/02(日)08:45 ID:TDPjDhzP0(1/4) AAS
E問題の意味が分からないんだが。
俺の考えたアルゴリズムは、
Mが0,1,2になる数、
Eが0,1,2になる数、
Xが0,1,2になる数、
を全て数えて
各組み合わせ27通りについて、
省6
377: (ワッチョイ 12bd-+Mc8) 2023/07/02(日)08:51 ID:TDPjDhzP0(2/4) AAS
関係ないけど、dictのkeyで回せば
if k not in dic["X"]:
continue
みたいなのいらなかったな
378(1): (ワッチョイ 6710-GKTn) 2023/07/02(日)08:52 ID:IX/DQMpQ0(1) AAS
i<j<k
379: (ワッチョイ 12bd-+Mc8) 2023/07/02(日)08:55 ID:TDPjDhzP0(3/4) AAS
>>378
ないてもいい?
380: (ワッチョイ 12bd-+Mc8) 2023/07/02(日)09:02 ID:TDPjDhzP0(4/4) AAS
雑なやり方だけど、
「E」に来た時点で、それより前のMの各012の数と
それより後のXの「012」の数を保持しておけば簡単に解けたわけか
381(1): (ワッチョイ ceca-Sjvf) 2023/07/02(日)10:28 ID:ZqX35jN50(1/3) AAS
Cみたいなのが普通に小数にしてソートして解けないとか、現実的に不要な精度を求めてるからじゃ。工夫して分数を比較とか一般的なプログラミングではあり得ない。
382: (ワッチョイ d701-runv) 2023/07/02(日)11:00 ID:zHWl+4BQ0(1) AAS
一切の誤差が許容できないケースは業プロでもあり得ると思う
383: (ワッチョイ e2ad-P14V) 2023/07/02(日)11:08 ID:KeYtCxoR0(1) AAS
COBOL使われてそう
384: (ワッチョイ 6743-usyi) 2023/07/02(日)11:14 ID:w7ISOQF/0(1) AAS
普通に業プロでも浮動小数点の誤差でやらかすのあるあるだけどな
とくに一致判定しだすと大抵はテストを通って後でトラブる
385: (ワッチョイ a225-+ypZ) 2023/07/02(日)11:34 ID:13GYnxJn0(1/2) AAS
むしろ業プロはバグだらけで運用でカバーするのが当たり前だか?
バグなくなるまでQAとデバッグしてたらいつまでたっても終わらない
386: (ワッチョイ a225-+ypZ) 2023/07/02(日)11:37 ID:13GYnxJn0(2/2) AAS
当たり前だが?
387: (アウアウウー Sabb-DX8j) 2023/07/02(日)11:40 ID:uPRSXMfXa(1/3) AAS
>>381
あり得ないのは誤差があることを知りながらdoubleを使うことだぞ
誤差が許容できないとわかってて整数で誤差のない計算ができることもわかってるんだから整数で計算するべき
わかってないお前が無能というだけ
388: (ワッチョイ ceca-Sjvf) 2023/07/02(日)11:40 ID:ZqX35jN50(2/3) AAS
しかし、スポーツとかゲームの勝率を管理するシステムがあったとして、
小数点以下6桁以上の精度のために内部的に分子分母を整数で別々に保存してるとは思えないのだがwww
389: (アウアウウー Sabb-DX8j) 2023/07/02(日)11:56 ID:uPRSXMfXa(2/3) AAS
思えよw
勝ち数と試合数を保存してるに決まってるだろw
390(1): (アウアウウー Sabb-DX8j) 2023/07/02(日)11:57 ID:uPRSXMfXa(3/3) AAS
逆に勝率だけ保存してその後の試合の結果どうすんの?w
過去の勝率からどうやって現在の勝率を計算するんだよw
391: (ワッチョイ ceca-Sjvf) 2023/07/02(日)12:04 ID:ZqX35jN50(3/3) AAS
それは当然してるけど、orderbyで引き出すときに、勝率をatcoder流でソートするとか多分ないw
ワテが知らないだけで分数流ベイズ統計学とかあるのかw
392: (アウアウウー Sabb-DX8j) 2023/07/02(日)12:04 ID:762mJONda(1/2) AAS
お前の我流が間違ってるだけだぞ
393: (アウアウウー Sabb-zrhl) 2023/07/02(日)12:50 ID:3YsXAzA4a(2/2) AAS
普通に業務でもあり得るんだよなぁ
394(1): (スプッッ Sd7a-Tn1R) 2023/07/02(日)15:00 ID:Kiw2FHRVd(1) AAS
>>390
n 試合後に
現在の勝率 R(n)「だけ」が判っている場合
n+1 試合後の勝率 R(n+1) は
n+1 試合目の勝ち負けが r (勝ちなら 1 負けなら 0) とすると
R(n+1) = (R(n) x n + r) / (n + 1)
で良いんじゃね
省2
395: (アウアウウー Sabb-DX8j) 2023/07/02(日)15:20 ID:762mJONda(2/2) AAS
>>394
そのnは試合数じゃないのかw
こんなこといちいち書かせるなよw
396: (ワッチョイ d701-+Mc8) 2023/07/02(日)15:24 ID:vW9xhJCj0(1) AAS
もう少し比較条件が複雑化されて
operator<なりstd::sortに渡すラムダ式をちゃんと定義しないと駄目なら一転して教育的とかいいそう
397: (ワッチョイ 23da-l2Kc) 2023/07/02(日)23:05 ID:CGuiBJy50(1/3) AAS
ARCゼロ完 地頭悪すぎる ガチで死にたい
上下前次1-新書関写板覧索設栞歴
あと 81 レスあります
スレ情報 赤レス抽出 画像レス抽出 歴の未読スレ AAサムネイル
ぬこの手 ぬこTOP 0.021s