競技プログラミング総合スレ 66 (478ﾚｽ)
競技プログラミング総合スレ 66 http://mevius.5ch.net/test/read.cgi/tech/1679465982/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
301: デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf) [] 2023/05/03(水) 19:48:56.95 ID:aKUbjdKi0 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 です。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/301
302: デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf) [] 2023/05/03(水) 19:49:22.48 ID:aKUbjdKi0 >>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 です。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/302
303: デフォルトの名無しさん (ｵｯﾍﾟｹ Sr8b-siYD) [sage] 2023/05/03(水) 21:06:39.53 ID:MtXxv88er うんち！w http://mevius.5ch.net/test/read.cgi/tech/1679465982/303
304: デフォルトの名無しさん (ﾜｯﾁｮｲ 5701-MUOW) [sage] 2023/05/04(木) 00:35:43.31 ID:FFDpqzE90 併合していって無駄のない表現にできればいける？ http://mevius.5ch.net/test/read.cgi/tech/1679465982/304
305: デフォルトの名無しさん (ﾜｯﾁｮｲ 375f-k3Rv) [sage] 2023/05/04(木) 01:33:09.74 ID:Pbw0n2Gt0 そんなことよりn乗で増えていくのを抑えないと無理なんでは http://mevius.5ch.net/test/read.cgi/tech/1679465982/305
306: デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf) [] 2023/05/04(木) 02:26:58.39 ID:iR6EpWdh0 2次元限定、座標は有理数限定にしたら、競プロの問題として成立しますか？ http://mevius.5ch.net/test/read.cgi/tech/1679465982/306
307: デフォルトの名無しさん (ﾜｯﾁｮｲ 572d-wHlW) [sage] 2023/05/04(木) 04:20:04.21 ID:W+5O3yqN0 >>306 yukicoderで出題してみれば？ http://mevius.5ch.net/test/read.cgi/tech/1679465982/307
308: デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf) [] 2023/05/05(金) 10:56:46.77 ID:xYbtWehf0 >>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 の部分集合の中で最大の直方体を求めよ。 この効率的な解法はありますか？ http://mevius
.5ch.net/test/read.cgi/tech/1679465982/308
309: デフォルトの名無しさん (ﾜｯﾁｮｲ bfd7-E7B+) [sage] 2023/05/05(金) 13:25:13.43 ID:CuujTRH+0 あるよ http://mevius.5ch.net/test/read.cgi/tech/1679465982/309
310: デフォルトの名無しさん (ﾌﾞｰｲﾓ MMab-8WUk) [sage] 2023/05/05(金) 18:31:53.93 ID:zrOWQZW0M 自分で解けてなければ自作の問題とは言わん http://mevius.5ch.net/test/read.cgi/tech/1679465982/310
311: デフォルトの名無しさん (ﾜｯﾁｮｲ 375f-67at) [sage] 2023/05/05(金) 21:17:04.26 ID:0zwWrX/A0 よくわからないけど [0, 1) の最大の区間は存在しないんだけど大丈夫そ？ http://mevius.5ch.net/test/read.cgi/tech/1679465982/311
312: デフォルトの名無しさん (ｱｳｱｳｳｰ Sa67-0YKo) [sage] 2023/05/13(土) 22:41:38.39 ID:WJe+G9hta 5分延長か 面白い対応するね http://mevius.5ch.net/test/read.cgi/tech/1679465982/312
313: デフォルトの名無しさん (ﾜｯﾁｮｲ 0333-qwOd) [sage] 2023/05/14(日) 00:45:51.21 ID:KvQ47IR30 攻撃を受けてもratedという前例ができたのはよかった http://mevius.5ch.net/test/read.cgi/tech/1679465982/313
314: デフォルトの名無しさん (ﾜｯﾁｮｲ 4307-9mXs) [sage] 2023/05/14(日) 06:52:48.64 ID:NgHJ91w50 コンテストモードの敗北 http://mevius.5ch.net/test/read.cgi/tech/1679465982/314
315: デフォルトの名無しさん (ﾜｯﾁｮｲ f37c-ECSL) [] 2023/05/17(水) 05:36:16.93 ID:UaIMjrrs0 >>294 女性だよ 検索したら本名とか出て来ると思うけど http://mevius.5ch.net/test/read.cgi/tech/1679465982/315
316: デフォルトの名無しさん (ﾜｯﾁｮｲ a32d-+/XS) [sage] 2023/05/17(水) 09:19:32.53 ID:tRah0iPS0 >>315 Youtubeで本人の歌声も聴けるしな http://mevius.5ch.net/test/read.cgi/tech/1679465982/316
317: デフォルトの名無しさん (ﾜｯﾁｮｲ d3b0-SwK+) [sage] 2023/05/20(土) 22:48:05.22 ID:IbXAPdJ/0 ６完… 今回は７完したかった… http://mevius.5ch.net/test/read.cgi/tech/1679465982/317
318: デフォルトの名無しさん (ｱｳｱｳｳｰ Sa2f-o1RM) [sage] 2023/05/20(土) 23:12:12.63 ID:+EVZ8y+Ka 配点割とその通りだったな http://mevius.5ch.net/test/read.cgi/tech/1679465982/318
319: デフォルトの名無しさん (ﾜｯﾁｮｲ 57db-3XON) [sage] 2023/05/22(月) 00:56:46.44 ID:mBh1GEMi0 パフォーマンスがinfinityになった回って61以前にあった？ http://mevius.5ch.net/test/read.cgi/tech/1679465982/319
320: デフォルトの名無しさん (ﾜｯﾁｮｲ abb0-IOpb) [sage] 2023/05/27(土) 22:44:08.16 ID:DM47Hxe/0 難しすぎるよ http://mevius.5ch.net/test/read.cgi/tech/1679465982/320
321: デフォルトの名無しさん (ﾜｯﾁｮｲ abb0-IOpb) [sage] 2023/05/27(土) 23:33:38.14 ID:DM47Hxe/0 コドフォもないし http://mevius.5ch.net/test/read.cgi/tech/1679465982/321
322: デフォルトの名無しさん (ﾜｯﾁｮｲ 99b0-AV1S) [sage] 2023/06/03(土) 23:01:24.39 ID:i1emxrQn0 6完 mod入力ミスってたのがアホすぎる http://mevius.5ch.net/test/read.cgi/tech/1679465982/322
323: デフォルトの名無しさん (ﾜｯﾁｮｲ c6bd-2a7c) [] 2023/06/04(日) 16:31:49.86 ID:VEMViUBd0 やっとE問題解けるようになってきた E問題って一個一個の実行時間が長いんだな http://mevius.5ch.net/test/read.cgi/tech/1679465982/323
324: デフォルトの名無しさん (ﾜｯﾁｮｲ c2bd-2a7c) [] 2023/06/04(日) 17:44:29.58 ID:0q9gSB9x0 競プロ有段者(強い人)に質問 Atcoderで一段階上に行くためには解説を何も見ずとも解けるレベルの一段階上を同じように解けるレベルになるまでその問題を解説だけ見て実装は全て自分で、っていう感じでひたすら練習していくっていうやり方は有効？ 自分の場合はD問題は9割ガタ解けて、Eがまだ実戦では歯が立たないレベル http://mevius.5ch.net/test/read.cgi/tech/1679465982/324
325: デフォルトの名無しさん (ﾜｯﾁｮｲ 45a4-Ya2I) [sage] 2023/06/04(日) 17:53:24.73 ID:AGQzq0Q+0 うん http://mevius.5ch.net/test/read.cgi/tech/1679465982/325
326: デフォルトの名無しさん (ﾜｯﾁｮｲ 02bd-2a7c) [] 2023/06/04(日) 20:29:27.17 ID:z/tZxQvT0 E問題思ったより簡単だな 食わず嫌いしてた http://mevius.5ch.net/test/read.cgi/tech/1679465982/326
327: デフォルトの名無しさん (ﾜｯﾁｮｲ 469a-dFNS) [sage] 2023/06/06(火) 11:53:03.19 ID:MhCqkbZk0 某所で「左右がバランスした括弧の列を生成する」という問題があり、解答が 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; が左右のバランス（単に'('と')'の数が同じというだけでなく）の条件に 効いているようですが、ピンとこないのです... 確かに正しい括弧の列のとき、それが成り 立つのはわかりますが、逆にそれがバランス条件を満たすのに十分であるというのが どなたかわかりやすい説明はないでしょうか http://mevius.5ch.net/test/read.cgi/tech/1679465982/327
328: デフォルトの名無しさん (ｱｳｱｳｳｰ Sac5-l0ym) [sage] 2023/06/06(火) 12:29:54.00 ID:GQVo4dJ/a しょーもない処理を複雑に描いてるだけのクソプログラムやな この関数は最初の呼び出しでlとrが同じ数字なるよう入れるのが前提で r<lの条件は例外処理みたいなもんやろ http://mevius.5ch.net/test/read.cgi/tech/1679465982/328
329: デフォルトの名無しさん (ﾜｯﾁｮｲ 45a4-4Uvu) [sage] 2023/06/06(火) 12:35:33.96 ID:UncR9VmG0 このコードの一部 `if (r < l) return;` について説明します。 ここで `l` と `r` はそれぞれまだ追加できる '(' の数と ')' の数を表しています。なので、このチェック `if (r < l) return;` は、')' の数が '(' の数より少なくなる場合、すなわち、開き括弧より閉じ括弧が少なくなる場合を防いでいます。 正しい括弧の列を生成するためには、2つの重要なルールを守らなければなりません： 1. 左括弧と右括弧の数が等しいこと 2. 任意の時
点で、右括弧の数が左括弧の数を超えないこと 1つ目のルールは、左括弧と右括弧を同数だけ生成すれば満たされます。しかし、2つ目のルールはもう少し注意が必要です。それは、どの時点でも、閉じ括弧の数が開き括弧の数を超えてはならないからです。これを超えてしまうと、括弧の列が無効になってしまいます。 例えば、"())(" のような列は、開き括弧と閉じ括弧の数は同じでも、2番目の閉じ括弧が開き括弧を超えているため、無効な括弧の列となります。 だからこそ、`if (r < l) return;` のチェックが必要なのです。これにより、閉じ
括弧の数が開き括弧を超えるような状況を防いでいます。これは、まだ追加できる閉じ括弧の数 `r` が、開き括弧 `l` より少なくなる場合、すなわち、閉じ括弧が開き括弧を超える可能性がある場合に、そのパスをすぐに終了させることで実現されています。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/329
330: デフォルトの名無しさん (JP 0H56-RtFh) [sage] 2023/06/06(火) 12:49:04.77 ID:FRsr3KcUH (を+1)を-1と対応させて累積和が常に非負っていうのがバランスしていることの必要十分条件であることを認めれば if(r < l)return; がそれの言い換えなことは明らか 証明したければ累積和が0になるところで文字列を分割して、それぞれの文字列の一番外側の括弧を取り外すとネストが一つ浅いものに帰着できるからネストの深さで帰納法を回すみたいなことを気をつけてやるといいんじゃないか http://mevius.5ch.net/test/read.cgi/tech/1679465982/330
331: デフォルトの名無しさん (ﾜｯﾁｮｲ 469a-dFNS) [sage] 2023/06/07(水) 08:00:55.26 ID:nPOLblkw0 >>329はChatGPTなのかな? すごいな >>330 どうもありがとうございます このコードの場合、再帰時に常に右側に括弧を追加することが if (r < l) return; で 必要十分になることの前提だと思うんですが.... >>329はそのことがうやむやのような http://mevius.5ch.net/test/read.cgi/tech/1679465982/331
332: デフォルトの名無しさん (ﾜｯﾁｮｲ 469a-dFNS) [sage] 2023/06/07(水) 08:33:42.08 ID:nPOLblkw0 >>327のコードとは別に、 (と)をそれぞれ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の(())を二つ並べた、と考えるべき? 要は、正しい括弧の追加操作のみをして再帰的に括弧列を生成することは可能なのか? あるいは単にすべてのパターンを生成して正当でないのを刈り取ることしかできないのか? などということが気になったのですが http://mevius.5ch.net/test/read.cgi/tech/1679465982/332
333: デフォルトの名無しさん (ﾜｯﾁｮｲ 012d-UlWg) [sage] 2023/06/07(水) 09:49:06.82 ID:Bta2HQ7X0 >>332 結論から言うと、それは難しい問題であり、一般的なアプローチでは、「全てのパターンを生成し、 それがバランスの取れた括弧列であるかどうかを判定する」という方法が用いられます。 しかし、バランスの取れた括弧列を生成するための一種の再帰的なパターンは存在します。 それは、大きさnの全てのバランスの取れた括弧列を生成した後で、その各々に対して以下の操作を行うことです： 1. '(' + P + ')' を追加する 2. P + '()' を追
加する 3. '()' + P を追加する ここで P は大きさnの任意のバランスの取れた括弧列です。 この操作を行うと、全ての大きさn+1のバランスの取れた括弧列を生成することができます。 ただし、これは重複する列を生成する可能性があるため、生成された列は一意であることを保証するために 何らかの方法で重複を除去する必要があります。 したがって、厳密には「全てのパターンを生成し、それがバランスの取れた括弧列であるかどうかを判定する」 という方法とは異なりますが、これは一種の再帰的なアプローチと言えます。 しかし、これらのアプローチ
は計算時間やメモリ使用量の観点から見ると、>>327に示されたDFSを用いたアプローチに比べて 効率的ではないかもしれません。また、DFSを用いたアプローチは明確に「正しい括弧の追加操作のみ」を行っていると言えます。 なぜなら、すべての括弧列を生成する過程で、同時にその列が正しい括弧列であるかどうかをチェックすることが可能だからです。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/333
334: デフォルトの名無しさん (ﾜｯﾁｮｲ 7d5f-RtFh) [sage] 2023/06/07(水) 10:10:41.04 ID:WomvMCD50 >>332 >>333 は嘘 バランスした括弧列の定義は全体を括弧で囲む操作と括弧列2つの結合で生成される集合だから、その()を追加するっていうのを右か左に追加するって意味だとするとレベル2以上の文字列同士の結合が考慮されていないの で、(())(())が作れない 中に()を挿入することを許すとすると、今度は全体を括弧で囲む操作はいらなくなる というのも、どんな空でないバランスした括弧列にも()の部分があるから、それを取り除くことを
繰り返すことで空にできるから、逆に空文字列に()を追加していくことで任意のバランスした括弧列が作れるし、バランスした括弧列の任意の箇所に()を挿入した文字列もまたバランスした括弧列になっている http://mevius.5ch.net/test/read.cgi/tech/1679465982/334
335: デフォルトの名無しさん (ﾜｯﾁｮｲ a905-4Uvu) [sage] 2023/06/07(水) 11:08:01.09 ID:DYKBdUd80 >>331 ご指摘の通り、このコードでは再帰的に右側に括弧を追加しています。具体的には、まず左括弧を追加し、その後で右括弧を追加しています。 この if (r < l) return; の制約は、この追加の順序に基づいています。開始時点では、開き括弧と閉じ括弧の数が等しく（つまり、l == r）、左括弧を先に追加します。そのため、追加の過程では一時的に l が r より小さくなります。しかし、その後すぐに右括弧を追加することでバランスを保ちま
す。 if (r < l) return; のチェックにより、右括弧が先に追加される（つまり、r < l となる）状況を防いでいます。これは、左括弧を追加した後でのみ右括弧を追加するという、このコードの括弧の追加の順序を反映しています。そのため、この制約が満たされない場合（つまり、右括弧が先に追加される場合）、そのパスは無効となり、すぐに終了します。 したがって、この if (r < l) return; の制約は、このコードの括弧の追加の順序に基づいて、左括弧と右括弧が正しくバランスを保つことを保証しています。 http://mevius.5ch.net/test/r
ead.cgi/tech/1679465982/335
336: デフォルトの名無しさん (ｵｯﾍﾟｹ Sr91-BHVC) [sage] 2023/06/07(水) 14:48:36.26 ID:w+aRYGw/r 非負のランダムウォーク書いて+1-1を()に対応させるだけだろ http://mevius.5ch.net/test/read.cgi/tech/1679465982/336
337: デフォルトの名無しさん (ﾜｯﾁｮｲ 797f-Ydfh) [sage] 2023/06/10(土) 17:29:19.24 ID:0oQUevmP0 >>327 閉じ括弧が開き括弧より少なかったら、ダメってことなだけでは。 開き括弧と閉じ括弧の数が同じって条件は最初の呼び出しではlとrが同じでなければならないって制約があると思う http://mevius.5ch.net/test/read.cgi/tech/1679465982/337
338: デフォルトの名無しさん (ﾜｯﾁｮｲ 89b0-SVCw) [sage] 2023/06/10(土) 22:46:50.51 ID:sqwX2ns70 6完… 途中まではいいペースもFで帰りがけにも頂点集合受け取るの忘れて時間ギリギリに http://mevius.5ch.net/test/read.cgi/tech/1679465982/338
339: デフォルトの名無しさん (ﾜｯﾁｮｲ 7b9a-D1r1) [sage] 2023/06/11(日) 20:43:12.18 ID:Fc1cWZtx0 >>337 例えば())(()は閉じ開きの括弧数だけでいうとおkだけど実際にはおkじゃない では何故これが生成されないか、他の駄目パターンもなぜ生成されないか気になった というのを既に考察したつもり http://mevius.5ch.net/test/read.cgi/tech/1679465982/339
340: デフォルトの名無しさん (ﾜｯﾁｮｲ 7b9a-D1r1) [sage] 2023/06/11(日) 20:59:44.70 ID:Fc1cWZtx0 しかし、解く時間が限られている場合にグダグダ悩んでいる暇はないよなあ そういう場合パターンを覚えておくしかない? http://mevius.5ch.net/test/read.cgi/tech/1679465982/340
341: デフォルトの名無しさん (ﾜｯﾁｮｲ 61b0-8SEE) [sage] 2023/06/17(土) 22:47:22.26 ID:/YYtpwSS0 ジャッジが終わらないよ http://mevius.5ch.net/test/read.cgi/tech/1679465982/341
342: デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM96-/52B) [sage] 2023/06/17(土) 23:10:07.92 ID:dXHH06bsM unratedおおすぎ http://mevius.5ch.net/test/read.cgi/tech/1679465982/342
343: デフォルトの名無しさん (ﾜｯﾁｮｲ 92ad-zFGp) [sage] 2023/06/17(土) 23:16:56.58 ID:re9nMjXH0 アーロンジャッジたすけて http://mevius.5ch.net/test/read.cgi/tech/1679465982/343
344: デフォルトの名無しさん (ﾜｯﾁｮｲ 092d-dYQK) [sage] 2023/06/18(日) 04:25:23.41 ID:KT9X3u120 atcoderがddos受けてるとして、潰して得をするのは誰だ？ http://mevius.5ch.net/test/read.cgi/tech/1679465982/344
345: デフォルトの名無しさん (ｱｳｱｳｳｰ Sacd-c3fv) [sage] 2023/06/18(日) 11:57:26.20 ID:zhu3s9uha ロシア中国 http://mevius.5ch.net/test/read.cgi/tech/1679465982/345
346: デフォルトの名無しさん (ﾜｯﾁｮｲ a325-p5N0) [sage] 2023/06/24(土) 17:44:41.70 ID:SdmUsAHw0 ガイジのみんなこっちおいで😆 怖がる必要ないよ✌ http://mevius.5ch.net/test/read.cgi/tech/1679465982/346
347: デフォルトの名無しさん (ｵｯﾍﾟｹ Sr81-g5c7) [sage] 2023/06/24(土) 18:57:52.69 ID:JQRvym1Fr うおおおおおおおお🤓 http://mevius.5ch.net/test/read.cgi/tech/1679465982/347
348: デフォルトの名無しさん (ﾜｯﾁｮｲ a325-p5N0) [sage] 2023/06/24(土) 19:30:32.53 ID:SdmUsAHw0 他のガイジもこっちおいで！ http://mevius.5ch.net/test/read.cgi/tech/1679465982/348
349: デフォルトの名無しさん (ﾜｯﾁｮｲ a3bd-/B6M) [] 2023/06/24(土) 22:23:51.32 ID:+O4dPU7T0 攻撃されてね？ http://mevius.5ch.net/test/read.cgi/tech/1679465982/349
350: デフォルトの名無しさん (ﾜｯﾁｮｲ a325-cli0) [sage] 2023/06/24(土) 22:28:05.07 ID:SdmUsAHw0 落ちてる！クソすぎ！！！ http://mevius.5ch.net/test/read.cgi/tech/1679465982/350
351: デフォルトの名無しさん (ﾜｯﾁｮｲ 75b0-GDjS) [sage] 2023/06/24(土) 22:42:50.37 ID:ZtOuHWP80 せっかくG解けたのに1分遅れになってしまった… http://mevius.5ch.net/test/read.cgi/tech/1679465982/351
352: デフォルトの名無しさん (ｱｳｱｳｳｰ Sa69-Auuh) [sage] 2023/06/24(土) 22:55:29.87 ID:gDpwuzMxa アンレでしょ、ね？ね？ http://mevius.5ch.net/test/read.cgi/tech/1679465982/352
353: デフォルトの名無しさん (ﾜｯﾁｮｲ 75b0-GDjS) [sage] 2023/06/24(土) 22:56:49.69 ID:ZtOuHWP80 ところでC正解者少なすぎ http://mevius.5ch.net/test/read.cgi/tech/1679465982/353
354: デフォルトの名無しさん (ﾜｯﾁｮｲ a325-cli0) [sage] 2023/06/24(土) 23:12:14.22 ID:SdmUsAHw0 10:10くらい？から今(10:50)までずっとatcoder開けませんが、同じ人いるかな なんてツイートしてるひともいるね http://mevius.5ch.net/test/read.cgi/tech/1679465982/354
355: デフォルトの名無しさん (ﾜｯﾁｮｲ 9dda-0drY) [sage] 2023/06/25(日) 01:40:55.82 ID:9o2+M89H0 このコードが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){ i
f((y & (1 << j)) != 0) cur = dp[j][cur]; } cout << cur << endl; } } http://mevius.5ch.net/test/read.cgi/tech/1679465982/355
356: デフォルトの名無しさん (ﾜｯﾁｮｲ 9dda-0drY) [sage] 2023/06/25(日) 01:41:11.75 ID:9o2+M89H0 どこかおかしい部分あるかな http://mevius.5ch.net/test/read.cgi/tech/1679465982/356
357: デフォルトの名無しさん (ﾜｯﾁｮｲ 4bd6-1Bpn) [sage] 2023/06/25(日) 02:14:14.53 ID:0IEJDuKo0 スタックサイズ http://mevius.5ch.net/test/read.cgi/tech/1679465982/357
358: デフォルトの名無しさん (ｱｳｱｳｳｰ Sa69-Auuh) [sage] 2023/06/25(日) 02:15:11.19 ID:3TXiYfiya >>355 マルチは市ね http://mevius.5ch.net/test/read.cgi/tech/1679465982/358
359: デフォルトの名無しさん (ｱｳｱｳｳｰ Sa69-yAbC) [] 2023/06/29(木) 15:31:24.42 ID:wEpX0/Cla Twitterのpaizaの広告とかに必ず現れる 「入力値をチェックしていない」 という返信をつける人は、具体的に何をチェックして、どう処理するの？ http://mevius.5ch.net/test/read.cgi/tech/1679465982/359
360: デフォルトの名無しさん (ｱｳｱｳｳｰ Sa69-yAbC) [] 2023/06/29(木) 15:35:22.33 ID:wEpX0/Cla たとえば、 ・Nは偶数 ・AとBの合計はN未満 といった制約は、実際のプログラムならチェックして例外をスローする しかし、 「nが整数値じゃない場合をチェックしていない」 みたいなよくわからない難癖をつける人もいる 整数値じゃなければint型にパースするときに、ほとんどの言語で例外になるからいいのでは http://mevius.5ch.net/test/read.cgi/tech/1679465982/360
361: デフォルトの名無しさん (ｽﾌﾟﾌﾟ Sd43-2HPs) [] 2023/06/29(木) 15:50:34.59 ID:WjHgY0Cmd >>355 ll で dp[39][100009], A[100009]; 何バイトあるん http://mevius.5ch.net/test/read.cgi/tech/1679465982/361
362: デフォルトの名無しさん (ﾜｯﾁｮｲ 7fb0-+Ydp) [sage] 2023/07/01(土) 22:45:27.97 ID:rC0kSH/20 今回は簡単めでしたね G解けなかったけど http://mevius.5ch.net/test/read.cgi/tech/1679465982/362
363: デフォルトの名無しさん (ﾜｯﾁｮｲ e2da-l2Kc) [sage] 2023/07/01(土) 23:33:06.19 ID:x6PMIr/p0 コンテスト初参加 C問題があまりにも酷いと思った 20分くらいかけて、priorityqueue<pair<double、int>> に値をプッシュする時にpairのsecondの方にマイナスを付ければ良いことに気がついたもののWA 何を試してもWAで、doubleの精度に問題があるんじゃないかと思って、ネット検索をしたら、long doubleという型があることを知り、試してみたら無事AC Ｃ問題で時間とメンタルを削られてD問題は諦めた 初参加とはいえ茶パフォはあまりに脳
障害すぎるだろ http://mevius.5ch.net/test/read.cgi/tech/1679465982/363
364: デフォルトの名無しさん (ﾜｯﾁｮｲ e2da-l2Kc) [sage] 2023/07/01(土) 23:39:31.52 ID:x6PMIr/p0 今回のＣ問題でpriorityqueueを使ったんだけど、priorityqueue<pair<double、int>> に値をプッシュする時、pairのsecondの方に-をつけて取り出す順番を工夫するのって典型？ ちょっとした閃きだけど思いついた時は俺ちょっと頭いいんじゃねって思っちゃった その後ものの見事に脳障害っぷりを晒してしまったけど http://mevius.5ch.net/test/read.cgi/tech/1679465982/364
365: デフォルトの名無しさん (ﾜｯﾁｮｲ a225-+ypZ) [sage] 2023/07/01(土) 23:43:47.83 ID:L7MIkgdg0 その発想は天才だよ、才能あるね http://mevius.5ch.net/test/read.cgi/tech/1679465982/365
366: デフォルトの名無しさん (ｻｻｸｯﾃﾛﾗ Sp5f-RHsg) [sage] 2023/07/01(土) 23:50:30.60 ID:wjWc9sXDp マジレスすると符号付けて逆順にすることで実装をシンプルにするのはかなりの典型です http://mevius.5ch.net/test/read.cgi/tech/1679465982/366
367: デフォルトの名無しさん (ｱｳｱｳｳｰ Sabb-zrhl) [sage] 2023/07/01(土) 23:53:37.30 ID:6JFt9TARa むしろそのマイナスにするのが主題と言ってもいいくらい http://mevius.5ch.net/test/read.cgi/tech/1679465982/367
368: デフォルトの名無しさん (ｱｳｱｳｳｰ Sabb-DX8j) [sage] 2023/07/01(土) 23:57:08.30 ID:CM44ThHXa C++ってFraction無いんだっけ？ まあ無くても自分で通分すれば済む話だが http://mevius.5ch.net/test/read.cgi/tech/1679465982/368
369: デフォルトの名無しさん (ﾜｯﾁｮｲ e2da-l2Kc) [sage] 2023/07/02(日) 00:35:29.46 ID:sYDH7cmq0 なるほど、ただの典型だったか… ただ、その典型を自分で思いついたのはちょっと嬉しい http://mevius.5ch.net/test/read.cgi/tech/1679465982/369
370: デフォルトの名無しさん (ﾜｯﾁｮｲ e2da-l2Kc) [sage] 2023/07/02(日) 00:39:10.97 ID:sYDH7cmq0 先程 D問題をACしてきた 結構簡単だし、C問題を普通に解けていたら多分四完出来た 今回のC問題みたいに本質的じゃない部分(long doubleという型を知っているかどうかみたいな)を問うのは本当にやめた方が良いと思う 問題の質がシンプルに低い http://mevius.5ch.net/test/read.cgi/tech/1679465982/370
371: デフォルトの名無しさん (ｱｳｱｳｳｰ Sabb-zrhl) [sage] 2023/07/02(日) 01:16:07.96 ID:3YsXAzA4a 小数の精度についての理解を問うなかなかの良問だと思ったけどね http://mevius.5ch.net/test/read.cgi/tech/1679465982/371
372: デフォルトの名無しさん (ﾜｯﾁｮｲ cb5f-5Jqn) [sage] 2023/07/02(日) 01:33:02.66 ID:K/v1SCuX0 浮動小数点数での出力を求められていない場合に浮動小数点数を使うのはアンチパターン 分数を管理する構造体を持ち出したり適切な比較関数を書いたりして対処するべき http://mevius.5ch.net/test/read.cgi/tech/1679465982/372
373: デフォルトの名無しさん (ｻｻｸｯﾃﾛﾗ Sp5f-RHsg) [sage] 2023/07/02(日) 03:53:32.35 ID:FFIcTLPjp 前回のC問題はただめちゃくちゃ面倒なだけでアレだったけど今週のC問題は何も悪くないし非本質的でもないだろ 浮動小数点数は誤差に気をつけるべきなんて競プロでは身につけておくべき典型知識だし競プロ外でも浮動小数点数の仕組みは知っておくべきだしm http://mevius.5ch.net/test/read.cgi/tech/1679465982/373
374: デフォルトの名無しさん (ｻｻｸｯﾃﾛﾗ Sp5f-RHsg) [sage] 2023/07/02(日) 03:56:07.16 ID:FFIcTLPjp 強いて言うならlong double型で無理矢理通すような解答を弾けるような設定にして比較関数やら有理数型を表す構造体やらの整数しか登場しなくて誤差の心配がない解答のみが通るようにしてほしかったがCでそれは酷かもしれない http://mevius.5ch.net/test/read.cgi/tech/1679465982/374
375: デフォルトの名無しさん (ﾜｯﾁｮｲ d701-OYD+) [sage] 2023/07/02(日) 04:23:31.59 ID:vN/hop9Q0 long double使わなくても解けるし、それ知らないと解けないと言ってる人のレベルが低すぎるだけ http://mevius.5ch.net/test/read.cgi/tech/1679465982/375
376: デフォルトの名無しさん (ﾜｯﾁｮｲ 12bd-+Mc8) [sage] 2023/07/02(日) 08:45:23.44 ID:TDPjDhzP0 E問題の意味が分からないんだが。 俺の考えたアルゴリズムは、 Mが0,1,2になる数、 Eが0,1,2になる数、 Xが0,1,2になる数、 を全て数えて 各組み合わせ27通りについて、 mex×場合分けの数 っていうやり方をしたんだがサンプル3の問題からしてそもそも合わない 日本語下手で説明難しいからコードを見てほしい。 https://atcoder.jp/contests/abc308/submissions/43167367 このやり方がなぜいけないのかわからない コンテスト中「E問題いけるや
ん！」と思ってただけに絶望だったわ、はぁ。。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/376
377: デフォルトの名無しさん (ﾜｯﾁｮｲ 12bd-+Mc8) [sage] 2023/07/02(日) 08:51:37.04 ID:TDPjDhzP0 関係ないけど、dictのkeyで回せば if k not in dic["X"]: continue みたいなのいらなかったな http://mevius.5ch.net/test/read.cgi/tech/1679465982/377
378: デフォルトの名無しさん (ﾜｯﾁｮｲ 6710-GKTn) [sage] 2023/07/02(日) 08:52:36.78 ID:IX/DQMpQ0 i<j<k http://mevius.5ch.net/test/read.cgi/tech/1679465982/378
379: デフォルトの名無しさん (ﾜｯﾁｮｲ 12bd-+Mc8) [sage] 2023/07/02(日) 08:55:34.57 ID:TDPjDhzP0 >>378 ないてもいい？ http://mevius.5ch.net/test/read.cgi/tech/1679465982/379
380: デフォルトの名無しさん (ﾜｯﾁｮｲ 12bd-+Mc8) [sage] 2023/07/02(日) 09:02:55.87 ID:TDPjDhzP0 雑なやり方だけど、 「E」に来た時点で、それより前のMの各012の数と それより後のXの「012」の数を保持しておけば簡単に解けたわけか http://mevius.5ch.net/test/read.cgi/tech/1679465982/380
381: デフォルトの名無しさん (ﾜｯﾁｮｲ ceca-Sjvf) [] 2023/07/02(日) 10:28:08.37 ID:ZqX35jN50 Cみたいなのが普通に小数にしてソートして解けないとか、現実的に不要な精度を求めてるからじゃ。工夫して分数を比較とか一般的なプログラミングではあり得ない。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/381
ﾒﾓ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 97 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.016s