競技プログラミング総合スレ 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/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はいつも知識ゲーだぞ
例えばセグ木とかローリングハッシュとかをコンテスト中に自分で発明できるひとなんてほとんどいないし

2023/01/28(土) 22:59:17.24

Gみたいに座圧とデータ構造組み合わせる問題は思い付いてから書ききるまでが長くてストレス貯まる

2023/01/28(土) 22:59:36.80

Gみたいに座圧とデータ構造組み合わせる問題は思い付いてから書ききるまでが長くてストレス貯まる

2023/01/28(土) 22:59:50.70

他の解法何も理解してないけどEはTrieが一番楽だと思ってる

2023/01/28(土) 23:01:27.73

Trieの方を先に思いついたがポインタアクセスの定数倍が怖くてやらなかった

2023/01/28(土) 23:01:42.36

Eはソートすると両隣と比較するだけで済むけどTrie解法の方を知らない

2023/01/28(土) 23:04:32.64

>>364
それを落としたい問題かと思ったのにな

2023/01/28(土) 23:06:52.79

>>371
解説に載ってるケースだから落としたいに決まってる

2023/01/28(土) 23:07:17.13

ワイもtrie木の存在を知らないまま再発明してた
もっと勉強しないとダメだな

2023/01/28(土) 23:09:01.81

今週は
将棋→atcoder→将棋→atcoderだけの休みw

2023/01/28(土) 23:09:31.14

Gを自作平衡二分木でやったらTLEしてしまった

2023/01/28(土) 23:09:39.07

チラ裏

2023/01/28(土) 23:09:48.10

Gを自作平衡二分木でやったらTLEしてしまった

2023/01/28(土) 23:10:16.89

エラーで二重書き込みしてしまった

2023/01/28(土) 23:10:33.81

今週は
将棋→atcoder→将棋→atcoderだけの休みw

2023/01/28(土) 23:11:17.15

なんかサーバがおかしいね

2023/01/28(土) 23:11:26.35

なんかエラー起きてるよな
サーバー不調か

2023/01/28(土) 23:13:35.66

>>371
連結じゃないパターンとかはちゃんと入ってるのに解説の図にも載ってるようなシンプルな例外が含まれてないの謎だよね

2023/01/28(土) 23:24:23.55

Exって小さい方から追加してワーシャルフロイド的にやればできるよなーって思ってそこから進まなかったけど、そのまんまなんだね
bitsetでの高速化という発想がいつも頭から抜けてしまう

2023/01/28(土) 23:27:22.96

まあ次数の方の条件はあんまり見逃さないと思うけどな
自分も連結の判定拾えず1wa だった

2023/01/28(土) 23:29:46.89

参加者がミスりやすい連結判定ではあるけど、解説で必要十分条件を整理しているのにテストケースに反映されていないのを見るとうーんとなってしまう

2023/01/28(土) 23:30:23.85

ミスりやすいのは

2023/01/28(土) 23:47:00.96

ExはGにあったらもうちょっと気づきやすい感ある

2023/01/29(日) 09:03:53.81

極端なテストケースを含めてない問題って意外とあるのかな
過去問を埋めてたんだけど、想定解では平方根で計算量を抑えるパートがあったのに普通にそこを全探索して通ってしまった
具体的にどの問題かとは言ってないからアレだけど自分で極端な場合を試してTLEすることは確認してる

2023/01/29(日) 11:25:47.61

C++なら通るってのは珍しくない
望ましいことではないけど大騒ぎするほどレアなことでもない

2023/01/29(日) 11:38:30.50

ABCのC以下なら有り得るがD以上でそんなことあるか？

2023/01/29(日) 14:53:32.40

昨日のExもbitset高速化が本質なところを、C++で愚直にO(N^3)やっても通るらしいし（勝手にコンパイラがベクトル化してくれてbitset高速化と等価な処理をしてくれる）、後半の問題でも非想定愚直解が通ることは普通にある

2023/01/29(日) 14:55:09.47

そういうのは大体コンパイラが運良く賢い最適化を適用できたときだから、狙って出すのはそんなに簡単じゃない

2023/01/29(日) 19:04:35.25

コンパイラの気持ちになればベクトル化効きそうなコード書くのはそんなムズくないと思う

2023/01/29(日) 22:06:29.55

他で類題が出たときにAtCoderはテストケースが弱いとよく言われている気がする