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

2021/07/28(水) 21:58:48.02

!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/

※前スレ
競技プログラミングにハマるプログラマのスレ 62
https://medaka.5ch.net/test/read.cgi/prog/1626625368/

VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

2021/08/15(日) 00:01:22.59

って思ったんだけど ARC121E で橙あるのか、じゃあ橙行きそうだ

2021/08/15(日) 00:27:24.96

時間足りなくてコンテスト中に見れなかったけど、GよりHのほうが簡単に感じた

2021/08/15(日) 01:11:14.80

問題見たけどまさに負辺対応mincostflowを実装できますか？という感じだ

2021/08/15(日) 03:22:13.67

>>193
そういうCSっぽいのを出すと受験を控えた電通のご子息の負担になってしまうんよ

2021/08/15(日) 03:25:58.48

>>205
新ABCで3回は出てるし、皮肉が成立してなくないか

2021/08/15(日) 03:52:35.22

Eは典型とかFは典型とかいう意見を見たけどほんとに典型なん？あれをはい典型だねと思って解けるようになる未来が見えないんだけど

2021/08/15(日) 04:50:36.43

Fはけんちゃんのそのまんまの記事があるから流石にね

2021/08/15(日) 14:08:24.22

プログラミング初心者にアルゴ式勧めてる人ちょくちょく見るけど
AOJ の ITP とかのほうが良くないか？

**デフォルトの名無しさん** (JP 0H42-pBez) · 2021/08/15(日) 14:54:37.55

Eは確かにありがちな貪欲っぽく見えるけど、典型だとしたらどんな名前がついてるのか気になるな

2021/08/15(日) 14:59:39.05

区間スケジューリング問題の類題じゃないの

2021/08/15(日) 16:06:46.79

>>211
お前すげえな。なるほど。

2021/08/15(日) 23:30:31.95

コドフォでます

2021/08/16(月) 07:46:06.39

Twitterと勘違いしてんちゃうぞ

2021/08/16(月) 12:41:38.02

チー牛なう

2021/08/16(月) 14:43:02.04

先週のDってKruscalとPrimのアルゴリズムを実装したことある人なら簡単だったのかな
緑だと厳しくて水の人らはそこそこ解けてるからこの辺り知識差がでたのか

2021/08/16(月) 14:46:05.39

マトロイドってやっといた方が良いの？

2021/08/16(月) 15:42:21.88

マトロイドは勉強したけど青黄往復レベルの自分だと直接的にそこまで役に立ったことはまだないかな
クラスカル法の一般化として理論は面白い、電気通信大の資料で勉強した
問題に出てくる対象がマトロイドになってるとわかると直感的に明らかでない場合も貪欲でできるとわかって嬉しい
けどそもそもマトロイドであることを初見で見抜いて示すのがそこまで簡単じゃない
自分の認識はこんなもんだけど橙以上の上位陣がよく話してるマトロイド交差みたいな上位典型もあって、自分が把握してない活用法がまだまだありそう

2021/08/16(月) 15:51:57.71

あとこの前のABC-Dではあまり最小全域木アルゴは意識したつもりはなかったけど、辺を段々追加して動的に管理するみたいな発想は確かにそのあたりのアルゴの影響で思い付けた可能性はあるかも
どちらかというと主客転倒がメインで、辺が寄与できる範囲の木を作ろうという気持ちだった

2021/08/16(月) 16:22:44.46

辺の寄与考えると小さい順にやるのがよさそうで、これクラスカル法じゃんとはなったな
俺はどっちかというとABC120-Dのお陰で思いつけたかな

2021/08/16(月) 18:21:55.66

>>216
ちょうど水色でなんとかそれ解けた、ってレベルだけど、
似たようなアイデアを断片的につかう問題をいくつもやってたからたまたま解けたって感じ。
やっぱ解きまくって典型解法に習熟するのが重要なんじゃない？
初等レベルの算数でも足し算、掛け算、割り算の筆算は練習しまくらないと慣れないし。

ちなみにクラスカルは楽勝に実装できるけど、プリムのやり方忘れたやべえ。マトロイドはなんのことだか知らんがな、って知識量。

2021/08/16(月) 23:12:02.22

それはunion-findがあるからですかね？

2021/08/17(火) 00:29:52.66

せやな。UnionFind覚えとけば簡単やろ

2021/08/17(火) 20:29:41.66

ウニオンフィンド(´・ω・｀)

2021/08/18(水) 23:33:39.30

こどふぉでます

2021/08/19(木) 01:51:19.53

div3なのにムズくないですか？

2021/08/19(木) 02:03:46.39

Eの後ろから見るアプローチ天才過ぎる
類題あったりします？
ゴールから考えるのに近いですかね

2021/08/19(木) 02:23:56.11

E は今日の div.3 の中では一番 adhoc 気味かもしれん
後ろから見るというより最後に付け足した文字列は何になるかというのを考えると自然かもしれん

2021/08/19(木) 02:58:40.08

ほどよい難易度だったね

2021/08/19(木) 11:00:23.69

ABC214-Dが茶色予想だったってchokudaiがあーだこーだーで言ってたね
・辺をコストでソートする
・Unionfindで管理する
って普通の人はクラスカル法を理解してないと着想難しいし、あれが茶色は流石にないでしょう

2021/08/19(木) 11:25:46.99

逆にクラスカル法理解してれば無だからなあ
どの知識が何色かなんてこの漢字は何年生で習うでしょうってくらい難しいししょうもない

2021/08/19(木) 12:02:52.17

最小全域木やるだけが茶色くらいなイメージあるな

2021/08/19(木) 12:06:47.36

dpやるだけ

2021/08/19(木) 12:56:10.30

クルスカル法を想起させたいなら最初から木構造にすな

2021/08/19(木) 13:11:02.73

あれそんなにクラスカル法結び付く問題かなあ、実装方針が外形的に同じなだけで本質的な部分は別だと自分は感じたけど

2021/08/19(木) 13:19:00.82

クラスカル法とはあんまり関係ない気がする

2021/08/19(木) 13:20:11.00

おれもそう思うわ
たまたま実装方法がクラスカルっぽくなっただけと感じる

2021/08/19(木) 13:21:50.46

解いてるときも、別にクラスカルのことは連想しなかったけど、解けたし。

2021/08/19(木) 15:55:26.69

考察全部終わってからクラスカルだなとはなったけど最初からクラスカルは違う気がする

2021/08/19(木) 17:06:54.35

最小全域木やるだけは水色くらいありそうな気がするが…
ufやるだけが茶～緑くらいのイメージ

2021/08/19(木) 19:38:17.56

一昔前ならUF使えて茶色なんてこと絶対なかったと思うんだけど、厳しすぎない？

2021/08/19(木) 20:03:19.71

知識問のdiffはこれからも下がっていきそう
昔より初級者はちゃんと勉強しないとレートが上がらないゲームになってるとは思う

2021/08/19(木) 20:39:43.61

クラスカルとは全く違う

クラスカルは最小の和が欲しいから、小さい方から貪欲に見ていくのであって、今回のは各辺の寄与をみるのに小さい方からみるとうまくいくというだけ

アルゴリズムが本質として違いすぎる

2021/08/20(金) 17:51:46.53

クラスカルとは違うけど枝を小さい順から見ていってunionするとか、プリムとは違うけど頂点集合のカットから最小の枝を選ぶとかの考え方を1度やっておくと
別の問題に帰着できそうね

2021/08/21(土) 00:34:03.74

今月ARC一回だけか。。

2021/08/21(土) 15:45:30.51

今日のFGHなにが出るだろうか
幾何系がそろそろ出てもおかしくないよね

2021/08/21(土) 16:31:30.90

CHT使うdpとか

2021/08/21(土) 22:10:18.81

Rustのメモリ安全性はボローチェッカーによって担保されているが、
Nimと比較してRustはタイプ量が多い事により限りなく低い生産性と
C++のような高い難読性、超巨大なバイナリ生成性能を兼ね備えています

Nimはバージョン1.5.1でRustのボローチェッカーに似た「View types」が実装されれば、
GC無しのView typesで参照の有効性を検証することによってメモリ安全性を保証しつつ
限りなく抑え込まれたタイプ量で高速化したCのソースコードを吐き出せます

Nimソースコード ==nimコンパイラ==> Cソースコード ==Cコンパイラ==> バイナリ

なので、nimコンパイラが通った時点でメモリ安全性が担保されませんか？

Nimの実験的特徴
著者：アンドレアス・ルンプ
バージョン： 1.5.1
http://nim-lang.github.io/Nim/manual_experimental.html

Nimは限りなく抑え込まれたタイプ量で高い生産性とPythonのような高い可読性を実現し
ているにもかかわらず、高速なCのソースコードを吐き出せるのでC言語でリモートワーク
されている方は割り振られた仕事が早く終わっても終わってないふりをして怠けることができる

「怠け者とはこうあるべきだ！」と言うとても大事な事を Nim は我々に教えてくれます

2021/08/21(土) 22:55:31.25

今回は比較的調整がうまく行ってる方なのかな？
Gは困難というほどでもないし、Fもちょうどいい塩梅

2021/08/21(土) 23:08:27.09

今日のC問題、26^8の並べ替えは全探索は無理と思ってたけど、8^8の並べ替え考えればいいんだな。

2021/08/21(土) 23:22:14.02

原理を知ってると応用がきくって基本だけど大事よな
今回のD

2021/08/21(土) 23:32:07.02

noshiさんの言ってるTaylor shiftやっと理解した
f(x) = \sum_{n=0}^N c_n x^nとする
二項定理から
f(x+a) = \sum_{n=0}^N c_n (x+a)^n
= \sum_{i=0}^N (\sum_{n=i}^N a^{n-i} c_n \binom{n}{i}) x^i
これは二項係数をばらしてj=N-i, k=N-nとして
\sum_{j=0}^N x^j /(N-j)! \sum_{k=0}^j (a^{j-k}/(j-k)!)((N-k)! c_{N-k})
になる

この後ろの部分をよく見ると畳み込みになってて、
g(x) = \sum_{n=0}^{N} (a^i/i!) x^i
h(x) = \sum_{n=0}^{N} (N-i)! c_(N-i) x^i
の畳み込み(g*h)(x)のi次の項に1/(N-i)!倍すればいい
これでO(NlogN)でFPSの平行移動が計算可能

2021/08/21(土) 23:32:14.25

さすがにleetcodeは無理

2021/08/22(日) 02:42:21.05

>>252
FPSではなく、多項式かと。

2021/08/22(日) 04:57:26.20

何言ってるのかと思ったけど一般の FPS だと定数項を含む式は合成できないってことか

2021/08/22(日) 13:12:10.90

Rustのメモリ安全性はボローチェッカーによって担保されているが、
Nimと比較してRustはタイプ量が多い事により限りなく低い生産性と
C++のような高い難読性、超巨大なバイナリ生成性能を兼ね備えています

Nimはバージョン1.5.1でRustのボローチェッカーに似た「View types」が実装されれば、
GC無しのView typesで参照の有効性を検証することによってメモリ安全性を保証しつつ
限りなく抑え込まれたタイプ量で高速化したCのソースコードを吐き出せます

Nimソースコード ==nimコンパイラ==> Cソースコード ==Cコンパイラ==> バイナリ

なので、nimコンパイラが通った時点でメモリ安全性が担保されませんか？

Nimの実験的特徴バージョン1.5.1
http://nim-lang.github.io/Nim/manual_experimental.html

第二プログラミング言語として Rust はオススメしません Nim をやるのです
https://wolfbash.hateblo.jp/entry/2017/07/30/193412

Nimは限りなく抑え込まれたタイプ量で高い生産性とPythonのような高い可読性を実現し
ているにもかかわらず、高速なCのソースコードを吐き出せるのでC言語でリモートワーク
されている方は割り振られた仕事が早く終わっても終わってないふりをして怠けることができる

「怠け者とはこうあるべきだ！」と言うとても大事な事を Nim は我々に教えてくれます

**デフォルトの名無しさん** (JP 0H1f-zH/y) · 2021/08/22(日) 13:20:23.57

>>254
>>255
ありがとう
最初Nが有限じゃなきゃ意味のない式だから確かにFPSじゃなくて多項式において適用可能か程度の認識で読んだけど、そもそも根本的に定数項を含むFPSを他のFPSに代入しちゃダメなのか
恥ずかしながら理解してなかった
確かに一般のFPSに1を代入したら容易に定数項が発散してしまうね
0に何掛けても0なので0次の項が爆発してしまう

2021/08/22(日) 23:15:22.56

ARC125-DのBIT使って解くパートがよくわからん教えて

2021/08/23(月) 00:00:54.44

dp[i]を先頭i個について最後の要素を必ず使う場合の答えとかしてそのままBITに乗せればいい

2021/08/23(月) 23:52:44.91

競技プログラミングは役に立たない

Competitive programming is useless
https://kislayverma.com/organizations/competitive-programming-is-useless/

2021/08/24(火) 11:36:43.63

ざっくり読んだけど、大意としては白カピさんが前言ってたようなことと大体似たような感じ？
優秀なITエンジニアを目指すことと競プロを突き詰めることは分けて考えた方がいいというのはまあそうだよねという感じ

2021/08/24(火) 12:55:23.18

青くらいまで取れたら十分でそれ以上は趣味かな

2021/08/24(火) 14:53:30.06

独創的な問題じゃなくて、
「このような要件を持ったRailsアプリを作りなさい」

というのが実際に求められることだからな

2021/08/24(火) 15:01:44.46

あと競技プログラミングで作ったものって
他の人の役に立たないよね？

あんなに優秀（笑）な人が時間をかけて作業してるのに
競技プログラミングの成果は無駄になる

ものづくりのためにあるプログラミングなのに物を作らない
ものづくりに必要ない技術の競技なってるから役に立たない

2021/08/24(火) 15:18:14.22

入り口の段階でコーディングに慣れたり頭の体操ができる的な効用はあると思うけどねー
まあ趣味なので一定レベル以上でそんなに実用的な期待のもとにやってる人は少ないと思う

2021/08/24(火) 21:34:58.15

黄 abc卒業、一つの到達点
青？
水アルゴカンスト
緑業務上は十分
茶入色！

なんか青だけ中途半端だな。自分の立ち位置をうまく説明できなくて就職も失敗しそう

2021/08/24(火) 21:50:18.98

クイズ・頭の体操・コードゴルフ

プログラミングのお題スレとか、上田隆一のシェル芸と同じ

2021/08/24(火) 23:28:11.24

Codeforces の時間です

2021/08/24(火) 23:43:32.61

Codeforces の時間は終わりました
来週の放送時間は未定です

2021/08/25(水) 02:33:04.77

>>266
それ書いた頃から色１つ以上ずれてる予感
最大流が青以下で出てない以上黄色でもカンストしてないし、灰色で高度なグラフや最適化アルゴリズムを実用レベルで使うことも可能でミスリーディング

今のatcoderはアルゴリズムをダシにしたただの算数パズル

2021/08/25(水) 02:37:42.84

アルゴ力カンストしてます！とか言われても笑ってしまうわ

2021/08/25(水) 02:58:48.07

白カピを信仰しろ

2021/08/25(水) 03:13:33.31

こどふぉは B で詰まりまくって爆死した
整数1, 2個与えて計算してくれみたいな感じの問題が苦手っぽい

2021/08/25(水) 03:26:54.54

グラフアルゴリズムを使えなくても、整数問題と漸化式と関連してdpが使えれば最悪青までいけるように調整してきたのがatcoder、受験生に優しい

2021/08/25(水) 04:56:41.94

門外漢に説明する場合実態よりも社長のブログ記事やから

2021/08/25(水) 10:41:38.03

こどふぉB、所謂整数1,2個系っぽくはない気がする普通のDPであまり数学っぽくはないというか

2021/08/29(日) 22:37:29.72

全然参加してないっぽいね

2021/08/29(日) 22:41:26.84

ad hoc coder

2021/08/29(日) 22:55:37.34

牛ゲーっていうんだこれ
G問題なのにad hocで妙だなって思ってたけどちゃんと高度典型に関わる問題だったんだね
牛ゲーへの帰着よりad hoc解の方が簡単で結果みんな解けているけど

2021/08/29(日) 22:58:14.42

Gまで比較的簡単だったことを考えるとなおさらHが際立つね

2021/08/29(日) 23:03:52.50

公式自体は知ってたけど固定されてるパターンしか見たことなくて応用できなかった

2021/08/29(日) 23:25:47.06

ああGは区間スケジューリングみたいな貪欲でいけるんだ
天才では？

2021/08/29(日) 23:38:12.75

牛ゲー理解したけど、これ知ってても帰着に訓練が要りそう

2021/08/30(月) 00:04:52.56

最短経路問題に帰着したあと、負辺に悩んだ末にグラフの特殊な形を利用して準線形にしたけど
解説見てなるほどなあとなった
初手で反転するタイプのやつ全般、いつも見落としてしまうな

2021/08/30(月) 02:38:00.45

システムテスト弱forces

2021/08/30(月) 03:40:50.80

Combined で E 通してる人と同室になる確率が低い

2021/08/31(火) 01:37:25.41

もしや解説でないとかあるのか？

2021/08/31(火) 03:50:25.65

なんの話かは知らんけど解説そのうち出すよといって何年も放置されてる問題は存在する

2021/08/31(火) 18:30:11.43

日本語圏を掘るだけでもかなりの知見が発掘できるように中国語圏にも知見がたくさん集まってると思うんだけど、なんかまとめてるサイトとか知ってたりする？

2021/08/31(火) 21:10:30.18

ジャッジでよく聞くのはluogu libre uojとか？
個人ブログはcsdnで書いてる人が多いイメージ

2021/09/01(水) 12:14:20.08

>>290
ありがとう
csdnはUIがどことなくredditに似てるね
多分zennとかqiita的なサービスなんだと思うけど
競プロは競争性編程(の簡体字)というみたいだ

2021/09/01(水) 12:15:18.08

libreは見れたけどluoguは接続できないな

2021/09/03(金) 17:59:41.58

https://oi-wiki.org/
ここにまとまってる知見だけでもかなりの量

2021/09/03(金) 18:06:19.71

すごいwikiですね

2021/09/03(金) 18:30:45.42

大半は日本でも広く知られていそうだがときどきマニアックなのが紛れ込んでるな

2021/09/03(金) 23:09:38.04

>>293
これはすごい…
Chtholly Treeとか初めて聞いたな
前のABCに出てきたLGV公式とかも当然載ってる

2021/09/03(金) 23:16:13.01

牛ゲーのことを差分约束と呼んでるのか

**デフォルトの名無しさん** (JP 0Hff-Sfec) · 2021/09/04(土) 22:47:23.13

Eみたいなの新しいデータ構造を作ってみようみたいな感じで面白いと思ったな

2021/09/04(土) 23:10:09.45

vEB木って俺の考えた最強のデータ構造感があってかなり好き
実践では使わないけど

**デフォルトの名無しさん** (JP 0Hff-Sfec) · 2021/09/04(土) 23:20:56.78

https://www.slideshare.net/catupper/nazoki
catupperさんがスライド出してる謎木だね

2021/09/06(月) 01:35:28.67

実装重すぎforces