競技プログラミング総合スレ 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/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

2023/02/11(土) 22:53:21.26

>>560
A問題ならまだ見て書くで分かる気がしますが
B,C問題をコピペじゃなくて1分,2分台で読んで書いてACって既に人間と思えないんですけど
上位様方達は凄いんですね

2023/02/11(土) 22:53:39.17

Bは読解めんどくさいけど、レ点の存在を知ってればだいぶ思考節約できるし、ある程度上級者ならソラで書いても1, 2分で解けるんじゃないか

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

C問題でACが28/29でREが1つだけ残ってて分からないのですが
コードのどこがおかしいか分かりますか？
テストケースが公開されていないので思いつかなくて・・・

自作関数などは省略してます
https://i.gyazo.com/58576b7851ef6038272e7cb78af48707.png
https://i.gyazo.com/e14f6e1124bfff6c2f117f807dbff63b.png

2023/02/11(土) 23:05:29.61

今回のGみたいな出現頻度低めの高度典型忘れた頃に出題されるから中々身に付かない

2023/02/11(土) 23:06:39.24

>>563
あたま

2023/02/11(土) 23:07:40.96

Exは除原理で立式して母関数使って整理するときれいな除算になるのか
Exは結構な数の問題がFPS講座になっている気がする

2023/02/11(土) 23:08:45.56

Bってグラフの説明いるの？
あれをまじめに読んじゃったせいで時間無駄にした

2023/02/11(土) 23:11:50.37

厳密に書くにはあれが一番なのかもしれないが、それはそれとして、やる操作に対して記述量が多すぎて驚く

2023/02/11(土) 23:13:14.69

>>565
ありがとうございます
ヒントが冒頭って意味でしょうか？
ヒントじゃなくて頭が悪いってことならそのとおりなので異論はありません

2023/02/11(土) 23:17:15.33

>>563
vectorの宣言だけどvst(N)じゃなくてvst(M)にすべきなんじゃないか
逆にRE1個で済むんだな

2023/02/11(土) 23:18:47.90

>>570
＞＞あたま
のヒントで気づいて
それでACなりました

2023/02/11(土) 23:21:04.95

Fが黄色。Fが青色上になったらノーカンにすべき。

2023/02/11(土) 23:22:15.58

思い込みと言うかこんな些細なミスに気づかずに1時間半も悩んでてて1完でメンタル壊れますね
REが解決できなくてドツボにハマる典型だと思いますが
すぐにBに着手してればもしかしたら解けてたかと思うと残念です
今日はBを今から解いてみて寝ます

**デフォルトの名無しさん** (JP 0H57-AGaU) · 2023/02/11(土) 23:25:03.24

確かにF青、G黄ぐらいが理想ではあるけど、一色上振れぐらいはいいんじゃないかな
FもGも難問って感じはしなかったけどやっぱりあの場合分けはキツいのかな

2023/02/11(土) 23:34:21.84

来週またTOYOTAだからABCの難度壊されるのか
オンサイトの枠なんかARCで好きに争っといてくれ

2023/02/11(土) 23:43:36.37

昔の企業コンARCの問題と比較すると普通にトヨタはARCでいい気がするんだよな

2023/02/11(土) 23:54:48.28

>>573
無事B問題30分ぐらいで解けました
予想通りACLのDSU使えました
3回連続は無いだろうと思ってたのに
やっぱこっち先にやればよかったトホホ

2023/02/12(日) 00:15:48.81

AGCの配点5-8-8ってA問題から青～黄色の激重セットになりそうだな

2023/02/12(日) 00:20:22.77

>>554
AtCoderの言語アップデートに関して 2023年版
https://atcoder.jp/posts/966
です　アップデート自体がいつになるかはわかりません…

2023/02/12(日) 00:22:33.59

>>579
ありがとうございます
丁度今さらっとシート見終わってここに戻って来たとこでした

2023/02/12(日) 00:24:27.27

アプデ前後にC++20で使える便利情報などが出回りそう

2023/02/12(日) 01:22:02.99

>>549
そうだね、1-q^nは性質がよくてありがたい
たとえばq-二項係数なんかはbinom(n,r)_q = Π_{i=1}^{r} ((1-q^(n-i))/(1-q^i))と表せてlogを取ると

log binom(n,r)_q = Σ_{i=1}^{r} log (1-q^(n-i)) - Σ_{i=1}^{r} log (1-q^i)

なわけだけど、log (1-q^i) =　- Σ_{k=1} q^ik / k（ここで疎であることが効く）を利用し、
log binom(n,r)_qをN次まで求めるのならばO(NlogN)で求められる（調和級数）
binom(n,r)_q = exp(log binom(n,r)_q)もexp取る操作がNewton法でO(NlogN)でできて、最終的にはO(NlogN)

2023/02/12(日) 01:30:42.49

(1-q^n)/(1-q)で定義されたq-数の積で表されるようなものならこの方針でほぼ対応できるんじゃないかな

2023/02/12(日) 01:40:39.16

>>581
https://qiita.com/Chippppp/items/620d2e5229f5c7e93f0c
もうまとめてくれてる人いるね
競プロでよくお世話になりそうなのはnumbers,bit,autoあたりかなの印象

2023/02/12(日) 09:16:26.52

言語アプデでGoとか相当良くなるんじゃないかな
Generics使えるようになるし

2023/02/12(日) 14:42:18.02

これもq-二項係数の言葉で説明できたりしますかね？

https://yukicoder.me/problems/no/986

2023/02/12(日) 14:54:27.27

例のQiita記事覗いたけど20代の主婦ってワードでちょっとびっくりしちゃった周りにそういう生き方してる人いないので

2023/02/12(日) 17:03:52.39

>>586
最後のはもろにq=2のq-二項係数だね
Π_{i=0}^{N-1} (2^M-2^i)/Π_{i=0}^{N-1} (2^N-2^i)
= Π_{i=1}^{N} (1-2^(M-i+1))/(1-2^i)
= binom(M, N)_2
丁度>>548に書いてある話かな、q=2以外のF_qでも同じような議論ができる
問題の誘導がお手本のようなq-二項係数の導出方法になっていると思う

あとすまん、>>582は指数ミスってるね、 Π_{i=1}^{r} ((1-q^(n-i+1))/(1-q^i))が正しい

2023/02/12(日) 18:43:07.51

>>584
それ見てatcoderはC++20対応まだなのかなって思ったんですよね
以前C++やる前にpython触ってたのでrangeなどの配列操作に慣れてたので
なんでC++こんな面倒なんだろうって思ってました
自分はC++20のrangeが便利そうだなって思ってます
テンプレで自作関数用意しちゃえばなんでも大差ないんでしょうけど
やっぱSTLや標準機能で動いてるって安心ですよね

2023/02/12(日) 23:32:43.82

今日のwriterロシアの人みたいだけどなんでatcoderでの出題なのかな

2023/02/13(月) 00:05:27.27

実験したらパスカルの三角形が出てきたから色々調べて何とかlucasの定理まで辿り着けたんだけどこれA問題で知識として要求されるレベルなのか

2023/02/13(月) 01:21:21.02

Lucasって言うと大袈裟に聞こえるけど再帰的な構造を見つけてくださいねってだけじゃね？

2023/02/13(月) 01:24:37.51

>>589
競プロだとコード長制限の観点からも嬉しいですね
テンプレもりもり書いてると結構すぐ超えちゃうので

2023/02/13(月) 21:58:26.16

>>590
海外でも難問と言えばAGCという評判だから、難しいセットをAGCに投稿しようと思う外国人はいると思う

2023/02/13(月) 22:36:59.14

普通にtourist AGCとかあるしな

2023/02/13(月) 22:49:24.44

こういう人を見ると凄く勿体無く感じる
何故、中卒なのかは分からないけど1年ちょいで青コーダーになれるだけの地頭があるなら、勉強をすれば東大や京大にだって余裕で受かるだろうに

【AtCoder】中卒の主婦が青コーダーになったおはなし【競技プログラミング】
https://qiita.com/mayocorn/items/4edff486428240864808

2023/02/14(火) 00:21:59.23

主婦に東大目指せと？

2023/02/14(火) 01:29:58.32

どういう学歴を辿るかは本人の自由だろうし、余計なお世話ではないか

2023/02/14(火) 01:32:50.93

>>588
あーこれだこれ
俺が知ったのはABCのEx問題かなんかだったが、解説でこのゆきこの問題と同じような感じで導出してた覚え

2023/02/14(火) 01:46:29.47

>>598
本当これに尽きる

2023/02/14(火) 02:20:57.01

東大生が～とか中卒が～とか何を話すにもわざわざ学歴を書いてイキらなきゃいいだけだぞ

2023/02/16(木) 01:26:12.31

ガチのフルコミットする奴(子なし主婦やニート)が増えれば青＝東大の相場は崩れる気がする

まあ子供育てる予定があって自分が東大レベルの学力を狙える根拠が1つでもあるならとりあえずやってみる、というのは子育て戦略として面白いし普通に優良

2023/02/16(木) 08:10:30.22

青=東大なんて言ってるの学歴厨しかおらんよ
マ板のゴミみたいな文化をこっちに持ち込むな

2023/02/16(木) 10:41:54.29

青って蔑称だろ

2023/02/16(木) 21:15:09.06

凄いのは凄いって言えばいいのに他所から「勿体ない」って言うのは傲慢よ

2023/02/17(金) 06:48:56.83

ABCの3完が精一杯でBやCが解けないこともたまにある灰色なのですが
ARCって参加して0完でもパフォ少し出ることあるから参加したほうが良いって本当ですか？

ARCのAすら解けないから毎回参加してなかったのですが
なんかスコア稼ぎみたいでズルっぽいので躊躇するけど
もし本当なら0完参加もありかも？

2023/02/17(金) 12:37:56.14

何もせず稼げるとしてそれが嬉しいなら自分でやってみたらいんじゃね

2023/02/17(金) 14:06:14.64

某所で見かけた問題（どこの問題かは規約の関係で言えない）なんだけど、いくら考えてもわかんなかったから誰か教えてほすぃ

N 個の正整数 L_1 ～ L_N が与えられる。ここで以下の二つの「操作」から好きな方を選ぶことを繰り返す。

・L の要素を任意に一つ選び、X 減らす。
・L の要素を任意に Y 個選び、それぞれ 1 減らす。

L の全ての要素を 0 以下にするには最低何回の操作が必要か？

1 <= N <= 100000
1 <= L_i <= 100000
1 <= X <= 100000
1 <= Y <= N
（制約条件はこれであってるはずだけどもし記憶違いだったらゴメン）

2023/02/17(金) 14:19:41.06

出展不明の問題には解答してはいけません
不正に荷担することになるかもしれません

2023/02/17(金) 14:22:27.12

それがどこの問題か知ってるけどその問題を公開することは許されてるわけ？許されててもダメだと思うけど

2023/02/17(金) 14:26:54.61

マジか、伏せとけば大丈夫かと思ったわ
じゃあ諦めるわ

2023/02/17(金) 15:36:51.10

かなりムズい気がするな
このスレではどのみち解けなさそう

2023/02/17(金) 16:40:00.47

や、俺は解けたけどな！

2023/02/17(金) 17:24:12.44

そんなに難しくはないけど、確かに解答したくはないな……
自力で頑張ってくれ

2023/02/17(金) 17:36:44.85

簡単すぎて草

2023/02/17(金) 20:35:59.16

マジでこれが難しいって言ってるのか？
茶色？

2023/02/17(金) 20:39:57.57

diff1600くらいはあると思う

2023/02/18(土) 03:39:57.25

Lは昇順にソート済みとする
まず後者の操作だけ考えるとmax(L_N,ceil((L_1+...+L_N)/Y))が下界で実は達成可能（この値は1回の操作で必ず1以上減らせる）
となると前者の操作は値の大きい方からやるべきで前者の操作回数を全探索することにすると二乗logにはなるがこの先がわからん

2023/02/18(土) 06:27:43.34

難しいじゃん黄Diff以上はありそう

2023/02/18(土) 12:46:27.04

>>618
シミュレーションの際に同じ値はまとめれば毎回最大値が1以上減るからステップ数抑えられるか
その間の算数はk個に操作するとして
k+max(m,ceil((s-x*k)/Y))
という式の最小化
面倒だから雰囲気だけだけど多分最小と最大とmaxの中身が丁度等しくなるとこくらいを調べれば十分なはず

2023/02/18(土) 14:52:45.65

ドヤりたいのわかったからヒント出すな

2023/02/18(土) 18:29:18.45

>>606
レーティングって長期的推移でみるものだから高々1個実力外で稼げたものは所詮あぶく銭にすぎないしパフォ目的ならオススメはしないかな
チャレンジしたい！って心意気ならすご～くいいと思います

2023/02/18(土) 20:05:46.57

>>622
ARC過去問覗いて見てそっ閉じしました
問題文や解説すらさっぱり理解出来ないので
せめてA問題が理解出来るくらいまでは参加は諦めます

2023/02/18(土) 20:35:51.39

誤爆見たぞ

2023/02/18(土) 23:19:15.25

Cまではとっつきやすかったね
chineristさんの回だからまた相当な難問が来るかと恐れていたけど

2023/02/18(土) 23:24:56.87

B問題は実家DP的ななにかを予想して遷移考えたけど、思ったより普通の算数で解けたな
Cは制約がゆるすぎて逆に解きにくかった
こんなこと言うと競プロに過学習してるっぽくてよくないんだが

2023/02/18(土) 23:35:35.53

Cの制約ってジャッジの都合なんかね

2023/02/19(日) 00:05:31.17

>>624
見たぞ2
少なくとも3人factorioスレ見てるやつが居るな

2023/02/19(日) 06:03:20.76

寝起きでARCのA問題見たらちょっと閃いた気がしたので
20分くらいですぐにサンプルACしたので提出したら見事にWAでしたｗ

流石にARCだからコーナーケースが仕込まれてるとは思いましたが
考えても何も思いつかないのですぐに解説見たけど理解するのに1時間くらい掛かりました
多分本番やってたらWAにドはまりしてストレスでメンタル壊れてたと思うので
精神衛生的に不参加で良かったです

最速提出で2分台の方のコード2つ見ましたが
まるでコーナーケースを知ってるかのようなコードでしたね

問題を読んでコーナーケースまで把握したコードを2分台で提出してACするってことは
典型問題として類題知ってるってことでしょうか？
本当に初見で直感で2分台なら凄すぎます

でも5分以内ACも20人くらいいるからわかる人には分かるのかな

2023/02/19(日) 12:49:58.63

類題知ってるとかではないと思うよ

2023/02/19(日) 13:34:36.91

2分はともかく、30分かけて良いなら解けなきゃダメだと思うよ
長さ15くらいまでのテストケース全生成は幅優先探索やるだけABC-Cくらいの難易度なので、これを作って手元で確かめれば条件なんて自明