競技プログラミング総合スレ 66 (478ﾚｽ)
上下前次1-新
271: (ﾜｯﾁｮｲ 1507-ZiWf) 2023/04/23(日)20:18 ID:5yiVxLP00(2/2) AAS
>>268
それでもいいし解けさえすればそれでなくてもいいというだけの話
272: (ﾌﾞｰｲﾓ MM3e-oS25) 2023/04/23(日)20:39 ID:PWijjkXzM(3/3) AAS
>>270
ありがと。
別にお酒に酔ってたわけじゃないのに、
なんで間違えたのかずっと悩んでたの
273: (ｱｳｱｳｳｰ Sa21-ZiWf) 2023/04/23(日)20:43 ID:LpJKh+XVa(2/2) AAS
Cは正規表現で解けるな
肯定的先読み言明を使えば一回のマッチでいける
274: (ﾜｯﾁｮｲ 7d01-8Z+s) 2023/04/23(日)21:48 ID:kV4uegyh0(1) AAS
質問タブでアナウンス送るの、知らない人にとっては分かりづらい
275: (ｽﾌｯ Sd0a-hie5) 2023/04/25(火)18:22 ID:NfKxocHyd(1) AAS
Chatgptの影響ですでにレート出にくくなってるとかある？
276(1): (ﾜｯﾁｮｲ e505-2JcT) 2023/04/25(火)18:32 ID:aoA2LcV80(1) AAS
GPTのおかげで誰でもCくらいまでは瞬殺できるし、緑茶らへんの人にとっては影響あるんじゃない？
277: (ｱｳｱｳｳｰ Sa21-9VOY) 2023/04/25(火)20:23 ID:Nhg6f6DZa(1) AAS
インタラクティブ問題なら回避できるんかな
278: (ｽｯﾌﾟ Sd0a-PPLO) 2023/04/25(火)22:48 ID:8h60ybjNd(1) AAS
茶色中盤くらいまではCまで早解きゲーだしまあ初心者は萎えるかもな
279: (ﾜｯﾁｮｲ 5d2d-YWDm) 2023/04/26(水)00:39 ID:v/InlOgJ0(1/2) AAS
D - Find by Query
この問題の意味がわからない、運が悪いとACできないとか無いの？
280: (ﾜｯﾁｮｲ 5d2d-YWDm) 2023/04/26(水)00:44 ID:v/InlOgJ0(2/2) AAS
ああ、境界を探すのか
281: (ﾜｯﾁｮｲ e5ad-8MXh) 2023/04/26(水)04:47 ID:CtDSQpU90(1) AAS
10 ^ 6で試せる回数が20回だから二分探索しかないんだけどこういうメタ読み辞めたいんだよな
282: (ｻｻｸｯﾃﾛﾙ Spbd-EuHm) 2023/04/26(水)04:53 ID:dFoBwinZp(1) AAS
何なら序盤で出てくるインタラクティブ問題っていう時点でパターンが限られすぎてて8、9割二分探索(の類型)であることが推測出来る
283: (ｱｳｱｳｳｰ Sa21-ZiWf) 2023/04/26(水)14:19 ID:pZKGmWvba(1) AAS
>>276
必ず正しい答えを出すわけじゃないから自分で直せないとペナルティ食らうぞ
284: (ﾜｯﾁｮｲ 7d01-8Z+s) 2023/04/26(水)18:10 ID:hY8jXU1C0(1) AAS
問題公開されてても提出できなかったらどうすんの
285: (ﾌﾞｰｲﾓ MM3e-Zf+n) 2023/04/26(水)18:32 ID:PpfAVk7MM(1) AAS
茶色だけみんなchatgptで序盤の問題解いてたのか
俺もそうしようかな
286: (ﾜｯﾁｮｲ e505-2JcT) 2023/04/27(木)13:25 ID:N5pXZR7+0(1) AAS
GPT使ってないからレートが低い、みたいなセルフハンディキャップはカッコ悪すぎるからGPTくらいは賢く利用しようね
287(2): (ﾜｯﾁｮｲ 5d2d-YWDm) 2023/04/28(金)04:45 ID:9dah9Cbv0(1) AAS
A,Bの問題文を整形してChatGPTに貼り付けて反応もどってくるの待つより自分で解いたほうが速いわけ
更に投稿前にチェックも必要だし
嫁にそのやり方を教えてA,B問題の投稿を担当してもらってる間に自分はCあたりから手を付けるのほうがいいかも
288: (ﾜｯﾁｮｲ 6a55-/HYv) 2023/04/28(金)08:08 ID:Qu9Tu4Uo0(1) AAS
>>287
そんな姑息なことをするほど、競技プログラミングで良い成績をおさめることにメリットはあるんですね。
289: (ﾜｯﾁｮｲ d1a4-2JcT) 2023/04/28(金)08:22 ID:39Dn9gJ30(1) AAS
>>287
APIあるんだから全部自動化するにきまってんだろ
290: (ﾜｯﾁｮｲ 17b0-NOa+) 2023/04/29(土)23:10 ID:yZQ+uKse0(1) AAS
5完しかできなかった
Dみたいなのが地味にめんどくさい
291: (ﾌﾞｰｲﾓ MM8f-ia05) 2023/04/29(土)23:17 ID:BBFLtm1nM(1) AAS
D問題昨日勉強した内容が出てきてめっちゃ嬉しかった
これ進研ゼミでやったことある状態だったわ
292: (ﾜｯﾁｮｲ 5701-MUOW) 2023/04/30(日)00:03 ID:VtRKwrnb0(1) AAS
Gで解説と違う方針で通したから解説書こうと思ったが、一応C++でも通るか確認したらC++だとTLEだったのでやめた
C++遅いね
293: (ｽﾌｯ Sdbf-TsFU) 2023/04/30(日)01:19 ID:WQH2sNqzd(1) AAS
Patisserie ABC 3 出るかと思って過去問見直したけど全然出なかった
294(1): (ﾜｯﾁｮｲ f7db-YI8Y) 2023/05/03(水)00:51 ID:83koBp/d0(1) AAS
ngtkanaって男性？
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
６完…
今回は７完したかった…
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分遅れになってしまった…
上下前次1-新書関写板覧索設栞歴
あと 127 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.023s