フワちゃん

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

プログラム

レス数: 479

ホーム » プログラム » 競技プログラミング総合スレ 66
概要: 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 です。
No.301名無しさん
#
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 です。
No.302名無しさん
#
>>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 です。
No.303名無しさん
#
うんち！w
No.304名無しさん
#
併合していって無駄のない表現にできればいける？
No.305名無しさん
#
そんなことよりn乗で増えていくのを抑えないと無理なんでは
No.306名無しさん
#
2次元限定、座標は有理数限定にしたら、競プロの問題として成立しますか？
No.307名無しさん
#
>>306

yukicoderで出題してみれば？
No.308名無しさん
#
>>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 の部分集合の中で最大の直方体を求めよ。
この効率的な解法はありますか？
No.309名無しさん
#
あるよ
No.310名無しさん
#
自分で解けてなければ自作の問題とは言わん
No.311名無しさん
#
よくわからないけど [0, 1) の最大の区間は存在しないんだけど大丈夫そ？
No.312名無しさん
#
5分延長か
面白い対応するね
No.313名無しさん
#
攻撃を受けてもratedという前例ができたのはよかった
No.314名無しさん
#
コンテストモードの敗北
No.315名無しさん
#
>>294

女性だよ
検索したら本名とか出て来ると思うけど
No.316名無しさん
#
>>315

Youtubeで本人の歌声も聴けるしな
No.317名無しさん
#
６完…
今回は７完したかった…
No.318名無しさん
#
配点割とその通りだったな
No.319名無しさん
#
パフォーマンスがinfinityになった回って61以前にあった？
No.320名無しさん
#
難しすぎるよ
No.321名無しさん
#
コドフォもないし
No.322名無しさん
#
6完
mod入力ミスってたのがアホすぎる
No.323名無しさん
#
やっとE問題解けるようになってきた
E問題って一個一個の実行時間が長いんだな
No.324名無しさん
#
競プロ有段者(強い人)に質問
Atcoderで一段階上に行くためには解説を何も見ずとも解けるレベルの一段階上を同じように解けるレベルになるまでその問題を解説だけ見て実装は全て自分で、っていう感じでひたすら練習していくっていうやり方は有効？
自分の場合はD問題は9割ガタ解けて、Eがまだ実戦では歯が立たないレベル
No.325名無しさん
#
うん
No.326名無しさん
#
E問題思ったより簡単だな
食わず嫌いしてた
No.327名無しさん
#
某所で「左右がバランスした括弧の列を生成する」という問題があり、解答が
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; が左右のバランス（単に'('と')'の数が同じというだけでなく）の条件に
効いているようですが、ピンとこないのです... 確かに正しい括弧の列のとき、それが成り
立つのはわかりますが、逆にそれがバランス条件を満たすのに十分であるというのが　
どなたかわかりやすい説明はないでしょうか
No.328名無しさん
#
しょーもない処理を複雑に描いてるだけのクソプログラムやな
この関数は最初の呼び出しでlとrが同じ数字なるよう入れるのが前提で
r<lの条件は例外処理みたいなもんやろ
No.329名無しさん
#
このコードの一部 `if (r < l) return;` について説明します。
ここで `l` と `r` はそれぞれまだ追加できる '(' の数と ')' の数を表しています。なので、このチェック `if (r < l) return;` は、')' の数が '(' の数より少なくなる場合、すなわち、開き括弧より閉じ括弧が少なくなる場合を防いでいます。
正しい括弧の列を生成するためには、2つの重要なルールを守らなければなりません：
1. 左括弧と右括弧の数が等しいこと
2. 任意の時点で、右括弧の数が左括弧の数を超えないこと
1つ目のルールは、左括弧と右括弧を同数だけ生成すれば満たされます。しかし、2つ目のルールはもう少し注意が必要です。それは、どの時点でも、閉じ括弧の数が開き括弧の数を超えてはならないからです。これを超えてしまうと、括弧の列が無効になってしまいます。
例えば、"())(" のような列は、開き括弧と閉じ括弧の数は同じでも、2番目の閉じ括弧が開き括弧を超えているため、無効な括弧の列となります。
だからこそ、`if (r < l) return;` のチェックが必要なのです。これにより、閉じ括弧の数が開き括弧を超えるような状況を防いでいます。これは、まだ追加できる閉じ括弧の数 `r` が、開き括弧 `l` より少なくなる場合、すなわち、閉じ括弧が開き括弧を超える可能性がある場合に、そのパスをすぐに終了させることで実現されています。
No.330名無しさん
#
(を+1)を-1と対応させて累積和が常に非負っていうのがバランスしていることの必要十分条件であることを認めれば if(r < l)return; がそれの言い換えなことは明らか
証明したければ累積和が0になるところで文字列を分割して、それぞれの文字列の一番外側の括弧を取り外すとネストが一つ浅いものに帰着できるからネストの深さで帰納法を回すみたいなことを気をつけてやるといいんじゃないか
No.331名無しさん
#
>>329
はChatGPTなのかな? すごいな
>>330
どうもありがとうございます
このコードの場合、再帰時に常に右側に括弧を追加することが if (r < l) return; で
必要十分になることの前提だと思うんですが....
>>329
はそのことがうやむやのような
No.332名無しさん
#
>>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の(())を二つ並べた、と考えるべき?
要は、正しい括弧の追加操作のみをして再帰的に括弧列を生成することは可能なのか?
あるいは単にすべてのパターンを生成して正当でないのを刈り取ることしかできないのか?
などということが気になったのですが
No.333名無しさん
#
>>332

結論から言うと、それは難しい問題であり、一般的なアプローチでは、「全てのパターンを生成し、
それがバランスの取れた括弧列であるかどうかを判定する」という方法が用いられます。
しかし、バランスの取れた括弧列を生成するための一種の再帰的なパターンは存在します。
それは、大きさnの全てのバランスの取れた括弧列を生成した後で、その各々に対して以下の操作を行うことです：
1. '(' + P + ')' を追加する
2. P + '()' を追加する
3. '()' + P を追加する
ここで P は大きさnの任意のバランスの取れた括弧列です。
この操作を行うと、全ての大きさn+1のバランスの取れた括弧列を生成することができます。
ただし、これは重複する列を生成する可能性があるため、生成された列は一意であることを保証するために
何らかの方法で重複を除去する必要があります。
したがって、厳密には「全てのパターンを生成し、それがバランスの取れた括弧列であるかどうかを判定する」
という方法とは異なりますが、これは一種の再帰的なアプローチと言えます。
しかし、これらのアプローチは計算時間やメモリ使用量の観点から見ると、
>>327
に示されたDFSを用いたアプローチに比べて
効率的ではないかもしれません。また、DFSを用いたアプローチは明確に「正しい括弧の追加操作のみ」を行っていると言えます。
なぜなら、すべての括弧列を生成する過程で、同時にその列が正しい括弧列であるかどうかをチェックすることが可能だからです。
No.334名無しさん
#
>>332

>>333
は嘘
バランスした括弧列の定義は全体を括弧で囲む操作と括弧列2つの結合で生成される集合だから、その()を追加するっていうのを右か左に追加するって意味だとするとレベル2以上の文字列同士の結合が考慮されていないの
で、(())(())が作れない
中に()を挿入することを許すとすると、今度は全体を括弧で囲む操作はいらなくなる
というのも、どんな空でないバランスした括弧列にも()の部分があるから、それを取り除くことを繰り返すことで空にできるから、逆に空文字列に()を追加していくことで任意のバランスした括弧列が作れるし、バランスした括弧列の任意の箇所に()を挿入した文字列もまたバランスした括弧列になっている
No.335名無しさん
#
>>331

ご指摘の通り、このコードでは再帰的に右側に括弧を追加しています。具体的には、まず左括弧を追加し、その後で右括弧を追加しています。
この if (r < l) return; の制約は、この追加の順序に基づいています。開始時点では、開き括弧と閉じ括弧の数が等しく（つまり、l == r）、左括弧を先に追加します。そのため、追加の過程では一時的に l が r より小さくなります。しかし、その後すぐに右括弧を追加することでバランスを保ちます。
if (r < l) return; のチェックにより、右括弧が先に追加される（つまり、r < l となる）状況を防いでいます。これは、左括弧を追加した後でのみ右括弧を追加するという、このコードの括弧の追加の順序を反映しています。そのため、この制約が満たされない場合（つまり、右括弧が先に追加される場合）、そのパスは無効となり、すぐに終了します。
したがって、この if (r < l) return; の制約は、このコードの括弧の追加の順序に基づいて、左括弧と右括弧が正しくバランスを保つことを保証しています。
No.336名無しさん
#
非負のランダムウォーク書いて+1-1を()に対応させるだけだろ
No.337名無しさん
#
>>327

閉じ括弧が開き括弧より少なかったら、ダメってことなだけでは。
開き括弧と閉じ括弧の数が同じって条件は最初の呼び出しではlとrが同じでなければならないって制約があると思う
No.338名無しさん
#
6完…
途中まではいいペースもFで帰りがけにも頂点集合受け取るの忘れて時間ギリギリに
No.339名無しさん
#
>>337

例えば())(()は閉じ開きの括弧数だけでいうとおkだけど実際にはおkじゃない
では何故これが生成されないか、他の駄目パターンもなぜ生成されないか気になった
というのを既に考察したつもり
No.340名無しさん
#
しかし、解く時間が限られている場合にグダグダ悩んでいる暇はないよなあ
そういう場合パターンを覚えておくしかない?
No.341名無しさん
#
ジャッジが終わらないよ
No.342名無しさん
#
unratedおおすぎ
No.343名無しさん
#
アーロンジャッジたすけて
No.344名無しさん
#
atcoderがddos受けてるとして、潰して得をするのは誰だ？
No.345名無しさん
#
ロシア中国
No.346名無しさん
#
ガイジのみんなこっちおいで😆
怖がる必要ないよ✌
No.347名無しさん
#
うおおおおおおおお🤓
No.348名無しさん
#
他のガイジもこっちおいで！
No.349名無しさん
#
攻撃されてね？
No.350名無しさん
#
落ちてる！クソすぎ！！！

このカテゴリの過去スレッド

http://mevius.5ch.io/test/read.cgi/tech/1678807578/

名無しさん
5ちゃんねるの運営はUPLIFT会員の皆さまに支えられています。
運営にご協力お願いいたします。


───────────────────...

C言語で関数を書いていくスレ

名無しさん
EchoAPIは私のワークフローに大きな助けとなっていて、特にRESTfulレスポンスのモック機能が便利で、バックエンドが完全に稼働し...