競技プログラミング総合スレ 65

■ このスレッドは過去ログ倉庫に格納されています
2022/12/26(月) 12:47:37.63ID:CkzYHyzir
!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/02/01(水) 16:25:26.10ID:G8geOuCTa
よく「C言語に多次元配列はない、あるのは配列の配列だけだ」なんて聞くけど、じゃあ「真の多次元配列」ってなんなのさ
a[1,2,3]みたいに所定の個数の添字を使わないとコンパイルエラーになるような配列とか？
2023/02/01(水) 16:28:00.66ID:lgst1CuMa
>>431
日本語苦手？
2023/02/01(水) 16:35:05.84ID:lgst1CuMa
一般的な多次元配列というのはこれ
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.82ID:G8geOuCTa
はえ～、じゃあジャグ配列ってのはいわゆるレトロニムだったのか
サンクス
2023/02/01(水) 17:19:44.17ID:Xxk6iIQM0
そうだね、レトロニムではある
C言語の初期から「配列へのポインタ」の配列を使うなんて当たり前だし

しかしメモリレイアウトがシーケンシャルになる多次元配列と、ポインタの配列は必要に応じて区別するもんだけど
2023/02/01(水) 17:42:02.48ID:lgst1CuMa
どこのメモリをどのように割り当てるかで用途やコードは変わるけどそれは特に「呼び分ける」必要はないってことだよ
他の言語のように文法から違うならともかく
たとえば二分木を配列にマップしてもそれは二分木だろ
2023/02/01(水) 18:12:59.33ID:5UExoC6r0
全く何が言いたいのかわからん
int A[3][5]は多次元配列でジャグ配列（配列のポインタの配列）じゃないと思うが
2023/02/01(水) 18:13:09.99ID:tEOpIEztM
C++のvector<vector<T>>はジャグ配列であって、当然多次元配列としても使えるがパフォーマンスは落ちるよね？ってだけなんだがそんなに変か？

要素数が動的な多次元配列（に機能を絞ってパフォーマンスを追求したもの）はC++にはなくてだからこそmdspanが提案されたりしてる
2023/02/01(水) 19:18:23.03ID:lgst1CuMa
>>438
大丈夫か？
ポインタの配列の話なんか誰もしてないぞw
多次元配列は一種類しかないから区別の必要はないと書いたよな？
2023/02/01(水) 19:20:20.77ID:lgst1CuMa
あ、そうかそうか
配列が第一級オブジェクトだと思ってるのかw
ちげーよw
442デフォルトの名無しさん (ﾜｯﾁｮｲ 1a55-5T4A)
垢版 |
2023/02/01(水) 19:23:36.17ID:zBkVwI+K0
レッドコーダーの人は、プログラミング言語についても詳しい人ばかりですか？
2023/02/01(水) 19:42:37.94ID:wHSgCyOm0
いいえ
2023/02/01(水) 19:53:24.92ID:5UExoC6r0
第一級オブジェクトじゃないと何が起きるの？
ポインタの配列をジャグ配列って呼ぶことにしていい？
2023/02/01(水) 20:30:34.21ID:bcQxhzDjM
抽象的なデータ構造としての配列の話をしてるのにC/C++の配列と混同してないか？
2023/02/01(水) 22:04:49.45ID:1VPsFaLs0
どうして寒色はこうも見苦しいのか
2023/02/01(水) 22:12:17.12ID:5UExoC6r0
ちな黄色
2023/02/01(水) 22:44:43.03ID:uzGFw6kGr
ソースは？
2023/02/01(水) 23:07:53.04ID:1VPsFaLs0
言語無関係な抽象的データ構造で多次元配列とジャグ配列を区別する意味なんてなおさら無いだろ
C/C++の話をしてるところにトンチンカンなこと言って割り込んできた言い訳がそれかよ
2023/02/02(木) 01:35:53.36ID:wNS591RpM
要件違うんだから区別する意味あるだろ
その調子だと配列もハッシュ関数がidなハッシュマップだから区別する必要ないとか言い出しそう
2023/02/02(木) 04:19:39.15ID:EnNL+Dwm0
元の話って速度の話じゃなかったのか？
ジャグ配列か多次元配列かは明確に速度が変わるから、考える意味はあると思うぞ
あとAtCoderはvector<vector<int> >をジャグ配列と呼んでる https://atcoder.jp/contests/APG4b/tasks/APG4b_t
2023/02/02(木) 08:03:13.54ID:unc+efpM0
抽象的なデータ構造だそうだからどちらが速いかはその言語によるぞ
2023/02/02(木) 10:49:56.77ID:EnNL+Dwm0
抽象的ってのは言語仕様に依存しない程度の意味じゃないんか
どの言語のジャグ配列も多次元配列より遅い、は真だと思うけど(もちろん多次元配列が無い言語はあるので、一次元配列で代用するものとして)
2023/02/02(木) 10:54:31.00ID:Yo++vCH+0
C#の多次元配列はジャグ配列より遅いよ
直感を信じずに速度が重要ならちゃんと検証しよう
https://zenn.dev/tremendous1192/articles/333df9cf3c0170
2023/02/02(木) 11:24:59.40ID:EnNL+Dwm0
>>454 検証結果マジか、シーケンシャルアクセスできるなら掛け算必要な方が遅いということかな
添字が範囲内なのかのassertなども含めると逆転しうるのか……
検証出してくれるのは助かる
2023/02/02(木) 11:27:29.66ID:EhYbzGf6a
んじゃそろそろイミフな言い訳やめてくれんかな
2023/02/02(木) 11:30:46.69ID:MROcVxaUM
不思議だな
どういう理由なんだ
2023/02/02(木) 11:34:06.46ID:EnNL+Dwm0
https://docs.unity3d.com/ja/2018.3/Manual/BestPracticeUnderstandingPerformanceInUnity8.html
この辺とか見た感じ、C#だと関数呼び出しで実装してるから遅いってことなのかな
速さを気にする言語じゃないし、こういうこともあるんだなぁ
2023/02/02(木) 11:34:22.95ID:MROcVxaUM
にしてもそもそもvector<vector<T>>をジャグ配列と呼ぶことに噛みつくこと自体がイミフじゃね？
2023/02/02(木) 11:37:52.38ID:MROcVxaUM
>>458
なるほどな
こういうのがあるから速度比較は難しい
2023/02/02(木) 11:48:18.09ID:EhYbzGf6a
>>459
え？w
2023/02/02(木) 11:53:17.19ID:QTnso+y6M
>>454
流し読みしたけどこの記事クオリティ低いから鵜呑みにするのはちょっと早計かな
3x2と2x3とかいうクソ小さい行列で実験してなんの意味があんのかよくわからんかった
2023/02/02(木) 12:00:46.82ID:eC04hXzt0
どこにUnityでC#動かしてる競技プログラミングサイトがあんだよ
「速さを気にする言語じゃないから」じゃないとか知ったかぶりはやめよな
2023/02/02(木) 12:02:39.09ID:Yo++vCH+0
>>462
それはそうだね、この記事だけじゃ微妙

でもまあ
"C# 多次元配列 ジャグ配列 速度"
とかでぐぐればいろんな検証結果出てくるし、いくつか見れば「多次元配列」は早いというわけじゃないのはなんとなくそれっぽいと思えるっしょ
2023/02/02(木) 12:05:07.71ID:bj9DDTEpd
C#は速さ気にしまくってるけど多次元配列は誰も使ってないし、あえて高速化するならSpan<T>で1次元扱いしたらいいから多次元配列は永遠に遅そう
2023/02/02(木) 12:06:06.09ID:EhYbzGf6a
自演きっついなこのスレ
なんだろう黄色を騙る茶色無職が常駐してんのかな
2023/02/02(木) 12:20:17.80ID:F3tsLQBup
ワッチョイがｱｳｱｳｳｰSaで文体が単芝使いの奴ってD問題で間違いを指摘されて暴言吐いてかつ浮動小数点数の話でも自分の間違いを一向に認めなかった奴と同一人物っぽいんだけど、もうスレのテンプレにNG推奨として追加した方が良くない？
前まではこんな奴居なかったし
2023/02/02(木) 12:22:50.20ID:Gzkf2uCba
だから無理矢理移住させると治安悪くなるって言ったのに
2023/02/02(木) 12:25:52.15ID:F3tsLQBup
端末使い分けてるか飛行機飛ばしてるっぽいんだけど、単芝使う+煽り文体+(今回の件でどっちが間違ってるかは置いといて)自分の間違いを絶対に認めようとしないって時点で同一人物なんだよなあ
2023/02/02(木) 12:31:31.89ID:ZUpBuKrwM
明らかに煽ることが目的のやつがいると思ったら個別にNGすればいいと思ってて、スレとして誰かをパージするようなことはしなくていいと思うんだよな
技術的な話に全く関係のないことを連投するやつが現れたらちょっと考える必要はあるが、全然まだそういうレベルじゃないだろ？
2023/02/02(木) 12:38:11.53ID:vof/cCRF0
議論になるなら良いんだけど、前例からもわかる通り間違ってることを堂々と発言した挙句に明白な根拠有りで誤りを指摘されても自分の誤りを認めず暴言を吐き始めるのが厄介だと思った
まあ今回の言い争いには直接絡んでないけどNGしとくわ
2023/02/02(木) 12:54:28.61ID:Ppl7cpkKa
ハッシュおじさんと同じ臭い腐臭
2023/02/02(木) 13:14:43.01ID:EhYbzGf6a
また論破されるから追い出すってかっこ悪すぎない？w
2023/02/02(木) 13:21:22.74ID:WNB2UXmap
前回で茶色になるようなレベルって自分で書き込んでるのにどこからそんな自信が湧いてくるのやら
それでいて寒色煽りしてるのも謎
2023/02/02(木) 13:55:09.74ID:unc+efpM0
論破されて自作自演で嘘の噂流すのかっこ悪すぎない？w
2023/02/02(木) 13:56:42.34ID:EnNL+Dwm0
このスレ、発言から青～黄が5人くらいは確定で居るからなぁ
某レッドコーダーも見てるっぽいし、下手な煽りは返り討ちにあう
2023/02/02(木) 13:57:36.22ID:unc+efpM0
返り討ちにあって追い出そうとするのかっこ悪すぎない？w
2023/02/02(木) 19:49:43.06ID:8e/EbPC1M
くんerのほうが知能高そうなのヤバいやろ
2023/02/02(木) 20:12:24.50ID:unc+efpM0
こいつより頭悪いやつなんていないだろ
2023/02/03(金) 21:24:06.48ID:ztTrwLKk0
明日のABCはARCよりかあ
やっぱり企業コンオンサイト予選はARC-likeな問題で選抜したいという思想はありそうだね
2023/02/03(金) 22:01:20.08ID:qVKOoofIp
中盤はいつもよりも難し目らしいからギリギリDが解けるかどうかみたいな層は明日厳しいかもね
キーエンスのD青EF黄程にはならないと思うけど
2023/02/03(金) 23:16:24.28ID:3wOaiFyt0
緑から水色の初心者から中級者の間の層が狩られそうね
2023/02/04(土) 00:15:56.94ID:5HHfxRG3M
「終盤は難しくない＝普段のABCと一緒」って意味だと仮定すると、中盤がARCで後ろはマニアック高度典型という、ただの昔の企業コンARCなんだよな
だったらU2800 ratedでもよくね？って思ってるけど、そこまですると初心者層が萎縮して参加しないかもしれなくて怖いんだろうか
2023/02/04(土) 00:18:39.84ID:5HHfxRG3M
企業コンは参加者数も稼がなきゃいけなくて大変だなって話
2023/02/04(土) 01:50:55.48ID:XT9wb8Pda
早解き苦手緑なんで明日は棄権しますわ
2023/02/04(土) 02:37:15.31ID:11TJ16Po0
ライバルを減らそうと必死で草生える
2023/02/04(土) 04:02:38.09ID:VlutLTNz0
高度な情報戦
2023/02/04(土) 20:49:46.88ID:DuPn66LGM
ちょくだい先生結婚マウントやめてください
2023/02/04(土) 21:45:26.38ID:qwiiBCAF0
週1回コンテスト前の30分～1時間だけ過去問題Bを1～2問解いて本番するだけにしてから苦行ストレスがほとんどなくなりました
今日はC初見問題だけど自力で考えて30分台でC解けたので満足

C問題最速で45秒でACとかテンプレ用意しててコピペレベルなのでしょうか？
Dなんて一応毎回問題だけはチラ見するけど何やったって自力で解法思いつかないから
もう開き直って毎回Cまで解いていつか茶色に成れればいいや
2023/02/04(土) 22:20:10.55ID:5scjLUe90
コンテスト中は順位表から読み取れる内容以外は他言に無用らしいから掲示板にはあんまり書かないほうがいいぞ
2023/02/04(土) 22:40:34.13ID:qwiiBCAF0
D嘘解法ぽいけど閃いたと思って暇つぶしに提出したらAC3TLE40WA3ってことはそこそこいい線行ってたぽい？
2023/02/04(土) 22:41:27.74ID:VlutLTNz0
ABCFの4完
やっぱりDに手を出さなきゃ良かった
2023/02/04(土) 22:43:35.14ID:YxTB5YYsp
キーエンスの再来だった
494デフォルトの名無しさん (ﾜｯﾁｮｲ 3f10-4O5A)
垢版 |
2023/02/04(土) 22:50:22.13ID:l8ebE2EL0
あと少しで国内200位入れなかった
層が厚すぎる
2023/02/04(土) 22:51:01.60ID:ZgVy8P1Na
>>491
問題外
496デフォルトの名無しさん (ｱｳｱｳｳｰ Sa93-/68i)
垢版 |
2023/02/04(土) 22:58:09.16ID:mQgt/9sra
>>489
ヒントになった途端通報されるかもしれないので注意
今回の場合、試験中に「Dが難しい」と叫んでいると取られかねない
497デフォルトの名無しさん (ﾜｯﾁｮｲ ffe2-Cjv8)
垢版 |
2023/02/04(土) 22:59:01.54ID:/q0XctAl0
なんでこれをDの位置におこうとおもったんだ
2023/02/04(土) 23:04:37.21ID:6AvE22Ut0
400点以上だと体感Fが一番簡単だったな
2023/02/04(土) 23:05:57.02ID:6AvE22Ut0
>>489
コンテスト中にSNSとか5chにコンテストのこと書き込むのは真面目にやめた方がいいよ
2023/02/04(土) 23:11:58.81ID:qwiiBCAF0
D問題で区間総和÷K=0で閃いたと思ったけど条件が足りなかったみたい
501デフォルトの名無しさん (ﾜｯﾁｮｲ cf01-EJkl)
垢版 |
2023/02/04(土) 23:14:05.17ID:366SNyz60
C問題で当たり前のようにunion findとかが出てきてビビった
勉強せんとなあ
2023/02/04(土) 23:15:42.29ID:qwiiBCAF0
解説見たらやっぱり何やってもこんなのコンテスト中に解けないやってなりますわ
おとなしくCまでを確実に解く練習を毎週末するだけでいいや
2023/02/04(土) 23:17:46.82ID:qwiiBCAF0
先週もだけどC問題で出るグラフ問題はACLのDSUに慣れさせようとする作問者の意図を感じます
解説もACL使ったら軽いと露骨に明示されてたから多分普及させたいんだろうなと
2023/02/04(土) 23:20:09.21ID:qwiiBCAF0
もう来週の問題も作成済みでACL使うグラフ問題シリーズが来週も出そう
とか言ってると来週はグラフ出すのやめたりするかな
ここ見てる？
2023/02/04(土) 23:20:54.02ID:ZgVy8P1Na
そんな当たり前のことを得意げに言われても…
506デフォルトの名無しさん (ﾜｯﾁｮｲ ffe2-Cjv8)
垢版 |
2023/02/04(土) 23:26:03.10ID:/q0XctAl0
unionfind、初中級のアルゴリズムの本にのってない気がする、atcoder高度すぎ
2023/02/04(土) 23:26:58.45ID:qwiiBCAF0
参加回数が規定数に満たないってことなんですが
今回ABCまで解けてレート380点とパフォーマンス７40点で差が360点くらいあるんですが
規定回数超えたら茶色に成れますかね？
茶色に成れたらもう満足なんですが
2023/02/04(土) 23:41:16.52ID:qwiiBCAF0
C問題で下記のようなコードで提出してACだったのですが
解説と違ったのですが解法として合ってますか？

（事前にいつものACLのDSUで入力済みとして）

　sum = 0;
foreach (g, d.groups()) { sum += g.size() - 1; }
cout << M - sum;
2023/02/04(土) 23:53:19.75ID:IojJ2/cf0
あってる、もっというと以下でいい
auto g = uf.groups();
int ans = m - (n - g.size());
2023/02/04(土) 23:59:17.63ID:6AvE22Ut0
UnionFindは、中身の理解と計算量解析自体は簡単ではないかもしれないけど、ブラックボックス化して使う分にはとても単純だから、まずはそういうものだと思って把握しといて損はないよ
2023/02/05(日) 00:01:06.52ID:L8nGaYgK0
Gはゼータ変換メビウス変換の要領でやれると思ったけど毎回頭がこんがらがる
いつかのARC-Dでもこういうゼータ変換メビウス変換の変種が出てた気がするけど、そのときもきつかった
2023/02/05(日) 00:13:05.03ID:zXAayJwsM
Eを最初セグ木でmin取ろうとしたらTLEして致命傷で済んだ
2023/02/05(日) 00:16:42.68ID:+Je3j6OX0
>>509
ありがとうございます
また嘘解法だったかと不安でしたが安心出来ました

ただDは解説配信見てもさっぱりでした
2023/02/05(日) 13:32:12.10ID:E/3apluda
union find は「プログラミング・コンテスト・チャレンジブック、第2版、2012」に載っていたような？
2023/02/05(日) 14:39:10.64ID:BCHcg2ZAM
競プロ本じゃなくて一般的なアルゴリズム本には載ってなさそうではある
516デフォルトの名無しさん (ﾜｯﾁｮｲ 3f55-zLlH)
垢版 |
2023/02/05(日) 14:44:21.92ID:bw48TasH0
>>515
セジウィック＆ウエイン
CLRS
浅野孝夫
の本に書いてありました。
517デフォルトの名無しさん (ﾜｯﾁｮｲ 3f55-zLlH)
垢版 |
2023/02/05(日) 14:45:43.39ID:bw48TasH0
>>515
Kleinberg & Tardosの本にも書いてありました。
2023/02/05(日) 15:24:54.49ID:TzydnmM+M
ありがとう
よく考えたらクラスカル法をまともに実装すりゃセットで出てくるから普通の学術書でバンバン出てくるものか
すまん、適当なこと言ったわ
2023/02/05(日) 15:35:59.28ID:TzydnmM+M
昨日のEx見てるがそれぞれのパーツはそんなに難しくなくても、コンテスト中に詰めるのは相当な情報処理能力要るなこれ
最上位は既に知ってる部分が多いから思考をショートカットして解けてる（部分問題はKUPCで既出）のか、初見でも化け物みたいな処理能力があるから解けるのか
2023/02/05(日) 23:56:53.84ID:L8nGaYgK0
enumerative combinatoricsで式クソデカ数え上げの練習をしよう
2023/02/06(月) 14:57:07.46ID:tLnW5713M
ちょくだい暇空信者だったのか…
2023/02/06(月) 17:17:12.74ID:CC5umvVS0
信者では無くないか？
どっちについても炎上するから関わりたくない、が直接反応されたから返答はしたように見える
AtCoderユーザーは暇空寄りだから、どちらかと言うと暇空側の立場を取るのが正解だし
本当は無反応が最善のはずだから、リプ返した時点で暇空応援の気持ちはありそうだけどな
2023/02/06(月) 17:28:55.79ID:5KzQx2I0M
＞AtCoderユーザーは暇空寄り
そうなんだ…ショック
2023/02/06(月) 17:55:26.95ID:8VwvYIdS0
誰やねん
2023/02/06(月) 18:05:31.15ID:atEmb0ZA0
誰だよ(´・ω・`)
2023/02/06(月) 18:34:28.57ID:vCbzFpDWM
chokudai定期的にいらんことに首突っ込むよな
2023/02/06(月) 19:09:41.21ID:P7WNzTvaa
最近やたらとイキってる陰謀論界隈の教祖様だろ
中立っていうならリプ返さないでほしい
心底気持ち悪い
2023/02/06(月) 19:29:13.93ID:TL/Aw+TK0
なんでミュートじゃなくてブロックするんやろなぁ。SNSの使い方下手すぎん
2023/02/06(月) 19:30:02.45ID:TL/Aw+TK0
ブロックした理由を解説して死体蹴りしてるのも謎
2023/02/06(月) 19:31:39.97ID:mjq9iwD6M
暇空応援公言は普通にショックだわ
あの界隈を胡散臭いと思わない感覚は怖い
2023/02/06(月) 20:23:50.09ID:7jgjd4tm0
ブロックにしても暇にしても弁解必死過ぎて草
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。