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

**仕様書無しさん** · 2024/04/25(木) 20:02:00.50

競技プログラミング、オンラインジャッジ、プログラミングコンテストや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/

前スレ
https://medaka.5ch.net/test/read.cgi/prog/1710398066/
競技プログラミングにハマるプログラマのスレ 166
https://medaka.5ch.net/test/read.cgi/prog/1710650865/
競技プログラミングにハマるプログラマのスレ 167
https://medaka.5ch.net/test/read.cgi/prog/1710987911/
競技プログラミングにハマるプログラマのスレ 168
https://medaka.5ch.net/test/read.cgi/prog/1711463770/
競技プログラミングにハマるプログラマのスレ 169
https://medaka.5ch.net/test/read.cgi/prog/1711884759/
競技プログラミングにハマるプログラマのスレ 170
https://medaka.5ch.net/test/read.cgi/prog/1712220373/
競技プログラミングにハマるプログラマのスレ 171(旧)
https://medaka.5ch.net/test/read.cgi/prog/1712726816/
競技プログラミングにハマるプログラマのスレ 171(新)
https://medaka.5ch.net/test/read.cgi/prog/1712726828/
競技プログラミングにハマるプログラマのスレ 172
https://medaka.5ch.net/test/read.cgi/prog/1713176839/

**仕様書無しさん** · 2024/04/25(木) 20:03:37.01

競プロを頑張るというのはガイジ教育の負の刷り込み
優秀な人間は起業するし様々な専門分野のプロとして活躍する

**仕様書無しさん** · 2024/04/25(木) 20:03:48.51

ガイジスレ終了

**仕様書無しさん** · 2024/04/25(木) 20:04:05.46

過去スレの165の名前だけ消えててちょっと気になるな

**仕様書無しさん** · 2024/04/25(木) 20:04:12.35

有能

**仕様書無しさん** · 2024/04/25(木) 20:05:40.09

>>2
こう思ってた頃があったが俺の間違いだった

**仕様書無しさん** · 2024/04/25(木) 20:17:14.15

>>1
過去スレ精進してね

**仕様書無しさん** · 2024/04/25(木) 20:17:28.13

>>1
ageカスは自演連投荒らしだから注意

**仕様書無しさん** · 2024/04/25(木) 20:18:02.28

上手くマージできたことに満足してスレを卒業出来そう　ありがとう　ありがとう

**仕様書無しさん** · 2024/04/25(木) 20:26:59.09

agerによるスレ統一で平和が訪れた

**仕様書無しさん** · 2024/04/25(木) 20:27:32.53

agerって書いてる時点で自演確定
ageカスはしたらばスレとやらに帰れ

**仕様書無しさん** · 2024/04/25(木) 20:29:31.88

体の相性ってなに

**仕様書無しさん** · 2024/04/25(木) 20:29:36.12

マージAC射精完了

**仕様書無しさん** · 2024/04/25(木) 20:30:17.99

性の喜びおじさんに教えてもらえ

**仕様書無しさん** · 2024/04/25(木) 20:30:35.00

ゴールデンウィークくらいゴミスレやめたら？

**仕様書無しさん** · 2024/04/25(木) 20:30:58.69

お前らチームワーク良すぎだろ
コミュ障じゃなかったのかよ

**仕様書無しさん** · 2024/04/25(木) 20:32:02.00

10秒差で生まれて10秒差で埋まるこれがdesteny

**仕様書無しさん** · 2024/04/25(木) 20:33:20.68

まるで双子のようだ

**仕様書無しさん** · 2024/04/25(木) 20:34:35.19

マルチスレッドおもしろかったね
またやろ

**仕様書無しさん** ころころ · 2024/04/25(木) 20:35:08.50

マルチスレッドじゃなくて平衡二分スレの回転だったが

**仕様書無しさん** · 2024/04/25(木) 20:40:18.16

結局どっちもゴシスレだったな

**仕様書無しさん** · 2024/04/25(木) 20:42:24.63

デアもしてただろ

**仕様書無しさん** · 2024/04/25(木) 20:42:57.50

俺がデアトークしたらゴシインコが頓珍漢な煽りしてきたんだろ
atcoderもこどふぉも俺の感想だらけだしゴシインコしかいなくなってしまったのだなあ

**仕様書無しさん** · 2024/04/25(木) 20:44:13.68

avcoderの感想戦は俺もいたぞ

**仕様書無しさん** · 2024/04/25(木) 20:44:30.18

いやデアトークしてたのは俺だけだぞ
お前人狼だろ

**仕様書無しさん** · 2024/04/25(木) 20:45:08.65

おれはゴシしてないが？

**仕様書無しさん** · 2024/04/25(木) 20:45:59.84

今夜お前釣るからよろしく

**仕様書無しさん** · 2024/04/25(木) 20:46:12.05

おれはゴシしかしてない

**仕様書無しさん** · 2024/04/25(木) 20:48:11.49

インコ2人狼1占い師1

**仕様書無しさん** · 2024/04/25(木) 20:49:23.70

俺はABCとARCの感想には毎回参加してるぞ
緑インコだけど

**仕様書無しさん** · 2024/04/25(木) 20:51:53.83

ドラケンはスレ見てないだろ

**仕様書無しさん** · 2024/04/25(木) 20:52:52.72

ARCには参加しないのだ！

**仕様書無しさん** · 2024/04/25(木) 20:54:54.16

のん氏のだ氏

**仕様書無しさん** · 2024/04/25(木) 20:57:35.83

水色→黄色になるためにマスターするべきアルゴリズムってこんだけで充分なのか
座標圧縮半分全列挙行列累乗ダブリング
Grundy 数 Rolling Hash 平方分割最大流
最小カット二部グラフ判定二部マッチング

**仕様書無しさん** · 2024/04/25(木) 21:00:32.62

はい

**仕様書無しさん** · 2024/04/25(木) 21:01:09.30

はい

**仕様書無しさん** · 2024/04/25(木) 21:07:19.54

俺は今緑色だけど、灰色時代に鉄則本でnimとgrundy数と座標圧縮と半分全列挙とダブリングとロリハは履修した
A～Eだとほとんど出てこないしあまり意味は無かった

**仕様書無しさん** · 2024/04/25(木) 21:08:48.51

それで灰色時代にアルゴリズムを知ってる(理解してる)ことと解けることには物凄く差があることを実感したんだよな

**仕様書無しさん** · 2024/04/25(木) 21:09:35.85

出題されないなら解く機会もないって意味ですね

**仕様書無しさん** · 2024/04/25(木) 21:10:44.06

くんはセグ木すら把握してないのに緑色だったからな
これが知能の差
知識があっても使いこなす知能がなきゃなんの意味もない

**仕様書無しさん** · 2024/04/25(木) 21:12:04.50

>>39
それもそうだし、F問題となると普通に難しい問題が多くて知識だけあってもあまり役に立たなかったんだよな

**仕様書無しさん** · 2024/04/25(木) 21:13:56.33

コンテストに参加する前は水色とかすぐになれるんだろうなと思ってました…

**仕様書無しさん** · 2024/04/25(木) 21:16:05.54

競プロは結局のところ知識ゲーじゃなくて算数パズルだからね
知識増やせばいいと思ってるのは甘い

考察体力をつけろ、とうむにくも言ってる

**仕様書無しさん** · 2024/04/25(木) 21:17:42.04

緑が喋った

**仕様書無しさん** · 2024/04/25(木) 21:17:53.77

ABCで黄になるだけだったら知識ゲーです

**仕様書無しさん** · 2024/04/25(木) 21:20:01.37

緑は雑魚
水色は最強

**仕様書無しさん** · 2024/04/25(木) 21:21:05.47

くんの近況知ってたら語れ

**仕様書無しさん** · 2024/04/25(木) 21:33:31.10

学割買ったみたいだけど通学してるんか

**仕様書無しさん** · 2024/04/25(木) 21:55:15.45

緑って言葉話せたの？

**仕様書無しさん** · 2024/04/25(木) 21:56:44.68

単語の理解度が浅いので意思疎通は困難

**仕様書無しさん** · 2024/04/25(木) 22:01:18.13

黄色タッチまでは努力ゲー、そこから先は才能ゲー
これが庶民の感覚

**仕様書無しさん** · 2024/04/25(木) 22:17:59.45

くんくん　くくん　くんくんく　くんくん
くんくんくくんく　くん！

**仕様書無しさん** · 2024/04/25(木) 22:24:28.38

TKNDKS+UTならなあ

**仕様書無しさん** · 2024/04/25(木) 22:28:00.14

未来のジェネルシってところか？
https://twitter.com/Nanaio627/status/1763965919016149425?t=VnFzt7uYpYhbXXX2bCrAvQ&s=19
https://twitter.com/thejimwatkins

**仕様書無しさん** · 2024/04/25(木) 22:34:31.15

いうほど未来か？
スレに居るならここで挨拶していいぞ

**仕様書無しさん** · 2024/04/25(木) 22:37:40.04

寧ろスレを見てこの世の真理に早い段階から気づいたからこそTKNDKSを受験して算オリ頑張った説まである

**仕様書無しさん** · 2024/04/25(木) 22:56:42.06

ジェネルシはTKNDKSの中では普通にやっていけるんじゃないのか

**仕様書無しさん** · 2024/04/25(木) 22:59:27.57

ルシファーはどうでしたか？

**仕様書無しさん** · 2024/04/25(木) 23:03:12.72

マージされた割には速度落ちるの謎だな

**仕様書無しさん** · 2024/04/25(木) 23:06:46.00

じゃあまた分裂しよう

**仕様書無しさん** · 2024/04/25(木) 23:08:05.28

子供の自慢ってすごいいびつな承認欲求だな
子供がかわいそう

**仕様書無しさん** · 2024/04/25(木) 23:10:03.21

ここは当事者だらけなのでね

**仕様書無しさん** · 2024/04/25(木) 23:37:28.21

子供は有名人らしい

**仕様書無しさん** · 2024/04/25(木) 23:49:07.18

高校生をゴシるのはちょっとね
成人してから出直してこい

**仕様書無しさん** · 2024/04/25(木) 23:52:25.96

ガイジガイジガイジ

**仕様書無しさん** · 2024/04/25(木) 23:55:22.94

何度見ても天才解法にしか見えないんだが
こういうのを機械的に処理するにはどうすればいいんだ？
https://atcoder.jp/contests/abc290/tasks/abc290_d

**仕様書無しさん** · 2024/04/25(木) 23:56:24.61

実験しまくってエスパーすれば解けそうな気がしなくもないけど、それだとあまり安定しなさそう

**仕様書無しさん** · 2024/04/25(木) 23:59:59.47

円環の構築典型なので暗記でよい

**仕様書無しさん** · 2024/04/26(金) 00:09:21.15

周期性を考えるとかじゃない？

**仕様書無しさん** · 2024/04/26(金) 00:10:34.02

周期がn/最大公約数になるところがムズい

**仕様書無しさん** · 2024/04/26(金) 00:15:29.45

呼び名で本質は変わんねえからお前が理解しやすい方で呼べばいいです
周期がそうなるのはセンス依存なので諦めて覚えろ
Nが素数ならKの倍数 mod Nは重複しないとか一度でも考えたことがあるなら解けてそうでないなら無理

**仕様書無しさん** · 2024/04/26(金) 00:24:57.14

円環典型とかセンスとか言ってる奴低レート透けすぎて無理すぎる適当なアドバイスすんな

とりあえず立式するとx=Da-Nbが出てきて、これはDとNのgcdを取るとax+byの形(a,bが互いに素ならばax+by=1なるx,yが存在するので任意の整数を作れる、大受典型でもある)がでるので、これをもとに周期がわかる
で周期さえわかってしまえば後はその分ずらすだけなのでおしまい

というかABC-D如きでセンスもクソもないだろレート透けすぎ

**仕様書無しさん** · 2024/04/26(金) 00:29:11.66

>>72
ax+by=1に関しては解説中の周期が被らない部分の説明まで忘れてたすまん

とりあえず立式すればこのいつもの式になるのでNとの周期性を考えればおしまい(俺も当時Dまで10分以内で解けてた)

**仕様書無しさん** · 2024/04/26(金) 00:30:23.01

まあ大学受験の数学とか真面目にやってなくてこの有名事実を知らないなら実験依存になってしまうのはそうだが、整数論の基本知識なので

**仕様書無しさん** · 2024/04/26(金) 00:31:36.00

提出欄見たら質問してるの緑マスくんかよ
バックグラウンドとかレートが分かりにくいからコテハンでやれ

**仕様書無しさん** · 2024/04/26(金) 00:31:49.96

Dで躓いてるやつに大学数学の講釈を垂れるの気持ちいいか？
お前の説明目線が違いすぎてセンスないよ

**仕様書無しさん** · 2024/04/26(金) 00:32:44.16

センスか？
原始根とかフェル小とかから明らかに互いが素なら操作2は起こらなそう
操作2が起きたらどうなる？→1個ずれた状態から同じことが置きますね

普通に実験ってどうにかなると思うが
あとこの問題を典型として記憶することはあんまりないと思う

**仕様書無しさん** · 2024/04/26(金) 00:33:14.43

カッコ列スタックとかよりも更に粒度が細かいので

**仕様書無しさん** · 2024/04/26(金) 00:33:36.01

>>76
冷静に考えたらそれはそうだから反省してる
それはそれとして円環典型だから暗記でいいみたいな適当なアドバイスする奴は許せない

**仕様書無しさん** · 2024/04/26(金) 00:35:17.97

別にフェルマーの小定理とかは説明するならそう、ってだけでもっと素朴な発見と実験から解けると思うけど
同じマスを踏むのはどういう条件か？踏んだらどうなるか？に注目すればほぼ解けるでしょ
中学生の時でも俺解けると思うけど

**仕様書無しさん** · 2024/04/26(金) 00:36:09.71

まって足し算か
誤読してた

**仕様書無しさん** · 2024/04/26(金) 00:37:09.14

掛け算だと解けなくない？

**仕様書無しさん** · 2024/04/26(金) 00:37:52.55

だからこの問題を抽象化するなら解説中にもあるaとnが互いに素ならば0,a,2a,…,(n-1)a はmod n での余りが全て異なるっていう部分と、こういう形に帰着させやすくするためにgcdを取って互いに素にしておく部分なんだって
これらは大学受験レベルの整数の有名事実とテクニックなので、バックグラウンドがあれば解けるし知らなかったら履修しようという話

**仕様書無しさん** · 2024/04/26(金) 00:39:07.93

特にGCDを取って互いに素にしておくことで一次不定方程式などを考えやすくするのは競プロでも無限回使われる典型テクニックで、流石に暖色ならば意識してないことはないと思う

**仕様書無しさん** · 2024/04/26(金) 00:40:07.26

ABCは全部典型なので何も考えずに頭に入れましょう終わり

**仕様書無しさん** · 2024/04/26(金) 00:40:49.29

何も考えず抽象化もせず解説をそのままオウム返しで理解したつもりになってるのがインコ典型なので

**仕様書無しさん** · 2024/04/26(金) 00:41:02.18

りんご式解説はわかりやすい

**仕様書無しさん** · 2024/04/26(金) 00:42:04.66

相変わらず書き込みからレートと学歴が透けることよ

**仕様書無しさん** · 2024/04/26(金) 00:42:26.30

ちんこ式解説

**仕様書無しさん** · 2024/04/26(金) 00:42:40.33

ABCは理論ではなく感覚で解きましょう。細かいことを考える必要はありません。これでみなさんも黄色コーダーです。by rng

**仕様書無しさん** · 2024/04/26(金) 00:45:17.84

でもあなた達寒色で停滞してるインコですよね

**仕様書無しさん** · 2024/04/26(金) 00:45:48.65

マージしたら勢い上がって楽しい！

**仕様書無しさん** · 2024/04/26(金) 00:46:02.90

原始根みたいな話と繋がってくるね

**仕様書無しさん** · 2024/04/26(金) 00:46:26.71

事実上並列じゃなかったから勢いは同じですよね

**仕様書無しさん** · 2024/04/26(金) 00:47:59.58

いえ実際に人が増えていたので並列とみなせます

**仕様書無しさん** · 2024/04/26(金) 00:48:45.71

考えるな感じろ

**仕様書無しさん** · 2024/04/26(金) 01:07:44.38

みなさんマルチコアなのでマルチスレッドにしたほうがパフォーマンスが上がります

**仕様書無しさん** · 2024/04/26(金) 01:17:51.49

スレッド間で通信できるようにしましょう

**仕様書無しさん** · 2024/04/26(金) 01:18:02.01

競合が起きないように気をつけて

**仕様書無しさん** · 2024/04/26(金) 01:33:47.19

マルチスレッドプログラミングができない純粋培養を絞り出せますね

**仕様書無しさん** · 2024/04/26(金) 01:39:03.32

はい　純粋培養インコは野生に帰ってください