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

2022/10/02(日) 17:43:58.66

↑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/

※前スレ
競技プログラミング総合スレ 63
https://mevius.5ch.net/test/read.cgi/tech/1627477128
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

2022/10/08(土) 22:50:57.84

ここにコードを乗せるのは無理があったか

2022/10/08(土) 22:56:46.79

G乱択想定解かー
教育的だね

2022/10/08(土) 22:58:15.49

pastebin辺り使え

2022/10/08(土) 23:04:25.31

>>28
あんま競プロでPython使わないんだけど、まずDってO(N^3)とかO(N^2√M)だから遅い言語だとちょっと定数倍遅いだけで2secで通らなくなるような問題だと思う
そしてそのコードは(x,y)で状態持ってたりしてて定数倍微妙そうなコードだなと思ったな
numpy使ってるってことはPyPyじゃなくてCPythonでしょ？それだとアルゴリズム自体は間違ってなくてもTLEで落ちるんじゃないかな

2022/10/08(土) 23:09:23.51

que.pop(0)ってやってるけど、PythonのlistにFIFOとしての機能あったっけ？
listの内部実装次第だけど、そこで計算量オーダー増えててもおかしくないような
queueを使いたいときにはdequeとか使ってる人が多い印象

2022/10/08(土) 23:09:40.62

suffix arrayってどの色のdiffくらいから前提知識として求められるアルゴリズムなん？

2022/10/08(土) 23:14:27.40

手元のPythonで見てみたけど、listでpop(0)すると配列の長さ分計算時間がかかってそうだから、その書き方だとO(N^4)とかO(N^5)になってるんじゃないかな
ぶっちゃけ別にBFSである必要はないからque.pop(0)→que.pop()でだいぶ早くなるんじゃない？
確かstackとしては使えたはず

2022/10/08(土) 23:14:43.63

深さ優先でも上手く行くんかな

2022/10/08(土) 23:18:18.42

>>35
出る難易度帯からすると青ぐらいの印象
ただ概念的にはそんなに難しくないかなあ（SA-ISというアルゴリズム自体は頭いいけど）
知識的な敷居の高さから後ろに置かれることが多いけど、水色ぐらいでも練習すればACLを活用しつつ普通に解けるレベルの問題も多いと思う

2022/10/08(土) 23:20:22.20

>>29
ちょっと今外で詳しくは見れてないけどこの手のdfsでTLEになるって
deque使わずにキューしちゃったか、訪れ済みのマスを飛ばしてないとかだよ

2022/10/08(土) 23:21:14.83

あ、すまん、ボケてたわ
最短距離問題からBFSである必要はあるわ、忘れてくれ
dequeをcollectionsからimportして、使えばいいと思うよ
あとnumpyを使わずに実装しなおしてPyPyで提出しなおせば

2022/10/08(土) 23:24:18.99

>>38
なるほどありがとう
丁度その手前の帯域にいるからこれを機に勉強してみるわ

2022/10/08(土) 23:36:17.47

>>25
二分探索だけど、ちょうどこの前話題になった「めぐる式」二分探索って実装方針がバグらせにくくておすすめだよ
ググれば出てくると思う

2022/10/08(土) 23:45:35.49

ARCの配点出たのか
この前みたいに5-7で崖ができるとやりにくいなー

2022/10/08(土) 23:49:58.84

>>42
めぐる式いいんだけどこの前のabc269Eみたいな２分探索だと色々バグらん？

2022/10/09(日) 00:03:22.87

>>44
判定関数をf(n) = (1 n 1 Nと入力したときの応答がn-1のときはtrue、nのときはfalse)みたいな風にすればめぐる式でできない？

2022/10/09(日) 00:05:11.03

初期値はok = N, ng = 0で

2022/10/09(日) 13:10:10.78

昨日コードかいたものだけど
サンクス、numpyをやめてqueをdequeにして
python3.8⇒pypyにしたらTLEにならず通った

しかし、python3.8にしたら通らなかった

なんだかな。。言語によっては通らないみたいなのやめた方がいいんじゃないだろうか。。

2022/10/09(日) 13:16:26.59

言語じゃなくて処理系の違いだからセーフ

2022/10/09(日) 13:22:07.84

計算量の見積りは大事な要素だから遅い言語使う方が悪いということになってる
実際Pythonはpypy あるしRubyはCrystalあるからどうにもならないって人はそんなにいないはず
aclがc++にしかない方が不公平に感じる

2022/10/09(日) 13:49:20.47

君もC++で書いて計算量的に数十倍かかるゴミコードでACしよう

2022/10/09(日) 13:53:56.11

CPythonだとC++の10～30倍ぐらいは遅いから、なんでもかんでも確実にCPythonで通るようにtime limit設定するとC++で非想定の悪い解がバンバン通るようになってゲームが成立しなくなる
一方PyPyは確かJavaと同等かちょっと遅い程度だからそれでほぼ通せるはず
言語ごとにtime limit変えるみたいな話もなくはないけど、ちょっと詳しい人なら遅い言語にC++とかのコンパイル済バイナリ埋め込んで通すみたいなことができてしまうし、現行のルールはなるべくしてなったものだと思うよ

2022/10/09(日) 15:09:36.52

そういえばAGCって年6回開催が目標だったけど、今年まだ2回しかやってないのか
一昔前はARC級が全然なくて黄橙がつらい言ってたけど、こっちは順調なペース
WTFもないし、上級者向けコンテストが枯渇してる

2022/10/09(日) 15:27:54.23

りんご時代より大幅に減ってるんだな
Admin無能すぎでは

2022/10/09(日) 16:24:26.89

admin を片手間の学生に任せてるのがおかしいのでは？

2022/10/09(日) 18:01:54.02

>>47
ジャンプの問題かな？
自分も Python & deque で最初は TLE した。
問題の対象性を利用して (i, j) が確定した時に
合わせて (j, i) の値もセットして訪問済みに
したら Python でも通るようになった。
一方で E は PyPy でないと通らなかったわ。

2022/10/09(日) 19:47:34.94

>>55
なんと。。1/2倍にしたっていうことだよね。確かに正方形だしナイトの動きだと思えばi.jも確定するね
定数倍速くするのは競プロ系だとあまり意味ないと思ってた

2022/10/09(日) 20:49:39.37

もうすぐレギュラーだ
A問題だけでもなんとかして解きたい

2022/10/09(日) 20:50:21.13

競プロ初めて2ヶ月、A問題さえ解ければ茶色になれる

2022/10/09(日) 20:57:07.39

よし、気合入れるぞ
A問題に全精力を注ぐ

2022/10/09(日) 21:51:11.27

緑から水色いくのにARCの問題解くのって効果的かな？それともABCの緑以上の問題解いてた方がいい？

2022/10/09(日) 23:03:37.83

a問題でスパゲッティコード書きまくって結局RE
泣きたいですよ

2022/10/09(日) 23:51:12.05

冷えたなー
Cが曲者だった

2022/10/09(日) 23:51:27.48

ARC2、3完安定してきたと思ったら初めて0完して泣いてる

2022/10/09(日) 23:52:59.43

A,Bも解きやすい感じではなかったね

2022/10/09(日) 23:55:49.59

AGC格に持っていけるかどうかは後ろの問題がどのぐらい面白くて難しいかだと思うけど、自分は判定できない
Fがとにかく難しかったみたいだけど
前の方の問題はAGCで出してもいい感じだと思う

2022/10/09(日) 23:56:27.36

Fじゃない、EとFだ

2022/10/10(月) 00:07:00.96

>>60
寒色がレートを伸ばす効果でいえばABCの練習の方がずっとコスパいいと思うから、当分ABCでいいと思う
ただ、暖色になった後も見据えてるんだったら、ARCもちょっとずつ考えてみるのも悪くないかな
あとARCの練習に関しては解説ACはしない方がいいと個人的には思っている

2022/10/10(月) 00:11:53.24

>>63
ワテは0完ボチボチ出すようになってからARC引退した

2022/10/10(月) 00:12:40.52

というかARCタイプだと黄色近い人でも大事故起こすこと結構あるんだな　問題の傾向的にABCで事故ることは少なそうだけど

2022/10/10(月) 02:58:46.48

ARCのA問題は安定して解けるんだけどそれ以降が不安定過ぎていま黄色だけどそのうち落ちそう

2022/10/10(月) 13:47:35.33

ARC低～中難度も努力すれば安定するぐらいの典型性のはずと思っているけど、似ている問題って他だとどのコンテストなんだろうね

2022/10/10(月) 14:38:04.12

>>42
ありがとうございます。
2分探索なんて簡単だなどと思っていても、実際実装しろと言われると何度実装したことがあっても
時間がかかってしまいます。

実装に時間がかからない方法って重要ですね。

**デフォルトの名無しさん** (ｽﾌｯ Sdea-HsIT) · 2022/10/10(月) 18:08:43.67

>>67
ありがとうございます！
Atcoder自体、数学パズルが好きでやってて暖色後のことも見据えてるのでちょくちょく解いてみます
解説ACはしない方が良いとは自分で充分熟考して、どうしようもなくなったときだけ解説を見るってことです？

2022/10/10(月) 22:00:30.58

>>73
強い人見てると解けなくても数か月間寝かせて後から解き直すみたいなのを繰り返しているから、そもそも解ける前に解説を読まない方がベターなのかも？
知識不足で解けない場合はかなりのタイムロスになっちゃうけど、知識面はABCの問題をたくさん解くことで十分身につくと思う

2022/10/10(月) 23:41:25.22

この俺が解説見るなんて的な負けん気がある人じゃないと強くなれない説

2022/10/11(火) 00:12:21.28

地頭がない人は自力で解こうとしても時間をドブに捨てるだけ

2022/10/11(火) 00:12:26.05

ABCの問題だとさっさと見て典型吸収したほうがいい場合のほうが多そう

2022/10/11(火) 00:31:31.56

二分探索はめぐる式もいいけど、やっぱり解がありうる範囲の幅に着目するのがいいんじゃないかと思う
これはめぐる式ほど何も考えずできるやり方じゃないけど、少なくともバグらない
幅に着目して、毎回幅が必ず半分以下になるようにすれば、無限ループとかも起こらないし
すべての要素が完全に意識内にあるようにできるから、デバッグも簡単

2022/10/11(火) 10:00:24.46

ARCがレート的に事故になるのって何色コーダーくらいから？
あと、緑（欲言えば水色）はABCのE問題まで完だけでなれるもの？

**デフォルトの名無しさん** (JP 0H96-yVtu) · 2022/10/11(火) 10:19:37.71

偏見だけどめぐる式使わない人めぐる式書いたことない

2022/10/11(火) 11:59:44.82

片っ端から解説開くタイプだけど暖色にはなれたから、黄色までなら知識偏重でもいいんじゃないかな
赤は知らん

2022/10/11(火) 12:11:38.75

米田の『プログラミングコンテストの鉄則』を読んでいますが、コードが分かりやすくて、バグもないですね。
さすがレッドコーダーですね。

2022/10/11(火) 12:15:12.17

米田は説明とかコードを大分使い回ししてるからこなれてきてるイメージあるわ

2022/10/11(火) 12:16:27.59

>>79
EどころかDまで早解き(30-40分)繰り返してたら絶対に入水できるよ

2022/10/11(火) 13:34:55.25

正しいアイディアが得られてから、素早く実装するにはどうすればいいのでしょうか？
いつも仮に正しいアイディアが得られたとしても、実装でもたついてしまいます。

2022/10/11(火) 13:37:37.48

まず3000acまで精進しましょう
自然と実装が早くなります

2022/10/11(火) 13:41:56.59

>>86
ありがとうございます。気が遠くなりますが、3000までいかなくても、次第に速くはなっていくと考えてがんばります。

2022/10/11(火) 14:51:38.87

>>79
これを見るとE安定（1500pt安定）の人なら水中位は固い
いろいろ噛み合えば青タッチもできるレベルだと思うね
このグラフは他の色についても分析できるから便利
https://twitter.com/kiri8128/status/1561356750355570689
https://twitter.com/kiri8128/status/1576256376518897665
https://twitter.com/kiri8128/status/1566074062786658307
https://twitter.com/5chan_nel (5ch newer account)

2022/10/11(火) 16:46:50.56

AC数800台で黄コーダーになった中学生

2022/10/11(火) 17:57:52.46

実装の速さは紙上デバッグを細部まで終わらせて迷いなく書くことだと思う

2022/10/11(火) 23:17:45.46

実装を速くするコツは２つあると考えてる。
１　思考の手間を省く。
　競プロでは毎回全く違うプログラムってことはあんまりなくて、DFSとか1次元DPとか累積和とか毎回書き方が同じ部品というのは結構ある。
　こういう部品に対しては、事前に書き方を決めておくことで、その部分はもう考えずに書けるようになる。
２　隅々まで理解する。
　複雑な問題を解くとき、なんとなくわかった状態で実装を始めている人は多いと思う。気持ちはわかるし、簡単な問題ならそれでいいと思う。
　でも、実装と深い思考は両立するのが難しい。複雑な思考が必要な問題では、先に最後まで（何行目に何を書くかまで）考えておいた方が速い。

2022/10/12(水) 21:59:18.79

chokudaiが同じ実力でも1年間で50程度レートが下がるみたいな感じの調査を見たって言ってるけど、ソースは何だろう
個人的には大体そんなもんな気がする

2022/10/13(木) 13:35:28.53

https://twitter.com/not_522/status/1580130152482099200?t=aj8v0JeHSojee_MKdb-TTw&s=19
https://twitter.com/5chan_nel (5ch newer account)

2022/10/13(木) 16:44:42.51

>>93
ありがとう
予想するに、logit([AよりBの方が難しく感じる確率]) = β_0 + β_1 [problems上のdifficultyの差] + β_2 [出題時点の差（単位は年）]としてβ_2/β_1 = 50だった的な感じかな
こういう回帰係数って素朴に割り算していいのかわからないけど
[problems上のdifficultyの差]と[出題時点の差]って独立っぽいから多重共線性とかはなさそう

2022/10/13(木) 17:29:37.68

>>90-91
ついつい、あせってアイディアが整理されていなくても書き始めてしまうんですよね。。。

『離散凸解析と最適化アルゴリズム』という本の第1章を読んだのですが、このような
理論的な本は競技プログラミングに役に立つことがありますか？

問題を解くばかりでは飛躍的な上達はなかなか難しいのではないかという気もします。

2022/10/13(木) 17:54:44.70

>>95
atcoderは大人のsapixなので役に立たないです

2022/10/13(木) 18:58:22.49

理論的な本は競技プログラミングに役に立つことがあります

2022/10/13(木) 20:38:36.86

>>95
mas 氏が離散凸を題材に作問されていたね。arc130_f。

2022/10/13(木) 21:10:49.03

凡人は数学の難しい話が役に立つところまでレートを伸ばせない

2022/10/13(木) 21:28:38.71

ABCで黄色以上でた問題は存在しないも同然じゃからのぉ
実務的には調べながら1問に3時間くらいかけて解ければ十分みたいな感じかと

2022/10/13(木) 21:29:29.75

その離散凸解析の本は理論系の中でもかなり競プロに役立つ方の本な気がする
けど、知識をつけて飛躍的に伸びるのはAtCoderの中でもABCで、そのABCで出てくるぐらいの知識なら特別な勉強をしなくても、問題解いて蟻本あたり読んでいれば身につくものという印象（Exは除く）
だから理論系の勉強がコスパがよいかというと微妙
ただ、競プロ抜きにしてもアルゴリズムの勉強は面白い部分があると思うし、そもそも競プロとは独立して価値があるものなので勉強して損はないんじゃないかなと思う

2022/10/13(木) 22:15:44.40

要約すると、理論的な本は競技プログラミングに役に立つことがあります

2022/10/13(木) 22:31:16.40

というのはまあ冗談で、少なくともレート2000以下とかならそんなのいらん
鉄則本や蟻本に習熟して、AtCoderを練習しまくて遭遇した知らなかったアルゴリズムを覚えればいいだけ
ヘタに大学生向けの参考書なんか読むより大学受験レベルの整数問題を解く練習したほうがいいくらい

2022/10/14(金) 01:47:17.08

こどふぉのdiv4難易度の上限がatcoderの500点問題くらいだから初心者にとっては早解きの練習になってありがたい

2022/10/14(金) 21:00:56.55

理論は楽しいから、競プロを手段化することで競プロへのモチベになる

2022/10/15(土) 19:47:28.91

今日も頑張るぞ
今日、ちゃんとCまでは解ければ茶色にはなれる

2022/10/15(土) 20:38:54.13

誤差の問題が出るから整数型でなんとかしよう

2022/10/15(土) 22:43:48.07

こういう重いのやるなら1問だけやれよ、ビギナーで1問70行とか無いわ

2022/10/15(土) 22:46:38.09

AtCoder を始めて10回ぐらい経ちましたが, A問題しか解けない状態が続いてます.
A：簡単
B：いくつかWA→解決できずに終了
といった感じです.
原因はコードを見てWAになる理由（そうなるケース）を見つけられないことだと思うのですが,
みなさんどのように対処されているのでしょうか

2022/10/15(土) 22:52:32.49

Aしか解けない人の気持ちはわからん
なんか計算量とか前提知識が足りてなさすぎる気がするから、AtCodeer本とか読んでみたら？
競プロは問題に書かれたことをシミュレーションするコードを書くコンテストじゃなくて、たくさんのアルゴリズム知識を駆使したうえでの数学のコンテストだよ

2022/10/15(土) 22:57:00.60

唯一、A問題だけはシミュレーションすれば解けるから、競プロ用の知識が足りてないのかなと思った

2022/10/15(土) 23:12:41.37

B問題に関しては計算量解析もそんなに問われないから、計算量の知識というよりはプログラミングコードを書くところとか、問題文の状況を考える基礎力とかかなあ
あんまいいアドバイスできないけど練習あるのみだよ、ABC-Bをたくさんやるのがいいと思う
競プロはよく役に立たないと言われているけど、ABCのC問題までは本当にプログラミングの基礎力と関わってそうだから、できないのなら練習して損はないと思うよ

2022/10/15(土) 23:14:09.46

永続データ構造ってどの色くらいから常識になる？というかどこからそういう知識を身につけてるんだ
あの問題文を読んで木構造を作るぞって気持ちに初見でなれるものなのかな

2022/10/15(土) 23:15:16.34

まあ今日のBはそこそこ解きにくい方だったと思う

2022/10/15(土) 23:15:18.35

おれも永続データ構造は全然知らんけど、木でいけそうだなということにはすぐ気づけたよ

2022/10/15(土) 23:18:30.16

Dまでは早解き安定して出来るけどEから不安定になるから水色以上埋めていくしかないか

2022/10/15(土) 23:18:43.87

>>113
ネットで競プロっぽいこと検索してたら結構出てくる
はまやんさんのブログとかにまとまってるやつオススメ
あれは別に木構造作ろうというよりは、

ページにAのデータ全部コピーするとオーバーヘッドやばい
↓
ポインタアクセスで処理したい
↓
どうせ末尾しか毎回アクセスしないし、linked listっぽくすればよさそう
↓
というか、データ自体は時系列テーブル上に保存しとけばよくないか？

みたいな感じで思いつくのが自然な気がする

2022/10/15(土) 23:20:23.90

テストケースの公開って普段はコンテスト後何日ぐらいで行われるんですか？

2022/10/15(土) 23:23:11.47

>>117
思考過程が分かりやすくて助かるわ　ありがとう

2022/10/15(土) 23:24:39.60

>>118
そんなにすぐじゃないイメージ、今のところ2～3週間遅れぐらい？
https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=0
そもそも作業者のAtCoder運営自体がテストケースを直接見てデバッグってスタイルをそんなに好きじゃなさそうだから作業モチベも低そう
ここに貼ってくれれば誰かしらが見て指摘したりはできると思うけど

2022/10/15(土) 23:38:17.61

Ex、問題文がもろにStern Brocot木で笑ったな
Exをガチ目に解きに来る人はみんな知ってるだろ

2022/10/15(土) 23:47:59.64

Stern Brocot木の必要部分だけを取ってきた木の辺の数がf(T)か？
知識一発芸ならもっとたくさんの人が解いてるだろうし、ここからもいろいろ考えなきゃダメそうだな

2022/10/15(土) 23:49:13.54

辺というか頂点か

2022/10/15(土) 23:59:48.98

A問題で初歩的なループや再帰を解禁したの
整数パズルみたいなのよりええな

2022/10/16(日) 00:19:15.15

競プロっぽい問題得意じゃない人からしたら整数パズルより愚直ループのが解きやすいし、整数パズルできるやつからしたらその辺の文法覚えるのは簡単だろうしで、最近のAの難易度からするとループ縛りは実情にあってなかった

2022/10/16(日) 07:01:44.35

『競技プログラミングの鉄則』という本の問題A19のナップザック問題について質問です。
アマゾンのレビューでも指摘がありますが、dp[i][j]に品物1からiまでの中から合計重量が
ぴったりjになるという条件を満たすナップザックへの入れ方のうち合計価値が最大になる
ときの合計価値を入れています。

普通に考えると、dp[i][j]には部分問題の答えを入れると思います。
つまり、品物1からiの中から合計重量がj以下になるという条件を満たすナップザックへの
入れ方のうち合計価値が最大になるときの合計価値を入れるのが普通だと思います。

これはなぜですか？

2022/10/16(日) 11:47:32.10

・計算量的にも実装の複雑さもほとんど変わらない(最後に全体maxをとるかどうかは微々たる差)
・重量合計がちょうどwになるときの最大価値の方が、重量合計がw以下になるときの最大価値よりも得られる情報が多い
・形式的冪級数で定式化したとき少しだけきれい

鉄則本持っとらんけど、このあたりの理由か？
二番目が多分重要で、競プロではちょうどwで書く人の方が多い気がするぞ

2022/10/16(日) 14:38:27.53

昨日初めてコンテストに挑戦しましたが、2問しか正解できませんでした
C++だけじゃなく、もう1個文字列操作用の言語を使った方が良いような気がしました
Perlが理想なのですが、VSCODEでのデバッグ環境の構築方法がわかりません

2022/10/16(日) 14:58:25.40

Perlは遅すぎてc問題でも解けない可能性あるからやめた方がいい
スクリプト言語ならPythonが無難