競技プログラミング総合スレ 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/02/02(木) 11:48:18.09

>>459
え？w

2023/02/02(木) 11:53:17.19

>>454
流し読みしたけどこの記事クオリティ低いから鵜呑みにするのはちょっと早計かな
3x2と2x3とかいうクソ小さい行列で実験してなんの意味があんのかよくわからんかった

2023/02/02(木) 12:00:46.82

どこにUnityでC#動かしてる競技プログラミングサイトがあんだよ
「速さを気にする言語じゃないから」じゃないとか知ったかぶりはやめよな

2023/02/02(木) 12:02:39.09

>>462
それはそうだね、この記事だけじゃ微妙

でもまあ
"C# 多次元配列ジャグ配列速度"
とかでぐぐればいろんな検証結果出てくるし、いくつか見れば「多次元配列」は早いというわけじゃないのはなんとなくそれっぽいと思えるっしょ

2023/02/02(木) 12:05:07.71

C#は速さ気にしまくってるけど多次元配列は誰も使ってないし、あえて高速化するならSpan<T>で1次元扱いしたらいいから多次元配列は永遠に遅そう

2023/02/02(木) 12:06:06.09

自演きっついなこのスレ
なんだろう黄色を騙る茶色無職が常駐してんのかな

2023/02/02(木) 12:20:17.80

ワッチョイがｱｳｱｳｳｰSaで文体が単芝使いの奴ってD問題で間違いを指摘されて暴言吐いてかつ浮動小数点数の話でも自分の間違いを一向に認めなかった奴と同一人物っぽいんだけど、もうスレのテンプレにNG推奨として追加した方が良くない？
前まではこんな奴居なかったし

2023/02/02(木) 12:22:50.20

だから無理矢理移住させると治安悪くなるって言ったのに

2023/02/02(木) 12:25:52.15

端末使い分けてるか飛行機飛ばしてるっぽいんだけど、単芝使う+煽り文体+(今回の件でどっちが間違ってるかは置いといて)自分の間違いを絶対に認めようとしないって時点で同一人物なんだよなあ

2023/02/02(木) 12:31:31.89

明らかに煽ることが目的のやつがいると思ったら個別にNGすればいいと思ってて、スレとして誰かをパージするようなことはしなくていいと思うんだよな
技術的な話に全く関係のないことを連投するやつが現れたらちょっと考える必要はあるが、全然まだそういうレベルじゃないだろ？

2023/02/02(木) 12:38:11.53

議論になるなら良いんだけど、前例からもわかる通り間違ってることを堂々と発言した挙句に明白な根拠有りで誤りを指摘されても自分の誤りを認めず暴言を吐き始めるのが厄介だと思った
まあ今回の言い争いには直接絡んでないけどNGしとくわ

2023/02/02(木) 12:54:28.61

ハッシュおじさんと同じ臭い腐臭

2023/02/02(木) 13:14:43.01

また論破されるから追い出すってかっこ悪すぎない？w

2023/02/02(木) 13:21:22.74

前回で茶色になるようなレベルって自分で書き込んでるのにどこからそんな自信が湧いてくるのやら
それでいて寒色煽りしてるのも謎

2023/02/02(木) 13:55:09.74

論破されて自作自演で嘘の噂流すのかっこ悪すぎない？w

2023/02/02(木) 13:56:42.34

このスレ、発言から青～黄が5人くらいは確定で居るからなぁ
某レッドコーダーも見てるっぽいし、下手な煽りは返り討ちにあう

2023/02/02(木) 13:57:36.22

返り討ちにあって追い出そうとするのかっこ悪すぎない？w

2023/02/02(木) 19:49:43.06

くんerのほうが知能高そうなのヤバいやろ

2023/02/02(木) 20:12:24.50

こいつより頭悪いやつなんていないだろ

2023/02/03(金) 21:24:06.48

明日のABCはARCよりかあ
やっぱり企業コンオンサイト予選はARC-likeな問題で選抜したいという思想はありそうだね

2023/02/03(金) 22:01:20.08

中盤はいつもよりも難し目らしいからギリギリDが解けるかどうかみたいな層は明日厳しいかもね
キーエンスのD青EF黄程にはならないと思うけど

2023/02/03(金) 23:16:24.28

緑から水色の初心者から中級者の間の層が狩られそうね

2023/02/04(土) 00:15:56.94

「終盤は難しくない＝普段のABCと一緒」って意味だと仮定すると、中盤がARCで後ろはマニアック高度典型という、ただの昔の企業コンARCなんだよな
だったらU2800 ratedでもよくね？って思ってるけど、そこまですると初心者層が萎縮して参加しないかもしれなくて怖いんだろうか

2023/02/04(土) 00:18:39.84

企業コンは参加者数も稼がなきゃいけなくて大変だなって話

2023/02/04(土) 01:50:55.48

早解き苦手緑なんで明日は棄権しますわ

2023/02/04(土) 02:37:15.31

ライバルを減らそうと必死で草生える

2023/02/04(土) 04:02:38.09

高度な情報戦

2023/02/04(土) 20:49:46.88

ちょくだい先生結婚マウントやめてください

2023/02/04(土) 21:45:26.38

週1回コンテスト前の30分～1時間だけ過去問題Bを1～2問解いて本番するだけにしてから苦行ストレスがほとんどなくなりました
今日はC初見問題だけど自力で考えて30分台でC解けたので満足

C問題最速で45秒でACとかテンプレ用意しててコピペレベルなのでしょうか？
Dなんて一応毎回問題だけはチラ見するけど何やったって自力で解法思いつかないから
もう開き直って毎回Cまで解いていつか茶色に成れればいいや

2023/02/04(土) 22:20:10.55

コンテスト中は順位表から読み取れる内容以外は他言に無用らしいから掲示板にはあんまり書かないほうがいいぞ

2023/02/04(土) 22:40:34.13

D嘘解法ぽいけど閃いたと思って暇つぶしに提出したらAC3TLE40WA3ってことはそこそこいい線行ってたぽい？

2023/02/04(土) 22:41:27.74

ABCFの4完
やっぱりDに手を出さなきゃ良かった

2023/02/04(土) 22:43:35.14

キーエンスの再来だった

2023/02/04(土) 22:50:22.13

あと少しで国内200位入れなかった
層が厚すぎる

2023/02/04(土) 22:51:01.60

>>491
問題外

2023/02/04(土) 22:58:09.16

>>489
ヒントになった途端通報されるかもしれないので注意
今回の場合、試験中に「Dが難しい」と叫んでいると取られかねない

2023/02/04(土) 22:59:01.54

なんでこれをDの位置におこうとおもったんだ

2023/02/04(土) 23:04:37.21

400点以上だと体感Fが一番簡単だったな

2023/02/04(土) 23:05:57.02

>>489
コンテスト中にSNSとか5chにコンテストのこと書き込むのは真面目にやめた方がいいよ

2023/02/04(土) 23:11:58.81

D問題で区間総和÷K=0で閃いたと思ったけど条件が足りなかったみたい

2023/02/04(土) 23:14:05.17

C問題で当たり前のようにunion findとかが出てきてビビった
勉強せんとなあ

2023/02/04(土) 23:15:42.29

解説見たらやっぱり何やってもこんなのコンテスト中に解けないやってなりますわ
おとなしくCまでを確実に解く練習を毎週末するだけでいいや

2023/02/04(土) 23:17:46.82

先週もだけどC問題で出るグラフ問題はACLのDSUに慣れさせようとする作問者の意図を感じます
解説もACL使ったら軽いと露骨に明示されてたから多分普及させたいんだろうなと

2023/02/04(土) 23:20:09.21

もう来週の問題も作成済みでACL使うグラフ問題シリーズが来週も出そう
とか言ってると来週はグラフ出すのやめたりするかな
ここ見てる？

2023/02/04(土) 23:20:54.02

そんな当たり前のことを得意げに言われても…

2023/02/04(土) 23:26:03.10

unionfind、初中級のアルゴリズムの本にのってない気がする、atcoder高度すぎ

2023/02/04(土) 23:26:58.45

参加回数が規定数に満たないってことなんですが
今回ABCまで解けてレート380点とパフォーマンス７40点で差が360点くらいあるんですが
規定回数超えたら茶色に成れますかね？
茶色に成れたらもう満足なんですが

2023/02/04(土) 23:41:16.52

C問題で下記のようなコードで提出してACだったのですが
解説と違ったのですが解法として合ってますか？

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

　sum = 0;
foreach (g, d.groups()) { sum += g.size() - 1; }
cout << M - sum;

2023/02/04(土) 23:53:19.75

あってる、もっというと以下でいい
auto g = uf.groups();
int ans = m - (n - g.size());

2023/02/04(土) 23:59:17.63

UnionFindは、中身の理解と計算量解析自体は簡単ではないかもしれないけど、ブラックボックス化して使う分にはとても単純だから、まずはそういうものだと思って把握しといて損はないよ

2023/02/05(日) 00:01:06.52

Gはゼータ変換メビウス変換の要領でやれると思ったけど毎回頭がこんがらがる
いつかのARC-Dでもこういうゼータ変換メビウス変換の変種が出てた気がするけど、そのときもきつかった

2023/02/05(日) 00:13:05.03

Eを最初セグ木でmin取ろうとしたらTLEして致命傷で済んだ

2023/02/05(日) 00:16:42.68

>>509
ありがとうございます
また嘘解法だったかと不安でしたが安心出来ました

ただDは解説配信見てもさっぱりでした

2023/02/05(日) 13:32:12.10

union find は「プログラミング・コンテスト・チャレンジブック、第2版、2012」に載っていたような？

2023/02/05(日) 14:39:10.64

競プロ本じゃなくて一般的なアルゴリズム本には載ってなさそうではある

2023/02/05(日) 14:44:21.92

>>515
セジウィック＆ウエイン
CLRS
浅野孝夫
の本に書いてありました。

2023/02/05(日) 14:45:43.39

>>515
Kleinberg & Tardosの本にも書いてありました。

2023/02/05(日) 15:24:54.49

ありがとう
よく考えたらクラスカル法をまともに実装すりゃセットで出てくるから普通の学術書でバンバン出てくるものか
すまん、適当なこと言ったわ

2023/02/05(日) 15:35:59.28

昨日のEx見てるがそれぞれのパーツはそんなに難しくなくても、コンテスト中に詰めるのは相当な情報処理能力要るなこれ
最上位は既に知ってる部分が多いから思考をショートカットして解けてる（部分問題はKUPCで既出）のか、初見でも化け物みたいな処理能力があるから解けるのか

2023/02/05(日) 23:56:53.84

enumerative combinatoricsで式クソデカ数え上げの練習をしよう

2023/02/06(月) 14:57:07.46

ちょくだい暇空信者だったのか…

2023/02/06(月) 17:17:12.74

信者では無くないか？
どっちについても炎上するから関わりたくない、が直接反応されたから返答はしたように見える
AtCoderユーザーは暇空寄りだから、どちらかと言うと暇空側の立場を取るのが正解だし
本当は無反応が最善のはずだから、リプ返した時点で暇空応援の気持ちはありそうだけどな

2023/02/06(月) 17:28:55.79

＞AtCoderユーザーは暇空寄り
そうなんだ…ショック

2023/02/06(月) 17:55:26.95

誰やねん

2023/02/06(月) 18:05:31.15

誰だよ(´・ω・`)

2023/02/06(月) 18:34:28.57

chokudai定期的にいらんことに首突っ込むよな

2023/02/06(月) 19:09:41.21

最近やたらとイキってる陰謀論界隈の教祖様だろ
中立っていうならリプ返さないでほしい
心底気持ち悪い

2023/02/06(月) 19:29:13.93

なんでミュートじゃなくてブロックするんやろなぁ。SNSの使い方下手すぎん

2023/02/06(月) 19:30:02.45

ブロックした理由を解説して死体蹴りしてるのも謎

2023/02/06(月) 19:31:39.97

暇空応援公言は普通にショックだわ
あの界隈を胡散臭いと思わない感覚は怖い

2023/02/06(月) 20:23:50.09

ブロックにしても暇にしても弁解必死過ぎて草

2023/02/07(火) 12:48:26.37

ABC232E Rook Pathなんだけど、
解説だと、ゴール(x2,y2)の位置で場合分けしてるんだけど、
スタートとの位置関係で分かれるんじゃないの？
シミュレーションしてみたらそんな挙動。

計算は同じになるんだろうけど

2023/02/07(火) 13:08:37.18

↓上級編がでますね。

アルゴリズム実技検定　公式テキスト［上級～エキスパート編］
中村謙弘、ｔｓｕｔａｊ

2023/02/07(火) 13:38:15.54

>>532
値が同じところで分けるとそうだけど、
多分解説は値が同じところで分けてるわけじゃなくて答えが計算しやすいように分割してるだけ
（集合内のfの和でgを定義してる）

このあたり確かに文章の流れがミスリーディングだね

2023/02/08(水) 19:11:20.77

公金の使われ方とか言って暇空は応援するのに
五輪談合で逮捕者出てる電通から金貰ってるのはいいの？
私女だけど男の人のダブスタ悲しい

2023/02/09(木) 18:50:48.66

ロシアと強いつながりがある競技プログラミングコミュニティ

2023/02/09(木) 21:38:31.53

ロシア批判に消極的に見えるのは
男子校理系的なキモさの極地って感じ

2023/02/09(木) 23:54:08.08

>>535
今ホットなのは暇空の方だしなぁ
話題性のある方に言及するのは普通でしょ？

2023/02/10(金) 07:46:52.03

競プロに関係しそうなq-類似の中国語記事
https://zhuanlan.zhihu.com/p/202494934
https://www.cnblogs.com/amagaisite/p/16475758.html

2023/02/10(金) 12:38:57.68

アルゴリズム実技検定　公式テキスト［上級～エキスパート編］
中村謙弘、ｔｓｕｔａｊ

↑予約注文しました。

2023/02/10(金) 15:45:03.21

q類似って情報量増やすシリーズですか？

2023/02/10(金) 18:12:43.91

情報量増やすシリーズって何

2023/02/10(金) 21:35:37.67

https://codeforces.com/gym/102978/problem/A
なんか、こういう総数は簡単なんだけどもうちょい細分化したものを数えたいときに新しい変数とかを導入するテクニック的な

2023/02/11(土) 00:45:13.40

まあ情報増やす感じよね
自然数の代わりに、[n]_q = 1+q+...+q^(n-1)というqの多項式を考えみる
そうすると普段の数え上げで出てくる概念についてもq-類似というものを考えることができて、q-類似はオリジナルより細かい情報を持っている
例えば普通の階乗は順列の数え上げだけど、そのq-類似であるq-階乗[k]_q! = [k]_q [k-1]_q ... [1]_qは、r次の係数が転倒数rの順列の数え上げになっている
どうしてそうなるかは挿入DPの要領だね
1を代入する、つまり係数の総和を取ればオリジナルの階乗を復元できもする

2023/02/11(土) 00:45:52.02

さらにq-二項係数というのもあって、binom(n, k)_q = [n]_q/([k]_q [n-k]_q)なんだけど、r次の係数が、r個の区別できない球をk個の区別できない箱に分ける（箱の容量は最大n-k個の球を収容可能）場合の数になってる
同じ意味だけど「grid上のpathで区切る領域の面積がrのpathの場合の数」の方が直感的にわかりやすいかな
https://scholarship.claremont.edu/cgi/viewcontent.cgi?article=1194&context=hmc_theses
すぐに役に立つ概念かわからないけど、数え上げの精密化と考えると面白い

2023/02/11(土) 00:47:23.46

>>545
訂正：path→lattice path

2023/02/11(土) 00:49:35.69

>>543
とかいろいろ書いておきながら普通にこれ俺にとって難しくて解答読んでも自信ない
まずVを無視した数の割り振りが、境界線の数え上げに対応してて、それぞれの境界線を適宜微妙にずらすことで非交差路の数え上げに帰着してLGV公式で解ける
さらにLGV公式で使う行列の各要素（すなわちある始点からある終点への行き方の数え上げ）を改造して、ある点pより右下を通過することが確定するところを通ったらx倍、点p自体を通ったら0倍みたいなルールでxの一次式を作り、Lagrange補間の要領で行列式の多項式を計算してV次の係数が答え的な感じ？
比較的典型性の高い数え上げを多項式で細かく分けて、係数から欲しい情報取り出すというのはまさにって感じに見える

2023/02/11(土) 17:12:01.33

どちらかというと、q-二項係数がFq上n次元ベクトル空間からk次元部分空間を選ぶときの数え上げになってるって話の方で存在を認識してたな
係数を見るというより、何かを代入して情報を取り出すタイプ

2023/02/11(土) 17:15:03.20

実装には詳しくないが、(1-q^n)/(1-q)みたいな疎な多項式の除算にできることを利用して高速化できる感じなのか？

2023/02/11(土) 19:05:11.90

q-二項係数を分割の数え上げで解釈する話も部分ベクトル空間の数え上げで解釈する話も証明見たら見たらせやな感あるが、この2つのどこがどう対応づいているのかあんまよくわからんな

**デフォルトの名無しさん** (JP 0H57-lJcr) · 2023/02/11(土) 19:35:59.54

またAGCやばそうな配点だ
endagorionってどんな問題出すんだ？

2023/02/11(土) 20:31:02.43

C++17が多数派だと思うのですが
C++20が未だに対応されない理由って何なのでしょうか？

本業が忙しすぎてそこまで手が回らないとか？
費用対効果が低くて恩恵を得られる人が少ないとか？
過去問まで対応させるとなると多すぎて単純に面倒だからとか？

上記全部当てはまりそうだから仕方ないか・・・

2023/02/11(土) 20:50:07.00

>>552
AtCoderなら、近いうちに言語アップデートが入るからそこで追加されるのでは？

2023/02/11(土) 20:59:47.47

>>553
そうなんですか？
知らなかったです
ありがとうございます

もしよろしければ言語アップデートのソース元ってありますか？

2023/02/11(土) 22:41:03.83

Bは面倒そうなので飛ばしてC
解法はすぐに思いついて実装に手間取って30分で提出したが
1つだけREになるコーナーケース？が分からずに時間切れ

残り15分くらいで一瞬Bやりかけたけて問題見たけど
CのREが分からないイライラを引きずって萎えたやる気出ないので
順位表見てたけどやっぱ今回のBCは難易度高かったぽい？

毎回こんなの1分2分で解いてる人いるけど
どんだけテンプレ用意してるんだろう

最速AC時間からすると自分のテンプレから探してコピペする時間としか思えない

2023/02/11(土) 22:42:57.96

Eまで脳死で解いていく問題セットでしたね(´・ω・`)

2023/02/11(土) 22:45:13.25

Convex hull trickEDPCで調べたばかりだったのに存在を忘れてた

2023/02/11(土) 22:46:55.58

5完でまったり

2023/02/11(土) 22:49:04.63

Fえらく簡単だなと思って実装してみたら想定の数倍厄介な問題だったな

2023/02/11(土) 22:50:22.19

>>555
基本的にはみんな普通に問題文読んでコード書いてるだけだ

極まってる赤色のひとだとこれぐらいの考察速度でコードを書く
（まあ、このひとに限っては更にコードゴルフもしてるからかなり変態っぽいけど）
https://www.youtube.com/watch?v=su1QrfVkZK4