競技プログラミングにハマるプログラマのスレ 161

**仕様書無しさん** · 2024/03/02(土) 16:16:40.58

競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ
次スレは>>950

AtCoder http://atcoder.jp/
yukicoder http://yukicoder.me/
Codeforces http://codeforces.com/
CodeChef http://codechef.com/
Project Euler http://projecteuler.net/
CLIST http://clist.by/
AtCoder Problems http://kenkoooo.com/atcoder/
AtCoder Clans http://kato-hiro.github.io/AtCoderClans/

前スレ
競技プログラミングにハマるプログラマのスレ 160
https://medaka.5ch.net/test/read.cgi/prog/1708962732/

**仕様書無しさん** · 2024/03/02(土) 23:48:30.69

セグ木に載るかを考えるという発想の引き出しがなかった

**仕様書無しさん** · 2024/03/02(土) 23:49:53.61

E～G、F青diff3問連続みたいな体感難易度だったから順番シャッフルされるだけでdiff変わりそう

**仕様書無しさん** · 2024/03/02(土) 23:50:11.11

E、普通にE8くんが出してるコナケ分かんなかったんだけど
どうすれば分かるんだ？テストの生成はやったけど、テストの生成も悪かった(全パターン生成出来てなかった)

**仕様書無しさん** · 2024/03/02(土) 23:51:26.48

日本以外
A 7066/7260
E 251/690
F 1006/1415

日本
A 4441/4458
E 394/921
F 593/940

日本勢はEでハマってそう

**仕様書無しさん** · 2024/03/02(土) 23:51:58.76

ランテスコード書いてデバッグするのは典型なので、精進の時からすぐテストケースなどを確認せずデバッグ練習するといい

**仕様書無しさん** · 2024/03/02(土) 23:52:47.27

G方針自明で典型2つ組み合わせるだけなのに解かれなさすぎなのは多分Eのせい

**仕様書無しさん** · 2024/03/02(土) 23:52:47.50

中華インコも正直E解けなさすぎて、なんかUm_nikの言う間違った方向性のやつが多そうなんだよな

**仕様書無しさん** · 2024/03/02(土) 23:53:28.15

Eの共通部分計算する算数パートやりたくなさすぎてFGに逃げたな

**仕様書無しさん** · 2024/03/02(土) 23:55:01.47

アドホックジャパンを目指していくか

**仕様書無しさん** · 2024/03/02(土) 23:55:59.81

コドフォフォーラムとか見ててもAGCは異常アドホックと世界的に恐れられているからな
まあ日本人も全然解けてないんだが

**仕様書無しさん** · 2024/03/03(日) 00:02:14.35

>>208
なんだそれ気になる
もとのツイートかなんかある？

**仕様書無しさん** · 2024/03/03(日) 00:03:38.85

ツイートっていうかコドフォ記事だな
「最近の若いやつら知識だけありすぎ、精進はそういうんじゃない」みたいなの
だいぶ前のやつだな

**仕様書無しさん** · 2024/03/03(日) 00:04:12.25

Do not force ideas or algorithms on problems

**仕様書無しさん** · 2024/03/03(日) 00:07:34.74

ありがとう

確かにそれはそうなんだけどなぁ

**仕様書無しさん** · 2024/03/03(日) 00:07:56.21

それもインコを的確に刺している記事（の一節）だな
ただもっと前に語ってた精進論で似たようなのあったんだよな

**仕様書無しさん** · 2024/03/03(日) 00:09:15.72

私が聞いたことあるけど履修したことない高度デア一覧みたいなやつでしょ

**仕様書無しさん** · 2024/03/03(日) 00:10:24.03

codeforces um_nikで検索したら色々出てくるな

How to practice Competitive Programming [Um_nik version]

**仕様書無しさん** · 2024/03/03(日) 00:11:19.16

https://codeforces.com/blog/entry/98806
Q: Ok, but how do I learn new techniques if I don’t read editorials? I’m not supposed to invent everything on my own, am I?
A: Most of the time you don’t need to learn any advanced stuff to solve the problem, you can’t solve it because you are not trying hard enough or not paying attention to details or just being stupid. My experience even says that most Russian schoolchildren who do CP know too many algorithms.

これだな

**仕様書無しさん** · 2024/03/03(日) 00:11:27.69

こういうことをやってるからコンテスト中に誤って解説動画を投稿しても許されるわけか

**仕様書無しさん** · 2024/03/03(日) 00:13:11.59

まあ、ABCで手っ取り早く黄色くなるんだったら、Um_nik的に間違った戦い方でもいいけど、そんなに強くなれないよってところだな

**仕様書無しさん** · 2024/03/03(日) 00:13:41.11

ratismが浸透してる証

**仕様書無しさん** · 2024/03/03(日) 00:14:10.11

新参が好きそうだがこういう今更な記事にかじり付いても強くはならんぞ

**仕様書無しさん** · 2024/03/03(日) 00:14:27.20

レートが上がって読んでみると共感できる部分が増えてるな
蟻本と同じ感じだ

**仕様書無しさん** · 2024/03/03(日) 00:14:51.62

知らなくて解けない、がほぼなくなった時点で考察と実装の練習をするべきナリね
auxiliary tree履修してる青コーダー聞いてるか～？

**仕様書無しさん** · 2024/03/03(日) 00:15:38.37

ABC-Fまでの知識はARC/AGCでも必須だよな
インコだから適当言ってるかもだけど

**仕様書無しさん** · 2024/03/03(日) 00:16:11.56

うむニクはコンテスト終了前に解説動画を投稿しました。　←うむニクにペナルティが課されるんやろなあ…
なのでうむニクの答案を使用した人を罰します　←は？

**仕様書無しさん** · 2024/03/03(日) 00:16:38.34

この記事に齧りつくってのもおかしな話で、やるべきは、地道に自分のレベルより上の問題を解いて考察、実装の練習を続けていけという話でしょ

**仕様書無しさん** · 2024/03/03(日) 00:17:13.96

auxiliary treeはマージテクで常に殴れるゴミだと強弁してるんだがひとつも反論ないのなんでだよ

**仕様書無しさん** · 2024/03/03(日) 00:17:43.64

>>227
codeforcesはatcoderよりratism激しいぞ

**仕様書無しさん** · 2024/03/03(日) 00:18:51.56

寒色は正しいこと言ってても理不尽downvoteされる模様

**仕様書無しさん** · 2024/03/03(日) 00:19:09.25

この前の問題ではマージテクでも通せたなあ、実際俺そうしたし、で流したけど、「常に」なんてどこに書いてあった？

**仕様書無しさん** · 2024/03/03(日) 00:19:16.02

>>230
うむニクを罰する、だと角が立つから婉曲表現してるのか
包含関係でうむニクも罰せられるので

**仕様書無しさん** · 2024/03/03(日) 00:19:23.78

umnikの記事はe8の記事のアンチテーゼかな

**仕様書無しさん** · 2024/03/03(日) 00:19:57.04

>>232
俺だけがずっと言ってる

**仕様書無しさん** · 2024/03/03(日) 00:22:12.03

E8くん、インコのために知のコモディティ化を進めてるけど、本人は算パズ好きでアドホック指向な気がする

**仕様書無しさん** · 2024/03/03(日) 00:23:58.08

本当に競プロは典型であるべきと言ってるのはSSRS君の印象だが、情報処理能力と知能が高すぎるので、rngと同じぐらい典型の意味合いが信用できない

**仕様書無しさん** · 2024/03/03(日) 00:25:15.56

SSRSくんの典型にはARC-Eまで含まれてそう

**仕様書無しさん** · 2024/03/03(日) 00:25:39.53

数回前のこどふぉも例のABCボス問もライブラリ化済みATで通したしその方が自然だと思ってるからなんか毎回マージテクで突っかかってくるやつは無視してたな
実際上位互換なのかは知らんし流石にそんなわけないだろって思ってるが、今までATで解いてきた問題全てをマージテクで解く方法をわざわざ検証してないため

**仕様書無しさん** · 2024/03/03(日) 00:25:44.38

SSRS君の英文を読むスピードが速すぎる話好き

**仕様書無しさん** · 2024/03/03(日) 00:26:16.55

CF div 1の半分以上の問題も典型扱いされてそう

**仕様書無しさん** · 2024/03/03(日) 00:26:37.07

俺が3ヶ月社畜として休出しているうちにインフレ進みすぎだろ
Fとか半年前なら500人だろ

**仕様書無しさん** · 2024/03/03(日) 00:28:20.13

Fはマジで半年前だったら青diff中位とかだと思うけど、最近毎回こういうの出てるせいでインコの過学習が進んでる

**仕様書無しさん** · 2024/03/03(日) 00:28:22.59

AT vs マージテクのバトル何がしたいのかよくわかんねえ
マージテクはATで解ける問題はすべて解けるから上位互換、だからAT要らないみたいな主張してるの？
俺ATで解ける問題に習熟してないから考えないと真偽わからんけど

**仕様書無しさん** · 2024/03/03(日) 00:29:20.75

セグ木が茶上位まで落ちる回

**仕様書無しさん** · 2024/03/03(日) 00:29:41.47

ちょっと考えたが、auxiliary tree上で一点更新区間取得するクソキモ問題は作れるから絶対要らないとまでは言えないか
N頂点の木があって、頂点vの色はCv、値はAv
1 v x　 Av ←x
2 v c 　vの部分木内で色cの頂点全てのなんかを取得

**仕様書無しさん** · 2024/03/03(日) 00:29:55.89

必要な頂点を抽出した木(位置関係はそのまま)を考えたい場面って割とあるし、ATの履修アンチになる理由がわからん

**仕様書無しさん** · 2024/03/03(日) 00:30:04.04

ただのRMQならもう茶だろうな
てかchatgptでも解けるだろうし、灰になってもおかしくない

**仕様書無しさん** · 2024/03/03(日) 00:31:01.30

鉄則本にもあるレベルのを捻り無しで出したらそら灰にはなるだろ

**仕様書無しさん** · 2024/03/03(日) 00:32:45.16

AT、普通に典型90にもあっただろ

**仕様書無しさん** · 2024/03/03(日) 00:33:35.78

流石に灰はない
参加者の7割がACするくらいだけど、そんなに勉強してる人ばかりじゃないでしょ

**仕様書無しさん** · 2024/03/03(日) 00:39:49.79

UFやるだけが灰な時点で

**仕様書無しさん** · 2024/03/03(日) 00:40:34.29

別にどんだけ早くセグ木履修してもいいんだけど、なんかもったいない感じがするな
(数年前に)最近の小学生はぺクスやってると聞いてもったいねぇと思った感情に似ている

**仕様書無しさん** · 2024/03/03(日) 00:41:45.70

例えが微妙すぎるだろ

**仕様書無しさん** · 2024/03/03(日) 00:42:24.83

246を適当に産んだにしてはauxiliary tree以外で解けなくてこまった
2 v c 　vの部分木内で色cに塗られた頂点がなければ-1　あれば該当頂点のAiの最小値　
で考えてるけどマージテクだと無理だな

**仕様書無しさん** · 2024/03/03(日) 00:43:47.38

>>254
俺も投稿してから思った
消したい

**仕様書無しさん** · 2024/03/03(日) 00:45:49.30

あーあ、黒歴史“造っちゃった”ねえ……ｗ

**仕様書無しさん** · 2024/03/03(日) 00:46:39.52

ペクスってなに？韓国語？apex？

**仕様書無しさん** · 2024/03/03(日) 00:47:01.67

セクスのことやろ

**仕様書無しさん** · 2024/03/03(日) 00:47:06.59

セクスのことやろ

**仕様書無しさん** · 2024/03/03(日) 00:47:40.15

apexというプログラミング言語があるらしい
最近の小学生は進んでるな

**仕様書無しさん** · 2024/03/03(日) 00:48:38.12

セクスって何？

**仕様書無しさん** · 2024/03/03(日) 00:48:51.90

最近鬱病とかが原因じゃなくて生活リズムがめちゃくちゃなせいでいつ寝ても数時間で目が覚めるようになってしまったんだが助けてほしい
コンテストにも支障出てる

**仕様書無しさん** · 2024/03/03(日) 00:48:52.44

>>115
多分こんなケースじゃねえかなあ

https://www.desmos.com/3d/b3849fdb21?lang=ja

「立方体1つの頂点の座標を(0,0,0)にして、残りの立方体の頂点の座標を『正の範囲で』全探索する」って戦略だとNoと誤答してしまう

**仕様書無しさん** · 2024/03/03(日) 00:49:31.11

あやしいURLかと思ってビビった

**仕様書無しさん** · 2024/03/03(日) 00:49:40.69

HELP！

**仕様書無しさん** · 2024/03/03(日) 00:52:36.40

>>263
俺も同じ
仕事帰ったらすぐ寝ちゃって、12時頃に目が覚め風呂入って4時ぐらいにまた寝てる

**仕様書無しさん** · 2024/03/03(日) 00:53:34.19

>>267
明らかに分割睡眠って眠りの質が浅いから困るわ

**仕様書無しさん** · 2024/03/03(日) 00:55:04.68

コンテスト後にすぐ寝るって難しい

**仕様書無しさん** · 2024/03/03(日) 00:55:24.86

俺も睡眠障害で困る
生命力でインコに負けて死んでコンテストに出らなくなったら死んでも死にきれん

**仕様書無しさん** · 2024/03/03(日) 00:55:43.76

コンテストに生活リズムを合わせないのが悪い
起きるのは夕方～夜で固定して良い

**仕様書無しさん** · 2024/03/03(日) 00:56:47.33

定期的に寝つきがゴミみたいに悪いか数時間で覚醒する睡眠障害のどっちかを引くから困る　
生活リズム直すのに無限時間かかるのに崩れる時は一瞬なのもカス

**仕様書無しさん** · 2024/03/03(日) 01:04:31.57

やる気失せたとか言ってるけどsakiさんからやる気について学んだことはもう忘れたのか？

**仕様書無しさん** · 2024/03/03(日) 01:09:21.42

ABCARC後にここで話してる時が一番楽しいな

**仕様書無しさん** · 2024/03/03(日) 01:10:31.51

ABCARC自体はそれほど楽しくないみたいに言うな

**仕様書無しさん** · 2024/03/03(日) 01:16:51.98

そう言ってるのだが

**仕様書無しさん** · 2024/03/03(日) 01:18:09.01

普段のスレがつまらないという意味かもしれない

**仕様書無しさん** · 2024/03/03(日) 01:23:16.27

コンテストは昼に開催してほしいわ

**仕様書無しさん** · 2024/03/03(日) 01:24:59.04

海外勢の都合もあるから昼に開催されることはないだろうな

**仕様書無しさん** · 2024/03/03(日) 01:25:15.20

E難問かと思ってFで沼ってしまった
やってみたら簡単だった…

**仕様書無しさん** · 2024/03/03(日) 01:26:35.26

E問題、killer2にはじかれた。
killer2ってどんなケースなんだろう。
走査範囲を0≦x,y,z＜15にしても通らないんだよな。
平行移動すれば同じかと思うのだが…

自分は0≦x,y,z＜8でやったんだけど、そのへんの範囲の決め方がわからないよ

**仕様書無しさん** · 2024/03/03(日) 01:30:46.90

>>273
教えてください
sakiさんなんて言ってましたか？

**仕様書無しさん** · 2024/03/03(日) 01:32:38.53

>>281
>>264

**仕様書無しさん** · 2024/03/03(日) 01:39:20.47

G除いたけど、前後で最大何文字共通するかでbitDPか

**仕様書無しさん** · 2024/03/03(日) 01:41:38.64

セグ木ってライブラリ化したほうがいいか？
適当に2個大きい素数乱択してダブルチェックしたいけど素数をランダムで生成するにはどうすれば良いですか？
埋め込んでその中から乱択でOK牧場？

**仕様書無しさん** · 2024/03/03(日) 01:45:45.15

セグ木のライブラリ作るか自殺するか悩み中

**仕様書無しさん** · 2024/03/03(日) 01:46:22.64

ロリハのこと話してる？

**仕様書無しさん** · 2024/03/03(日) 01:47:06.73

ホンマや
ロリハセグ木のことだつた

**仕様書無しさん** · 2024/03/03(日) 01:47:29.97

自殺はさておき、どう考えてもセグ木の話題じゃなくて悩み中

**仕様書無しさん** · 2024/03/03(日) 01:49:53.63

ライブラリ化するんならBITに載せた方がよくね

**仕様書無しさん** · 2024/03/03(日) 01:54:04.48

>>290
確かにかーに

**仕様書無しさん** · 2024/03/03(日) 01:54:33.33

つか窃盗するか？
オススメある？

**仕様書無しさん** · 2024/03/03(日) 01:56:16.91

BITってO(n)構築できたっけ？

**仕様書無しさん** · 2024/03/03(日) 02:01:53.89

>>292
犯罪予告？

**仕様書無しさん** · 2024/03/03(日) 02:09:45.28

やったことないけどO(n)で累積和取ってO(1)区間取得をO(n)回やるだけでは

**仕様書無しさん** · 2024/03/03(日) 02:12:57.13

そもそもBITですらなくね

**仕様書無しさん** · 2024/03/03(日) 02:14:50.32

素数をランダムに生成するんだったら適当に乱数だしてミラーラビン法で判定すればいいんじゃないかな

ミラーラビン法は確率的アルゴリズムだけど64bitの範囲に限定すれば決定的に判定する方法はあるし、実際いまc++で試してみたら一個素数を見つけ出すのに0.1秒もかからなかったし

**仕様書無しさん** · 2024/03/03(日) 02:15:54.55

よく考えるとロリハフェニク木の実装鬱だな
更新クエリやりたくなさすぎる

**仕様書無しさん** · 2024/03/03(日) 02:16:48.92

ロリハ　素数
で検索したら素数乱択するのはガイジって書いてありますね

**仕様書無しさん** · 2024/03/03(日) 02:33:25.67

すみません、6種類取れば良いですよね

**仕様書無しさん** · 2024/03/03(日) 02:35:43.61

デアの話題迷惑だから他でやれ