競技プログラミング総合スレ 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/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はテストケースが弱いとよく言われている気がする

2023/01/29(日) 23:03:39.53

終了2分後にC解けた…

2023/01/29(日) 23:03:56.11

このwriterのARC-A問題毎回めちゃくちゃ難しくない？
Bすぐ気づけたから一命を取り留めたけどAの場合分けでごちゃごちゃさせすぎてWA量産してたから初めの一時間くらいは絶望状態だった

2023/01/29(日) 23:11:21.90

Aを未証明で通したけど解説見たら全然違うことやってたから自分の解法が正しいのか分からん

2023/01/29(日) 23:11:43.07

今日難度調整する気あった？
悪ノリ勘弁してくれよ

2023/01/29(日) 23:16:45.73

Aはたしかに難しめだったけど、ARCで類題を見たことある気がする

2023/01/29(日) 23:26:35.43

コンセプトだけならAよりCの方が簡単な気がする
Cは無限場合分けがキツいけど、天才的発想が要るタイプじゃない

2023/01/29(日) 23:32:43.87

Aも天才って感じの問題じゃないけどな
ただ回文って頭壊れるよな

2023/01/29(日) 23:34:37.09

Bがやたらと解きやすかったからAのやりにくさが際立ったのもある

2023/01/29(日) 23:51:53.28

A問題diff1500超えは笑う　ARC最高記録かな
実際AGCって言われても違和感無かった

2023/01/29(日) 23:58:11.53

前半も難しかったけど、任意色コーダーもお手上げのEFもすごい
500-500-700-900-1000↑-1000↑ぐらいの配点のAGCでも違和感がないね
ARCは定期的にこういう回が来る

2023/01/30(月) 00:26:54.26

このまま開催が少ないと文句言われてるagc にすれば良かったよね

2023/01/30(月) 00:34:49.18

TwitterのTLに昨日のABCの感想が混ざってるせいで、E問題F問題解けたみたいなツイートがたまに流れてきて驚く

2023/01/30(月) 00:47:36.97

最新ツイート表示にしろ

2023/01/30(月) 15:34:29.73

Twitterで解決しなかったのでここで質問
昨日のARC-Cを手元でテストケース生成する時、値域は1≦A_i≦4で十分？
重複順列を全部生成しなくてもこれで網羅できてると思うんだけど、証明に自信が持てない

**デフォルトの名無しさん** (JP 0H46-6dB/) · 2023/01/30(月) 16:18:46.19

十分ってどういう意味？

2023/01/30(月) 16:34:57.65

解答の場合分けを全部網羅できるかって話ならまあできてそうじゃないか
偶数も奇数も種類数は3以上いらないはず
コンテストジャッジのテストケースとして十分かという話だと、微妙な嘘解法とかに弱そうな予感がするが

2023/01/30(月) 16:38:59.08

コンテスト中に実験や検証の目的で手元でテストケースを生成するという話なら、そこまで条件絞れてる時点でもうテストケース生成要らんレベルで解けてるだろ感あるが

2023/01/30(月) 18:06:00.04

仮に無限個のテストケースを一瞬でジャッジできるとして、1≦A_i≦2e5で作った2e5^N通りのテストケースと1≦A_i≦4で作った4^N通りのテストケースは任意のコードに対して同じAC/WAの結果を返すという主張です

2023/01/30(月) 18:08:07.48

任意の、は流石に過激主張か(57が入力に含まれているとpanicするコードなんかは落とせない)
場合分け系解法なら常に同じになる、程度で

2023/01/30(月) 18:19:02.93

想定解の場合分けをするコードの出力なら一致する
しょうもない話をするが、57を見たら常にYesを出力も場合分け解法だと思うので、場合分け解法なら常に一致するとは限らない

2023/01/30(月) 18:25:48.00

そりゃ想定解を書きゃ一致するだろ
そういう揚げ足を取って欲しい訳じゃないんだが

2023/01/30(月) 18:26:57.35

まあ偶数が奇数の種類数が3以上ある場合に挙動が変わって不正解を吐き出すような嘘解法って特に思いつかんよな

2023/01/30(月) 18:30:03.28

>>415
意図が不明瞭なんだが、要するにコンテスト中のテストケースとして十分か知りたいのか？
すなわち自然に生えてくる嘘解法を落とすには十分かみたいな
任意の場合分け系解法に対して、みたいな話なら一致しないコードをいくらでも構成できるから偽だが

2023/01/30(月) 18:30:45.18

あれだわ、こっちで証明書くから正しいか正しくないかだけ教えて欲しい

今回の問題は、Aの各要素の偶奇を定めた時、どの二要素が交換可能かという関係が1位に定まる
この時にAをBに一致できるかという問題はソーティングネットワークであるから、0-1原理より二値のみ見れば正当性が判定できる
各要素の偶奇もいるから、結局{1, 2, 3, 4}の4元のみで場合分けの正当性が判定できる

2023/01/30(月) 18:40:13.31

>>418
場合分けに偶奇いずれかの種類数が3以上のときに生じるような情報を使っている場合は、4元に置き換えた時点でYes/Noの出力が変わることがあるので偽なんじゃね
場合分けに使っていい情報をある程度制限すれば真になりそうだが

2023/01/30(月) 19:12:29.53

まだ全然理解してないけどプログラムを入力からソーティングネットワークへの関数だと思ってる？

2023/01/30(月) 19:21:19.32

>>418
偶奇は要素に対する条件だからソーティングネットーワークは話が違う気がする
位置に対する条件だったらわかるけど

2023/01/30(月) 19:29:00.95

プログラムは全ての(i,j), 1<=i<j<=Nに対し「最初位置iにあったものと位置jにあったものが交換可能」かを定め、それを元に判定を行うものであるという仮定がある？

2023/01/30(月) 19:33:31.82

ソーティングネットワーク知らなかったけど面白そう

**デフォルトの名無しさん** (JP 0Hcf-ozkd) · 2023/01/31(火) 11:48:36.09

全然話についていけてないけど、場合分け系解法の定義がはっきりすればもうちょっと議論しやすくなりそう

2023/02/01(水) 10:33:12.46

多次元のデータを扱う過程でvectorだとMLEするのに全く同じサイズで代わりに生配列を使ったらメモリ制限余裕でクリアしたんだけど、これってvectorの方がより多くの情報を保持してるってこと？
軽く調べてみた感じvectorの各次元のサイズの順番次第でも変わってくるらしいんだけどもしかして生配列の方が地雷少なかったりする？

2023/02/01(水) 10:54:25.86

vectorは配列サイズより大きな領域を確保してpush_backに備えるから
push_backした時に現在のサイズじゃ足りないと二倍の大きさのメモリを確保してそこに既存データをコピーする

2023/02/01(水) 12:13:43.49

多分だけど、
二次元の配列を生配列でやるとメモリ上は連続に並ぶけど
vectorでやるとそうではないので、その分のロスはあると思う