競技プログラミング総合スレ 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/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でやるとそうではないので、その分のロスはあると思う

2023/02/01(水) 12:25:44.63

要素数を保持するメンバ関数.size()も悪さに加担してそうだけど色々原因が絡んでそうだな
生配列って変数を要素数に使えないのと初期値に気をつける以外に何か注意すべき点あったかな

2023/02/01(水) 13:47:00.53

vector<vector<T>>は多次元配列じゃなくてジャグ配列だよ

2023/02/01(水) 14:39:57.27

ジャグ配列という言葉を覚えたてでドヤりたいのか知らんけどC++で区別する意味ねーぞ
そもそも配列じゃないし

2023/02/01(水) 16:23:28.28

？
現にパフォーマンスに差があるって話してんだから区別する意味あるに決まってる

2023/02/01(水) 16:25:26.10

よく「C言語に多次元配列はない、あるのは配列の配列だけだ」なんて聞くけど、じゃあ「真の多次元配列」ってなんなのさ
a[1,2,3]みたいに所定の個数の添字を使わないとコンパイルエラーになるような配列とか？

2023/02/01(水) 16:28:00.66

>>431
日本語苦手？

2023/02/01(水) 16:35:05.84

一般的な多次元配列というのはこれ
https://e-words.jp/w/%E5%A4%9A%E6%AC%A1%E5%85%83%E9%85%8D%E5%88%97.html
C言語で昔から多次元配列と呼ばれてたやつだ

ところがもう一種類の多次元配列を持つ言語が現れて区別の必要が出てきた
そのため片方を多次元配列、片方をジャグ配列と呼ぶようになった

ジャグ配列のジャグとはギザギザという意味で要素である各配列の要素数がバラバラという意味だな
C++の配列(vectorは配列に非ず)では区別の必要はない

2023/02/01(水) 16:46:12.82

はえ～、じゃあジャグ配列ってのはいわゆるレトロニムだったのか
サンクス

2023/02/01(水) 17:19:44.17

そうだね、レトロニムではある
C言語の初期から「配列へのポインタ」の配列を使うなんて当たり前だし

しかしメモリレイアウトがシーケンシャルになる多次元配列と、ポインタの配列は必要に応じて区別するもんだけど

2023/02/01(水) 17:42:02.48

どこのメモリをどのように割り当てるかで用途やコードは変わるけどそれは特に「呼び分ける」必要はないってことだよ
他の言語のように文法から違うならともかく
たとえば二分木を配列にマップしてもそれは二分木だろ

2023/02/01(水) 18:12:59.33

全く何が言いたいのかわからん
int A[3][5]は多次元配列でジャグ配列（配列のポインタの配列）じゃないと思うが

2023/02/01(水) 18:13:09.99

C++のvector<vector<T>>はジャグ配列であって、当然多次元配列としても使えるがパフォーマンスは落ちるよね？ってだけなんだがそんなに変か？

要素数が動的な多次元配列（に機能を絞ってパフォーマンスを追求したもの）はC++にはなくてだからこそmdspanが提案されたりしてる

2023/02/01(水) 19:18:23.03

>>438
大丈夫か？
ポインタの配列の話なんか誰もしてないぞw
多次元配列は一種類しかないから区別の必要はないと書いたよな？

2023/02/01(水) 19:20:20.77

あ、そうかそうか
配列が第一級オブジェクトだと思ってるのかw
ちげーよw

2023/02/01(水) 19:23:36.17

レッドコーダーの人は、プログラミング言語についても詳しい人ばかりですか？

2023/02/01(水) 19:42:37.94

いいえ

2023/02/01(水) 19:53:24.92

第一級オブジェクトじゃないと何が起きるの？
ポインタの配列をジャグ配列って呼ぶことにしていい？

2023/02/01(水) 20:30:34.21

抽象的なデータ構造としての配列の話をしてるのにC/C++の配列と混同してないか？

2023/02/01(水) 22:04:49.45

どうして寒色はこうも見苦しいのか

2023/02/01(水) 22:12:17.12

ちな黄色

2023/02/01(水) 22:44:43.03

ソースは？

2023/02/01(水) 23:07:53.04

言語無関係な抽象的データ構造で多次元配列とジャグ配列を区別する意味なんてなおさら無いだろ
C/C++の話をしてるところにトンチンカンなこと言って割り込んできた言い訳がそれかよ

2023/02/02(木) 01:35:53.36

要件違うんだから区別する意味あるだろ
その調子だと配列もハッシュ関数がidなハッシュマップだから区別する必要ないとか言い出しそう

2023/02/02(木) 04:19:39.15

元の話って速度の話じゃなかったのか？
ジャグ配列か多次元配列かは明確に速度が変わるから、考える意味はあると思うぞ
あとAtCoderはvector<vector<int> >をジャグ配列と呼んでる https://atcoder.jp/contests/APG4b/tasks/APG4b_t

2023/02/02(木) 08:03:13.54

抽象的なデータ構造だそうだからどちらが速いかはその言語によるぞ

2023/02/02(木) 10:49:56.77

抽象的ってのは言語仕様に依存しない程度の意味じゃないんか
どの言語のジャグ配列も多次元配列より遅い、は真だと思うけど(もちろん多次元配列が無い言語はあるので、一次元配列で代用するものとして)

2023/02/02(木) 10:54:31.00

C#の多次元配列はジャグ配列より遅いよ
直感を信じずに速度が重要ならちゃんと検証しよう
https://zenn.dev/tremendous1192/articles/333df9cf3c0170

2023/02/02(木) 11:24:59.40

>>454 検証結果マジか、シーケンシャルアクセスできるなら掛け算必要な方が遅いということかな
添字が範囲内なのかのassertなども含めると逆転しうるのか……
検証出してくれるのは助かる