競技プログラミング総合スレ 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/01(日) 17:41:14.99

遷移の節約がメインって考えると確かに補グラフが本質か
むしろ行列累乗の発想を使えないからwalkの本質的な部分とは遠いかもしれない
そもそも俺はDPを一から生やすのが苦手な方だから、DPのテンプレとして既知問題が役に立ったという感じかな

2021/08/01(日) 17:47:22.80

>>99
俺もheuristic全然できないけどそんなことはなさそう
基本的なアルゴリズムの組み合わせで解を探索してあげるのが主だからそんなに高度な知識はいらないって聞いたことがある

2021/08/01(日) 18:46:28.69

ナップサックだと嘘になるような貪欲でもheuristicだと十分な解法になり得る
ちゃんとした貪欲が書けるだけどもかなり強いよ

2021/08/01(日) 23:17:01.04

コドフォやります

2021/08/02(月) 00:06:59.46

>>99
Heuristicsは貪欲書けてBFSとDFSができれば何もできないってことはまずないと思う
あとは勇気を持って噓貪欲書いて、結果をビジュアライザで見ながら改善していけばいい

2021/08/02(月) 02:04:52.64

クエリのやつABCで復習したのですんなり解けてうれしい

2021/08/02(月) 02:24:36.26

おめでとう

2021/08/02(月) 04:57:00.13

制約がn=2*10^5とかで想定解がO(n)なのって出題者の優しさでしょうか
それとも定数倍とかの関係？
O(nlogn)解で通った人←

2021/08/02(月) 05:19:48.94

N と NlogN の区別はなかなか厳しいことが知られております
N 個の入力を与える問題なら問題を解くより入出力を捌く時間の方がネックになるなんてこともある

2021/08/02(月) 12:15:14.37

入出力数がO(n)ならn=10^7とかにするとそこがボトルネックになって非本質ゲーになりがち
あと遅い言語でO(n log n)落としてO(n)通すように設計するとC++ではO(n log n)が普通に通るなんてことがある
logを落とす力を評価するコンテストサイトもあるっぽいけど、AtCoderは入出力ゲーとか言語格差とかそんなに好きじゃないのであまりそういう力は問わない

2021/08/02(月) 12:50:39.03

一応ABC189-Cがlogの有無を意図してるっぽい

2021/08/02(月) 14:48:31.21

POJで鍛えなさい

2021/08/02(月) 18:36:35.29

logは2つつくとめちゃくちゃ速度落ちるよね

2021/08/02(月) 19:53:01.87

セグ木上の二分探索とかlog二つをlog一つに落とせて嬉しいパターンが結構ある気がする

2021/08/02(月) 20:48:14.11

https://atcoder.jp/contests/abc208/tasks/abc208_f
これは割と変なlogつけると通らないんじゃないかな

2021/08/02(月) 22:33:06.34

logって2つあるほうが早いんじゃないんです？

**デフォルトの名無しさん** (JP 0H89-HYiC) · 2021/08/02(月) 23:02:50.81

log x × log xのことじゃね
log log xではなく

2021/08/03(火) 13:47:56.92

最近競プロで必要そうな知識を整理してて、集めるとそれなりの分量になるなと思った反面、AGCの難問には基本的な知識しか問わないけど難しいものが結構あるよね
多分知識入れただけじゃ解けるようにならなそう
どうやって練習してる？

2021/08/03(火) 19:10:08.89

天才以外お断りパズルコンテストだぞ

2021/08/03(火) 19:24:48.79

高1でatcoder赤になった奴、東進全統高で上級生抑えて一位だな。
プログラミングと受験勉強の配分はどうなってるんだ?

2021/08/03(火) 19:48:26.20

全方向に才能が溢れていた結果としてAtCoder赤になったのであれば、受験勉強も軽くクリアできてもそんなに不思議じゃない

2021/08/03(火) 19:54:23.17

AGCもなんだかんだで練習量でそこそこ溶けるまでは解ける
個別の練習はやってないや

2021/08/03(火) 19:55:24.31

✕　溶けるまでは解ける
◯　解ける

2021/08/03(火) 20:12:18.13

>>119
https://www.oreilly.co.jp/books/9784873114057/
読んだことある？

2021/08/03(火) 20:41:09.91

>>123
結局演習量という話はよく聞くね

>>125
ありがとう、読んだことないや
目次を見たけどかなり競プロと相性がよさそうだね

2021/08/03(火) 22:19:00.93

なんかのめり込んでる時期はAGC全然勝てなかったけど一旦離れてたらいい感じに力抜けて苦手意識なくなったな

2021/08/04(水) 00:02:03.33

あるある
めちゃくちゃやってた時期よりもレート伸びてるわ今

2021/08/04(水) 13:37:25.83

ここしばらくコンテストしか出てないけどレートなんやかんや上がってるわ

2021/08/04(水) 22:11:47.50

エレガントな問題解決ポチった
数オリの問題も結構含まれてるっぽくて楽しみ

2021/08/05(木) 02:17:05.07

>>130
英語版の公式サイトに解説マニュアルあるよ。載ってるのは選ばれた問題だけだけど

2021/08/05(木) 20:50:38.29

PaizaってAからやたら計算量ギリギリな問題が多くなる気がする...
TLEで一発終了なのがキツい

2021/08/06(金) 21:22:03.99

>>131
ありがとう
届いたから読んでるけどまさに算数パズルという感じの問題が集まってて面白い
普通に演習問題の中に難しいのも結構あるから世話になるかも

2021/08/07(土) 12:48:17.49

132だけどやっとA取れました...
茶色になった記念でpaizaに挑戦したけど意外と苦戦した

Aの美術館のセキュリティって問題でasin,acosが出てきて三角関数の逆関数の使い方を色々学べて楽しかった(これだけじゃネタバレにならんと思う)
asinは終域が-π/2～π/2で全単射
acosは終域が0～πで全単射だからモジュールの仕様で出てくるradianに気をつけないといけないんよね

2021/08/07(土) 14:56:20.68

paizaの問題は話さん方がいいよ

2021/08/07(土) 15:00:37.61

ぶっちゃけアウト臭い書き込み

2021/08/07(土) 15:16:31.01

解答の本質とは関係ないぐらいの書き込みなんだろうから直ちにアウトってレベルじゃないと信じるけど、事前に要求知識が分かるだけでも微妙なのでやめといた方がいいと思う
あれ提出までの時間も評価対象だし

2021/08/07(土) 15:32:05.34

一切言及しないほうが無難

2021/08/07(土) 16:04:55.36

誰も聞いてないのにスレチのpaizaのネタバレを始める茶色

2021/08/07(土) 17:20:38.22

rated砂漠の時ってみんな過去問解いたりしてんの？

2021/08/07(土) 19:55:50.34

山ほど溜まってるコンテスト中にACできなかった問題を処理してる
rated 砂漠時に限らないけど

2021/08/08(日) 13:14:36.11

leetcodeのLISをO(nlogn)で解くってググれば出てくるんで典型なんですかね？
もしコーディング面接だったら解ける気がしないですね

2021/08/08(日) 13:16:52.61

典型だけど覚えてなきゃまあ無理だね

2021/08/09(月) 18:48:38.87

diffよりも正確な問題難易度の指標ってないだろうか
chokudaiはdiff信仰をやめろって言ってるけど現状問題点数が全くあてにならないから結局diff見るしかないんだけど

2021/08/09(月) 19:02:08.36

正確な難易度指標がほしいモチベがなくない？

2021/08/09(月) 19:18:16.99

>>145
勉強として考えるなら適正問題探す意味は薄いけどさ
今の実力でぎりぎり解けたり解けなかったりする問題がすぐにわかったらゲームとしては遊びやすくて嬉しくない？

2021/08/09(月) 19:27:37.98

>>146
その使い方なら diff 程度の信頼度でも十分だと思うけどどう？

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

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