X
競技プログラミングにハマるプログラマのスレ 173
■ このスレッドは過去ログ倉庫に格納されています
0001仕様書無しさん
垢版 |
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/
0002仕様書無しさん
垢版 |
2024/04/25(木) 20:03:37.01
競プロを頑張るというのはガイジ教育の負の刷り込み
優秀な人間は起業するし様々な専門分野のプロとして活躍する
0004仕様書無しさん
垢版 |
2024/04/25(木) 20:04:05.46
過去スレの165の名前だけ消えててちょっと気になるな
0009仕様書無しさん
垢版 |
2024/04/25(木) 20:18:02.28
上手くマージできたことに満足してスレを卒業出来そう　ありがとう　ありがとう
0011仕様書無しさん
垢版 |
2024/04/25(木) 20:27:32.53
agerって書いてる時点で自演確定
ageカスはしたらばスレとやらに帰れ
0016仕様書無しさん
垢版 |
2024/04/25(木) 20:30:58.69
お前らチームワーク良すぎだろ
コミュ障じゃなかったのかよ
0023仕様書無しさん
垢版 |
2024/04/25(木) 20:42:57.50
俺がデアトークしたらゴシインコが頓珍漢な煽りしてきたんだろ
atcoderもこどふぉも俺の感想だらけだしゴシインコしかいなくなってしまったのだなあ
0025仕様書無しさん
垢版 |
2024/04/25(木) 20:44:30.18
いやデアトークしてたのは俺だけだぞ
お前人狼だろ
0030仕様書無しさん
垢版 |
2024/04/25(木) 20:49:23.70
俺はABCとARCの感想には毎回参加してるぞ
緑インコだけど
0034仕様書無しさん
垢版 |
2024/04/25(木) 20:57:35.83
水色→黄色になるためにマスターするべきアルゴリズムってこんだけで充分なのか
座標圧縮 半分全列挙 行列累乗 ダブリング
Grundy 数 Rolling Hash 平方分割 最大流
最小カット 二部グラフ判定 二部マッチング
0037仕様書無しさん
垢版 |
2024/04/25(木) 21:07:19.54
俺は今緑色だけど、灰色時代に鉄則本でnimとgrundy数と座標圧縮と半分全列挙とダブリングとロリハは履修した
A～Eだとほとんど出てこないしあまり意味は無かった
0038仕様書無しさん
垢版 |
2024/04/25(木) 21:08:48.51
それで灰色時代にアルゴリズムを知ってる(理解してる)ことと解けることには物凄く差があることを実感したんだよな
0039仕様書無しさん
垢版 |
2024/04/25(木) 21:09:35.85
出題されないなら解く機会もないって意味ですね
0040仕様書無しさん
垢版 |
2024/04/25(木) 21:10:44.06
くんはセグ木すら把握してないのに緑色だったからな
これが知能の差
知識があっても使いこなす知能がなきゃなんの意味もない
0041仕様書無しさん
垢版 |
2024/04/25(木) 21:12:04.50
>>39
それもそうだし、F問題となると普通に難しい問題が多くて知識だけあってもあまり役に立たなかったんだよな
0042仕様書無しさん
垢版 |
2024/04/25(木) 21:13:56.33
コンテストに参加する前は水色とかすぐになれるんだろうなと思ってました…
0043仕様書無しさん
垢版 |
2024/04/25(木) 21:16:05.54
競プロは結局のところ知識ゲーじゃなくて算数パズルだからね
知識増やせばいいと思ってるのは甘い

考察体力をつけろ、とうむにくも言ってる
0051仕様書無しさん
垢版 |
2024/04/25(木) 22:01:18.13
黄色タッチまでは努力ゲー、そこから先は才能ゲー
これが庶民の感覚
0052仕様書無しさん
垢版 |
2024/04/25(木) 22:17:59.45
くんくん　くくん　くんくんく　くんくん
くんくんくくんく　くん！
0055仕様書無しさん
垢版 |
2024/04/25(木) 22:34:31.15
いうほど未来か？
スレに居るならここで挨拶していいぞ
0056仕様書無しさん
垢版 |
2024/04/25(木) 22:37:40.04
寧ろスレを見てこの世の真理に早い段階から気づいたからこそTKNDKSを受験して算オリ頑張った説まである
0057仕様書無しさん
垢版 |
2024/04/25(木) 22:56:42.06
ジェネルシはTKNDKSの中では普通にやっていけるんじゃないのか
0061仕様書無しさん
垢版 |
2024/04/25(木) 23:08:05.28
子供の自慢ってすごいいびつな承認欲求だな
子供がかわいそう
0064仕様書無しさん
垢版 |
2024/04/25(木) 23:49:07.18
高校生をゴシるのはちょっとね
成人してから出直してこい
0067仕様書無しさん
垢版 |
2024/04/25(木) 23:56:24.61
実験しまくってエスパーすれば解けそうな気がしなくもないけど、それだとあまり安定しなさそう
0071仕様書無しさん
垢版 |
2024/04/26(金) 00:15:29.45
呼び名で本質は変わんねえからお前が理解しやすい方で呼べばいいです
周期がそうなるのはセンス依存なので諦めて覚えろ
Nが素数ならKの倍数 mod Nは重複しないとか一度でも考えたことがあるなら解けてそうでないなら無理
0072仕様書無しさん
垢版 |
2024/04/26(金) 00:24:57.14
円環典型とかセンスとか言ってる奴低レート透けすぎて無理すぎる適当なアドバイスすんな

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

というかABC-D如きでセンスもクソもないだろレート透けすぎ
0073仕様書無しさん
垢版 |
2024/04/26(金) 00:29:11.66
>>72
ax+by=1に関しては解説中の周期が被らない部分の説明まで忘れてたすまん

とりあえず立式すればこのいつもの式になるのでNとの周期性を考えればおしまい(俺も当時Dまで10分以内で解けてた)
0074仕様書無しさん
垢版 |
2024/04/26(金) 00:30:23.01
まあ大学受験の数学とか真面目にやってなくてこの有名事実を知らないなら実験依存になってしまうのはそうだが、整数論の基本知識なので
0075仕様書無しさん
垢版 |
2024/04/26(金) 00:31:36.00
提出欄見たら質問してるの緑マスくんかよ
バックグラウンドとかレートが分かりにくいからコテハンでやれ
0076仕様書無しさん
垢版 |
2024/04/26(金) 00:31:49.96
Dで躓いてるやつに大学数学の講釈を垂れるの気持ちいいか？
お前の説明目線が違いすぎてセンスないよ
0077仕様書無しさん
垢版 |
2024/04/26(金) 00:32:44.16
センスか？
原始根とかフェル小とかから明らかに互いが素なら操作2は起こらなそう
操作2が起きたらどうなる？→1個ずれた状態から同じことが置きますね

普通に実験ってどうにかなると思うが
あとこの問題を典型として記憶することはあんまりないと思う
0078仕様書無しさん
垢版 |
2024/04/26(金) 00:33:14.43
カッコ列スタックとかよりも更に粒度が細かいので
0079仕様書無しさん
垢版 |
2024/04/26(金) 00:33:36.01
>>76
冷静に考えたらそれはそうだから反省してる
それはそれとして円環典型だから暗記でいいみたいな適当なアドバイスする奴は許せない
0080仕様書無しさん
垢版 |
2024/04/26(金) 00:35:17.97
別にフェルマーの小定理とかは説明するならそう、ってだけでもっと素朴な発見と実験から解けると思うけど
同じマスを踏むのはどういう条件か？踏んだらどうなるか？に注目すればほぼ解けるでしょ
中学生の時でも俺解けると思うけど
0083仕様書無しさん
垢版 |
2024/04/26(金) 00:37:52.55
だからこの問題を抽象化するなら解説中にもあるaとnが互いに素ならば0,a,2a,…,(n-1)a はmod n での余りが全て異なるっていう部分と、こういう形に帰着させやすくするためにgcdを取って互いに素にしておく部分なんだって
これらは大学受験レベルの整数の有名事実とテクニックなので、バックグラウンドがあれば解けるし知らなかったら履修しようという話
0084仕様書無しさん
垢版 |
2024/04/26(金) 00:39:07.93
特にGCDを取って互いに素にしておくことで一次不定方程式などを考えやすくするのは競プロでも無限回使われる典型テクニックで、流石に暖色ならば意識してないことはないと思う
0085仕様書無しさん
垢版 |
2024/04/26(金) 00:40:07.26
ABCは全部典型なので何も考えずに頭に入れましょう 終わり
0086仕様書無しさん
垢版 |
2024/04/26(金) 00:40:49.29
何も考えず抽象化もせず解説をそのままオウム返しで理解したつもりになってるのがインコ典型なので
0088仕様書無しさん
垢版 |
2024/04/26(金) 00:42:04.66
相変わらず書き込みからレートと学歴が透けることよ
0090仕様書無しさん
垢版 |
2024/04/26(金) 00:42:40.33
ABCは理論ではなく感覚で解きましょう。細かいことを考える必要はありません。これでみなさんも黄色コーダーです。by rng
0094仕様書無しさん
垢版 |
2024/04/26(金) 00:46:26.71
事実上並列じゃなかったから勢いは同じですよね
0095仕様書無しさん
垢版 |
2024/04/26(金) 00:47:59.58
いえ実際に人が増えていたので並列とみなせます
0097仕様書無しさん
垢版 |
2024/04/26(金) 01:07:44.38
みなさんマルチコアなのでマルチスレッドにしたほうがパフォーマンスが上がります
0100仕様書無しさん
垢版 |
2024/04/26(金) 01:33:47.19
マルチスレッドプログラミングができない純粋培養を絞り出せますね
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況