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

2023/03/22(水) 15:19:42.08

!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

2023/04/10(月) 16:20:04.87

DAGにoutdegreeおよびindegreeが0の点が両方とも存在することは、自明です。
もしそのような点がなければ、閉路が存在することになるからです。
トポロジカルソートなどという考え方を持ち出すまでもありません。

2023/04/10(月) 16:26:05.43

トポロジカルソートを明示的に実行しなくても、DAGの最長パス問題をDPで解くことは可能です。
ただし、その際に頂点の処理順序や依存関係の解決が重要となるため、トポロジカルソートの考え方が役立ちます。

トポロジカルソートを適用したDPでは、頂点の依存関係が効率的に解決されるため、計算量はO(V+E)です。
ここで、Vは頂点数、Eは辺数です。トポロジカルソートによって得られた頂点の順序に従ってDPを行うことで、
各頂点と辺に対して一度だけ計算が行われます。

一方、トポロジカルソートを適用しないDPでは、無駄な計算が発生する可能性があります。
例えば、メモ化再帰を用いたDPの場合、計算量は最悪O(2^V)になることがあります。
これは、全ての頂点に対して、それぞれを含むか含まないかの選択肢があるためです。

2023/04/10(月) 19:58:08.22

>>181
多項式 f(n) について計算したい
calc(f) で求めたい値を返す関数として
f が定数ならそれを返す
定数でないなら g(n)=f(n+1)-f(n)
とgを定めて
calc(f) = gcd(f(1), calc(g))
を計算すればいい、再帰の深さはfの次数で抑えられる

2023/04/10(月) 20:30:41.82

『アルゴリズム実技検定公式テキストエントリー～中級編』に載っている
DAGの最長パスを求めるコードでは、トポロジカルソートを陽には使っていないです。

2023/04/10(月) 21:31:52.04

その本持ってないからその本の解法教えて
そしたら質問の回答するよ

2023/04/10(月) 21:57:16.12

>>197
ソースコードは以下です：
github.com/kenkoooo/pastbook-source-code/blob/master/chukyu/python/chapter06/section04/6-4-8.py

2023/04/10(月) 22:22:43.61

確かに陽にトポロジカルソートはしてないね
値が確定する順序がトポロジカルソート順の逆順にはなってるけど

多分、以下のようなことを言いたいんじゃないかな

・各頂点の値を一つずつ順に確定していって、
・一度確定した頂点を再度訪れる必要がない
・そのようなことが可能な確定順が存在する

確かに考え方によっては自明とも思えるかもしれないけど、逆にそれくらいのことしか言ってないということでは

2023/04/10(月) 22:32:19.30

この問題の場合はメモ化再帰でトポロジカルソートを使わなくても計算量はO(N+M)です。
頂点間に循環がないため、再帰の深さが頂点数Nを超えることがなく、
各頂点に対して rec 関数が最大1回しか呼び出されないからです。

トポロジカルソートを使ってそのコードを書き換えるとこうなります。
https://ideone.com/1NbHIf

2023/04/11(火) 00:50:14.84

んげりいいいいいいいwwwwww

2023/04/11(火) 10:56:16.23

>>199-200
ありがとうございました。

>>200
コードを見たのですが、

# トポロジカルソートで得られた順序に沿って最長経路を更新
for u in order:
for v in edges[u]:
length[v] = max(length[v], length[u] + 1)

の「for u in order:」でなぜ良いのかが分かりません。orderの要素を後ろから見ていかなければ
ならないように思ったのですが、そうではないのはなぜでしょうか？

2023/04/11(火) 11:11:09.23

for u in order:
■■■■print(u)

とすると自分が思っている順序とちょうど逆順で表示されます。

order.append(u)

を実行すると order の最大インデックスの要素の次に u が挿入されますよね。

そうだとすると、 order[0], order[1], … は queue から出てきた順に並べたものになりますよね。

2023/04/11(火) 11:15:16.38

多分、単純な勘違いなんですが、どこを勘違いしているのかが分かりません。

2023/04/11(火) 11:16:45.70

あ、分かりました。
与えられた有向グラフの辺の向きをすべて逆にしても、最長パスの長さは変わりませんね。

2023/04/11(火) 11:35:54.50

以下のコードは全く無駄なことをやっていますが、自分の理解通りなのはこちらのコードです：
ideone.com/gMUZDZ

2023/04/11(火) 13:43:59.54

すまん初めてこのスレ来たんだけど連投してるやつはネームド？

2023/04/11(火) 14:46:33.78

ネームド志望

2023/04/11(火) 15:09:56.33

>>195
天才か

gcd(f(1),f(2),...)
=gcd(f(1),f(2)-f(1),f(3)-f(2),...)
ということか

確かに典型だが無限で思考がストップしてしまっていた

2023/04/11(火) 18:39:41.18

pythonで2分探索を行う bisect というものがあります。

bisect.bisect(l, a)

としたとき、 a in l であるかどうかも判定したいのですが、そのような関数は用意されていませんか？
自分で作るしかないですかね？

2023/04/11(火) 18:42:16.72

Pythonに2分探索で整列済みのリスト l に要素 a が含まれるかどうかを調べる関数はありますか？

2023/04/11(火) 18:44:52.56

もちろん、 bisect を使って、簡単に実装できますが、用意されている関数はないですか？

2023/04/11(火) 19:14:39.91

がんばれ

2023/04/11(火) 19:20:22.62

まあ、以下のコードでいいと思うのですが、車輪の再発明はしたくないですよね。

i = bisect.bisect_left(l, a)
if l[i] == a:
return True
else:
return False

2023/04/11(火) 23:36:07.25

車輪の再発明はしたくないですよ

2023/04/12(水) 00:15:56.65

公式を読めと言いたいが
https://docs.python.org/ja/3.8/library/bisect.html
集合でも管理してinで判定すれば良いのでは(´・ω・`)

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 出るかと思って過去問見直したけど全然出なかった