競技プログラミング総合スレ 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/
※前スレ
競技プログラミングにハマるプログラマのスレ 62
https://medaka.5ch.net/test/read.cgi/prog/1626625368/
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured >>98
マジだ
すまん、EDPC-Rのwalkの方だな
どっちもRで大体この辺にあったグラフの問題だよなあって感じで覚えてて、問題開いてよく確認してないから間違えた 遷移の節約がメインって考えると確かに補グラフが本質か
むしろ行列累乗の発想を使えないからwalkの本質的な部分とは遠いかもしれない
そもそも俺はDPを一から生やすのが苦手な方だから、DPのテンプレとして既知問題が役に立ったという感じかな >>99
俺もheuristic全然できないけどそんなことはなさそう
基本的なアルゴリズムの組み合わせで解を探索してあげるのが主だからそんなに高度な知識はいらないって聞いたことがある ナップサックだと嘘になるような貪欲でもheuristicだと十分な解法になり得る
ちゃんとした貪欲が書けるだけどもかなり強いよ >>99
Heuristicsは貪欲書けてBFSとDFSができれば何もできないってことはまずないと思う
あとは勇気を持って噓貪欲書いて、結果をビジュアライザで見ながら改善していけばいい クエリのやつABCで復習したのですんなり解けてうれしい 制約がn=2*10^5とかで想定解がO(n)なのって出題者の優しさでしょうか
それとも定数倍とかの関係？
O(nlogn)解で通った人← N と NlogN の区別はなかなか厳しいことが知られております
N 個の入力を与える問題なら問題を解くより入出力を捌く時間の方がネックになるなんてこともある 入出力数がO(n)ならn=10^7とかにするとそこがボトルネックになって非本質ゲーになりがち
あと遅い言語でO(n log n)落としてO(n)通すように設計するとC++ではO(n log n)が普通に通るなんてことがある
logを落とす力を評価するコンテストサイトもあるっぽいけど、AtCoderは入出力ゲーとか言語格差とかそんなに好きじゃないのであまりそういう力は問わない 一応ABC189-Cがlogの有無を意図してるっぽい セグ木上の二分探索とかlog二つをlog一つに落とせて嬉しいパターンが結構ある気がする log x × log xのことじゃね
log log xではなく 最近競プロで必要そうな知識を整理してて、集めるとそれなりの分量になるなと思った反面、AGCの難問には基本的な知識しか問わないけど難しいものが結構あるよね
多分知識入れただけじゃ解けるようにならなそう
どうやって練習してる？ 高1でatcoder赤になった奴、東進全統高で上級生抑えて一位だな。
プログラミングと受験勉強の配分はどうなってるんだ? 全方向に才能が溢れていた結果としてAtCoder赤になったのであれば、受験勉強も軽くクリアできてもそんなに不思議じゃない AGCもなんだかんだで練習量でそこそこ溶けるまでは解ける
個別の練習はやってないや >>123
結局演習量という話はよく聞くね
>>125
ありがとう、読んだことないや
目次を見たけどかなり競プロと相性がよさそうだね なんかのめり込んでる時期はAGC全然勝てなかったけど一旦離れてたらいい感じに力抜けて苦手意識なくなったな あるある
めちゃくちゃやってた時期よりもレート伸びてるわ今 ここしばらくコンテストしか出てないけどレートなんやかんや上がってるわ エレガントな問題解決ポチった
数オリの問題も結構含まれてるっぽくて楽しみ >>130
英語版の公式サイトに解説マニュアルあるよ。載ってるのは選ばれた問題だけだけど PaizaってAからやたら計算量ギリギリな問題が多くなる気がする...
TLEで一発終了なのがキツい >>131
ありがとう
届いたから読んでるけどまさに算数パズルという感じの問題が集まってて面白い
普通に演習問題の中に難しいのも結構あるから世話になるかも 132だけどやっとA取れました...
茶色になった記念でpaizaに挑戦したけど意外と苦戦した
Aの美術館のセキュリティって問題でasin,acosが出てきて三角関数の逆関数の使い方を色々学べて楽しかった(これだけじゃネタバレにならんと思う)
asinは終域が-π/2〜π/2で全単射
acosは終域が0〜πで全単射だからモジュールの仕様で出てくるradianに気をつけないといけないんよね 解答の本質とは関係ないぐらいの書き込みなんだろうから直ちにアウトってレベルじゃないと信じるけど、事前に要求知識が分かるだけでも微妙なのでやめといた方がいいと思う
あれ提出までの時間も評価対象だし 誰も聞いてないのにスレチのpaizaのネタバレを始める茶色 rated砂漠の時ってみんな過去問解いたりしてんの？ 山ほど溜まってるコンテスト中にACできなかった問題を処理してる
rated 砂漠時に限らないけど leetcodeのLISをO(nlogn)で解くってググれば出てくるんで典型なんですかね？
もしコーディング面接だったら解ける気がしないですね diffよりも正確な問題難易度の指標ってないだろうか
chokudaiはdiff信仰をやめろって言ってるけど現状問題点数が全くあてにならないから結局diff見るしかないんだけど >>145
勉強として考えるなら適正問題探す意味は薄いけどさ
今の実力でぎりぎり解けたり解けなかったりする問題がすぐにわかったらゲームとしては遊びやすくて嬉しくない？ >>146
その使い方なら diff 程度の信頼度でも十分だと思うけどどう？ 一元的な指標を作るのは難しいね
ただ点数、diff、平均AC時間、ABC or ARC or AGC、コンテスト中の問題の位置あたりを使えば何かしら予測できそうではある
あと難易度評価と言えばAOJ-ICPCの投票システムとかも悪くなさそう Tree Gameとか問題だけ見たら黄diffがいいところなのにAGC-Fに置いてあるってだけで赤diffなんだよな
diff、点数、出題時期、傾向、コンテスト時間、点数、問題位置あたりをパラメータにしてなんかすごいパワーで問題単体の指標が出来たら嬉しそう >>150
そんなことあるのか…今回のABCも8問になったから多すぎて終わらんくてHが赤difとかになってしまったのだろうか 分割統治FFTはtwitterの人々の反応をみても知識レベル的に橙〜赤はあるようには見えるし、今回はそんなに極端に上がったわけではなさそう
ただ、今回のFレベルの問題が仮にHの位置にあったら橙diff上位になるみたいなことは普通にありえそう 8問制になったことで今まで以上にdiffの信憑性がイマイチになりそうなんだよな
EFGHのうち典型3問、実装1問だとしたら
実装問が難易度的には一番易しくても橙diffとかになりかねないし
diffにとらわれず全部覚えろという意見ももっともだが、なるべく効率的にやっていきたいので
やっぱりよりよい指標ができたら嬉しい EをFGHと同じ括りにしてるのよくわからないけど
毎週高々三つなら全部やればいいじゃんとしか 新しい知識週3つ身につけるのって結構しんどくないか Fは500点問題としては難しかった。6問の時のFのままの難易度では。 くまくまここ見て誕生年変えただろ、案外見てるもんなんだな ABCで明らかにRatedが解けない様な問題たくさん出してるのってどういう意図なのかな 高難度典型枠は高レベル向け典型90としてみるとありがたいけど、だったらストレートに高レベル向け典型90という形で出してもよかったんじゃないかなあとも思う
界隈の知識レベルを向上させる？みたいなコンセプトそんなに悪いとは思わないからさ ratedが解けない問題出す云々は他のコンテストでもそうじゃないか？
ARCの後ろとかもそんなもんだと思う ARCもAGCもratedで全完が出るかどうか、くらいの回が多いしABCもそうなっていくのかね
一般論としてはratedが全完同士のスピード勝負になるよりは上から下まで点数の勝負になるほうが健全と思うけど、
ABCは上位のかなりの人数が2400になるから全完多めでも問題ないはずなんだよな 平成ABCでのまぐれ全完が最初で最後の全完になった ABC全完しても2400パフォ出ない簡単回が続いてた頃より今の方が好みだな まあ色々文句も出てるけど、e問題までは確実に以前の難易度に戻ったから良かったと思う それはほんとに思う Eまで大分解きやすくなったよね ありがたい EはABC198以前の難易度になった感じかな
まだサンプル2だしE青パフォとかになることもありそう 社長曰く
Easy/Easy/灰-茶/茶-緑/水-青/青/黄-橙/黄-橙
辺りを狙っていくとのことだったので、E青は全然ありうると思う
現時点ではFが思ったより難しいのがアナウンスと異なる点 それな
試してもないのに解ける問題数が〜みたいな社長の妄想によりそうなってる
初心者にオススメのコンテストは英語に抵抗なければCF Div. 3だわ こどふぉは Div.3 だろうが A の時点で for かけないとキツい >>167
なるほど、たしかにRatedで全完する人がいっぱいいると、スピード勝負になっちゃうもんな
全完をちゃんと狙うのはABC卒業してからだな for文書けない人に配慮する前に気にすべきことがあるんじゃないかとは思う こないだのA問題は実質的にfor書けない人配慮してないと思う ACLにあるけどあえて自作したライブラリあったら教えてください
その理由も 前から持ってたやつが結構あって、自分で作ったやつの方が慣れてるからそっち使うことはよくある
ACLのが基本よくできてるが ACLできた時点で大体持ってたな
floor sumとかconvolutionあたりは持ってなかったからACL使ってる 由は負辺対応してない、双対変数の復元がない、計算量が悪い そういやACLが登場したけどまだABCでネットワークフローの問題でてない？ 全然GH見てる余裕なかったな
Gは時間が十分あったら赤diffというほどは難しそうに見えない、ARC中盤で出したら黄diff上位〜橙diff下位ぐらい？ ■ このスレッドは過去ログ倉庫に格納されています
