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

2023/04/12(水) 09:07:44.12

今IT系とは全く別の職種だから転職したくてAtCoder始めたけど楽しいな
未経験で他職種に転職出来るのか分からんけど

2023/04/12(水) 09:21:22.65

>>216
2分探索することは確定でそこで発見できるのにそれに加えてわざわざ他の集合を使う意味とは？

2023/04/12(水) 09:24:04.21

>>217
最低緑以上になればJobsで転職できる可能性はあるが緑っていっぱいいるので年齢や運が絡むかもな

2023/04/12(水) 09:48:33.24

>>219
ありがとう
数学好きでアルゴリズムも昔やったことあったから緑まではすんなりいけたわ
今は水色目指して色々やってるけどアルゴリズム的要素より数学要素のほうが多く感じるな
年齢は25だからあと3年位がギリギリかなあと思ってる

2023/04/12(水) 10:00:29.60

水より緑の方が採用しやすい
ほんとに転職したいなら水まで行ったらとか思わない方がいい

2023/04/12(水) 12:09:52.88

>>221
今年色々あって復職したてだから転職活動するなら来年以降かもしれんわ、一応ビズリーチとか登録はしたけど
水色より緑のほうが採用しやすいのはなぜ？

2023/04/12(水) 17:15:55.13

今から狂気プログラミング始めるならPythonでいいかな、

2023/04/12(水) 18:22:04.45

brainfuckがいいと思うよ

2023/04/12(水) 20:36:03.56

以下の問題ですが、パスするまでに1日かかりました。

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

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

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

ideone.com/NY8mNY

2023/04/12(水) 20:42:57.91

あ、模範解答を見たら、実装するのも実は大変じゃないんですね。

2023/04/13(木) 14:51:21.47

>>225
> こういうアイディアはほとんど必要がないけれども、実装するのが大変という
> 問題の対処方法を教えてください。
「アイデアを出すか頑張って実装する」以外の答えが思いつかんのだが真面目に聞いてるのか？

2023/04/13(木) 16:57:11.93

実装大変だなーと思ったら、自分のアイディアが悪いと思ってまず間違いないですか？

というのも、模範解答を見ると実装もシンプルな場合ばかりなので。

2023/04/13(木) 17:03:32.55

風向風速とかの簡単で面倒な問題も初期の頃はあったなあ
最近見ないけど無いと言い切る材料もない

2023/04/14(金) 00:49:29.86

土曜夕方にコドフォdiv1あるじゃん

2023/04/14(金) 00:57:35.22

普通デートするよね

2023/04/15(土) 15:22:24.86

中国にウクライナ侵攻関連で厚い助力を求めるようだな
台湾侵攻の際には、米軍を混乱させるためにロシアは北海道に、北朝鮮は南に牽制するという話もあったしそりゃそうだよな

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

中国の李尚福国防相はロシアのショイグ国防相の招きに応じ、16日からロシア訪問を開始する。
ショイグ氏は李氏と軍事協力および世界や地域の安全保障について議論すると語ったと、ロシアの国営タス通信は報じた。

2023/04/15(土) 18:34:37.16

そうですか。中国やロシア、北朝鮮の動向は世界の平和や安全に影響を与える可能性がありますね。

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

また、安保理が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.62

今回のABCレート不具合で変動なしらしいな
苦手分野過ぎてAとBしか解けなかったからありがたいわ

2023/04/15(土) 22:42:31.24

5完
バグりまくるし止まりまくるし散々だった

2023/04/15(土) 22:45:28.79

>>218
調子良かったのにunratedかよ☹

2023/04/15(土) 22:55:38.71

のんびり解いてた割には暖まるなあと思ってたけどこれDDoSの影響で普段速く解く人が遅れたってことか🥶

2023/04/15(土) 23:06:02.45

あと5分あったらF修正して解けてた…

2023/04/16(日) 16:50:33.05

https://twitter.com/chokudai/status/1643492418497699841
マルチchokudaiサーチがダサくないと思ってるところに草生える
https://twitter.com/5chan_nel (5ch newer account)

2023/04/16(日) 18:18:14.06

研究者が自分の名前を手法に付けることは、研究コミュニティで一般的には推奨されていません。ただし、研究者が特定の手法やアルゴリズムを開発した場合、その手法が他の研究者や専門家によって引用されることがあります。この場合、研究者の名前が手法に関連付けられることがあります。

2023/04/16(日) 18:55:38.54

今回のCでどうしても3つTLEが潰せない

2023/04/16(日) 19:06:04.93

どうしても自力で解けないなら解説読んでいいんじゃね

2023/04/16(日) 22:30:54.90

もし自分でアルゴリズム開発したらかっこいい略称付けたいよね

2023/04/16(日) 22:32:11.67

>>241
俺かよ
PriorityqueやSortedSetを使わずに普通の配列やSetを使って出力時に都度ソートしたら行けた
自前のライブラリだと重すぎるみたいだな

2023/04/17(月) 08:58:02.89

Aho, Hopcroft and UllmanのThe Design and Analysis of Computer Algorithmsという
非常に古い本はもうゴミのような本でしょうか？

2023/04/17(月) 12:28:12.67

今アホって言った？

2023/04/17(月) 22:20:09.89

最近は自分で判断できない輩が増えてきたな。

2023/04/17(月) 22:52:26.54

>>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.58

アルゴリズムデザイン、重版されて書店に並んでて嬉しかった

2023/04/20(木) 19:31:49.09

https://mathlog.info/articles/4204

今までにない斬新なセグ木の解説記事

2023/04/20(木) 19:42:54.89

>>250
その下のスーパー某もすごいな

2023/04/21(金) 12:31:14.61

レートは？書いた人の

2023/04/21(金) 13:07:22.60

正確な数値はともかく灰色以外の何に見えるんだ？

2023/04/21(金) 13:16:18.21

読む価値があるか確認するために聞いたんだけど

2023/04/21(金) 13:19:22.09

ないよ

2023/04/21(金) 13:20:36.38

ないアルヨ

2023/04/21(金) 13:23:56.80

ないのかあるのかどっちだと突っ込んでほしいジジイおるな

2023/04/21(金) 13:26:33.33

ツッコんでほしいアルヨ

2023/04/21(金) 17:05:10.19

関数型しか触ったことないに1ペソ

2023/04/22(土) 21:46:10.29

またUnratedやないか
誰やねんDDoSしてるやつ
こんなサイトにしても意味ないやろ

2023/04/22(土) 22:42:13.57

久しぶりにABCDEG6完😤

2023/04/22(土) 23:12:42.60

中国かロシアやろな
国がらみの可能性もあるから犯人探しは無意味

2023/04/23(日) 01:27:17.24

意図的に狙われてるのは確かだけどなんの目的で狙ってるんやろ

2023/04/23(日) 15:36:40.71

C問題なんだけど解説みたいに反転させる必要ある？
一つでも-が含まれてたらoの最大長答えるだけじゃない？
つまりn未満のoの最大長答えるだけでしょ

2023/04/23(日) 15:44:39.80

解答例のやり方だと反転の必要あるな
串が出てきて初めてansに入るから

2023/04/23(日) 18:46:05.86

反転させて2回チェックすれば団子判定をシンプルにできるって意図じゃないかな

2023/04/23(日) 18:54:15.92

出題者は反転してない
どっちでもいいんじゃね

2023/04/23(日) 20:08:08.02

-が入っていれば、oと-しかないのだからoは-と接してるわけで、oと-どちらかなければ-1、両方あれば連続したoの長さでいいんじゃないの？

2023/04/23(日) 20:10:50.67

久し振りにやったんだけど、
rated選んだつもりなのにunratedになってたんだけど、自分が選び間違えたの？
成績よくなかったからいいんだけど

2023/04/23(日) 20:17:55.91

質問タブに書いてあるけどDDOSのせいで全員unratedの無効試合になってる

2023/04/23(日) 20:18:35.89

>>268
それでもいいし解けさえすればそれでなくてもいいというだけの話

2023/04/23(日) 20:39:44.51

>>270
ありがと。
別にお酒に酔ってたわけじゃないのに、
なんで間違えたのかずっと悩んでたの

2023/04/23(日) 20:43:02.12

Cは正規表現で解けるな
肯定的先読み言明を使えば一回のマッチでいける

2023/04/23(日) 21:48:22.47

質問タブでアナウンス送るの、知らない人にとっては分かりづらい

**デフォルトの名無しさん** (ｽﾌｯ Sd0a-hie5) · 2023/04/25(火) 18:22:04.22

Chatgptの影響ですでにレート出にくくなってるとかある？

2023/04/25(火) 18:32:28.97

GPTのおかげで誰でもCくらいまでは瞬殺できるし、緑茶らへんの人にとっては影響あるんじゃない？

2023/04/25(火) 20:23:26.21

インタラクティブ問題なら回避できるんかな

2023/04/25(火) 22:48:32.00

茶色中盤くらいまではCまで早解きゲーだしまあ初心者は萎えるかもな

2023/04/26(水) 00:39:41.99

D - Find by Query
この問題の意味がわからない、運が悪いとACできないとか無いの？

2023/04/26(水) 00:44:09.42

ああ、境界を探すのか

2023/04/26(水) 04:47:13.13

10 ^ 6で試せる回数が20回だから二分探索しかないんだけどこういうメタ読み辞めたいんだよな

2023/04/26(水) 04:53:12.19

何なら序盤で出てくるインタラクティブ問題っていう時点でパターンが限られすぎてて8、9割二分探索(の類型)であることが推測出来る

2023/04/26(水) 14:19:57.84

>>276
必ず正しい答えを出すわけじゃないから自分で直せないとペナルティ食らうぞ

2023/04/26(水) 18:10:09.71

問題公開されてても提出できなかったらどうすんの

2023/04/26(水) 18:32:26.54

茶色だけみんなchatgptで序盤の問題解いてたのか
俺もそうしようかな

2023/04/27(木) 13:25:15.77

GPT使ってないからレートが低い、みたいなセルフハンディキャップはカッコ悪すぎるからGPTくらいは賢く利用しようね

2023/04/28(金) 04:45:15.96

A,Bの問題文を整形してChatGPTに貼り付けて反応もどってくるの待つより自分で解いたほうが速いわけ
更に投稿前にチェックも必要だし
嫁にそのやり方を教えてA,B問題の投稿を担当してもらってる間に自分はCあたりから手を付けるのほうがいいかも

2023/04/28(金) 08:08:18.98

>>287

そんな姑息なことをするほど、競技プログラミングで良い成績をおさめることにメリットはあるんですね。

2023/04/28(金) 08:22:56.44

>>287
APIあるんだから全部自動化するにきまってんだろ

2023/04/29(土) 23:10:27.33

5完しかできなかった
Dみたいなのが地味にめんどくさい

2023/04/29(土) 23:17:20.22

D問題昨日勉強した内容が出てきてめっちゃ嬉しかった
これ進研ゼミでやったことある状態だったわ

2023/04/30(日) 00:03:32.63

Gで解説と違う方針で通したから解説書こうと思ったが、一応C++でも通るか確認したらC++だとTLEだったのでやめた
C++遅いね

**デフォルトの名無しさん** (ｽﾌｯ Sdbf-TsFU) · 2023/04/30(日) 01:19:01.58

Patisserie ABC 3 出るかと思って過去問見直したけど全然出なかった

2023/05/03(水) 00:51:23.91

ngtkanaって男性？

2023/05/03(水) 04:10:47.45

黄色だから野郎じゃない

2023/05/03(水) 17:06:24.93

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.99

日本語で書いてくれ

2023/05/03(水) 19:29:13.60

B1とB2の直方体の数が異なる場合、B1とB2は等しくない
B1とB2の直方体の数が同じ場合、B1とB2に含まれる直方体の番号を並べ替える
各直方体の対応する要素が等しくない場合、B1とB2は等しくない
すべての直方体の対応する要素が等しい場合、B1とB2は等しい

2023/05/03(水) 19:40:48.41

B1 が1個のn次元直方体からなる集合とします。
それを2つに分けた2つのn次元直方体の和集合を B2 とします。
B1 を構成する直方体の数は 1 です。
B2 を構成する直方体の数は 2 です。
ですが、B1 = B2 です。

2023/05/03(水) 19:43:42.25

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 です。

2023/05/03(水) 19:48:56.95

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 です。

2023/05/03(水) 19:49:22.48

>>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.53

うんち！w

2023/05/04(木) 00:35:43.31

併合していって無駄のない表現にできればいける？

2023/05/04(木) 01:33:09.74

そんなことよりn乗で増えていくのを抑えないと無理なんでは

2023/05/04(木) 02:26:58.39

2次元限定、座標は有理数限定にしたら、競プロの問題として成立しますか？

2023/05/04(木) 04:20:04.21

>>306
yukicoderで出題してみれば？

2023/05/05(金) 10:56:46.77

>>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.43

あるよ

2023/05/05(金) 18:31:53.93

自分で解けてなければ自作の問題とは言わん

2023/05/05(金) 21:17:04.26

よくわからないけど [0, 1) の最大の区間は存在しないんだけど大丈夫そ？

2023/05/13(土) 22:41:38.39

5分延長か
面白い対応するね

2023/05/14(日) 00:45:51.21

攻撃を受けてもratedという前例ができたのはよかった

2023/05/14(日) 06:52:48.64

コンテストモードの敗北

2023/05/17(水) 05:36:16.93

>>294
女性だよ
検索したら本名とか出て来ると思うけど

2023/05/17(水) 09:19:32.53

>>315
Youtubeで本人の歌声も聴けるしな

2023/05/20(土) 22:48:05.22

６完…
今回は７完したかった…

2023/05/20(土) 23:12:12.63

配点割とその通りだったな

2023/05/22(月) 00:56:46.44

パフォーマンスがinfinityになった回って61以前にあった？

2023/05/27(土) 22:44:08.16

難しすぎるよ

2023/05/27(土) 23:33:38.14

コドフォもないし

2023/06/03(土) 23:01:24.39

6完
mod入力ミスってたのがアホすぎる

2023/06/04(日) 16:31:49.86

やっとE問題解けるようになってきた

E問題って一個一個の実行時間が長いんだな

2023/06/04(日) 17:44:29.58

競プロ有段者(強い人)に質問

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

自分の場合はD問題は9割ガタ解けて、Eがまだ実戦では歯が立たないレベル

2023/06/04(日) 17:53:24.73

うん

2023/06/04(日) 20:29:27.17

E問題思ったより簡単だな
食わず嫌いしてた

2023/06/06(火) 11:53:03.19

某所で「左右がバランスした括弧の列を生成する」という問題があり、解答が

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; が左右のバランス（単に'('と')'の数が同じというだけでなく）の条件に
効いているようですが、ピンとこないのです... 確かに正しい括弧の列のとき、それが成り
立つのはわかりますが、逆にそれがバランス条件を満たすのに十分であるというのが　
どなたかわかりやすい説明はないでしょうか

2023/06/06(火) 12:29:54.00

しょーもない処理を複雑に描いてるだけのクソプログラムやな
この関数は最初の呼び出しでlとrが同じ数字なるよう入れるのが前提で
r<lの条件は例外処理みたいなもんやろ

2023/06/06(火) 12:35:33.96

このコードの一部 `if (r < l) return;` について説明します。

ここで `l` と `r` はそれぞれまだ追加できる '(' の数と ')' の数を表しています。なので、このチェック `if (r < l) return;` は、')' の数が '(' の数より少なくなる場合、すなわち、開き括弧より閉じ括弧が少なくなる場合を防いでいます。

正しい括弧の列を生成するためには、2つの重要なルールを守らなければなりません：

1. 左括弧と右括弧の数が等しいこと
2. 任意の時点で、右括弧の数が左括弧の数を超えないこと

1つ目のルールは、左括弧と右括弧を同数だけ生成すれば満たされます。しかし、2つ目のルールはもう少し注意が必要です。それは、どの時点でも、閉じ括弧の数が開き括弧の数を超えてはならないからです。これを超えてしまうと、括弧の列が無効になってしまいます。

例えば、"())(" のような列は、開き括弧と閉じ括弧の数は同じでも、2番目の閉じ括弧が開き括弧を超えているため、無効な括弧の列となります。

だからこそ、`if (r < l) return;` のチェックが必要なのです。これにより、閉じ括弧の数が開き括弧を超えるような状況を防いでいます。これは、まだ追加できる閉じ括弧の数 `r` が、開き括弧 `l` より少なくなる場合、すなわち、閉じ括弧が開き括弧を超える可能性がある場合に、そのパスをすぐに終了させることで実現されています。

**デフォルトの名無しさん** (JP 0H56-RtFh) · 2023/06/06(火) 12:49:04.77

(を+1)を-1と対応させて累積和が常に非負っていうのがバランスしていることの必要十分条件であることを認めれば if(r < l)return; がそれの言い換えなことは明らか
証明したければ累積和が0になるところで文字列を分割して、それぞれの文字列の一番外側の括弧を取り外すとネストが一つ浅いものに帰着できるからネストの深さで帰納法を回すみたいなことを気をつけてやるといいんじゃないか

2023/06/07(水) 08:00:55.26

>>329はChatGPTなのかな? すごいな
>>330 どうもありがとうございます

このコードの場合、再帰時に常に右側に括弧を追加することが if (r < l) return; で
必要十分になることの前提だと思うんですが.... >>329はそのことがうやむやのような

2023/06/07(水) 08:33:42.08

>>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の(())を二つ並べた、と考えるべき?

要は、正しい括弧の追加操作のみをして再帰的に括弧列を生成することは可能なのか?
あるいは単にすべてのパターンを生成して正当でないのを刈り取ることしかできないのか?
などということが気になったのですが

2023/06/07(水) 09:49:06.82

>>332
結論から言うと、それは難しい問題であり、一般的なアプローチでは、「全てのパターンを生成し、
それがバランスの取れた括弧列であるかどうかを判定する」という方法が用いられます。

しかし、バランスの取れた括弧列を生成するための一種の再帰的なパターンは存在します。
それは、大きさnの全てのバランスの取れた括弧列を生成した後で、その各々に対して以下の操作を行うことです：

1. '(' + P + ')' を追加する
2. P + '()' を追加する
3. '()' + P を追加する
ここで P は大きさnの任意のバランスの取れた括弧列です。

この操作を行うと、全ての大きさn+1のバランスの取れた括弧列を生成することができます。
ただし、これは重複する列を生成する可能性があるため、生成された列は一意であることを保証するために
何らかの方法で重複を除去する必要があります。

したがって、厳密には「全てのパターンを生成し、それがバランスの取れた括弧列であるかどうかを判定する」
という方法とは異なりますが、これは一種の再帰的なアプローチと言えます。

しかし、これらのアプローチは計算時間やメモリ使用量の観点から見ると、>>327に示されたDFSを用いたアプローチに比べて
効率的ではないかもしれません。また、DFSを用いたアプローチは明確に「正しい括弧の追加操作のみ」を行っていると言えます。
なぜなら、すべての括弧列を生成する過程で、同時にその列が正しい括弧列であるかどうかをチェックすることが可能だからです。

2023/06/07(水) 10:10:41.04

>>332
>>333 は嘘
バランスした括弧列の定義は全体を括弧で囲む操作と括弧列2つの結合で生成される集合だから、その()を追加するっていうのを右か左に追加するって意味だとするとレベル2以上の文字列同士の結合が考慮されていないの
で、(())(())が作れない

中に()を挿入することを許すとすると、今度は全体を括弧で囲む操作はいらなくなる
というのも、どんな空でないバランスした括弧列にも()の部分があるから、それを取り除くことを繰り返すことで空にできるから、逆に空文字列に()を追加していくことで任意のバランスした括弧列が作れるし、バランスした括弧列の任意の箇所に()を挿入した文字列もまたバランスした括弧列になっている

2023/06/07(水) 11:08:01.09

>>331
ご指摘の通り、このコードでは再帰的に右側に括弧を追加しています。具体的には、まず左括弧を追加し、その後で右括弧を追加しています。

この if (r < l) return; の制約は、この追加の順序に基づいています。開始時点では、開き括弧と閉じ括弧の数が等しく（つまり、l == r）、左括弧を先に追加します。そのため、追加の過程では一時的に l が r より小さくなります。しかし、その後すぐに右括弧を追加することでバランスを保ちます。

if (r < l) return; のチェックにより、右括弧が先に追加される（つまり、r < l となる）状況を防いでいます。これは、左括弧を追加した後でのみ右括弧を追加するという、このコードの括弧の追加の順序を反映しています。そのため、この制約が満たされない場合（つまり、右括弧が先に追加される場合）、そのパスは無効となり、すぐに終了します。

したがって、この if (r < l) return; の制約は、このコードの括弧の追加の順序に基づいて、左括弧と右括弧が正しくバランスを保つことを保証しています。

2023/06/07(水) 14:48:36.26

非負のランダムウォーク書いて+1-1を()に対応させるだけだろ

2023/06/10(土) 17:29:19.24

>>327
閉じ括弧が開き括弧より少なかったら、ダメってことなだけでは。

開き括弧と閉じ括弧の数が同じって条件は最初の呼び出しではlとrが同じでなければならないって制約があると思う

2023/06/10(土) 22:46:50.51

6完…
途中まではいいペースもFで帰りがけにも頂点集合受け取るの忘れて時間ギリギリに

2023/06/11(日) 20:43:12.18

>>337
例えば())(()は閉じ開きの括弧数だけでいうとおkだけど実際にはおkじゃない
では何故これが生成されないか、他の駄目パターンもなぜ生成されないか気になった
というのを既に考察したつもり

2023/06/11(日) 20:59:44.70

しかし、解く時間が限られている場合にグダグダ悩んでいる暇はないよなあ
そういう場合パターンを覚えておくしかない?

2023/06/17(土) 22:47:22.26

ジャッジが終わらないよ

2023/06/17(土) 23:10:07.92

unratedおおすぎ

2023/06/17(土) 23:16:56.58

アーロンジャッジたすけて

2023/06/18(日) 04:25:23.41

atcoderがddos受けてるとして、潰して得をするのは誰だ？

2023/06/18(日) 11:57:26.20

ロシア中国

2023/06/24(土) 17:44:41.70

ガイジのみんなこっちおいで😆
怖がる必要ないよ✌

2023/06/24(土) 18:57:52.69

うおおおおおおおお🤓

2023/06/24(土) 19:30:32.53

他のガイジもこっちおいで！

2023/06/24(土) 22:23:51.32

攻撃されてね？

2023/06/24(土) 22:28:05.07

落ちてる！クソすぎ！！！

2023/06/24(土) 22:42:50.37

せっかくG解けたのに1分遅れになってしまった…

2023/06/24(土) 22:55:29.87

アンレでしょ、ね？ね？

2023/06/24(土) 22:56:49.69

ところでC正解者少なすぎ

2023/06/24(土) 23:12:14.22

10:10くらい？から今(10:50)までずっとatcoder開けませんが、同じ人いるかな
なんてツイートしてるひともいるね

2023/06/25(日) 01:40:55.82

このコードがaws環境でsegmentationfaultになる原因わかる人いる？
ちなみにatcoderではこのコードでACを取れたので致命的な間違いがあるわけでは無さそう
int main(){
ll n, q, dp[39][100009], A[100009];
cin >> n >> q;

rep(i, 1, n) {
cin >> A[i];
dp[0][i] = A[i];
}

rep(i, 1, 29){
rep(j, 1, n){
dp[i][j] = dp[i-1][dp[i-1][j]];
}
}

rrep(i, q){
ll x, y;
cin >> x >> y;
ll cur = x;

Rep(j, 29, 0){
if((y & (1 << j)) != 0) cur = dp[j][cur];
}

cout << cur << endl;
}
}

2023/06/25(日) 01:41:11.75

どこかおかしい部分あるかな

2023/06/25(日) 02:14:14.53

スタックサイズ

2023/06/25(日) 02:15:11.19

>>355
マルチは市ね

2023/06/29(木) 15:31:24.42

Twitterのpaizaの広告とかに必ず現れる

「入力値をチェックしていない」

という返信をつける人は、具体的に何をチェックして、どう処理するの？

2023/06/29(木) 15:35:22.33

たとえば、

・Nは偶数
・AとBの合計はN未満

といった制約は、実際のプログラムならチェックして例外をスローする
しかし、

「nが整数値じゃない場合をチェックしていない」

みたいなよくわからない難癖をつける人もいる
整数値じゃなければint型にパースするときに、ほとんどの言語で例外になるからいいのでは

2023/06/29(木) 15:50:34.59

>>355
ll で dp[39][100009], A[100009];
何バイトあるん

2023/07/01(土) 22:45:27.97

今回は簡単めでしたね
G解けなかったけど

2023/07/01(土) 23:33:06.19

コンテスト初参加
C問題があまりにも酷いと思った
20分くらいかけて、priorityqueue<pair<double、int>> に値をプッシュする時にpairのsecondの方にマイナスを付ければ良いことに気がついたもののWA
何を試してもWAで、doubleの精度に問題があるんじゃないかと思って、ネット検索をしたら、long doubleという型があることを知り、試してみたら無事AC
Ｃ問題で時間とメンタルを削られてD問題は諦めた
初参加とはいえ茶パフォはあまりに脳障害すぎるだろ

2023/07/01(土) 23:39:31.52

今回のＣ問題でpriorityqueueを使ったんだけど、priorityqueue<pair<double、int>> に値をプッシュする時、pairのsecondの方に-をつけて取り出す順番を工夫するのって典型？
ちょっとした閃きだけど思いついた時は俺ちょっと頭いいんじゃねって思っちゃった
その後ものの見事に脳障害っぷりを晒してしまったけど

2023/07/01(土) 23:43:47.83

その発想は天才だよ、才能あるね

2023/07/01(土) 23:50:30.60

マジレスすると符号付けて逆順にすることで実装をシンプルにするのはかなりの典型です

2023/07/01(土) 23:53:37.30

むしろそのマイナスにするのが主題と言ってもいいくらい

2023/07/01(土) 23:57:08.30

C++ってFraction無いんだっけ？
まあ無くても自分で通分すれば済む話だが

2023/07/02(日) 00:35:29.46

なるほど、ただの典型だったか…
ただ、その典型を自分で思いついたのはちょっと嬉しい

2023/07/02(日) 00:39:10.97

先程 D問題をACしてきた
結構簡単だし、C問題を普通に解けていたら多分四完出来た
今回のC問題みたいに本質的じゃない部分(long doubleという型を知っているかどうかみたいな)を問うのは本当にやめた方が良いと思う問題の質がシンプルに低い

2023/07/02(日) 01:16:07.96

小数の精度についての理解を問うなかなかの良問だと思ったけどね

2023/07/02(日) 01:33:02.66

浮動小数点数での出力を求められていない場合に浮動小数点数を使うのはアンチパターン
分数を管理する構造体を持ち出したり適切な比較関数を書いたりして対処するべき

2023/07/02(日) 03:53:32.35

前回のC問題はただめちゃくちゃ面倒なだけでアレだったけど今週のC問題は何も悪くないし非本質的でもないだろ
浮動小数点数は誤差に気をつけるべきなんて競プロでは身につけておくべき典型知識だし競プロ外でも浮動小数点数の仕組みは知っておくべきだしm

2023/07/02(日) 03:56:07.16

強いて言うならlong double型で無理矢理通すような解答を弾けるような設定にして比較関数やら有理数型を表す構造体やらの整数しか登場しなくて誤差の心配がない解答のみが通るようにしてほしかったがCでそれは酷かもしれない

2023/07/02(日) 04:23:31.59

long double使わなくても解けるし、それ知らないと解けないと言ってる人のレベルが低すぎるだけ

2023/07/02(日) 08:45:23.44

E問題の意味が分からないんだが。

俺の考えたアルゴリズムは、

Mが0,1,2になる数、
Eが0,1,2になる数、
Xが0,1,2になる数、
を全て数えて

各組み合わせ27通りについて、

mex×場合分けの数

っていうやり方をしたんだがサンプル3の問題からしてそもそも合わない

日本語下手で説明難しいからコードを見てほしい。
https://atcoder.jp/contests/abc308/submissions/43167367
このやり方がなぜいけないのかわからない

コンテスト中「E問題いけるやん！」と思ってただけに絶望だったわ、はぁ。。

2023/07/02(日) 08:51:37.04

関係ないけど、dictのkeyで回せば
if k not in dic["X"]:
continue

みたいなのいらなかったな

2023/07/02(日) 08:52:36.78

i<j<k

2023/07/02(日) 08:55:34.57

>>378
ないてもいい？

2023/07/02(日) 09:02:55.87

雑なやり方だけど、
「E」に来た時点で、それより前のMの各012の数と
それより後のXの「012」の数を保持しておけば簡単に解けたわけか

2023/07/02(日) 10:28:08.37

Cみたいなのが普通に小数にしてソートして解けないとか、現実的に不要な精度を求めてるからじゃ。工夫して分数を比較とか一般的なプログラミングではあり得ない。

2023/07/02(日) 11:00:12.04

一切の誤差が許容できないケースは業プロでもあり得ると思う

2023/07/02(日) 11:08:00.56

COBOL使われてそう

2023/07/02(日) 11:14:00.32

普通に業プロでも浮動小数点の誤差でやらかすのあるあるだけどな
とくに一致判定しだすと大抵はテストを通って後でトラブる

2023/07/02(日) 11:34:46.41

むしろ業プロはバグだらけで運用でカバーするのが当たり前だか？
バグなくなるまでQAとデバッグしてたらいつまでたっても終わらない

2023/07/02(日) 11:37:01.69

当たり前だが？

2023/07/02(日) 11:40:04.07

>>381
あり得ないのは誤差があることを知りながらdoubleを使うことだぞ
誤差が許容できないとわかってて整数で誤差のない計算ができることもわかってるんだから整数で計算するべき
わかってないお前が無能というだけ

2023/07/02(日) 11:40:34.10

しかし、スポーツとかゲームの勝率を管理するシステムがあったとして、
小数点以下6桁以上の精度のために内部的に分子分母を整数で別々に保存してるとは思えないのだがｗｗｗ

2023/07/02(日) 11:56:01.97

思えよw
勝ち数と試合数を保存してるに決まってるだろw

2023/07/02(日) 11:57:10.10

逆に勝率だけ保存してその後の試合の結果どうすんの？w
過去の勝率からどうやって現在の勝率を計算するんだよw

2023/07/02(日) 12:04:01.86

それは当然してるけど、orderbyで引き出すときに、勝率をatcoder流でソートするとか多分ないｗ
ワテが知らないだけで分数流ベイズ統計学とかあるのかｗ

2023/07/02(日) 12:04:59.74

お前の我流が間違ってるだけだぞ

2023/07/02(日) 12:50:39.91

普通に業務でもあり得るんだよなぁ

2023/07/02(日) 15:00:00.77

>>390
n 試合後に
現在の勝率 R(n)「だけ」が判っている場合
n+1 試合後の勝率 R(n+1) は
n+1 試合目の勝ち負けが r (勝ちなら 1 負けなら 0) とすると
R(n+1) = (R(n) x n + r) / (n + 1)
で良いんじゃね
もちろん誤差は蓄積するよ
こんなこと一々描くのも恥ずかしいレベル

2023/07/02(日) 15:20:20.64

>>394
そのnは試合数じゃないのかw
こんなこといちいち書かせるなよw

2023/07/02(日) 15:24:37.03

もう少し比較条件が複雑化されて
operator<なりstd::sortに渡すラムダ式をちゃんと定義しないと駄目なら一転して教育的とかいいそう

2023/07/02(日) 23:05:02.47

ARCゼロ完地頭悪すぎるガチで死にたい

2023/07/02(日) 23:07:06.37

昨日はABC三完
今日はARCゼロ完
A問題は解けそうだったけど結局最後までAC出来ず
頭が悪すぎる
IQ1しか無いよ俺は

2023/07/02(日) 23:13:24.16

数理能力皆無の知的障害者です

2023/07/03(月) 01:30:24.77

・解説開くとTwitterに飛ぶやつあるが、アカウント持ってないから見れない。
・今日のARC出題者はPCT。何千人の大人が高校生の手の上で転がされていると思うと笑える。

2023/07/03(月) 09:36:39.54

大人は経験を積んでるから対応力があるわけで素の能力的には筋力でも記憶力でも計算力でも高校生くらいがピークだろ
ずっと数学に取り組んできた高校生が年食ったにわかより数学力高いのは何もおかしくない

2023/07/03(月) 09:44:41.24

女子高生ですが質問良いですか？

2023/07/03(月) 17:22:23.00

女子高生は伊藤ハムと株式会社響の登録商標

2023/07/03(月) 17:33:27.76

女子高生®

2023/07/03(月) 21:06:06.47

女子高生++

2023/07/03(月) 21:54:41.71

32進数で18のガールです

2023/07/04(火) 01:04:41.48

コードクイーンの足切りライン調べたら女性率わかりそう

2023/07/04(火) 12:50:20.11

高校生の茶パフォ、大人の緑パフォが通過してるのは観測した

2023/07/04(火) 20:30:01.45

CodeQUEENの予選通過ボーダーは4000位くらいか
決勝が200人だから、予選参加者の女性率は1/20くらい？意外と多い

2023/07/04(火) 23:33:24.09

普段よりは多いはずだしmaxで5%って少なすぎでは

2023/07/04(火) 23:40:14.20

情報系学科には5%も女子いないしそんなもんだろ

2023/07/05(水) 01:19:41.42

決勝50人だという認識だけど変わった？

2023/07/06(木) 21:25:45.68

明日ICPC国内予選で、紙デバッグのためにソースコード印刷できる環境を作りたいんだけど、どういう方法で印刷するのがおすすめ？？
できれば関数とか変数に色ついた状態で印刷できるのがよくて（結局白黒印刷でそこまで判別できないんだろうけど……）、コマンド一発とかだとさらに嬉しい。

ubuntu on wslで、C++のコードを印刷する予定。

2023/07/06(木) 22:38:13.51

うんち！ｗ

2023/07/07(金) 01:30:49.16

>>413
エディタでスクショ撮って印刷すれば？
それかSlidesCodeHighlighter

2023/07/07(金) 03:12:20.80

関数とか変数のfontを変えればいいんじゃないの?