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

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

2023/01/19(木) 12:51:55.35

Eなら提出前に気づきそうなもんだが

2023/01/19(木) 12:54:15.21

>>233
10の16乗の桁数くらいだと1ずれるんですよね

>>234
3つだけWAになって何これ？ってなりました

2023/01/19(木) 12:57:28.46

>>235
なるほど、いい問題だったんだなぁ

2023/01/19(木) 17:30:26.00

その問題特有の性質じゃなくてc++だとpow関数がdouble型を返す仕組みになってることが原因だから問題の本質とは関係ない
pow関数は誤差が怖いから他の方法を使って累乗を求めた方がいい

2023/01/19(木) 21:38:50.39

225,226の言ってる事が理解できて勉強になった
楽したいが為に使おうとしちゃうけど、関数の使い所って難しいね

2023/01/20(金) 02:33:59.68

C++のpowあるあるひっかけ問題だなと察して
場当たり的に自作powぽいものを実装してACしましたが
以前他人様の提出見た時に自作powをテンプレ化してる人が複数人いて
なんでだろうと疑問に思っていましたがこういう時に役に立つのだと思いました

ちょっとしたことですがこういう典型的な自作関数などのテンプレを用意しておくだけで
数秒から数分の節約になるんだなと思いました

教プロやってる人にとっては知ってて当然のことなのかもしれませんし
これを知識と言うのか典型と言うのか分かりませんがテンプレなどの事前の準備が大事なんですね

2023/01/20(金) 08:50:50.07

>>237
いいや、doubleが溢れる桁数を問う問題を兼ねてるからいい問題と言ったんだよ
doubleだけじゃなくlong longでも同じことが起こり得るから本質に気づいてないお前は気をつけとけよ

2023/01/20(金) 11:42:24.05

え？

2023/01/20(金) 11:53:34.18

>>241
わかんない？
困ったな
doubleは整数部と小数部で計算が違うから整数部のみ使う場合において誤差は発生しないんだよ
ただし整数部が大きくなりすぎると指数を使って下の桁を小数部に回すから誤差が発生するようになる
doubleで扱えなくてlong longで扱える整数の範囲ということを問題から読み取る必要があるってことね

long longも大きくなりすぎると負の数になって計算が狂うから知らなかったなら気をつけなよ

2023/01/20(金) 12:12:55.31

え？？

**デフォルトの名無しさん** (JP 0H8e-hMQo) · 2023/01/20(金) 12:13:09.15

よくわからないんだけど、pow(a, b)は普通exp(b*log(a))で実装されてるから整数の自然数乗だろうが非整数を扱うことになるんだけど、そういう話ではない？

2023/01/20(金) 12:25:06.54

>>244
そういう話ではないな
俺はpowじゃなくdoubleの話をしてる
処理系の実装で整数のpowでもわざわざ小数を使ってるせいで誤差が出るとするとそもそも戻り値がdoubleだろうがlong longだろうがpowを使うなという話になるな
つまりdoubleじゃなくpowの実装がザコいせい

2023/01/20(金) 12:43:22.43

ここまで堂々と頭の悪いこと言われると反応に困っちゃう

2023/01/20(金) 12:44:49.90

文字は聞き返さなくてもちょっと目を上げれば読み直せるからまあ頑張れ
話について来れなきゃレスしない方がいいぞ

**デフォルトの名無しさん** (JP 0H29-EsBK) · 2023/01/20(金) 12:59:28.86

前回のARCのCとDを焼きなましでやってるのを見てAHC初心者から見るとすごいなーと思うばかりなんだけど、こういうのって近傍設計が肝なんだろうか

2023/01/20(金) 17:02:00.07

間違ってることをドヤ顔で言う人ってなんだろう？

2023/01/20(金) 17:24:08.90

間違ってる知識を堂々と書いてるようじゃそりゃC、Dくらいまでしか解けないよ

2023/01/20(金) 17:43:56.53

多分前回のARCのCとDだったら焼くより普通に解く方が簡単だな

2023/01/20(金) 18:45:03.00

字が読めないからどういう話で自分が何を間違ってるかに気づいてないんだろ

2023/01/20(金) 22:31:37.16

IEEE754を覚えていないのは百歩譲って許せるとして、誤り指摘された時に調べずに嘘を強弁できるのは精神力すごいわ
競プロには向いてないけど

2023/01/20(金) 22:35:23.59

競プロなんかより浮動小数点数の仕組みの理解の方が大事

2023/01/20(金) 23:14:11.93

日本語からまなべばいんじゃね
ひらがなおおめにしてみた

2023/01/20(金) 23:18:09.22

前回のD問題でも自分の誤りを認めずに暴言吐いてた奴と同一人物だから無視でいいよもう

2023/01/21(土) 08:14:27.49

そういやそんなやついたな
寒色は人じゃないんだから身の程わきまえろよ

2023/01/21(土) 10:49:09.24

170cm以下と寒色は人権ないってマジですか？

2023/01/21(土) 12:24:47.69

身長は関係ないだろ！

2023/01/21(土) 20:05:05.68

競技プログラミングの鉄則で勉強してるけど本当に才能ゲーすぎるな
俺みたいな脳障害だと☆3レベルの問題でも初見で解けない