競技プログラミング総合スレ 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/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とみなすってこと
<<はシフト演算子

2023/01/22(日) 17:01:07.41

<<はシフト演算子と言って、数値の各bitをずらす働きがある
例えば5はbitで表すと101だが、5<<2は10100だ
bitを1つ左にずらすごとに数字は2倍になるから、これは1の2^60倍をansに代入してる

ただずらす数字がint型だと、通常32bitだから60もずらしたら溢れるという問題がある
そこで1LLと書くことでlong long型の1であるとコンパイラに教えてやり、オーバーフローが起きないようにしてる

2023/01/22(日) 23:09:41.75

Cまでは速攻で解けた

2023/01/22(日) 23:09:56.89

正解してたんだけど、
Aの問題の99...353で割るタイミングってどこが適当なんだろう？
よくわからなさすぎて10^i全部に99…353で割って、更にA＊B前にも99…353で割って、
最後の出力でも99…353で割ってしまった。

2023/01/22(日) 23:11:11.20

D1見つけてそれ使って比較出来るところまでは気付けたのにマージソートにまで辿り着けなくて勿体ない

2023/01/22(日) 23:13:05.12

お、ナメクジから初めてようやく茶色になれたw
こらからも頑張りますw

2023/01/22(日) 23:15:38.53

>>297
Cまでは解きたかった、、、
遊びがない場合とで分けたかったんだけど、遊びがなくても完全一致のケースもあるし...と考えてたら時間足りなかった
場合分け発生するのによく速攻で出来るね

2023/01/22(日) 23:18:31.18

AとCの解説微妙に違う……？

2023/01/22(日) 23:22:25.50

>>302
積を99…353で割ってない事とか？

2023/01/22(日) 23:26:01.92

ソートもちゃんと勉強しておかないといけないなー

2023/01/22(日) 23:43:34.23

比較的解きやすい回だったはずだけど、Dなんで思いつけなかったんだろう
反省

2023/01/23(月) 00:16:21.13

>>299
これ

2023/01/23(月) 00:35:02.59

>>303
A
自分が解説の意図を勘違いしてるかもしれないけど、ajとbjを交換することを考えるなら、
aibj+ajbiとaibi+ajbj
ではなく
aibj+ajbiとaiaj+bjbi
を比較するべきでは

Cはいま見返したら問題なかった
自分が初見時に誤読したのか訂正されたのか分からん（圧縮後のBの長さ、って最初から書いてあったっけ）

2023/01/23(月) 00:37:35.71

Cは本人が訂正したとTwitterに書いてた

2023/01/23(月) 08:36:16.47

>>307
自分の認識だけど
Aは解説。
307の言ってるのは解法。
Aの解説を達成するためには307で合ってるけど省略されてるという認識。

2023/01/23(月) 08:48:11.39

>>309
ごめんよく分かってない
解説の

ここで、～前者となります。

と、

よって、～最小化できます

の部分がどう繋がってるのか分からない

2023/01/23(月) 08:50:24.31

2＊4+3＊5と　2＊5+3＊4を比べる時
Aの解説は
2＊4+3＊5、3＊5+2＊4
どっちでも良いけどどっちかに大きい方を寄せると最小だよと言っている

307の計算が前提

2023/01/23(月) 12:13:39.30

>>311

2＊4+3＊5と　2＊5+3＊4を比べる時
Aの解説は
2＊4+3＊5の2と4が3、5よりそれぞれ小さい(
大きい)なら前者、そうじゃないなら後者だよって話

>
> 307の計算が前提

2023/01/23(月) 13:01:50.68

最近このスレって新参ばかりだな
寒色が程度の低い話をするばかりでちっとも面白くない

2023/01/23(月) 13:08:45.38

>>312
そこまでは分かってるけど、そこから次の行の「よって、」以下にどう繋がってるのかが分からない

aibi+ajbj
はどう桁を交換しても作れないから関係なくない？

2023/01/23(月) 15:36:06.70

暖色は分からなくても自力で考える力が高いからこんなところで質問しないんだよな
自分で高度な話題を振っかければ暖色も反応すると思うぞ

2023/01/23(月) 15:53:11.40

できるならやってみなよ

2023/01/23(月) 15:54:19.89

arc154_c って文字列テクニックとかでもっと速くなりますかね？

2023/01/23(月) 16:04:41.32

本質は文字列 S, T が与えられて、S を rotate して T を（連続とは限らない）部分列として含むようにできるか、かな？

**デフォルトの名無しさん** (JP 0Hff-MR1E) · 2023/01/23(月) 16:38:20.37

何も考えてないけど文字列アルゴが効くのは連続部分列系じゃないの

2023/01/23(月) 17:10:24.74

区間部分列だと遷移ベクトルを考えるのがDISCO!とかにあったけど……今回は種類数が多いから辛いんだよな
種類が多いならAとBの先頭を出現数が最も少ない文字で固定すれば少しは速くなりそうだが、誤差程度だろうし

2023/01/23(月) 17:27:33.65

ウェーブレット木/行列って競プロでどれくらい使える？

2023/01/23(月) 17:46:57.36

>>321 2-SATより上、セグ木より下くらいの頻度で使える
正直言ってACLに匹敵する実用性がある

2023/01/23(月) 19:05:17.82

遅延セグ木はもう誰でも知ってそうなデータ構造と化してるけど、WMは有用性の割にまだそんなに広まってないよな

2023/01/23(月) 20:48:26.48

ABC97 B Exponentialについて教えていただけませんか？
Python3です。

from math import sqrt

x = int(input())
ans = 1

for i in range(1,x+1):
if sqrt(i) % 1 == 0:
ans = i

print(ans)

これを提出するとtest4,6,7だけWAになります。
テストケースは検索したけど見つからず...。
よろしくお願いしますm(._.)m

2023/01/23(月) 20:50:24.16

for文のインデントがおかしくなってますね(汗)
無視して下さい

2023/01/23(月) 21:32:24.11

>>324
pが3以上の場合も考える必要があります

2023/01/23(月) 21:35:37.58

sqrt(i)%1に思うことはあるけど、その前にまず誤読してないか？
試しにsqrt(i)%1==0なるiを全部出力させてサンプル1と比較してみなよ

2023/01/23(月) 23:43:27.87

>>326
>>327
完全に勘違いしてました(汗)
ありがとうございます。

2023/01/25(水) 05:47:55.43

プログラムだかソフトウエアだか忘れたけど、ひろゆきみたいに上から目線で君臨しているやつまだいるの？
たかが一般人のくせになｗ

2023/01/25(水) 09:07:59.22

自己紹介かな？

2023/01/25(水) 11:49:43.90

>>294
>>295
ありがとうございます

2023/01/25(水) 11:49:51.41

>>296
ありがとうございます

2023/01/25(水) 11:55:46.11

しゃくとり法について質問
解答例の通りに実装すれば計算量がO(N)で済むと書いてるけど、解答例だとN-1回ループのfor文の中にwhile文が入ってるんだけど、これで本当に計算量がO(N)で済むの？
頭が悪すぎて解説読みこんでもわかんね
https://i.imgur.com/clPvzaA.jpg
https://i.imgur.com/7oJcUMF.jpg

2023/01/25(水) 12:12:47.43

それ読んでわからんなら一生わからんやろ