競技プログラミング総合スレ 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/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レベルの問題でも初見で解けない

2023/01/21(土) 20:10:22.78

「社員着服のつけ」下請けに楽天モバイルが契約解除で経営危機
https://news.yahoo.co.jp/articles/d60a8867bdb5c6da90bbed1d8a910d4bff63b23a

さすが楽天グループはトップから末端までクソしかいねえなw

2023/01/21(土) 20:23:40.08

みんなが初見で解ける問題なんて本に載せても意味ないやん

2023/01/21(土) 21:37:13.32

無理

2023/01/21(土) 21:40:34.12

なんか毎週こんなことやってる自分が急に虚しくなってきた
生まれつき頭の良い人達だけが楽しめるものなんでしょうね
勉強してどうにかなるようなものじゃないって薄々気がついてたけど
毎回自分の無能さを思い知るだけの罰ゲームは終わりにします

2023/01/21(土) 21:48:06.59

初見で解法が思いつかない
解説を少しづつ見てヒントを小出しにしつつなるべく自力で解く
それでもどうにもならないから写経する

知ってるか知らないか
覚えてるか覚えてないか
テンプレ作ってるか作ってないか
初見で解けるか解けないか

そりゃ流行るわけ無いですよ
極一部の出来る人しか楽しめない
上位も全体も外人だらけ

フェードアウトした人多そう

2023/01/21(土) 21:51:49.04

別にこれ以上流行って欲しいとは思ってないんで……

2023/01/21(土) 22:43:38.68

BとCでつまづいたせいでD解けなかった
Cはもうちょいシンプルに解けるやつにしてくれよw

2023/01/21(土) 22:44:43.48

Fまで解けた割にパフォ渋いんだけど参加者数の問題？
順位も青色から見てそんなに悪くないのに

2023/01/21(土) 22:45:39.87

Bはnnのケース忘れてた
Cは最小0円を忘れてた
限られた時間だと短縮しすぎてこういうの漏れちゃうね

2023/01/21(土) 22:46:04.60

Fわかんね
絶妙に110縛りが邪魔くさい

2023/01/21(土) 22:46:13.44

>>268
もうパフォ出てる？

2023/01/21(土) 22:49:17.47

>>268
なんかpredictor変かもしれんね

2023/01/21(土) 22:50:03.50

>>272
前回も表示バグってた気がするしそうだと信じたい

2023/01/21(土) 22:51:36.48

>>268
全抜多いからでは？

2023/01/21(土) 22:53:37.02

検索したらやっぱり皆も同じ感想っぽいな

2023/01/21(土) 23:01:36.37

まだパフォ出てないぞ
Gができなくて残念

2023/01/21(土) 23:09:02.32

>>260,265
マジレスしておくと、ある程度のレベルまでは間違いなくガチ暗記ゲーだからね
異常な天才は競プロ対策してなくても解けまくれるかもしれんけど、普通のひとにとっては暗記ゲー

そしていろんなことを暗記しまくると(理解度が深まってくると)、応用もどんどん効いて難しい問題も解けるようになる

まあ大学受験とかでも同じだろ
基礎を暗記してからようやく応用ができるようになる

2023/01/21(土) 23:11:45.67

多分200ぐらい低く出てる

2023/01/21(土) 23:20:33.40

なんかパフォ低くない？😐

2023/01/22(日) 02:02:34.60

やっとF自力ACできた
素数である必要がなかった…

2023/01/22(日) 02:25:58.37

>>277
CD程度の問題を見て解法が思いつかず何やっても無理だと悟って
あまりの自分の無能さに嫌気がして
悪態をついた愚痴にマジレスしてくれる優しさに救われます

暗記ゲーにしては範囲が広すぎるし
勉強することを精進だと自分に言い聞かせてましたが
毎回理解出来ないものを永遠と写経するだけになっていて
初見で解法が思いつかないことが苦痛とストレスになって
病みそうなレベルなので
精神衛生的にも少し教プロから距離をおくつもりです

2023/01/22(日) 03:04:01.89

>>281
まあ、プログラミングというより数学の競技だと思っておけば安心するだろうね

大学受験数学は当然として、中学受験数学で学ぶようなテクニックが活用できたりするし、
そういう受験数学のエリートがさらにアルゴリズムをめっちゃ勉強して競い合うのが競技プログラミングだ

もし中学受験とかやってないのに、そういう連中に追いつき越えたいなら、そういうエリートがやってるよりもはるかな修練が必要だよ
まあそういうエリートは数学的な問題を解くのが大好きだから現時点の瞬間的な修練量でさえなかなか超えられないだろう
アルゴリズムやデータ構造というより数学そのものの勉強も必要になってくるしね

2023/01/22(日) 04:18:00.16

明日のARC早解き大事そうで不安

2023/01/22(日) 09:04:17.31

「競技」プログラミングが十分な勉強と対策をしなくてもできるなら、もうそれは競技じゃないんよ
競技なんだから、勝ちたきゃ多くの対戦相手を蹴落とすだけの努力をしなきゃいけない

2023/01/22(日) 14:02:44.50

今日のARCで大事なのは700点の難度だよなあ
maroon回ほど極端に難しくなることはないと予想

2023/01/22(日) 14:12:07.62

ABCだったら初見力なんてそんなに大事じゃなくて、ちょっと変形された問題が解けることが重要だと思うんだよな
ちょっとの変形に対応できるかどうかの練習をするのにも、土台としてまず知識が要るので、知識ないうちは才能の有無すらわからんよ
むしろ初見力があっても知識不足だと解けないのがABC
AGCは逆に知識無くても初見で解けるやつもいるから、最初はABCよりAGCの方がパフォーマンス出やすいやつもいる

2023/01/22(日) 14:14:50.28

初心者にマウントとるスレは今日も平常運転

2023/01/22(日) 14:17:25.11

ただ、瞬発的に解法を発想できないのは仕方ないにしても（知識不足だと発想の引き出しがないからそりゃ無理）、解説を読む段階になったら時間を掛けてでも書いてあることを理解するように心掛けないと類題を解けるようにならないと思うぞ

2023/01/22(日) 15:03:59.25

800点はブレで結構解きやすいこともあるけど900点はきっちり難しい印象がある
ただ昔の問題だと1000点超えでもそんなでもない問題も稀にあるから決めつけで解けないと思うのもよくないんだろう

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

昨日のG残り時間少なくて諦めてたけどEかFくらいに置かれてたら印象変わってそう
600点問題の基準が良くわからない

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

ABCは自分の中では結構E<F=G<Exみたいな印象があるかなあ
真っ当にGの方が難しいときもあるけど

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

それと6問ABC時代のF（600点）は今のGより難しかったような気がするね

2023/01/22(日) 16:49:33.03

質問
long long ans＝1ll ＜＜60
このコードのllと＜＜60ってどういう意味なんですか？
apg4bにも載ってなくてわからん…

2023/01/22(日) 16:59:23.70

> apg4bにも載ってなくてわからん…

https://atcoder.jp/contests/apg4b/tasks/APG4b_y
https://atcoder.jp/contests/apg4b/tasks/APG4b_ac

2023/01/22(日) 17:00:16.35

llは1をlong longとみなすってこと
<<はシフト演算子