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

■ このスレッドは過去ログ倉庫に格納されています
2022/12/26(月) 12:47:37.63ID:CkzYHyzir
!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/

※前スレ
競技プログラミング総合スレ 64
https://mevius.5ch.net/test/read.cgi/tech/1664700238/
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured
86sage (ｵｯﾍﾟｹ Srbb-A544)
垢版 |
2023/01/03(火) 01:14:46.33ID:3U7/noadr
>>84 >>85
もしかして: AtCoder Companions
2023/01/03(火) 01:39:20.81ID:5KR4gJydM
言語仕様の勘違い由来のバグ取りはかなり気付くの難しいから、初心者がそういうの見つけるのに使えそうだな
2023/01/04(水) 01:26:53.42ID:WeNv9SlE0
今年こそ青に定着したいのに三が日何もやってねえ...(´・ω・`)
2023/01/04(水) 08:04:52.46ID:aNwmJoG10
正月で生活リズムが整っちゃってこどふぉに出られなくなっちゃった
2023/01/04(水) 15:05:35.57ID:JS//sD6wM
Hello 2023普通に良コンテストだったぞ
ドンマイ
2023/01/04(水) 22:15:22.80ID:vSzNCwvu0
えAtCoder Companions有能すぎるんだけど. これ何でテンプレ入ってないん?
2023/01/04(水) 23:19:19.62ID:mr/FCdH/0
TL少し長めの問題なら、10^9回計算する解法でも通るんだね（想定解法じゃなかったけど）
2023/01/05(木) 06:17:26.70ID:7AKtp3Yz0
重複組合せの式nHrで、整数のオーバーフローをできるだけ避けて計算したいのですが

とある、場合の数を数える問題で、普通はたぶんDP的に解くんだけど、規則的な形だった
ので、「これって重複組合せじゃん」と見抜いたんですよ
でnHrを例の階乗の公式(n+r)!/n!/r!で計算して、テストケースを走らせるとnやrが小さい
のは通るのでやはりおkらしい。ただnやrが大きくなると階乗がオーバーフローしてしまう
解が数式で求まったのに数値的にはそんなに便利じゃないって?

でも普通nHrの計算って分子と分母でキャンセルして結果は大きくならないことが多い
ですよね。うまいこと変形したらオーバーフローしなさそう。もしそういうのが既にあれば
nHrの漸化式みたいので計算する手もありそう、って結局DPみたいなことしてる気がw
2023/01/05(木) 10:09:29.03ID:36BPqP5u0
ちなみにnとrはどういう大きさの値？
2023/01/05(木) 10:51:51.53ID:7AKtp3Yz0
>>94
どちらも2から60ぐらいの間の整数がランダムな感じでセットされるようです
2023/01/05(木) 11:18:12.30ID:36BPqP5u0
>>95
(n+r)!/n!/r! = n+r C r
と変形して、あとはKnuthのTAOCPに載ってるオーバーフローしにくいやり方で組み合わせを計算してみよう
https://stackoverflow.com/questions/1838368/calculating-the-amount-of-combinations/1838732#1838732
97デフォルトの名無しさん (ﾜｯﾁｮｲ 362a-3363)
垢版 |
2023/01/05(木) 12:36:04.14ID:BpZRjrYb0
パスカルの三角形で計算する方が確実かな
2023/01/05(木) 12:51:55.08ID:7AKtp3Yz0
>>96
どうもです。が、n, mは実際には100ぐらいまでいくようで（すみません）、
リンク先の最初のコードだと 100 C 99 とかで間違った答えが。おっとクヌース先生敗北?

こういう場合は普通にCの性質より 100 C 99 = 100 C (100-99) = 100 C 1 とすれば
精度も計算量も良さそうです
というわけで... 全テストケースクリアしました! ありがとうございます
2023/01/05(木) 13:03:57.95ID:dpF3fKIy0
100C50はint64に収まらないからね
2023/01/05(木) 13:23:09.26ID:7AKtp3Yz0
>>99
そうですね、nCrで r=n/2付近はでかい数になりますよね
テストケースではそういう場合は除外されているようです

そういうわけで、組み合わせを直接計算するとテストケースでは64bit整数がいるんですが、
組み合わせの直接計算でなく、DPで再帰的に場合の数を計算するようなコードだと
32bit整数で大丈夫な感じなんですが... ええと
2023/01/05(木) 13:39:53.75ID:7AKtp3Yz0
ああそうか、それが実質的には >>97 パスカルの三角形を上向きに登っていくのと等価なの
かな。三角形がでかい場合はあんま三角形の底辺の真ん中の方には行かない場合のみで
と自己納得w
2023/01/05(木) 14:48:33.70ID:WkAYqVn/d
よくわからんけど答えが32bit整数に収まる程度なら適当に大きめのmodとればいいんじゃないの
2023/01/07(土) 18:03:15.80ID:Fs1C7h8fp
ARC3週連続か
2023/01/07(土) 19:51:43.95ID:SPR4wSEy0
ARC生えまくり
嬉しいけど息切れしないか心配
105デフォルトの名無しさん (ｱｳｱｳｳｰ Sa85-mbJl)
垢版 |
2023/01/07(土) 22:45:57.01ID:LoL6HnAVa
Dの解説読んでもわけわからん
まず、割り切れるのがわかってるんだから、iの最大値なんて関係なくない？

iの2乗で割り切れる時に解が見つかるとして計算したけど時間内に解が求められなかった。
糞問題じゃないのこれ？
2023/01/07(土) 22:47:21.33ID:j8FCEvhl0
どんまい
2023/01/07(土) 22:47:32.24ID:/Ri7nxfpM
解けなかったら糞問
で、おまえのレートは？
2023/01/07(土) 22:49:07.34ID:e3AWo2MYp
Dで素因数分解出来ることが保証されてるのが頭から抜けてたせいで絶対想定解じゃないだろって思いながら無駄にミラーラビン素数判定法とか使ってしまった
2023/01/07(土) 22:51:15.35ID:e3AWo2MYp
素因数分解出来ることっていうより素因数分解の一意性か
2023/01/07(土) 22:52:05.10ID:SPR4wSEy0
問題は全然クソじゃないと思うけど、i=1,2,…,⌊N^(1/3)⌋のうち、N が i で割り切れるような最大の i って書き方が何か変で、i=2,…,⌊N^(1/3)⌋のうちNを割り切る最小のiと言った方が正しいような気がする
2023/01/07(土) 22:54:54.84ID:SPR4wSEy0
G、本質パートからしてボリュームあるのにさらに任意ｍod二項係数使うんかいって思ったけど、想定解は全然使ってなかった
2023/01/07(土) 22:57:18.84ID:SPR4wSEy0
>>105
ちなみに、そのやり方でTLEしないと思うんだけど、N^(1/3)までで探索打ち切った？
113デフォルトの名無しさん (ｱｳｱｳｳｰ Sa85-mbJl)
垢版 |
2023/01/07(土) 22:58:15.60ID:LoL6HnAVa
あー、二乗の計算時間もだめだってのか。効率化難しいな。
sqrt使うところに頭が向かわなかったわ。
お前らよく解けるねこれ...
114デフォルトの名無しさん (ｱｳｱｳｳｰ Sa85-mbJl)
垢版 |
2023/01/07(土) 22:59:01.50ID:LoL6HnAVa
>>105
打ち切った。でもダメだった。
2023/01/07(土) 23:00:27.31ID:j8FCEvhl0
Dは想定回じゃなくても、いろんなテクで解けるし、みんないずれかの解法にサクッとたどり着いてる感じだな
2023/01/07(土) 23:01:13.52ID:SPR4wSEy0
>>113
なんかその書きぶりだと、もしかしてj^2 = N/iになるようなjも探索で出した感じ？
2023/01/07(土) 23:01:47.41ID:e3AWo2MYp
Eが素直なDFSすぎてDと逆でも良いだろとは思った
2023/01/07(土) 23:03:43.12ID:SPR4wSEy0
Eはむしろ個人的には意表を突かれた感じでギョッとした
Fの方が実は素直にロリハやるだけだったりする
119デフォルトの名無しさん (ｱｳｱｳｳｰ Sa85-mbJl)
垢版 |
2023/01/07(土) 23:04:53.24ID:LoL6HnAVa
>112
すまん、冷静に考えたら打ち切ってない
必ず1個の解が見つかるはずで、解が見つかったら打ち切ったら良いんだから、N^(1/3)までカウントアップしないと思ったんだ。だから、N^(1/3)で止めるロジックは無意味だと思ってる。

ただ、自分のやり方だと解を二乗根に絞って計算したせいで最大値がN^(1/2)/2になってしまったんだね。
そのせいか...
120デフォルトの名無しさん (ﾜｯﾁｮｲ 11bd-vxq+)
垢版 |
2023/01/07(土) 23:06:46.63ID:SPR4wSEy0
>>119
>必ず1個の解が見つかるはずで、解が見つかったら打ち切ったら良いんだから、N^(1/3)までカウントアップしないと思ったんだ。だから、N^(1/3)で止めるロジックは無意味だと思ってる。
確かにそれはそう、ナンセンスな質問ですまない
O(N^(1/2))になってたのがTLEの原因っぽいね
2023/01/07(土) 23:08:57.85ID:j8FCEvhl0
EやFはサクッと解けたけど、おれもDはちょっとギョッとしたよ
おれも数学弱だな
てかEなんてほぼナイーブで解けるレベルに感じたし、500点問題としてはあまりにも簡単すぎでは
2023/01/07(土) 23:47:37.23ID:XF8T3NwUM
Ex、Polya の原理や包除原理知ってても簡単に見えないし、ABCで出した理由は有名問題だからなんかな
2023/01/07(土) 23:49:55.07ID:XF8T3NwUM
というか、GみたいのもOEISにあるのな
この問題用に出てきた謎の量にしか見えなかったが
2023/01/08(日) 00:04:08.29ID:lAEXMGQ20
なんちゃらのフルイ使わないでやったらTLEして
脳死で数値設定したら足りなくてWAした雑魚
125デフォルトの名無しさん (ﾜｯﾁｮｲ 5bba-wqvi)
垢版 |
2023/01/08(日) 01:25:51.19ID:4thZdV2f0
ついこないだライブラリ作ったポラード・ローの高速素因数分解でDをしばき倒せたので良かった
2023/01/08(日) 11:32:11.67ID:4xTAT7w0a
Dは簡単すぎて本当にこれでいいのか何度も見直したんだが

まず2から順に素数で割っていって割り切れたものがpかq
さらに同じ数で割って割り切れたらp確定
その場合はp*pで割った商がq

割り切れなかった場合はその素数がqなので割った商の平方根がp
2023/01/08(日) 11:59:00.32ID:VXOhkNVAd
それの計算量解析ができるか？って問題だからな
2023/01/08(日) 12:11:35.54ID:4xTAT7w0a
できるだろ
素数の判定・列挙はO(sqr(N))
2023/01/08(日) 12:14:36.88ID:xVz3ul4wp
そうじゃなくて小さい方がNの平方根で抑えられるかを見抜けるのが本質では
2023/01/08(日) 12:14:57.98ID:xVz3ul4wp
平方根じゃなくて立方根
2023/01/08(日) 12:16:33.74ID:PLtXzXPr0
>>128
N≤9×10¹⁸ なのでそれではだめ
2023/01/08(日) 12:17:04.65ID:4xTAT7w0a
ていうか小さい順に割っていくならpとqの最大値で最も時間がかかるからO(root3(N)*T)
2023/01/08(日) 12:17:37.84ID:4xTAT7w0a
>>131
なんでよ？
2023/01/08(日) 12:22:05.66ID:xVz3ul4wp
>>133
p,qのうちの大きくない方は必ずNの立方根(2×10^6程度)になって、昇順から自然数を見ると割り切れた時点で素因数なのは確定するから素数の判定は実は関係ない(だからp,qが最悪ケースの√N(10^9オーダー)であっても素数判定をする必要はない)っていうのがDのポイントだと思う
2023/01/08(日) 12:23:24.79ID:PLtXzXPr0
>>132
ああ、そこを見積もりできてるならおｋ
2023/01/08(日) 12:24:29.59ID:xVz3ul4wp
>>134
最悪ケースは　p=2,q=10^18程度　だった
2023/01/08(日) 12:33:13.02ID:4xTAT7w0a
>>136
pが2なら最善だろ
真面目に素因数分解するんじゃなくpかqのどちらかになる素因数を一つみつけたら後はO(1)
2023/01/08(日) 12:35:54.01ID:xVz3ul4wp
>>137
もし素数判定をするならこのqがめちゃくちゃ大きい素数のケースが判定出来ない(けど実際は必要ないことを見抜けば良い)って話
2023/01/08(日) 12:40:40.46ID:4xTAT7w0a
>>138
わからん
p=2なら4で割ればqが出るじゃん
最初に一つ素因数を見つけたらその二乗で割り切れるかどうかでそれがpかqか判別できるからそこからO(1)になると最初から書いてるんだが
2023/01/08(日) 12:46:00.22ID:xVz3ul4wp
>>139
素数の判定云々の話をしてそれに対してそれだとアウトってレスがついてたから、アウトな方の方針を書いただけで小さい方が高々Nの立法根になることを見抜けてるなら問題ないってこと
2023/01/08(日) 12:48:17.86ID:4xTAT7w0a
見抜けてるのは最初のレスを見てもらえばわかると思うが俺が見抜けてようが見抜けてなかろうがそれでアウトになるはずなくね？
2023/01/08(日) 12:54:12.01ID:BtN5SsI/r
うんち！ｗ
2023/01/08(日) 12:56:12.81ID:xVz3ul4wp
昇順に素因数を確認する方針を取れば自然と10^6程度までで解が求まるけど、実際にはその方針に辿り着けないような人もいて、正解の方針を取らないで何も考えずにp、qの素数判定をしたりすると間に合わなくなるからそこで篩い落としてるっていう話
別に間違いを指摘してるわけではない
2023/01/08(日) 12:56:42.45ID:lAEXMGQ20
なんか草
2023/01/08(日) 12:57:52.94ID:PLtXzXPr0
>>126,128には計算量の話が全くなかったから突っ込まれてただけだよ
計算量がNの立方根らへんになることがわかってれば良い
2023/01/08(日) 13:09:39.78ID:4xTAT7w0a
なんでわかってないやつが偉そうなんだw
2023/01/08(日) 13:10:29.67ID:4xTAT7w0a
>>131
このアルゴリズムでだめな理由を書いてからいえやw
2023/01/08(日) 13:14:58.62ID:HsiWAu8/a
はいはいすごいすごい
2023/01/08(日) 13:23:07.45ID:4xTAT7w0a
めんどくせえ
2023/01/08(日) 19:02:56.17ID:FA2WmfgIM
レートは寒色なのにIDは真っ赤、と……
2023/01/08(日) 19:35:57.28ID:7H0KKt1L0
レスバするのも煽るのもやめろ
2023/01/08(日) 19:48:45.82ID:PbV2sMf50
初歩的なプログラミングに慣れてきたから、ABCの過去問を解いてるんだけど、解説を読んでも意味不明な場合はどうすればいいんだ？ABC284のC問題が何度読んでもよく分からない 深さ優先探索とか幅優先探索なんてAPG4bになかった気がする頭がどうしようもなく悪いみたいだから競プロやめようかな
2023/01/08(日) 19:52:33.27ID:PbV2sMf50
こんな簡単な問題で詰まってるってどうしようも無いレベルの脳障害よな…、
2023/01/08(日) 19:53:37.12ID:nECg26E4a
p=2の時に最悪になるなんてとぼけたこと言うやつが煽るスレ
こんなアホが複数いるとは思えんから自演だろーなー
悔しかったんだなー
2023/01/08(日) 19:56:51.09ID:nECg26E4a
>>152
これはdisjoint-setを知ってるかどうかだけの問題だから解けなくても何も気にしなくて大丈夫
2023/01/08(日) 20:04:48.91ID:1vMHtyHnp
レスバするつもりはないけどせめてワッチョイ確認しろよ
自演してるのはどっちやねん
2023/01/08(日) 20:06:10.50ID:nECg26E4a
お前だろw
知能でわかるのになぜバレないと思うんだw
2023/01/08(日) 20:07:28.74ID:1vMHtyHnp
129は俺だけど131は別人だぞ
2023/01/08(日) 20:08:26.38ID:nECg26E4a
はいはい
あと全部俺ね
2023/01/08(日) 20:08:41.85ID:nECg26E4a
病気か？w
2023/01/08(日) 20:11:16.79ID:gWSxWaz50
幅優先探索も深さ優先探索もUnionFindも知識的な話で、知らなきゃ理解に詰まるのはしょうがない
解説は基本かなりダイジェスト気味だから、一回もう少し詳しいサイトなり本で勉強すればいいと思うよ
2023/01/08(日) 20:12:44.36ID:4UuUf9f70
桁数が多い平方数の平方根ってどう計算するのが正しいのかな。単に sqrt 取って int にキャストするのだと計算誤差の関係で sqrt の小数点以下が .9999989 みたいになっていたら困るし、だからと言って sqrt に任意の小さい数（0.001 とか）を足してから int にキャストするのも格好悪いし。あるいは元の数が long long で収まる大きさだったら sqrt はピッタリ求まるのかな。
2023/01/08(日) 20:18:18.77ID:4A4PT21lp
>>162
roundすればよくない？
2023/01/08(日) 20:34:40.46ID:4UuUf9f70
>>163
確かに。でも round が安心して使えるなら、昨日の問題とは別に一般の素因数求めるコードで for (int i = 2; i * i <= n; i++) ってよく見かけるけど、for (int i = 2; i <= round(sqrt(n)); i++) と書いたほうが掛け算の回数が減っていいんじゃないかと思ったわ（計算時間の差は微々たるものだろうけど）。鉄則本での配列の宣言にもあった A[100007] とかと同じで競プロ業界のお作法なのかしら。
2023/01/08(日) 20:36:13.61ID:rVivGDpza
>>162
↓の記事にめっちゃ詳しく書いてあるけど、long longに収まる整数でもfloatやdoubleで表せるとは限らない
コンピュータの小数は難しい

https://qiita.com/y-yoshinari/items/76260f6359d5b4418b33
2023/01/08(日) 20:36:51.62ID:MjmTh3T5r
なんでround(sqrt(n))の方が速いと思えるんですか？
2023/01/08(日) 20:40:17.96ID:8iA8H0pf0
浮動小数点数は値がデカいとスッカスカになって、例えば一定以上の大きさの奇数を表せなかったりするのが怖いんだよな
sqrtぐらいならなんだかんだうまくいくのかもしれないけど俺は浮動小数点数と仲良くないからsqrtは二分探索書いてる
2023/01/08(日) 20:54:43.75ID:4UuUf9f70
>>166
そっか、n の値を別の変数 m とかにコピーして、ループ内では m の方を素因数で割っていくイメージだったのですが（その場合 n は不変なのでコンパイラがちゃんと仕事をしていれば sqrt の計算は1回のみ）、i * i <= n で上限チェックをしているコードはループ内で n を変えていく想定なわけですか。
2023/01/09(月) 06:27:27.63ID:NBV9jC+W0
１問ずつ解説動画上げてくのか
2023/01/12(木) 18:08:12.84ID:hau3jnvxM
ARC対策に去年初めのARCの問題を考えてみたら、当時解けたのに今解けなくて笑えない
2023/01/14(土) 20:20:04.00ID:o0xk1/qD0
正月ボケで開催日を間違えて今年最初のABCを見逃してしまいました
昨年末から精進するのを休憩してプログラミングから全く離れていたので
ぶっつけでABC284やってみたらあっさりCまで解けて安心しました

そろそろ参加10回くらいになりますがDの壁が高過ぎると感じているので
灰色のまましばらく解けるものを確実にこなせたらと思います
ずっと毎日精進するのはストレスに感じ始めていたので
コンテスト前などの気の向いた時だけ勉強するようにしてみます

と書いてて今からやる気満々だったABC285は明日じゃん...
ARCは問題見ただけで自分の無能さを思い知るので見ないでおきます
172デフォルトの名無しさん (ｱｳｱｳｳｰ Sa91-PwPr)
垢版 |
2023/01/14(土) 23:01:05.01ID:lOE4TlVsa
C、判定も分割方法もわかったけどそこから回答例出す方法思いつかなかった...
今から説明読んで精進します
173デフォルトの名無しさん (ｱｳｱｳｳｰ Sa91-PwPr)
垢版 |
2023/01/14(土) 23:06:25.55ID:lOE4TlVsa
Bは無理だと思って捨てたけど
1,2の位置だけでわかるのかよ...
なんかそんなに行列が壊れないようなトリックになってそうとは思ったけど、
まさかここまでとは...全然気づかなかった。
174デフォルトの名無しさん (ｱｳｱｳｳｰ Sa91-PwPr)
垢版 |
2023/01/14(土) 23:09:19.49ID:lOE4TlVsa
むしろ、奇数偶数さえ押さえてれば1の場所だけで良いのか。
2023/01/14(土) 23:09:32.98ID:Sr0okIFG0
C後ちょっとだったけど500人近くも解いててびっくり
2023/01/14(土) 23:35:20.12ID:PSuT81xP0
C問題はslopetrick系かな？と思ったけど式書いてみたら本当に単純な一次関数でびっくり
2023/01/14(土) 23:35:51.38ID:PSuT81xP0
>>172
地味に復元めんどくさいよね
2023/01/15(日) 19:37:41.30ID:x61tbRba0
ABC283のキャンペーンで500円当たった
2023/01/15(日) 22:40:11.85ID:d5cspaf50
俺がその場で考え出した超スパゲッティなunion-findでD問題何とか通してやったぜ
ひどいコードだから是非見てほしい、次のレスで
2023/01/15(日) 22:40:40.75ID:hjFyqJMa0
やっぱ日頃から精進してないとABCまででも苦戦しますね
問題文が何を問うているのか理解するのに時間が掛かりすぎるのと
解法のイメージは出来ているのにちょっとした関数を用意してないだけで
わざわざ場当たり的に実装して手間取ったり

C問題解けたのが終わる直前でDは無理だと思ったので順位表見てたら
snukeさんがC解いたのが7分台と知って
自分の無能さを痛感しました
2023/01/15(日) 22:40:49.45ID:d5cspaf50
dic = {}
flag = True


def find(tt, update=None):
if update:
if dic[tt] == tt:
dic[tt] = update
return
cc = dic[tt]
dic[tt] = update
find(cc, update)
return
if dic[tt] == tt:
return tt
p = find(dic[tt])
dic[tt] = p
return p
2023/01/15(日) 22:41:06.05ID:d5cspaf50
for i in range(int(input())):
a, b = input().split(" ")
if a in dic and b in dic:
for temp in (a, b):
find(temp)
if dic[a] == dic[b]:
flag = False
break
new_ = dic[b]
find(a, new_)
elif a in dic:
dic[b] = dic[a]
elif b in dic:
dic[a] = dic[b]
else:
dic[a] = a
dic[b] = a
print("Yes") if flag else print("No")
183デフォルトの名無しさん (ｱｳｱｳｳｰ Sa91-PwPr)
垢版 |
2023/01/15(日) 22:41:25.41ID:C77/nrWVa
D...
サイクルになるとNGとなるようにプログラムが作りきれなかった。
Cの問題を応用すれば良いのはわかるのに、単純に時間内に改良出来ん。
もったいなかったなぁ、、、
2023/01/15(日) 22:44:59.43ID:d5cspaf50
そういえば今度応用情報受験するんだけど、競プロ勢（といっても俺はガチ初心者レベルだが）
にとって午後のアルゴリズム問題って得意だったりするんだろうか
2023/01/15(日) 22:46:26.67ID:d5cspaf50
見づらいからこっちでシェアするわ
https://atcoder.jp/contests/abc285/submissions/38073975

こんなに汚いunion-findでよく通したなって自分をほめたい
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況