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

1 名前：デフォルトの名無しさん [2023/03/22(水) 15:19:42.08 ID:9X0hpeOca.net] !extend:checked:vvvvv:1000:512 !extend:checked:vvvvv:1000:512 !extend:checked:vvvvv:1000:512 ↑2行になるようにする 競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ 次スレは>>950 AtCoder https://atcoder.jp/ yukicoder https://yukicoder.me/ Codeforces https://codeforces.com/ CodeChef https://codechef.com/ Project Euler https://projecteuler.net/ CLIST https://clist.by/ AtCoder Problems https://kenkoooo.com/atcoder/ AtCoder Clans https://kato-hiro.github.io/AtCoderClans/ ※前スレ 競技プログラミング総合スレ 65 https://mevius.5ch.net/test/read.cgi/tech/1672026457/ VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured 237 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ c7ad-/dh0) mailto:sage [2023/04/15(土) 22:55:38.71 ID:2lW0lXjE0.net] のんびり解いてた割には暖まるなあと思ってたけどこれDDoSの影響で普段速く解く人が遅れたってことか🥶 238 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 47b0-AIBz) mailto:sage [2023/04/15(土) 23:06:02.45 ID:hxYUx3pC0.net] あと5分あったらF修正して解けてた… 239 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 4707-uZLY) mailto:sage [2023/04/16(日) 16:50:33.05 ID:+7pzCas80.net] https://twitter.com/chokudai/status/1643492418497699841 マルチchokudaiサーチがダサくないと思ってるところに草生える (deleted an unsolicited ad) 240 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 67a4-ws6F) mailto:sage [2023/04/16(日) 18:18:14.06 ID:iQzJN3tu0.net] 研究者が自分の名前を手法に付けることは、研究コミュニティで一般的には推奨されていません。ただし、研究者が特定の手法やアルゴリズムを開発した場合、その手法が他の研究者や専門家によって引用されることがあります。この場合、研究者の名前が手法に関連付けられることがあります。 241 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 072d-7nfa) mailto:sage [2023/04/16(日) 18:55:38.54 ID:uh3dAZwl0.net] 今回のCでどうしても3つTLEが潰せない 242 名前：デフォルトの名無しさん (ｱｳｱｳｳｰ Sacb-uZLY) mailto:sage [2023/04/16(日) 19:06:04.93 ID:Ke39kkrTa.net] どうしても自力で解けないなら解説読んでいいんじゃね 243 名前：デフォルトの名無しさん (ｵｯﾍﾟｹ Srfb-g0sp) mailto:sage [2023/04/16(日) 22:30:54.90 ID:SVYFRHN6r.net] もし自分でアルゴリズム開発したらかっこいい略称付けたいよね 244 名前：デフォルトの名無しさん (ｱｳｱｳｳｰ Sacb-4m2x) mailto:sage [2023/04/16(日) 22:32:11.67 ID:XfEQvCuWa.net] >>241 俺かよ PriorityqueやSortedSetを使わずに普通の配列やSetを使って出力時に都度ソートしたら行けた 自前のライブラリだと重すぎるみたいだな 245 名前：デフォルトの名無しさん [2023/04/17(月) 08:58:02.89 ID:5c7uVWzN0.net] Aho, Hopcroft and UllmanのThe Design and Analysis of Computer Algorithmsという 非常に古い本はもうゴミのような本でしょうか？ 246 名前：デフォルトの名無しさん mailto:sage [2023/04/17(月) 12:28:12.67 ID:WWhqmq79r.net] 今アホって言った？ 247 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 07da-vbZL) mailto:sage [2023/04/17(月) 22:20:09.89 ID:5e6VxUA80.net] 最近は自分で判断できない輩が増えてきたな。 248 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ c705-9i6p) mailto:sage [2023/04/17(月) 22:52:26.54 ID:LKkslgOL0.net] >>245 Aho, Hopcroft, and UllmanのThe Design and Analysis of Computer Algorithmsという本は、1974年に初版が出版された古いテキストですが、ゴミのような本とまで言うのは必ずしも適切ではありません。この本は、コンピュータアルゴリズムの設計と解析に関する初期の基本的な理論と概念をカバーしており、多くの現代のアルゴリズムの基礎となっています。しかし、この本が初版が出版されてから約半世紀が経過し、その間にコンピュータ科学やアルゴリズムに関する研究は大幅に進歩しています。例えば、機械学習、データマイニング、並列化、分散システムなどのトピックが現代のアルゴリズム研究の重要な分野となっていますが、これらはこの本では扱われていません。 この本は古典的なアルゴリズムの理解には役立ちますが、より新しいアルゴリズムや技術の発展を学ぶためには、最近出版された書籍やオンラインリソースを利用することが望ましいです。例えば、Cormen, Leiserson, Rivest, and SteinによるIntroduction to AlgorithmsやKleinberg and TardosのAlgorithm Designといった現代のテキストは、最新の研究や技術を含んでおり、現在の学習者に適した教材です。 つまり、Aho, Hopcroft, and UllmanのThe Design and Analysis of Computer Algorithmsは、歴史的な価値があるという点でゴミのような本とは言えませんが、現代のアルゴリズム研究や技術を学ぶ上で最も適切な教材ではないかもしれません。学ぶ内容に応じて、より新しいリソースや書籍を利用することを検討してみてください。 249 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 7fd6-GSlL) mailto:sage [2023/04/17(月) 23:36:48.58 ID:y8gbGQlA0.net] アルゴリズムデザイン、重版されて書店に並んでて嬉しかった 250 名前：デフォルトの名無しさん (ｱｳｱｳｳｰ Sacb-J8Vk) mailto:sage [2023/04/20(木) 19:31:49.09 ID:f2njLhGLa.net] https://mathlog.info/articles/4204 今までにない斬新なセグ木の解説記事 251 名前：デフォルトの名無しさん (ｱｳｱｳｳｰ Sacb-uZLY) mailto:sage [2023/04/20(木) 19:42:54.89 ID:mhtgTGfFa.net] >>250 その下のスーパー某もすごいな 252 名前：デフォルトの名無しさん (ｵｯﾍﾟｹ Srfb-Lcwe) mailto:sage [2023/04/21(金) 12:31:14.61 ID:Oi9Mt79Gr.net] レートは？書いた人の 253 名前：デフォルトの名無しさん (ｱｳｱｳｳｰ Sacb-uZLY) mailto:sage [2023/04/21(金) 13:07:22.60 ID:/VhDvdfwa.net] 正確な数値はともかく灰色以外の何に見えるんだ？ 254 名前：デフォルトの名無しさん (ｵｯﾍﾟｹ Srfb-Lcwe) mailto:sage [2023/04/21(金) 13:16:18.21 ID:wvR7tFMwr.net] 読む価値があるか確認するために聞いたんだけど 255 名前：デフォルトの名無しさん (ｱｳｱｳｳｰ Sacb-uZLY) mailto:sage [2023/04/21(金) 13:19:22.09 ID:/VhDvdfwa.net] ないよ 256 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ bfd7-KgtD) mailto:sage [2023/04/21(金) 13:20:36.38 ID:Va2XyxIX0.net] ないアルヨ 257 名前：デフォルトの名無しさん (ｱｳｱｳｳｰ Sacb-uZLY) mailto:sage [2023/04/21(金) 13:23:56.80 ID:/VhDvdfwa.net] ないのかあるのかどっちだと突っ込んでほしいジジイおるな 258 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ bfd7-KgtD) mailto:sage [2023/04/21(金) 13:26:33.33 ID:Va2XyxIX0.net] ツッコんでほしいアルヨ 259 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ c75f-icHo) mailto:sage [2023/04/21(金) 17:05:10.19 ID:k2duIDVm0.net] 関数型しか触ったことないに1ペソ 260 名前：デフォルトの名無しさん (ﾌﾞｰｲﾓ MM3e-Zf+n) mailto:sage [2023/04/22(土) 21:46:10.29 ID:5GqLc7RXM.net] またUnratedやないか 誰やねんDDoSしてるやつ こんなサイトにしても意味ないやろ 261 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 15b0-8fVP) mailto:sage [2023/04/22(土) 22:42:13.57 ID:/cmb/FVj0.net] 久しぶりにABCDEG6完😤 262 名前：デフォルトの名無しさん (ｱｳｱｳｳｰ Sa21-m1As) mailto:sage [2023/04/22(土) 23:12:42.60 ID:rVcI1++Da.net] 中国かロシアやろな 国がらみの可能性もあるから犯人探しは無意味 263 名前：デフォルトの名無しさん mailto:sage [2023/04/23(日) 01:27:17.24 ID:moyGSSduM.net] 意図的に狙われてるのは確かだけどなんの目的で狙ってるんやろ 264 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 5d2d-YWDm) mailto:sage [2023/04/23(日) 15:36:40.71 ID:60YTymnP0.net] C問題なんだけど解説みたいに反転させる必要ある？ 一つでも-が含まれてたらoの最大長答えるだけじゃない？ つまりn未満のoの最大長答えるだけでしょ 265 名前：デフォルトの名無しさん (ｱｳｱｳｳｰ Sa21-m1As) mailto:sage [2023/04/23(日) 15:44:39.80 ID:QD8bkyZga.net] 解答例のやり方だと反転の必要あるな 串が出てきて初めてansに入るから 266 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ e5ad-8MXh) mailto:sage [2023/04/23(日) 18:46:05.86 ID:MZTwl0QJ0.net] 反転させて2回チェックすれば団子判定をシンプルにできるって意図じゃないかな 267 名前：デフォルトの名無しさん (ｱｳｱｳｳｰ Sa21-ZiWf) mailto:sage [2023/04/23(日) 18:54:15.92 ID:LpJKh+XVa.net] 出題者は反転してない どっちでもいいんじゃね 268 名前：デフォルトの名無しさん (ﾌﾞｰｲﾓ MM3e-oS25) mailto:sage [2023/04/23(日) 20:08:08.02 ID:PWijjkXzM.net] -が入っていれば、oと-しかないのだからoは-と接してるわけで、oと-どちらかなければ-1、両方あれば連続したoの長さでいいんじゃないの？ 269 名前：デフォルトの名無しさん (ﾌﾞｰｲﾓ MM3e-oS25) mailto:sage [2023/04/23(日) 20:10:50.67 ID:PWijjkXzM.net] 久し振りにやったんだけど、 rated選んだつもりなのにunratedになってたんだけど、自分が選び間違えたの？ 成績よくなかったからいいんだけど 270 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 1507-ZiWf) mailto:sage [2023/04/23(日) 20:17:55.91 ID:5yiVxLP00.net] 質問タブに書いてあるけどDDOSのせいで全員unratedの無効試合になってる 271 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 1507-ZiWf) mailto:sage [2023/04/23(日) 20:18:35.89 ID:5yiVxLP00.net] >>268 それでもいいし解けさえすればそれでなくてもいいというだけの話 272 名前：デフォルトの名無しさん (ﾌﾞｰｲﾓ MM3e-oS25) mailto:sage [2023/04/23(日) 20:39:44.51 ID:PWijjkXzM.net] >>270 ありがと。 別にお酒に酔ってたわけじゃないのに、 なんで間違えたのかずっと悩んでたの 273 名前：デフォルトの名無しさん (ｱｳｱｳｳｰ Sa21-ZiWf) mailto:sage [2023/04/23(日) 20:43:02.12 ID:LpJKh+XVa.net] Cは正規表現で解けるな 肯定的先読み言明を使えば一回のマッチでいける 274 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 7d01-8Z+s) mailto:sage [2023/04/23(日) 21:48:22.47 ID:kV4uegyh0.net] 質問タブでアナウンス送るの、知らない人にとっては分かりづらい 275 名前：デフォルトの名無しさん (ｽﾌｯ Sd0a-hie5) mailto:sage [2023/04/25(火) 18:22:04.22 ID:NfKxocHyd.net] Chatgptの影響ですでにレート出にくくなってるとかある？ 276 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ e505-2JcT) mailto:sage [2023/04/25(火) 18:32:28.97 ID:aoA2LcV80.net] GPTのおかげで誰でもCくらいまでは瞬殺できるし、緑茶らへんの人にとっては影響あるんじゃない？ 277 名前：デフォルトの名無しさん (ｱｳｱｳｳｰ Sa21-9VOY) mailto:sage [2023/04/25(火) 20:23:26.21 ID:Nhg6f6DZa.net] インタラクティブ問題なら回避できるんかな 278 名前：デフォルトの名無しさん (ｽｯﾌﾟ Sd0a-PPLO) mailto:sage [2023/04/25(火) 22:48:32.00 ID:8h60ybjNd.net] 茶色中盤くらいまではCまで早解きゲーだしまあ初心者は萎えるかもな 279 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 5d2d-YWDm) mailto:sage [2023/04/26(水) 00:39:41.99 ID:v/InlOgJ0.net] D - Find by Query この問題の意味がわからない、運が悪いとACできないとか無いの？ 280 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 5d2d-YWDm) mailto:sage [2023/04/26(水) 00:44:09.42 ID:v/InlOgJ0.net] ああ、境界を探すのか 281 名前：デフォルトの名無しさん mailto:sage [2023/04/26(水) 04:47:13.13 ID:CtDSQpU90.net] 10 ^ 6で試せる回数が20回だから二分探索しかないんだけどこういうメタ読み辞めたいんだよな 282 名前：デフォルトの名無しさん mailto:sage [2023/04/26(水) 04:53:12.19 ID:dFoBwinZp.net] 何なら序盤で出てくるインタラクティブ問題っていう時点でパターンが限られすぎてて8、9割二分探索(の類型)であることが推測出来る 283 名前：デフォルトの名無しさん mailto:sage [2023/04/26(水) 14:19:57.84 ID:pZKGmWvba.net] >>276 必ず正しい答えを出すわけじゃないから自分で直せないとペナルティ食らうぞ 284 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 7d01-8Z+s) mailto:sage [2023/04/26(水) 18:10:09.71 ID:hY8jXU1C0.net] 問題公開されてても提出できなかったらどうすんの 285 名前：デフォルトの名無しさん (ﾌﾞｰｲﾓ MM3e-Zf+n) mailto:sage [2023/04/26(水) 18:32:26.54 ID:PpfAVk7MM.net] 茶色だけみんなchatgptで序盤の問題解いてたのか 俺もそうしようかな 286 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ e505-2JcT) mailto:sage [2023/04/27(木) 13:25:15.77 ID:N5pXZR7+0.net] GPT使ってないからレートが低い、みたいなセルフハンディキャップはカッコ悪すぎるからGPTくらいは賢く利用しようね 287 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 5d2d-YWDm) mailto:sage [2023/04/28(金) 04:45:15.96 ID:9dah9Cbv0.net] A,Bの問題文を整形してChatGPTに貼り付けて反応もどってくるの待つより自分で解いたほうが速いわけ 更に投稿前にチェックも必要だし 嫁にそのやり方を教えてA,B問題の投稿を担当してもらってる間に自分はCあたりから手を付けるのほうがいいかも 288 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-/HYv) mailto:sage [2023/04/28(金) 08:08:18.98 ID:Qu9Tu4Uo0.net] >>287 そんな姑息なことをするほど、競技プログラミングで良い成績をおさめることにメリットはあるんですね。 289 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ d1a4-2JcT) mailto:sage [2023/04/28(金) 08:22:56.44 ID:39Dn9gJ30.net] >>287 APIあるんだから全部自動化するにきまってんだろ 290 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 17b0-NOa+) mailto:sage [2023/04/29(土) 23:10:27.33 ID:yZQ+uKse0.net] 5完しかできなかった Dみたいなのが地味にめんどくさい 291 名前：デフォルトの名無しさん (ﾌﾞｰｲﾓ MM8f-ia05) mailto:sage [2023/04/29(土) 23:17:20.22 ID:BBFLtm1nM.net] D問題昨日勉強した内容が出てきてめっちゃ嬉しかった これ進研ゼミでやったことある状態だったわ 292 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 5701-MUOW) mailto:sage [2023/04/30(日) 00:03:32.63 ID:VtRKwrnb0.net] Gで解説と違う方針で通したから解説書こうと思ったが、一応C++でも通るか確認したらC++だとTLEだったのでやめた C++遅いね 293 名前：デフォルトの名無しさん (ｽﾌｯ Sdbf-TsFU) [2023/04/30(日) 01:19:01.58 ID:WQH2sNqzd.net] Patisserie ABC 3 出るかと思って過去問見直したけど全然出なかった 294 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ f7db-YI8Y) mailto:sage [2023/05/03(水) 00:51:23.91 ID:83koBp/d0.net] ngtkanaって男性？ 295 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 97ad-muTB) mailto:sage [2023/05/03(水) 04:10:47.45 ID:k35m8F9T0.net] 黄色だから野郎じゃない 296 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf) [2023/05/03(水) 17:06:24.93 ID:aKUbjdKi0.net] 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) mailto:sage [2023/05/03(水) 17:43:05.99 ID:C+dlbD9Z0.net] 日本語で書いてくれ 298 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 572d-wHlW) mailto:sage [2023/05/03(水) 19:29:13.60 ID:ElyXadep0.net] B1とB2の直方体の数が異なる場合、B1とB2は等しくない B1とB2の直方体の数が同じ場合、B1とB2に含まれる直方体の番号を並べ替える 各直方体の対応する要素が等しくない場合、B1とB2は等しくない すべての直方体の対応する要素が等しい場合、B1とB2は等しい 299 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf) mailto:sage [2023/05/03(水) 19:40:48.41 ID:aKUbjdKi0.net] B1 が1個のn次元直方体からなる集合とします。 それを2つに分けた2つのn次元直方体の和集合を B2 とします。 B1 を構成する直方体の数は 1 です。 B2 を構成する直方体の数は 2 です。 ですが、B1 = B2 です。 300 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf) [2023/05/03(水) 19:43:42.25 ID:aKUbjdKi0.net] 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 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf) [2023/05/03(水) 19:48:56.95 ID:aKUbjdKi0.net] 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:22.48 ID:aKUbjdKi0.net] >>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) mailto:sage [2023/05/03(水) 21:06:39.53 ID:MtXxv88er.net] うんち！w 304 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 5701-MUOW) mailto:sage [2023/05/04(木) 00:35:43.31 ID:FFDpqzE90.net] 併合していって無駄のない表現にできればいける？ 305 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 375f-k3Rv) mailto:sage [2023/05/04(木) 01:33:09.74 ID:Pbw0n2Gt0.net] そんなことよりn乗で増えていくのを抑えないと無理なんでは 306 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf) [2023/05/04(木) 02:26:58.39 ID:iR6EpWdh0.net] 2次元限定、座標は有理数限定にしたら、競プロの問題として成立しますか？ 307 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 572d-wHlW) mailto:sage [2023/05/04(木) 04:20:04.21 ID:W+5O3yqN0.net] >>306 yukicoderで出題してみれば？ 308 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf) [2023/05/05(金) 10:56:46.77 ID:xYbtWehf0.net] >>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 の部分集合の中で最大の直方体を求めよ。 この効率的な解法はありますか？ 309 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ bfd7-E7B+) mailto:sage [2023/05/05(金) 13:25:13.43 ID:CuujTRH+0.net] あるよ 310 名前：デフォルトの名無しさん (ﾌﾞｰｲﾓ MMab-8WUk) mailto:sage [2023/05/05(金) 18:31:53.93 ID:zrOWQZW0M.net] 自分で解けてなければ自作の問題とは言わん 311 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 375f-67at) mailto:sage [2023/05/05(金) 21:17:04.26 ID:0zwWrX/A0.net] よくわからないけど [0, 1) の最大の区間は存在しないんだけど大丈夫そ？ 312 名前：デフォルトの名無しさん [2023/05/14(日) 13:25:49.39 ID:0RYyu89NT] 曰本に原爆落とした世界最悪のならす゛者ヒステリ一國家の犬コ口ジャップと違って世界中に氣球飛ばしてる習近平を全面的に支持しようぜ 都心まて゛数珠つなき゛て゛クソ航空機飛は゛しまくって，クソポリ公は威力業務妨害へリ飛は゛しまくって仕事に勉強にと妨害して住民の神経破壞 して犯罪惹起してるし，温室効果ガスに騒音にコ□ナにとまき散らして氣侯変動させて災害連發させて國土に國力にと破壊して人殺して 私権侵害して私腹を肥やす史上最悪の強盜殺人の首魁齊藤鉄夫ら殺人腐敗テ口リストに乗っ取られたクソ曰本全國と゛こからでも２４時間 必す゛クソシナの気球が見えるくらいに飛は゛しまくってクソ航空機を根絶やしにしてくれたら、離島全部クソシナの領土ってことでいいよな 何が領空侵犯だ、撃墜すへ゛きは何も住民に危害を加えていない氣球て゛はなく，四六時中グ儿ク゛ル私権侵害しまくってるクソポリ公へリた゛ろ 専制主義と民主主義の対立た゛の言ってるハ゛力か゛いるが，地球破壞して私権侵害して私腹を肥やす強盜殺人テ口國家との対立というのか゛正解 民主主義とは銃刀法などなく個人がスティンカ゛−を所持して，平穏な生活を妨害するテ□リス├から身を守る権利か゛住民にある社會た゛ボケ 創価学会員は、何百萬人も殺傷して損害を与えて私腹を肥やし続けて逮捕者まで出てる世界最悪の殺人腐敗組織公明党を 池田センセ―が□をきけて容認するとか本氣て゛思ってるとしたら侮辱にもほどがあるぞ！ ｈＴТрｓ：／／ｉ．ｉｍｇｕｒ，сοｍ／hnli1ga.jpeg 313 名前：デフォルトの名無しさん mailto:sage [2023/05/13(土) 22:41:38.39 ID:WJe+G9hta.net] 5分延長か 面白い対応するね 314 名前：デフォルトの名無しさん mailto:sage [2023/05/14(日) 00:45:51.21 ID:KvQ47IR30.net] 攻撃を受けてもratedという前例ができたのはよかった 315 名前：デフォルトの名無しさん mailto:sage [2023/05/14(日) 06:52:48.64 ID:NgHJ91w50.net] コンテストモードの敗北 316 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ f37c-ECSL) [2023/05/17(水) 05:36:16.93 ID:UaIMjrrs0.net] >>294 女性だよ 検索したら本名とか出て来ると思うけど 317 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ a32d-+/XS) mailto:sage [2023/05/17(水) 09:19:32.53 ID:tRah0iPS0.net] >>316 Youtubeで本人の歌声も聴けるしな 318 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ d3b0-SwK+) mailto:sage [2023/05/20(土) 22:48:05.22 ID:IbXAPdJ/0.net] ６完… 今回は７完したかった… 319 名前：デフォルトの名無しさん (ｱｳｱｳｳｰ Sa2f-o1RM) mailto:sage [2023/05/20(土) 23:12:12.63 ID:+EVZ8y+Ka.net] 配点割とその通りだったな 320 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 57db-3XON) mailto:sage [2023/05/22(月) 00:56:46.44 ID:mBh1GEMi0.net] パフォーマンスがinfinityになった回って61以前にあった？ 321 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ abb0-IOpb) mailto:sage [2023/05/27(土) 22:44:08.16 ID:DM47Hxe/0.net] 難しすぎるよ 322 名前：デフォルトの名無しさん mailto:sage [2023/05/27(土) 23:33:38.14 ID:DM47Hxe/0.net] コドフォもないし 323 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ 99b0-AV1S) mailto:sage [2023/06/03(土) 23:01:24.39 ID:i1emxrQn0.net] 6完 mod入力ミスってたのがアホすぎる 324 名前：デフォルトの名無しさん [2023/06/04(日) 16:31:49.86 ID:VEMViUBd0.net] やっとE問題解けるようになってきた E問題って一個一個の実行時間が長いんだな 325 名前：デフォルトの名無しさん [2023/06/04(日) 17:44:29.58 ID:0q9gSB9x0.net] 競プロ有段者(強い人)に質問 Atcoderで一段階上に行くためには解説を何も見ずとも解けるレベルの一段階上を同じように解けるレベルになるまでその問題を解説だけ見て実装は全て自分で、っていう感じでひたすら練習していくっていうやり方は有効？ 自分の場合はD問題は9割ガタ解けて、Eがまだ実戦では歯が立たないレベル 326 名前：デフォルトの名無しさん mailto:sage [2023/06/04(日) 17:53:24.73 ID:AGQzq0Q+0.net] うん 327 名前：デフォルトの名無しさん [2023/06/04(日) 20:29:27.17 ID:z/tZxQvT0.net] E問題思ったより簡単だな 食わず嫌いしてた 328 名前：デフォルトの名無しさん mailto:sage [2023/06/06(火) 11:53:03.19 ID:MhCqkbZk0.net] 某所で「左右がバランスした括弧の列を生成する」という問題があり、解答が 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; が左右のバランス（単に'('と')'の数が同じというだけでなく）の条件に 効いているようですが、ピンとこないのです... 確かに正しい括弧の列のとき、それが成り 立つのはわかりますが、逆にそれがバランス条件を満たすのに十分であるというのが　 どなたかわかりやすい説明はないでしょうか 329 名前：デフォルトの名無しさん mailto:sage [2023/06/06(火) 12:29:54.00 ID:GQVo4dJ/a.net] しょーもない処理を複雑に描いてるだけのクソプログラムやな この関数は最初の呼び出しでlとrが同じ数字なるよう入れるのが前提で r<lの条件は例外処理みたいなもんやろ 330 名前：デフォルトの名無しさん mailto:sage [2023/06/06(火) 12:35:33.96 ID:UncR9VmG0.net] このコードの一部 `if (r < l) return;` について説明します。 ここで `l` と `r` はそれぞれまだ追加できる '(' の数と ')' の数を表しています。なので、このチェック `if (r < l) return;` は、')' の数が '(' の数より少なくなる場合、すなわち、開き括弧より閉じ括弧が少なくなる場合を防いでいます。 正しい括弧の列を生成するためには、2つの重要なルールを守らなければなりません： 1. 左括弧と右括弧の数が等しいこと 2. 任意の時点で、右括弧の数が左括弧の数を超えないこと 1つ目のルールは、左括弧と右括弧を同数だけ生成すれば満たされます。しかし、2つ目のルールはもう少し注意が必要です。それは、どの時点でも、閉じ括弧の数が開き括弧の数を超えてはならないからです。これを超えてしまうと、括弧の列が無効になってしまいます。 例えば、"())(" のような列は、開き括弧と閉じ括弧の数は同じでも、2番目の閉じ括弧が開き括弧を超えているため、無効な括弧の列となります。 だからこそ、`if (r < l) return;` のチェックが必要なのです。これにより、閉じ括弧の数が開き括弧を超えるような状況を防いでいます。これは、まだ追加できる閉じ括弧の数 `r` が、開き括弧 `l` より少なくなる場合、すなわち、閉じ括弧が開き括弧を超える可能性がある場合に、そのパスをすぐに終了させることで実現されています。 331 名前：デフォルトの名無しさん mailto:sage [2023/06/06(火) 12:49:04.77 ID:FRsr3KcUH.net] (を+1)を-1と対応させて累積和が常に非負っていうのがバランスしていることの必要十分条件であることを認めれば if(r < l)return; がそれの言い換えなことは明らか 証明したければ累積和が0になるところで文字列を分割して、それぞれの文字列の一番外側の括弧を取り外すとネストが一つ浅いものに帰着できるからネストの深さで帰納法を回すみたいなことを気をつけてやるといいんじゃないか 332 名前：デフォルトの名無しさん mailto:sage [2023/06/07(水) 08:00:55.26 ID:nPOLblkw0.net] >>330はChatGPTなのかな? すごいな >>331 どうもありがとうございます このコードの場合、再帰時に常に右側に括弧を追加することが if (r < l) return; で 必要十分になることの前提だと思うんですが.... >>330はそのことがうやむやのような 333 名前：デフォルトの名無しさん mailto:sage [2023/06/07(水) 08:33:42.08 ID:nPOLblkw0.net] >>328のコードとは別に、 (と)をそれぞれ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の(())を二つ並べた、と考えるべき? 要は、正しい括弧の追加操作のみをして再帰的に括弧列を生成することは可能なのか? あるいは単にすべてのパターンを生成して正当でないのを刈り取ることしかできないのか? などということが気になったのですが 334 名前：デフォルトの名無しさん mailto:sage [2023/06/07(水) 09:49:06.82 ID:Bta2HQ7X0.net] >>333 結論から言うと、それは難しい問題であり、一般的なアプローチでは、「全てのパターンを生成し、 それがバランスの取れた括弧列であるかどうかを判定する」という方法が用いられます。 しかし、バランスの取れた括弧列を生成するための一種の再帰的なパターンは存在します。 それは、大きさnの全てのバランスの取れた括弧列を生成した後で、その各々に対して以下の操作を行うことです： 1. '(' + P + ')' を追加する 2. P + '()' を追加する 3. '()' + P を追加する ここで P は大きさnの任意のバランスの取れた括弧列です。 この操作を行うと、全ての大きさn+1のバランスの取れた括弧列を生成することができます。 ただし、これは重複する列を生成する可能性があるため、生成された列は一意であることを保証するために 何らかの方法で重複を除去する必要があります。 したがって、厳密には「全てのパターンを生成し、それがバランスの取れた括弧列であるかどうかを判定する」 という方法とは異なりますが、これは一種の再帰的なアプローチと言えます。 しかし、これらのアプローチは計算時間やメモリ使用量の観点から見ると、>>328に示されたDFSを用いたアプローチに比べて 効率的ではないかもしれません。また、DFSを用いたアプローチは明確に「正しい括弧の追加操作のみ」を行っていると言えます。 なぜなら、すべての括弧列を生成する過程で、同時にその列が正しい括弧列であるかどうかをチェックすることが可能だからです。 335 名前：デフォルトの名無しさん mailto:sage [2023/06/07(水) 10:10:41.04 ID:WomvMCD50.net] >>333 >>334 は嘘 バランスした括弧列の定義は全体を括弧で囲む操作と括弧列2つの結合で生成される集合だから、その()を追加するっていうのを右か左に追加するって意味だとするとレベル2以上の文字列同士の結合が考慮されていないの で、(())(())が作れない 中に()を挿入することを許すとすると、今度は全体を括弧で囲む操作はいらなくなる というのも、どんな空でないバランスした括弧列にも()の部分があるから、それを取り除くことを繰り返すことで空にできるから、逆に空文字列に()を追加していくことで任意のバランスした括弧列が作れるし、バランスした括弧列の任意の箇所に()を挿入した文字列もまたバランスした括弧列になっている 336 名前：デフォルトの名無しさん mailto:sage [2023/06/07(水) 11:08:01.09 ID:DYKBdUd80.net] >>332 ご指摘の通り、このコードでは再帰的に右側に括弧を追加しています。具体的には、まず左括弧を追加し、その後で右括弧を追加しています。 この if (r < l) return; の制約は、この追加の順序に基づいています。開始時点では、開き括弧と閉じ括弧の数が等しく（つまり、l == r）、左括弧を先に追加します。そのため、追加の過程では一時的に l が r より小さくなります。しかし、その後すぐに右括弧を追加することでバランスを保ちます。 if (r < l) return; のチェックにより、右括弧が先に追加される（つまり、r < l となる）状況を防いでいます。これは、左括弧を追加した後でのみ右括弧を追加するという、このコードの括弧の追加の順序を反映しています。そのため、この制約が満たされない場合（つまり、右括弧が先に追加される場合）、そのパスは無効となり、すぐに終了します。 したがって、この if (r < l) return; の制約は、このコードの括弧の追加の順序に基づいて、左括弧と右括弧が正しくバランスを保つことを保証しています。 337 名前：デフォルトの名無しさん mailto:sage [2023/06/07(水) 14:48:36.26 ID:w+aRYGw/r.net] 非負のランダムウォーク書いて+1-1を()に対応させるだけだろ

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef