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

2022/12/26(月) 12:47:37.63

!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

2023/01/05(木) 14:48:33.70

よくわからんけど答えが32bit整数に収まる程度なら適当に大きめのmodとればいいんじゃないの

2023/01/07(土) 18:03:15.80

ARC3週連続か

2023/01/07(土) 19:51:43.95

ARC生えまくり
嬉しいけど息切れしないか心配

2023/01/07(土) 22:45:57.01

Dの解説読んでもわけわからん
まず、割り切れるのがわかってるんだから、iの最大値なんて関係なくない？

iの2乗で割り切れる時に解が見つかるとして計算したけど時間内に解が求められなかった。
糞問題じゃないのこれ？

2023/01/07(土) 22:47:21.33

どんまい

2023/01/07(土) 22:47:32.24

解けなかったら糞問
で、おまえのレートは？

2023/01/07(土) 22:49:07.34

Dで素因数分解出来ることが保証されてるのが頭から抜けてたせいで絶対想定解じゃないだろって思いながら無駄にミラーラビン素数判定法とか使ってしまった

2023/01/07(土) 22:51:15.35

素因数分解出来ることっていうより素因数分解の一意性か

2023/01/07(土) 22:52:05.10

問題は全然クソじゃないと思うけど、i=1,2,…,⌊N^(1/3)⌋のうち、N が i で割り切れるような最大の i って書き方が何か変で、i=2,…,⌊N^(1/3)⌋のうちNを割り切る最小のiと言った方が正しいような気がする

2023/01/07(土) 22:54:54.84

G、本質パートからしてボリュームあるのにさらに任意ｍod二項係数使うんかいって思ったけど、想定解は全然使ってなかった

2023/01/07(土) 22:57:18.84

>>105
ちなみに、そのやり方でTLEしないと思うんだけど、N^(1/3)までで探索打ち切った？

2023/01/07(土) 22:58:15.60

あー、二乗の計算時間もだめだってのか。効率化難しいな。
sqrt使うところに頭が向かわなかったわ。
お前らよく解けるねこれ...

2023/01/07(土) 22:59:01.50

>>105
打ち切った。でもダメだった。

2023/01/07(土) 23:00:27.31

Dは想定回じゃなくても、いろんなテクで解けるし、みんないずれかの解法にサクッとたどり着いてる感じだな

2023/01/07(土) 23:01:13.52

>>113
なんかその書きぶりだと、もしかしてj^2 = N/iになるようなjも探索で出した感じ？

2023/01/07(土) 23:01:47.41

Eが素直なDFSすぎてDと逆でも良いだろとは思った

2023/01/07(土) 23:03:43.12

Eはむしろ個人的には意表を突かれた感じでギョッとした
Fの方が実は素直にロリハやるだけだったりする

2023/01/07(土) 23:04:53.24

>112
すまん、冷静に考えたら打ち切ってない
必ず1個の解が見つかるはずで、解が見つかったら打ち切ったら良いんだから、N^(1/3)までカウントアップしないと思ったんだ。だから、N^(1/3)で止めるロジックは無意味だと思ってる。

ただ、自分のやり方だと解を二乗根に絞って計算したせいで最大値がN^(1/2)/2になってしまったんだね。
そのせいか...

2023/01/07(土) 23:06:46.63

>>119
>必ず1個の解が見つかるはずで、解が見つかったら打ち切ったら良いんだから、N^(1/3)までカウントアップしないと思ったんだ。だから、N^(1/3)で止めるロジックは無意味だと思ってる。
確かにそれはそう、ナンセンスな質問ですまない
O(N^(1/2))になってたのがTLEの原因っぽいね

2023/01/07(土) 23:08:57.85

EやFはサクッと解けたけど、おれもDはちょっとギョッとしたよ
おれも数学弱だな
てかEなんてほぼナイーブで解けるレベルに感じたし、500点問題としてはあまりにも簡単すぎでは

2023/01/07(土) 23:47:37.23

Ex、Polya の原理や包除原理知ってても簡単に見えないし、ABCで出した理由は有名問題だからなんかな

2023/01/07(土) 23:49:55.07

というか、GみたいのもOEISにあるのな
この問題用に出てきた謎の量にしか見えなかったが

2023/01/08(日) 00:04:08.29

なんちゃらのフルイ使わないでやったらTLEして
脳死で数値設定したら足りなくてWAした雑魚

2023/01/08(日) 01:25:51.19

ついこないだライブラリ作ったポラード・ローの高速素因数分解でDをしばき倒せたので良かった

2023/01/08(日) 11:32:11.67

Dは簡単すぎて本当にこれでいいのか何度も見直したんだが

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

割り切れなかった場合はその素数がqなので割った商の平方根がp

2023/01/08(日) 11:59:00.32

それの計算量解析ができるか？って問題だからな

2023/01/08(日) 12:11:35.54

できるだろ
素数の判定・列挙はO(sqr(N))

2023/01/08(日) 12:14:36.88

そうじゃなくて小さい方がNの平方根で抑えられるかを見抜けるのが本質では

2023/01/08(日) 12:14:57.98

平方根じゃなくて立方根

2023/01/08(日) 12:16:33.74

>>128
N≤9×10¹⁸ なのでそれではだめ

2023/01/08(日) 12:17:04.65

ていうか小さい順に割っていくならpとqの最大値で最も時間がかかるからO(root3(N)*T)

2023/01/08(日) 12:17:37.84

>>131
なんでよ？

2023/01/08(日) 12:22:05.66

>>133
p,qのうちの大きくない方は必ずNの立方根(2×10^6程度)になって、昇順から自然数を見ると割り切れた時点で素因数なのは確定するから素数の判定は実は関係ない(だからp,qが最悪ケースの√N(10^9オーダー)であっても素数判定をする必要はない)っていうのがDのポイントだと思う

2023/01/08(日) 12:23:24.79

>>132
ああ、そこを見積もりできてるならおｋ

2023/01/08(日) 12:24:29.59

>>134
最悪ケースは　p=2,q=10^18程度　だった

2023/01/08(日) 12:33:13.02

>>136
pが2なら最善だろ
真面目に素因数分解するんじゃなくpかqのどちらかになる素因数を一つみつけたら後はO(1)

2023/01/08(日) 12:35:54.01

>>137
もし素数判定をするならこのqがめちゃくちゃ大きい素数のケースが判定出来ない(けど実際は必要ないことを見抜けば良い)って話

2023/01/08(日) 12:40:40.46

>>138
わからん
p=2なら4で割ればqが出るじゃん
最初に一つ素因数を見つけたらその二乗で割り切れるかどうかでそれがpかqか判別できるからそこからO(1)になると最初から書いてるんだが

2023/01/08(日) 12:46:00.22

>>139
素数の判定云々の話をしてそれに対してそれだとアウトってレスがついてたから、アウトな方の方針を書いただけで小さい方が高々Nの立法根になることを見抜けてるなら問題ないってこと

2023/01/08(日) 12:48:17.86

見抜けてるのは最初のレスを見てもらえばわかると思うが俺が見抜けてようが見抜けてなかろうがそれでアウトになるはずなくね？

2023/01/08(日) 12:54:12.01

うんち！ｗ

2023/01/08(日) 12:56:12.81

昇順に素因数を確認する方針を取れば自然と10^6程度までで解が求まるけど、実際にはその方針に辿り着けないような人もいて、正解の方針を取らないで何も考えずにp、qの素数判定をしたりすると間に合わなくなるからそこで篩い落としてるっていう話
別に間違いを指摘してるわけではない

2023/01/08(日) 12:56:42.45

なんか草

2023/01/08(日) 12:57:52.94

>>126,128には計算量の話が全くなかったから突っ込まれてただけだよ
計算量がNの立方根らへんになることがわかってれば良い

2023/01/08(日) 13:09:39.78

なんでわかってないやつが偉そうなんだw

2023/01/08(日) 13:10:29.67

>>131
このアルゴリズムでだめな理由を書いてからいえやw

2023/01/08(日) 13:14:58.62

はいはいすごいすごい

2023/01/08(日) 13:23:07.45

めんどくせえ

2023/01/08(日) 19:02:56.17

レートは寒色なのにIDは真っ赤、と……

2023/01/08(日) 19:35:57.28

レスバするのも煽るのもやめろ

2023/01/08(日) 19:48:45.82

初歩的なプログラミングに慣れてきたから、ABCの過去問を解いてるんだけど、解説を読んでも意味不明な場合はどうすればいいんだ？ABC284のC問題が何度読んでもよく分からない深さ優先探索とか幅優先探索なんてAPG4bになかった気がする頭がどうしようもなく悪いみたいだから競プロやめようかな

2023/01/08(日) 19:52:33.27

こんな簡単な問題で詰まってるってどうしようも無いレベルの脳障害よな…、

2023/01/08(日) 19:53:37.12

p=2の時に最悪になるなんてとぼけたこと言うやつが煽るスレ
こんなアホが複数いるとは思えんから自演だろーなー
悔しかったんだなー

2023/01/08(日) 19:56:51.09

>>152
これはdisjoint-setを知ってるかどうかだけの問題だから解けなくても何も気にしなくて大丈夫

2023/01/08(日) 20:04:48.91

レスバするつもりはないけどせめてワッチョイ確認しろよ
自演してるのはどっちやねん

2023/01/08(日) 20:06:10.50

お前だろw
知能でわかるのになぜバレないと思うんだw

2023/01/08(日) 20:07:28.74

129は俺だけど131は別人だぞ

2023/01/08(日) 20:08:26.38

はいはい
あと全部俺ね

2023/01/08(日) 20:08:41.85

病気か？w

2023/01/08(日) 20:11:16.79

幅優先探索も深さ優先探索もUnionFindも知識的な話で、知らなきゃ理解に詰まるのはしょうがない
解説は基本かなりダイジェスト気味だから、一回もう少し詳しいサイトなり本で勉強すればいいと思うよ

2023/01/08(日) 20:12:44.36

桁数が多い平方数の平方根ってどう計算するのが正しいのかな。単に sqrt 取って int にキャストするのだと計算誤差の関係で sqrt の小数点以下が .9999989 みたいになっていたら困るし、だからと言って sqrt に任意の小さい数（0.001 とか）を足してから int にキャストするのも格好悪いし。あるいは元の数が long long で収まる大きさだったら sqrt はピッタリ求まるのかな。

2023/01/08(日) 20:18:18.77

>>162
roundすればよくない？

2023/01/08(日) 20:34:40.46

>>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.61

>>162
↓の記事にめっちゃ詳しく書いてあるけど、long longに収まる整数でもfloatやdoubleで表せるとは限らない
コンピュータの小数は難しい

https://qiita.com/y-yoshinari/items/76260f6359d5b4418b33

2023/01/08(日) 20:36:51.62

なんでround(sqrt(n))の方が速いと思えるんですか？

2023/01/08(日) 20:40:17.96

浮動小数点数は値がデカいとスッカスカになって、例えば一定以上の大きさの奇数を表せなかったりするのが怖いんだよな
sqrtぐらいならなんだかんだうまくいくのかもしれないけど俺は浮動小数点数と仲良くないからsqrtは二分探索書いてる

2023/01/08(日) 20:54:43.75

>>166
そっか、n の値を別の変数 m とかにコピーして、ループ内では m の方を素因数で割っていくイメージだったのですが（その場合 n は不変なのでコンパイラがちゃんと仕事をしていれば sqrt の計算は1回のみ）、i * i <= n で上限チェックをしているコードはループ内で n を変えていく想定なわけですか。

2023/01/09(月) 06:27:27.63

１問ずつ解説動画上げてくのか

2023/01/12(木) 18:08:12.84

ARC対策に去年初めのARCの問題を考えてみたら、当時解けたのに今解けなくて笑えない

2023/01/14(土) 20:20:04.00

正月ボケで開催日を間違えて今年最初のABCを見逃してしまいました
昨年末から精進するのを休憩してプログラミングから全く離れていたので
ぶっつけでABC284やってみたらあっさりCまで解けて安心しました

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

と書いてて今からやる気満々だったABC285は明日じゃん...
ARCは問題見ただけで自分の無能さを思い知るので見ないでおきます

2023/01/14(土) 23:01:05.01

C、判定も分割方法もわかったけどそこから回答例出す方法思いつかなかった...
今から説明読んで精進します

2023/01/14(土) 23:06:25.55

Bは無理だと思って捨てたけど
1,2の位置だけでわかるのかよ...
なんかそんなに行列が壊れないようなトリックになってそうとは思ったけど、
まさかここまでとは...全然気づかなかった。

2023/01/14(土) 23:09:19.49

むしろ、奇数偶数さえ押さえてれば1の場所だけで良いのか。

2023/01/14(土) 23:09:32.98

C後ちょっとだったけど500人近くも解いててびっくり

2023/01/14(土) 23:35:20.12

C問題はslopetrick系かな？と思ったけど式書いてみたら本当に単純な一次関数でびっくり

2023/01/14(土) 23:35:51.38

>>172
地味に復元めんどくさいよね

2023/01/15(日) 19:37:41.30

ABC283のキャンペーンで500円当たった

2023/01/15(日) 22:40:11.85

俺がその場で考え出した超スパゲッティなunion-findでD問題何とか通してやったぜ
ひどいコードだから是非見てほしい、次のレスで

2023/01/15(日) 22:40:40.75

やっぱ日頃から精進してないとABCまででも苦戦しますね
問題文が何を問うているのか理解するのに時間が掛かりすぎるのと
解法のイメージは出来ているのにちょっとした関数を用意してないだけで
わざわざ場当たり的に実装して手間取ったり

C問題解けたのが終わる直前でDは無理だと思ったので順位表見てたら
snukeさんがC解いたのが7分台と知って
自分の無能さを痛感しました

2023/01/15(日) 22:40:49.45

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.05

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")

2023/01/15(日) 22:41:25.41

D...
サイクルになるとNGとなるようにプログラムが作りきれなかった。
Cの問題を応用すれば良いのはわかるのに、単純に時間内に改良出来ん。
もったいなかったなぁ、、、

2023/01/15(日) 22:44:59.43

そういえば今度応用情報受験するんだけど、競プロ勢（といっても俺はガチ初心者レベルだが）
にとって午後のアルゴリズム問題って得意だったりするんだろうか

2023/01/15(日) 22:46:26.67

見づらいからこっちでシェアするわ
https://atcoder.jp/contests/abc285/submissions/38073975

こんなに汚いunion-findでよく通したなって自分をほめたい

2023/01/15(日) 22:47:08.29

>>179
酷かろうが作ったもの勝ちだよw
dfsにこだわったのは悪くない筈なんだけど、
全探索にして、上書き発生したらNGにするだけなのに、色々脱線して組めなかったわw
最後の最後で初期値1にしてた事に気付いたしw

2023/01/15(日) 22:48:38.06

E解けなくてショック

2023/01/15(日) 22:49:53.12

union-find自分で実装するのめんどくさかったから最初どこかからコピペしようとしてたわ

けど、通常のユニファイと違って文字列のアクセスだからどうやって応用したらいいかがわからなかった

>初期値１
これはなんのこと？

2023/01/15(日) 22:50:56.98

>>187
1週間が5000日とか気が遠くなるなw

2023/01/15(日) 22:51:31.11

名前ごとに番号つければいいだけ

2023/01/15(日) 22:52:12.97

TOPページの左側に表示されているランキング上位10位に日本の国旗が無いのに気づいてしまった

2023/01/15(日) 22:52:13.73

終わったあと冷静にやったらE解けた

2023/01/15(日) 22:52:56.31

>>190
そう思ったけど、改名前と改名後どっちがどうだとかいろいろ考えてたらわけわからなくなって結局自力実装してしまった。

2023/01/15(日) 22:53:56.36

>>191
ほんまやん
やっぱ日本てITレベル低いんだろうか

2023/01/15(日) 22:54:41.45

>>188
Cの問題をそのまま利用(大文字小文字だけは違うけど)して英字列を数値に変換したんだよ

最近のdfs絡みって全部初期値が0か1の問題だけだったので、そのまま組んでしまってて、、、
でも例題がそれで通ってたせいで迷走してしまった。

2023/01/15(日) 22:57:50.51

>>195
なんと。。。。職人技だな、その発想はなかった。
数字に変換したいのなら普通にハッシュ関数とかの方が計算量的に早かったりするんだろうか

2023/01/15(日) 23:04:31.35

>>196
よくよく考えたらグラフに置き換えるのに数値に変換する必要もないですね・・・
グラフ問題出たら最低でもノータイムで解けるようにしとかないといかんですね。
勿体ない時間が多すぎた。

2023/01/15(日) 23:05:19.32

Gのドミノ置けるか判定なんてどうせフローでしょ感

2023/01/15(日) 23:07:20.31

>>197
連続した整数にするできるならまだしも、離散的な数字を生成するのならメリットはあまりないですな

グラフ問題ノータイムか。。。まだまだ練習が必要そう

2023/01/15(日) 23:08:13.12

そうだ、あとA問題
これの解き方まじでわからんかった

https://atcoder.jp/contests/abc285/submissions/38045467

こんな感じで書いたんだけどもっと効率的な書き方あるんだろうか

2023/01/15(日) 23:09:14.98

>>200
大きい方を小さい方で割った答えが２ならYes

2023/01/15(日) 23:10:20.42

そうか。。よく見たら下のノードは倍だった。。。。。

いやひどい。。なぜ気づかなかったのか