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

1デフォルトの名無しさん (ｱｳｱｳｳｰ Sa77-waiq)
垢版 |
2023/03/22(水) 15:19:42.08ID:9X0hpeOca
!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
225デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/12(水) 20:36:03.56ID:AXD/P1A20
以下の問題ですが、パスするまでに1日かかりました。

atcoder.jp/contests/past202004-open/tasks/past202004_g

こういうアイディアはほとんど必要がないけれども、実装するのが大変という
問題の対処方法を教えてください。

1日かかって作成したコードは以下です：

ideone.com/NY8mNY
226デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/12(水) 20:42:57.91ID:AXD/P1A20
あ、模範解答を見たら、実装するのも実は大変じゃないんですね。
2023/04/13(木) 14:51:21.47ID:YZ8/Xbx00
>>225
> こういうアイディアはほとんど必要がないけれども、実装するのが大変という
> 問題の対処方法を教えてください。
「アイデアを出すか頑張って実装する」以外の答えが思いつかんのだが真面目に聞いてるのか？
228デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb)
垢版 |
2023/04/13(木) 16:57:11.93ID:lV5klkX+0
実装大変だなーと思ったら、自分のアイディアが悪いと思ってまず間違いないですか？

というのも、模範解答を見ると実装もシンプルな場合ばかりなので。
2023/04/13(木) 17:03:32.55ID:UbSfQqvCa
風向風速とかの簡単で面倒な問題も初期の頃はあったなあ
最近見ないけど無いと言い切る材料もない
2023/04/14(金) 00:49:29.86ID:PKpPv7DW0
土曜夕方にコドフォdiv1あるじゃん
2023/04/14(金) 00:57:35.22ID:iX1MRsL1r
普通デートするよね
2023/04/15(土) 15:22:24.86ID:J7EhpH7h0
中国にウクライナ侵攻関連で厚い助力を求めるようだな
台湾侵攻の際には、米軍を混乱させるためにロシアは北海道に、北朝鮮は南に牽制するという話もあったしそりゃそうだよな

https://www.bloomberg.co.jp/news/articles/2023-04-14/RT3MFKDWX2PT01
中国は、プーチン大統領が１年以上前にウクライナ侵攻を命じて以来初めて、国防相をロシアに派遣する。中ロの緊密な関係があらためて示唆される。

中国の李尚福国防相はロシアのショイグ国防相の招きに応じ、16日からロシア訪問を開始する。
ショイグ氏は李氏と軍事協力および世界や地域の安全保障について議論すると語ったと、ロシアの国営タス通信は報じた。
2023/04/15(土) 18:34:37.16ID:YgeZYNMw0
そうですか。中国やロシア、北朝鮮の動向は世界の平和や安全に影響を与える可能性がありますね。

最新のニュースによると、米国が中国の台湾侵攻を確実視しており、日本も中国と戦火を交える可能性があるという記事がありました。¹

また、安保理が18日に北朝鮮のICBM発射について緊急会合を開催することになりました。²

ロシアはウクライナ侵攻で敗色濃厚であり、北朝鮮の核ミサイル開発にも深刻な影響を受けているという記事もありました。³

これらの情報はあなたの興味に沿っていますか？

(1) 米国が確実視する中国の台湾侵攻、そうなれば日本も中国と戦火を .... https://jbpress.ismedia.jp/articles/-/74803?page=3 アクセス日時 4/15/2023.
(2) 安保理が18日に北朝鮮会合 ICBM発射で日米欧要請. https://www.nikkei.com/article/DGXZQOCB150XP0V10C23A4000000/ アクセス日時 4/15/2023.
(3) 敗色濃厚のロシア、北朝鮮の核ミサイル開発にも深刻な影響. https://jbpress.ismedia.jp/articles/-/74792 アクセス日時 4/15/2023.
(4) [FT]北朝鮮、ロシアに急接近 中国の思惑から離反 - 日本経済新聞. https://www.nikkei.com/article/DGXZQOCB120DR0S2A910C2000000/ アクセス日時 4/15/2023.
(5) ロシアと中国、北朝鮮情勢巡り緊密に連携 | ロイター. https://jp.reuters.com/article/northkorea-missiles-russia-idJPKCN2LM1RV アクセス日時 4/15/2023.
(6) 「中露と北朝鮮がサイバー攻撃」初の名指し…自衛隊の防衛 .... https://www.yomiuri.co.jp/politics/20210927-OYT1T50080/ アクセス日時 4/15/2023.
2023/04/15(土) 22:26:08.62ID:KbvfxJ7qM
今回のABCレート不具合で変動なしらしいな
苦手分野過ぎてAとBしか解けなかったからありがたいわ
2023/04/15(土) 22:42:31.24ID:hxYUx3pC0
5完
バグりまくるし止まりまくるし散々だった
2023/04/15(土) 22:45:28.79ID:2lW0lXjE0
>>218
調子良かったのにunratedかよ☹
2023/04/15(土) 22:55:38.71ID:2lW0lXjE0
のんびり解いてた割には暖まるなあと思ってたけどこれDDoSの影響で普段速く解く人が遅れたってことか🥶
2023/04/15(土) 23:06:02.45ID:hxYUx3pC0
あと5分あったらF修正して解けてた…
2023/04/16(日) 16:50:33.05ID:+7pzCas80
https://twitter.com/chokudai/status/1643492418497699841
マルチchokudaiサーチがダサくないと思ってるところに草生える
https://twitter.com/5chan_nel (5ch newer account)
2023/04/16(日) 18:18:14.06ID:iQzJN3tu0
研究者が自分の名前を手法に付けることは、研究コミュニティで一般的には推奨されていません。ただし、研究者が特定の手法やアルゴリズムを開発した場合、その手法が他の研究者や専門家によって引用されることがあります。この場合、研究者の名前が手法に関連付けられることがあります。
2023/04/16(日) 18:55:38.54ID:uh3dAZwl0
今回のCでどうしても3つTLEが潰せない
2023/04/16(日) 19:06:04.93ID:Ke39kkrTa
どうしても自力で解けないなら解説読んでいいんじゃね
2023/04/16(日) 22:30:54.90ID:SVYFRHN6r
もし自分でアルゴリズム開発したらかっこいい略称付けたいよね
2023/04/16(日) 22:32:11.67ID:XfEQvCuWa
>>241
俺かよ
PriorityqueやSortedSetを使わずに普通の配列やSetを使って出力時に都度ソートしたら行けた
自前のライブラリだと重すぎるみたいだな
245デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-7nfa)
垢版 |
2023/04/17(月) 08:58:02.89ID:5c7uVWzN0
Aho, Hopcroft and UllmanのThe Design and Analysis of Computer Algorithmsという
非常に古い本はもうゴミのような本でしょうか？
2023/04/17(月) 12:28:12.67ID:WWhqmq79r
今アホって言った？
2023/04/17(月) 22:20:09.89ID:5e6VxUA80
最近は自分で判断できない輩が増えてきたな。
2023/04/17(月) 22:52:26.54ID:LKkslgOL0
>>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は、歴史的な価値があるという点でゴミのような本とは言えませんが、現代のアルゴリズム研究や技術を学ぶ上で最も適切な教材ではないかもしれません。学ぶ内容に応じて、より新しいリソースや書籍を利用することを検討してみてください。
2023/04/17(月) 23:36:48.58ID:y8gbGQlA0
アルゴリズムデザイン、重版されて書店に並んでて嬉しかった
2023/04/20(木) 19:31:49.09ID:f2njLhGLa
https://mathlog.info/articles/4204

今までにない斬新なセグ木の解説記事
2023/04/20(木) 19:42:54.89ID:mhtgTGfFa
>>250
その下のスーパー某もすごいな
2023/04/21(金) 12:31:14.61ID:Oi9Mt79Gr
レートは？書いた人の
2023/04/21(金) 13:07:22.60ID:/VhDvdfwa
正確な数値はともかく灰色以外の何に見えるんだ？
2023/04/21(金) 13:16:18.21ID:wvR7tFMwr
読む価値があるか確認するために聞いたんだけど
2023/04/21(金) 13:19:22.09ID:/VhDvdfwa
ないよ
2023/04/21(金) 13:20:36.38ID:Va2XyxIX0
ないアルヨ
2023/04/21(金) 13:23:56.80ID:/VhDvdfwa
ないのかあるのかどっちだと突っ込んでほしいジジイおるな
2023/04/21(金) 13:26:33.33ID:Va2XyxIX0
ツッコんでほしいアルヨ
2023/04/21(金) 17:05:10.19ID:k2duIDVm0
関数型しか触ったことないに1ペソ
2023/04/22(土) 21:46:10.29ID:5GqLc7RXM
またUnratedやないか
誰やねんDDoSしてるやつ
こんなサイトにしても意味ないやろ
2023/04/22(土) 22:42:13.57ID:/cmb/FVj0
久しぶりにABCDEG6完😤
2023/04/22(土) 23:12:42.60ID:rVcI1++Da
中国かロシアやろな
国がらみの可能性もあるから犯人探しは無意味
2023/04/23(日) 01:27:17.24ID:moyGSSduM
意図的に狙われてるのは確かだけどなんの目的で狙ってるんやろ
2023/04/23(日) 15:36:40.71ID:60YTymnP0
C問題なんだけど解説みたいに反転させる必要ある？
一つでも-が含まれてたらoの最大長答えるだけじゃない？
つまりn未満のoの最大長答えるだけでしょ
2023/04/23(日) 15:44:39.80ID:QD8bkyZga
解答例のやり方だと反転の必要あるな
串が出てきて初めてansに入るから
2023/04/23(日) 18:46:05.86ID:MZTwl0QJ0
反転させて2回チェックすれば団子判定をシンプルにできるって意図じゃないかな
2023/04/23(日) 18:54:15.92ID:LpJKh+XVa
出題者は反転してない
どっちでもいいんじゃね
2023/04/23(日) 20:08:08.02ID:PWijjkXzM
-が入っていれば、oと-しかないのだからoは-と接してるわけで、oと-どちらかなければ-1、両方あれば連続したoの長さでいいんじゃないの？
2023/04/23(日) 20:10:50.67ID:PWijjkXzM
久し振りにやったんだけど、
rated選んだつもりなのにunratedになってたんだけど、自分が選び間違えたの？
成績よくなかったからいいんだけど
2023/04/23(日) 20:17:55.91ID:5yiVxLP00
質問タブに書いてあるけどDDOSのせいで全員unratedの無効試合になってる
2023/04/23(日) 20:18:35.89ID:5yiVxLP00
>>268
それでもいいし解けさえすればそれでなくてもいいというだけの話
2023/04/23(日) 20:39:44.51ID:PWijjkXzM
>>270
ありがと。
別にお酒に酔ってたわけじゃないのに、
なんで間違えたのかずっと悩んでたの
2023/04/23(日) 20:43:02.12ID:LpJKh+XVa
Cは正規表現で解けるな
肯定的先読み言明を使えば一回のマッチでいける
2023/04/23(日) 21:48:22.47ID:kV4uegyh0
質問タブでアナウンス送るの、知らない人にとっては分かりづらい
2023/04/25(火) 18:22:04.22ID:NfKxocHyd
Chatgptの影響ですでにレート出にくくなってるとかある？
2023/04/25(火) 18:32:28.97ID:aoA2LcV80
GPTのおかげで誰でもCくらいまでは瞬殺できるし、緑茶らへんの人にとっては影響あるんじゃない？
2023/04/25(火) 20:23:26.21ID:Nhg6f6DZa
インタラクティブ問題なら回避できるんかな
2023/04/25(火) 22:48:32.00ID:8h60ybjNd
茶色中盤くらいまではCまで早解きゲーだしまあ初心者は萎えるかもな
2023/04/26(水) 00:39:41.99ID:v/InlOgJ0
D - Find by Query
この問題の意味がわからない、運が悪いとACできないとか無いの？
2023/04/26(水) 00:44:09.42ID:v/InlOgJ0
ああ、境界を探すのか
2023/04/26(水) 04:47:13.13ID:CtDSQpU90
10 ^ 6で試せる回数が20回だから二分探索しかないんだけどこういうメタ読み辞めたいんだよな
2023/04/26(水) 04:53:12.19ID:dFoBwinZp
何なら序盤で出てくるインタラクティブ問題っていう時点でパターンが限られすぎてて8、9割二分探索(の類型)であることが推測出来る
2023/04/26(水) 14:19:57.84ID:pZKGmWvba
>>276
必ず正しい答えを出すわけじゃないから自分で直せないとペナルティ食らうぞ
2023/04/26(水) 18:10:09.71ID:hY8jXU1C0
問題公開されてても提出できなかったらどうすんの
2023/04/26(水) 18:32:26.54ID:PpfAVk7MM
茶色だけみんなchatgptで序盤の問題解いてたのか
俺もそうしようかな
2023/04/27(木) 13:25:15.77ID:N5pXZR7+0
GPT使ってないからレートが低い、みたいなセルフハンディキャップはカッコ悪すぎるからGPTくらいは賢く利用しようね
2023/04/28(金) 04:45:15.96ID:9dah9Cbv0
A,Bの問題文を整形してChatGPTに貼り付けて反応もどってくるの待つより自分で解いたほうが速いわけ
更に投稿前にチェックも必要だし
嫁にそのやり方を教えてA,B問題の投稿を担当してもらってる間に自分はCあたりから手を付けるのほうがいいかも
2023/04/28(金) 08:08:18.98ID:Qu9Tu4Uo0
>>287

そんな姑息なことをするほど、競技プログラミングで良い成績をおさめることにメリットはあるんですね。
2023/04/28(金) 08:22:56.44ID:39Dn9gJ30
>>287
APIあるんだから全部自動化するにきまってんだろ
2023/04/29(土) 23:10:27.33ID:yZQ+uKse0
5完しかできなかった
Dみたいなのが地味にめんどくさい
2023/04/29(土) 23:17:20.22ID:BBFLtm1nM
D問題昨日勉強した内容が出てきてめっちゃ嬉しかった
これ進研ゼミでやったことある状態だったわ
2023/04/30(日) 00:03:32.63ID:VtRKwrnb0
Gで解説と違う方針で通したから解説書こうと思ったが、一応C++でも通るか確認したらC++だとTLEだったのでやめた
C++遅いね
293デフォルトの名無しさん (ｽﾌｯ Sdbf-TsFU)
垢版 |
2023/04/30(日) 01:19:01.58ID:WQH2sNqzd
Patisserie ABC 3 出るかと思って過去問見直したけど全然出なかった
2023/05/03(水) 00:51:23.91ID:83koBp/d0
ngtkanaって男性？
2023/05/03(水) 04:10:47.45ID:k35m8F9T0
黄色だから野郎じゃない
296デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf)
垢版 |
2023/05/03(水) 17:06:24.93ID:aKUbjdKi0
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 であるかそうでないかを判定してください。

↑自作の問題です。
この問題って効率的なアルゴリズムが存在しますか？
2023/05/03(水) 17:43:05.99ID:C+dlbD9Z0
日本語で書いてくれ
2023/05/03(水) 19:29:13.60ID:ElyXadep0
B1とB2の直方体の数が異なる場合、B1とB2は等しくない
B1とB2の直方体の数が同じ場合、B1とB2に含まれる直方体の番号を並べ替える
各直方体の対応する要素が等しくない場合、B1とB2は等しくない
すべての直方体の対応する要素が等しい場合、B1とB2は等しい
2023/05/03(水) 19:40:48.41ID:aKUbjdKi0
B1 が1個のn次元直方体からなる集合とします。
それを2つに分けた2つのn次元直方体の和集合を B2 とします。
B1 を構成する直方体の数は 1 です。
B2 を構成する直方体の数は 2 です。
ですが、B1 = B2 です。
300デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf)
垢版 |
2023/05/03(水) 19:43:42.25ID:aKUbjdKi0
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.95ID: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 です。
302デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf)
垢版 |
2023/05/03(水) 19:49:22.48ID: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 です。
2023/05/03(水) 21:06:39.53ID:MtXxv88er
うんち！w
2023/05/04(木) 00:35:43.31ID:FFDpqzE90
併合していって無駄のない表現にできればいける？
2023/05/04(木) 01:33:09.74ID:Pbw0n2Gt0
そんなことよりn乗で増えていくのを抑えないと無理なんでは
306デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf)
垢版 |
2023/05/04(木) 02:26:58.39ID:iR6EpWdh0
2次元限定、座標は有理数限定にしたら、競プロの問題として成立しますか？
2023/05/04(木) 04:20:04.21ID:W+5O3yqN0
>>306
yukicoderで出題してみれば？
308デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-hzXf)
垢版 |
2023/05/05(金) 10:56:46.77ID: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 の部分集合の中で最大の直方体を求めよ。


この効率的な解法はありますか？
2023/05/05(金) 13:25:13.43ID:CuujTRH+0
あるよ
2023/05/05(金) 18:31:53.93ID:zrOWQZW0M
自分で解けてなければ自作の問題とは言わん
2023/05/05(金) 21:17:04.26ID:0zwWrX/A0
よくわからないけど [0, 1) の最大の区間は存在しないんだけど大丈夫そ？
2023/05/13(土) 22:41:38.39ID:WJe+G9hta
5分延長か
面白い対応するね
2023/05/14(日) 00:45:51.21ID:KvQ47IR30
攻撃を受けてもratedという前例ができたのはよかった
2023/05/14(日) 06:52:48.64ID:NgHJ91w50
コンテストモードの敗北
315デフォルトの名無しさん (ﾜｯﾁｮｲ f37c-ECSL)
垢版 |
2023/05/17(水) 05:36:16.93ID:UaIMjrrs0
>>294
女性だよ
検索したら本名とか出て来ると思うけど
2023/05/17(水) 09:19:32.53ID:tRah0iPS0
>>315
Youtubeで本人の歌声も聴けるしな
2023/05/20(土) 22:48:05.22ID:IbXAPdJ/0
６完…
今回は７完したかった…
2023/05/20(土) 23:12:12.63ID:+EVZ8y+Ka
配点割とその通りだったな
2023/05/22(月) 00:56:46.44ID:mBh1GEMi0
パフォーマンスがinfinityになった回って61以前にあった？
2023/05/27(土) 22:44:08.16ID:DM47Hxe/0
難しすぎるよ
2023/05/27(土) 23:33:38.14ID:DM47Hxe/0
コドフォもないし
2023/06/03(土) 23:01:24.39ID:i1emxrQn0
6完
mod入力ミスってたのがアホすぎる
323デフォルトの名無しさん (ﾜｯﾁｮｲ c6bd-2a7c)
垢版 |
2023/06/04(日) 16:31:49.86ID:VEMViUBd0
やっとE問題解けるようになってきた

E問題って一個一個の実行時間が長いんだな
324デフォルトの名無しさん (ﾜｯﾁｮｲ c2bd-2a7c)
垢版 |
2023/06/04(日) 17:44:29.58ID:0q9gSB9x0
競プロ有段者(強い人)に質問

Atcoderで一段階上に行くためには解説を何も見ずとも解けるレベルの一段階上を同じように解けるレベルになるまでその問題を解説だけ見て実装は全て自分で、っていう感じでひたすら練習していくっていうやり方は有効？

自分の場合はD問題は9割ガタ解けて、Eがまだ実戦では歯が立たないレベル
2023/06/04(日) 17:53:24.73ID:AGQzq0Q+0
うん
新着レスの表示
レスを投稿する

5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況