競技プログラミング総合スレ 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/09(月) 19:53:06.68

>>147
た、たしかに…

2021/08/09(月) 20:50:23.56

一元的な指標を作るのは難しいね
ただ点数、diff、平均AC時間、ABC or ARC or AGC、コンテスト中の問題の位置あたりを使えば何かしら予測できそうではある
あと難易度評価と言えばAOJ-ICPCの投票システムとかも悪くなさそう

2021/08/09(月) 21:22:43.06

Tree Gameとか問題だけ見たら黄diffがいいところなのにAGC-Fに置いてあるってだけで赤diffなんだよな
diff、点数、出題時期、傾向、コンテスト時間、点数、問題位置あたりをパラメータにしてなんかすごいパワーで問題単体の指標が出来たら嬉しそう

2021/08/09(月) 21:23:13.93

2文目、149とほとんど同じこと言ってたわ

2021/08/09(月) 22:35:42.42

>>150
そんなことあるのか…今回のABCも8問になったから多すぎて終わらんくてHが赤difとかになってしまったのだろうか

2021/08/09(月) 23:22:45.32

分割統治FFTはtwitterの人々の反応をみても知識レベル的に橙～赤はあるようには見えるし、今回はそんなに極端に上がったわけではなさそう
ただ、今回のFレベルの問題が仮にHの位置にあったら橙diff上位になるみたいなことは普通にありえそう

2021/08/09(月) 23:27:18.20

こどふぉでます

2021/08/09(月) 23:31:11.11

どうぞ

2021/08/09(月) 23:48:37.40

8問制になったことで今まで以上にdiffの信憑性がイマイチになりそうなんだよな
EFGHのうち典型3問、実装1問だとしたら
実装問が難易度的には一番易しくても橙diffとかになりかねないし
diffにとらわれず全部覚えろという意見ももっともだが、なるべく効率的にやっていきたいので
やっぱりよりよい指標ができたら嬉しい

2021/08/10(火) 01:12:05.76

せめて120分にしたらもう少しdiff下がるよね

2021/08/10(火) 01:37:07.20

ビット演算系やめてください><

2021/08/10(火) 01:53:40.55

EをFGHと同じ括りにしてるのよくわからないけど
毎週高々三つなら全部やればいいじゃんとしか

2021/08/10(火) 07:29:54.11

新しい知識週3つ身につけるのって結構しんどくないか

2021/08/10(火) 08:42:22.48

Fは500点問題としては難しかった。6問の時のFのままの難易度では。

2021/08/10(火) 13:50:51.09

くまくまここ見て誕生年変えただろ、案外見てるもんなんだな

2021/08/10(火) 20:47:31.28

そういうのはあっちでどうぞ

2021/08/10(火) 21:06:15.34

ABCで明らかにRatedが解けない様な問題たくさん出してるのってどういう意図なのかな

2021/08/10(火) 21:13:14.40

高難度典型枠は高レベル向け典型90としてみるとありがたいけど、だったらストレートに高レベル向け典型90という形で出してもよかったんじゃないかなあとも思う
界隈の知識レベルを向上させる？みたいなコンセプトそんなに悪いとは思わないからさ

2021/08/10(火) 21:37:39.83

ratedが解けない問題出す云々は他のコンテストでもそうじゃないか？
ARCの後ろとかもそんなもんだと思う

2021/08/10(火) 22:23:49.89

ARCもAGCもratedで全完が出るかどうか、くらいの回が多いしABCもそうなっていくのかね
一般論としてはratedが全完同士のスピード勝負になるよりは上から下まで点数の勝負になるほうが健全と思うけど、
ABCは上位のかなりの人数が2400になるから全完多めでも問題ないはずなんだよな

2021/08/10(火) 22:46:22.62

平成ABCでのまぐれ全完が最初で最後の全完になった

2021/08/11(水) 00:11:42.49

ABC全完しても2400パフォ出ない簡単回が続いてた頃より今の方が好みだな

2021/08/11(水) 00:56:37.31

そのうち5完で2400出る回が出そう

2021/08/11(水) 02:40:27.47

まあ色々文句も出てるけど、e問題までは確実に以前の難易度に戻ったから良かったと思う

2021/08/12(木) 06:44:33.27

それはほんとに思う　Eまで大分解きやすくなったよね　ありがたい

2021/08/12(木) 12:26:52.35

EはABC198以前の難易度になった感じかな
まだサンプル2だしE青パフォとかになることもありそう

2021/08/12(木) 13:06:07.88

社長曰く
Easy/Easy/灰-茶/茶-緑/水-青/青/黄-橙/黄-橙

辺りを狙っていくとのことだったので、E青は全然ありうると思う
現時点ではFが思ったより難しいのがアナウンスと異なる点

2021/08/12(木) 19:00:50.50

easyは1個ではダメなのかな

2021/08/12(木) 21:19:29.53

それな
試してもないのに解ける問題数が～みたいな社長の妄想によりそうなってる
初心者にオススメのコンテストは英語に抵抗なければCF Div. 3だわ

2021/08/12(木) 22:08:44.55

こどふぉは Div.3 だろうが A の時点で for かけないとキツい

2021/08/12(木) 23:15:20.77

>>167
なるほど、たしかにRatedで全完する人がいっぱいいると、スピード勝負になっちゃうもんな
全完をちゃんと狙うのはABC卒業してからだな

2021/08/13(金) 02:06:11.01

卒業どころか今のabcでの全完は橙が最低ライン感

2021/08/13(金) 04:54:00.24

for文書けない人に配慮する前に気にすべきことがあるんじゃないかとは思う

2021/08/13(金) 04:59:00.27

配慮できるところはしたらいいよ

2021/08/13(金) 09:15:28.52

こないだのA問題は実質的にfor書けない人配慮してないと思う

2021/08/13(金) 10:00:25.00

こないだのaは自信なかったんで全探で解いたわ

2021/08/13(金) 12:09:33.84

ACLにあるけどあえて自作したライブラリあったら教えてください
その理由も

2021/08/13(金) 12:29:51.97

理解のために全部自作した

2021/08/13(金) 12:52:15.47

Pythonなので自作せざるを得なかった

2021/08/13(金) 16:20:50.50

Pythonも非公式であるよ

2021/08/13(金) 19:37:23.95

前から持ってたやつが結構あって、自分で作ったやつの方が慣れてるからそっち使うことはよくある
ACLのが基本よくできてるが

2021/08/13(金) 19:39:29.14

ACLできた時点で大体持ってたな
floor sumとかconvolutionあたりは持ってなかったからACL使ってる

2021/08/14(土) 00:47:37.98

最小費用流
理

2021/08/14(土) 00:49:50.26

由は負辺対応してない、双対変数の復元がない、計算量が悪い

2021/08/14(土) 05:59:35.72

自分が知る範囲だとSSPで十分な問題ばかりだ

2021/08/14(土) 15:46:07.08

そういやACLが登場したけどまだABCでネットワークフローの問題でてない？

2021/08/14(土) 16:00:48.86

205F

2021/08/14(土) 19:52:51.26

>>194 あざっす

2021/08/14(土) 22:44:25.33

ちょうど最小費用流出て草

2021/08/14(土) 22:45:45.02

D重い方から考えてたけど軽い方からなのかー

2021/08/14(土) 22:46:53.54

くくく、このスレで予習できたかいがあったぜ・・・

2021/08/14(土) 22:47:28.63

うわー

2021/08/14(土) 23:27:08.23

全然GH見てる余裕なかったな
Gは時間が十分あったら赤diffというほどは難しそうに見えない、ARC中盤で出したら黄diff上位～橙diff下位ぐらい？

2021/08/14(土) 23:57:47.01

包除原理知ってるなら時間あれば解けるはず
多分橙もいかないと思う

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とか