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

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

2023/01/25(水) 12:16:30.97

自己解決俺がただのガイジだった

2023/01/25(水) 12:20:19.29

Ri＝nである場合、そもそも増やさないから全体の計算量はO(n)で済むんだね
頭が悪すぎてこの程度のことすら理解するのに時間がかかる

2023/01/25(水) 12:41:49.83

まあそんなもんでしょ
どうせ無限時間必要とするから、1つずつ典型を学んでいけばいい
レッドコーダーでも問題文誤読したせいで問題解けないこともある

2023/01/25(水) 12:43:36.96

それはそうだが寒色の言うことじゃねえな

2023/01/26(木) 00:53:34.00

蟻本と螺旋本の電子版がセールで500円になってるの神すぎる
紙版しか持ってなかったから即ポチった

2023/01/26(木) 11:52:45.66

螺旋本\蟻本で有用な情報ってなんかある？

2023/01/26(木) 13:05:43.15

記憶違いでなければ蟻本ってとうの昔に更新しなくなったPKUに則ってたと思うんだけど、新しい版では書き換えられてたりするの？

2023/01/27(金) 15:09:59.38

これ見ると東大生でも大半が緑色以下なんだよな
参加者のレベルがあまりに高すぎてエリートでも灰～緑程度のレベルで燻ってる
これから、AtCoderに参入する人はこの事実を知っておいた方がいいわ
https://i.imgur.com/zfVNSBr.jpg

2023/01/27(金) 15:11:53.02

青より上までいけるのは東大生でも極わずか
1部の数学エリートしか楽しめない娯楽それがAtCoder
俺は恐ろしい世界に入り込んでしまったんだな…

2023/01/27(金) 15:12:19.44

画質糞すぎません？

2023/01/27(金) 15:15:25.25

こっちはまだ少しましかな

https://i.imgur.com/jKZaXCC.jpg

2023/01/27(金) 15:26:17.89

これのほうがいいか
しかも、これは1年半以上前のデータだからな
今は当時よりも参加者のレベルが上がってるから、東大生であっても緑まで行くのは相当苦戦するかも
Fラン大学とかだと茶色も無理なんじゃないか
https://docs.google.com/spreadsheets/u/0/d/1_rtU2geWnkZyOBYXyvPtcyn9GRfucd7GGFQqoGM5fZE/htmlview

2023/01/27(金) 15:30:53.28

東大生が多いのは事実だけど全員が競プロに本気出してるわけではなくて適当にやってる人や合わなくて緑以下で辞めるような人もカウントされちゃってるから競プロに取り組んだ時間も結構重要よ

2023/01/27(金) 15:58:00.21

そうだよ
真面目にやって緑とかセンス無いから諦めたほうがいいよ

2023/01/27(金) 17:29:25.91

ていうか競プロなんて役に立たないんだから、時間を注ぎ込んでないほうが賢くて偉い

2023/01/27(金) 19:58:07.53

競プロと人生くらい両立しろ

2023/01/28(土) 22:42:28.61

前回茶色になれて、今回Dで解けた。
ようやくEの世界と対峙する事が出来そう。

2023/01/28(土) 22:42:57.04

だめだーdpどう使うのか思い付かん
70分お茶飲んでた

2023/01/28(土) 22:44:30.61

Cは楽な方法思いつかなかったから
鬼のように条件縛りしたけど、あれで良かったのかよw

2023/01/28(土) 22:45:29.10

自分もFで1時間以上椅子を温めていた
ここ安定して解ければ黄色になれそうなんだけど二乗の木DPなんて知らなかったし経験が足りてない

2023/01/28(土) 22:47:05.23

またCで誤解法でACしちゃったかも？
解説見ると条件3つあるのに
if文2個でダメ元で提出したらACしちゃった

ACLのDSUで入力してmergeして

条件2つだけ

if (d.groups().size() != 1) return false;
if (N - 1 != M) return false;

上記抜けたらYes
return true;

これって正しいですか？
ACしたのに自身が無い

2023/01/28(土) 22:48:00.90

>>342
これ、出典どこです？

2023/01/28(土) 22:50:49.59

>>355
4 3
1 2
1 3
1 4
とかはNoだけど、それだとYesになるかな

2023/01/28(土) 22:52:36.25

>>355
次数が3以上の頂点を含む木だとダメだから嘘解法では

2023/01/28(土) 22:53:07.92

>>355
木だったらだめだな
というかこれ落とすテストケースないのか…

2023/01/28(土) 22:53:14.42

>>355
解説の1つ目の例で間違いなのになんで通るのかw

2023/01/28(土) 22:53:41.85

>>359
×木だったら
○一般の木だったら

2023/01/28(土) 22:55:37.76

EとかはSAISしたあとにLCPテーブルとセグ木を組み合わせる例の典型知ってればすぐ思いつくし、知識ゲー感あるな

2023/01/28(土) 22:56:20.81

あちゃー
また誤解法やらかしちゃいましたかね
ラッキーACの方が後でメンタル凹むのでWAにしてください
ダメ元とはいえテストケースで全部通ったから提出したけどやっぱり罠だったか

2023/01/28(土) 22:57:41.57

C次数3以上の頂点を含む木のテストケースすら入ってないってガバガバすぎる

2023/01/28(土) 22:58:00.26

>>362
ABCはいつも知識ゲーだぞ
例えばセグ木とかローリングハッシュとかをコンテスト中に自分で発明できるひとなんてほとんどいないし