競技プログラミング総合スレ 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/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

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

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

2023/01/15(日) 23:12:18.99

>>199
＞離散的な数字を生成するのならメリットはあまりない
その通り・・・C問題の後で、これは数値に置き換えると効率よくなるはずだ！
って声に従って変換してました・・・が意味なかったですね。

なんというか、学校等の模試って１問前の問題を応用することが多くて、
それが完全に染みついてるんですよね。

2023/01/15(日) 23:12:58.55

Aは完全二分木の頂点を配列上で管理する話で、発展的な知識で思考をショートカットできる系の問題と言ってもいいかもしれんな（これぐらいなら再発明するやついっぱいいるだろうが）
ARC/AGCの低難度で出る一見アドホックな問題もこういう感じだったりするんだろうか

2023/01/15(日) 23:13:17.67

>>202
自分は法則探しに時間使ったので、ある意味力業の方が早かったかもしれません。

2023/01/16(月) 11:42:48.72

>>194
AtCoderは日本で現役最強格の人や、世界的にも最強に近かった日本人選手が運営で作問作業のコアな部分に携わってるから出られなくて、ランキングにいない
それを差し引いても、中国や東欧の方がやや強いけど

2023/01/16(月) 11:45:15.43

中国や東欧の人に問題作らせよう(名案)

2023/01/16(月) 16:21:39.59

>>204
過去のABの比じゃなく難解だったので飛ばして
C→B→Aの順で解きましたが
全条件を組み込みするのは絶対に嫌だったので
何か法則があるんだろうなと捏ねくり回してたら2倍か2倍+1に気づいたので
if文1行で解けましたが解説見ると知ってる人や上位の方が1-2分で解けるのも納得です

考えて解く問題より知ってるかどうかって問題が多い気がしますが
どちらにしてもD問題の壁が高過ぎるのは変わらないので
DNAとかIQなど持って生まれたもので精進レベルではどうにもならない感が半端無いなと思います

2023/01/16(月) 16:36:42.01

二分木の配列実装を知らないレベルでIQやDNAを云々するのは結論を急ぎすぎ
知識増やしても壁を乗り越えられなくなってから言おう

2023/01/16(月) 17:19:37.05

AtCoder青色くらいまでは本一冊程度の知識を身に付けていますか？で終わりなんだよな
典型90問とEDPCを全部解いてて水色以下の人を見たことないし

2023/01/16(月) 17:56:32.76

努力でどこまでできるかについては諸説あるが、知識がないうちは自分が知識あれば解けるかどうかすらも分からんもんで、最初のレートの伸びが悪くても一旦勉強してみてから考えてもいいんじゃないか
ABCのD突破するのに要る知識だったら普通のエンジニアリングで遭遇するものも多いから、そこまで損はない

2023/01/16(月) 18:00:22.74

最初天才にしか見えなかった解き方が、有名でありきたりな定石の変種に過ぎなかったなんてよくあることよ
まあもちろん発見者は天才なんだろうが

2023/01/16(月) 18:02:24.18

少なくともD問題くらいまでに関しては毎回かなり典型的な知識しか要求されないし問題も素直なものが多いからそのレベルだとセンスとか関係なく訓練すれば迷わず書けるようになると思う

2023/01/16(月) 18:10:09.09

それとレートの伸びが早くて天才に見える人も、中学受験とか数学オリンピックで競プロの役に立つ思考パターンを予めたくさんインプットされてるのがデカいんじゃないかって話もあるからな

2023/01/16(月) 18:14:52.41

AtCoderの社長の人の本を少し読みましたが、アカデミックな香りが全くしません。
そういう人が非常に強いというのが不思議です。
逆にアルゴリズムが専門の大学教授は強いのだろうかと疑問に思ってしまいます。

2023/01/16(月) 18:19:44.82

弱い相関はあるだろうが、基本別の能力だぞ
極論チェスプレイヤーが数学者として成功できるかみたいな話
逆にアルゴリズムの世界的な研究者がCodeForcesでそんなに強くなかったりな
高齢だからしょうがない部分もあるが

2023/01/16(月) 18:45:28.99

アルゴリズムや関連理論を知っていることと時間内にアルゴリズムを問題に適用できるかは別だしな
だから研究者でも寒色は全然よくある
まぁ若い頃に精進すればもっと上に行ってただろうけど、それをする必要があるかはさておいて

2023/01/16(月) 19:26:15.35

>>214
作問者はそういう経歴を辿ってるひとだらけだから傾向は偏っている
アカデミックな研究者が作問してたらもっと別な傾向になるだろう。新しく発表されたアルゴリズムを元ネタにした作問とかしそう

2023/01/16(月) 19:41:30.89

そうなった場合"精進＝アルゴリズム系の論文を読み漁る"になった可能性もあるのか...
そうだったらハマってなかったわ

2023/01/16(月) 21:05:40.99

まあレート競争するのが楽しいって体質なら、そうなったらそうなったで普通に論文も楽しく読めちゃう可能性あるけどな
Kaggleで論文読むの割と楽しいぞ

2023/01/16(月) 21:58:45.57

暖色コーダーは割と気軽に論文読んでるしな
競プロ強い人は研究者適正もあるとは思うわ

2023/01/16(月) 22:05:55.89

983 デフォルトの名無しさん (ﾜｯﾁｮｲ 6f71-0qRf) 2022/10/03(月) 20:26:59.27 ID:lndyBnH50
https://twitter.com/intent/favorite?tweet_id=1516784253656506369
@rui314
さん
あれはSAPIXとか鉄緑会と同じカルチャーだと思う。
https://twitter.com/5chan_nel (5ch newer account)
https://twitter.com/5chan_nel (5ch newer account)

2023/01/16(月) 22:14:02.31

リンク先でいいねに誘導するトラップな

2023/01/17(火) 01:36:16.99

>>222
せめてURLくらい直してからコピペしろ

2023/01/18(水) 23:04:40.18

https://twitter.com/31415926five/status/1614620071787401217
先週のC問題、この人と同じ状況になってWAが出ます
これ何が原因だと思いますか？
https://twitter.com/5chan_nel (5ch newer account)

**225** (ﾜｯﾁｮｲ cd2d-sAzJ) · 2023/01/18(水) 23:06:58.61

自己解決しましたdoubleの精度の問題でした

2023/01/19(木) 07:34:58.63

>>226
解説読んで無いからよくわからんけど26進法じゃないの？
書いてある方法の解き方がよくわからんw

2023/01/19(木) 09:50:28.45

全探索とかdoubleとかどう使うんだ

2023/01/19(木) 09:57:14.64

26進法ぽいっちゃぽいけど0が無いんだよな
Aが1で26が桁上がり無しのZ
27で桁が上がってAA
単純に前から順にAからZを1から26に変換して26倍して次を足せばいい

2023/01/19(木) 11:58:12.74

c++ならこんだけやで

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

触ったことないから詳しくはわかんないけどrubyとかならもっと短くできそう

2023/01/19(木) 12:27:13.37

C#は多分こんな感じ
Console.WriteLine(Console.ReadLine().Aggregate(0L,(p,c)=>p*26+c-'A'+1));

2023/01/19(木) 12:47:40.51

>>227
pow関数使って26の累乗を求めるアプローチだと
整数型にキャストしないとWAが出るのです

2023/01/19(木) 12:50:59.12

小数部使わないのに誤差出るか？