競技プログラミング総合スレ 66 (478レス)
1-

295: (ワッチョイ 97ad-muTB) 2023/05/03(水)04:10 ID:k35m8F9T0(1) AAS
黄色だから野郎じゃない
296: (ワッチョイ 9f55-hzXf) 2023/05/03(水)17:06 ID:aKUbjdKi0(1/5) AAS
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) 2023/05/03(水)17:43 ID:C+dlbD9Z0(1) AAS
日本語で書いてくれ
298: (ワッチョイ 572d-wHlW) 2023/05/03(水)19:29 ID:ElyXadep0(1) AAS
B1とB2の直方体の数が異なる場合、B1とB2は等しくない
B1とB2の直方体の数が同じ場合、B1とB2に含まれる直方体の番号を並べ替える
各直方体の対応する要素が等しくない場合、B1とB2は等しくない
すべての直方体の対応する要素が等しい場合、B1とB2は等しい
299: (ワッチョイ 9f55-hzXf) 2023/05/03(水)19:40 ID:aKUbjdKi0(2/5) AAS
B1 が1個のn次元直方体からなる集合とします。
それを2つに分けた2つのn次元直方体の和集合を B2 とします。
B1 を構成する直方体の数は 1 です。
B2 を構成する直方体の数は 2 です。
ですが、B1 = B2 です。
300: (ワッチョイ 9f55-hzXf) 2023/05/03(水)19:43 ID:aKUbjdKi0(3/5) AAS
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
(1): (ワッチョイ 9f55-hzXf) 2023/05/03(水)19:48 ID:aKUbjdKi0(4/5) AAS
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) 2023/05/03(水)19:49 ID:aKUbjdKi0(5/5) AAS
>>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) 2023/05/03(水)21:06 ID:MtXxv88er(1) AAS
うんち!w
304: (ワッチョイ 5701-MUOW) 2023/05/04(木)00:35 ID:FFDpqzE90(1) AAS
併合していって無駄のない表現にできればいける?
305: (ワッチョイ 375f-k3Rv) 2023/05/04(木)01:33 ID:Pbw0n2Gt0(1) AAS
そんなことよりn乗で増えていくのを抑えないと無理なんでは
306
(1): (ワッチョイ 9f55-hzXf) 2023/05/04(木)02:26 ID:iR6EpWdh0(1) AAS
2次元限定、座標は有理数限定にしたら、競プロの問題として成立しますか?
307
(1): (ワッチョイ 572d-wHlW) 2023/05/04(木)04:20 ID:W+5O3yqN0(1) AAS
>>306
yukicoderで出題してみれば?
308: (ワッチョイ 9f55-hzXf) 2023/05/05(金)10:56 ID:xYbtWehf0(1) AAS
>>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 の直方体とする。
省5
309: (ワッチョイ bfd7-E7B+) 2023/05/05(金)13:25 ID:CuujTRH+0(1) AAS
あるよ
310: (ブーイモ MMab-8WUk) 2023/05/05(金)18:31 ID:zrOWQZW0M(1) AAS
自分で解けてなければ自作の問題とは言わん
311: (ワッチョイ 375f-67at) 2023/05/05(金)21:17 ID:0zwWrX/A0(1) AAS
よくわからないけど [0, 1) の最大の区間は存在しないんだけど大丈夫そ?
312: (アウアウウー Sa67-0YKo) 2023/05/13(土)22:41 ID:WJe+G9hta(1) AAS
5分延長か
面白い対応するね
313: (ワッチョイ 0333-qwOd) 2023/05/14(日)00:45 ID:KvQ47IR30(1) AAS
攻撃を受けてもratedという前例ができたのはよかった
314: (ワッチョイ 4307-9mXs) 2023/05/14(日)06:52 ID:NgHJ91w50(1) AAS
コンテストモードの敗北
315
(1): (ワッチョイ f37c-ECSL) 2023/05/17(水)05:36 ID:UaIMjrrs0(1) AAS
>>294
女性だよ
検索したら本名とか出て来ると思うけど
316: (ワッチョイ a32d-+/XS) 2023/05/17(水)09:19 ID:tRah0iPS0(1) AAS
>>315
Youtubeで本人の歌声も聴けるしな
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使わなくても解けるし、それ知らないと解けないと言ってる人のレベルが低すぎるだけ
1-
あと 103 レスあります
スレ情報 赤レス抽出 画像レス抽出 歴の未読スレ AAサムネイル

ぬこの手 ぬこTOP 0.019s