競技プログラミング総合スレ 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 SNSヲチ勢はNG推奨
健全な競プロスレにしましょう インドコンって特有の問題傾向ってあるの？
AtCoderは算数パズル多め的な感じの 苦痛なlog落としの問題とか謎い式を変形していく問題とか？
俺は知らないけどFPSを使う系の問題もあるらしい 結構勉強にはなりそうだね、atcoderにはなさそうな感じ
それだけ聞くと好きかもしれない 見てみたらインドコンのがコドフォより英文読みやすかった
英文はこっち標準がいい 競プロと関係ない馬鹿な話題が蔓延ってたから移行うれしい たったレス10個で落ちてなかったスレがあるから大丈夫そうな気がするけど 前スレで質問あるって言ってた人、こっちで聞いてみたら
俺も可能な範囲で答えるよ のいみ鍵垢なってるじゃん
非公開リストで見てたのに 8問ABC が始まったら AtCoder Problems の横枠？がまた狭くなるのかな
AGC-like とかもう問題名が何も見えんのだけども 25分後くらいにこどふぉ div. 2 です
夜更かしする人は出ましょう 米ニューヨーク市
7月30日以降のワクチン接種者全員に
100ドルを配布するキャンペーン開始 質問いいですか
Ford-Fulkersonの計算量O(FE)の最大流量Fって何のことですか？具体的にどう見積もればいいのでしょうか こどふぉのレートなんて溶かしても余裕じゃない？
橙から落ちるとかならありかもしれんが今日はDiv.2 only だし >>28
最大流量F ってのはそのままの意味で、 始点から終点へ流せる量の最大値
見積もりは難しいと思う。自明なカットで上界与えるくらいしかできないんじゃないかな
(辺容量の最大値) * (辺数) とか >>30
ありがとうございます！スッキリしました
AOJのVerify用問題も(辺容量の最大値)*(辺数)が10^7に収まるようになってるので取りあえずその見積もりで問題なさそうですね
（1/4とかの定数倍はつけてもよさそうですが）
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A&;lang=jp 最大流が青までの問題に出ない教プロに何の価値があるんだろうか 蟻本だと中級だからそんなに発展的な内容という位置づけではないわな 最大流とかグラフ系を増やしてしまうと進学校の数学の先生が激おこですからね IOIシラバスで明確に除外されてるものは黄色以降でいいだろ こんなのがあるのか、有効グラフの連結分解が明確に除外ってw
https://www.ioi-jp.org/ioi/ioi-syllabus_jp.pdf
中高生の「事情」に一般人が配慮する一般向けコンテスト >>35
これはどう考え方？
ARCで前提にするつもりのテクニックはABCで出しておかないと
ARCがそのテクニックを学ぶための教育的コンテンツになってしまうし、ARCの位置づけはそうではないと思うんだが
一切出さないかABCでも出すかの二択しかないと思っていた
それはそうと実はCodeChef LunchtimeはIOIのシラバスに沿うというルールなんだよな
言うほど守られていないが >>37
ABCの600点(解けたらABC卒業;黄diff〜)
に少し難しいアルゴリズムを出すことは否定しない >>38
なるほどだけど、少し難しいアルゴリズムが結果的に青dif以下になるなら点数にはこだわらなくていい気がするなあ
本当にフロー流すだけ、とかはIOIで除外されてるけど青ボーダーくらいになりそうだし500点ででても違和感がない
(そんなん出すなよ、というのは一理はある) ZebranessとかGrid and Tokensは黄diffだったねえ アルゴリズムってなんでこんな仰々しい名前多いんだろ
連鎖行列積問題とか行列積コスト最小化問題って書いてたら、何となくやってること分かりそうなのにわざわざ難しく書く matrix chain multiplicationの直訳だからじゃない
日本語だと仰々しいが英語だと簡潔
どっちも最適化する対象が名前からわからんけど そもそもそれDPでとける問題の名前であってアルゴリズムの名前じゃなくない？ 行列積コスト最小化問題だと行列が3つ以上あるように見えないな
英語のchain要素は欲しい 行列鎖積が限界じゃない
方鎖積とか言い出すと意味が取れなくなって危険 8問楽しみだ
1問1問にどこまで固執して良いのかな見極めが重要そう 緑〜水difの問題生やすの難しそうだよな…Writerは頑張って欲しい そういえば4問ABCから6問ABCに変わった初回はunratedになったのを思い出した
今回も参加者増えてジャッジ詰まらないか心配 171 仕様書無しさん sage 2021/07/30(金) 19:51:47.26
IDありの方でいい感じに自演してるけど楽しい
こっち見てない人多そうだししばらくバレなそう 今日は yukicoder と Educational なこどふぉです まあIDなしスレの方でこのスレについて適当に煽るやつが出てくるのも自然ななりゆきだな ABC unrated なら インド優先でいいんでないか
トーナメントは知らん 直近コドフォAの考え方教えてください
自分は小中大のスライスの数が3:4:5なので、その辺りから必要な枚数をO(1)で導こうとしたのですがうまくいきませんでした
答えが小中大の枚数に関わらず(n+1)/2*5だなとわかった人はどんな発想でそうなったのか知りたいです
よろしくお願いします
ちなみに関係ないかも知れませんが女子中学生です >>64
小中大も単位枚数当たりにかかる時間が同じ
拡張ユークリッド互除法の観点から、ある程度大きな数の偶数は、6 と 8 のペアの組み合わせで作れるみたいなのがある (実際には 6 以上の整数すべてが 3 つのペアから作れる) 8問ABCか
黄パフォラインは1-2-3-4-5-6の組み合わせで6完とかかな？ 4問から6問への移行のときも参加者増えてたし今日は少なくとも9000人は参加しそう
多けりゃ1万 4問から6問のときはrated対象変化のほうが大きそう
今回はそこまで変わらないと予想 問題数の多さに嫌気さして減るまであるかもね。実質何にも変わらないとしても 解説放送、スタイル変えないなら深夜3時コースじゃん Fが実装難でGが数論の中レベル典型という感じで難度逆転か
数学問はAtCoderだとみんな解くからね Fが実装辛すぎて震撼してたが、終わってみるとこれに数十分掛けてるようでは。。という気持ちになるんだよな
実装難問題はだいたいそうなんだけど 今日のC問題、
Bだけソートして、
二分探索でB[l]<=A[i]<B[r](l+1==r)となるl,rを探して
min(今までの最小,min(abs(A[i] - B[l]),abs(A[i] - B[r]))))
で最小値だそうとしたんだけど、WAが2つ。
ソートする前に10の9乗よりちょっと大きい数字とその負の数をBに付けた。TLEはない。
なんで？
…とここまで書いてちょっと大きい数を
10**9+20から3*(10**9)に替えたら全部通った。
ドンマイ、俺 つまらない実装ミスでF問題落として魂抜けた
ちゃんと大きめのサンプル作って試していればよかったのに Aの提出者数8554 -> 7822か
700人くらい減ったな ratedの人でGH解けてる人どれくらいいるのかな G は知識があればなんとかなる
H は畳み込みをブラックボックスとして使ってた人は厳しいかも rated だけど E までは簡単で考察も実装も F より G の方が軽かったし、G は無限人解けてそう
H は知らん 難易度若干シグモイドっぽいの解消して欲しいな(難しいとは思うが) Gは位数とか原始根みたいなちょっと進んだ整数論を学んでたら知ってるような概念割とそのまんまなので、考察負荷も確かにそんな高くない
Fも考察の本体は「あるバスに乗ったあとに乗るバスがあるとすれば一意に定まる」に気づいて超頂点を作るだけな気がするけど、ダブリング二分探索みたいなおまけ部分が重い
AtCoderで重実装問の後ろに軽い数学問出したらそらそっちに流れるわなという >>83
C茶、D緑、E水、F青を目指してたんだろうなと思ってる
CDEはその点ちょっとブレただけで割と悪くないのでは？
Fは運営がユーザーの実装力を過大評価してたといういつものやつ >>85
いまグラフ作ってたんだけどまさにその通りだったわ
https://i.imgur.com/tQx8HP0.jpg
Fがもう少し低ければめちゃくちゃいい勾配のセットだったんだな、惜しい >>86
やっぱFだけおかしいね
どうすりゃよかったんだろう
最初から逆有向森？みたいなのを明示的に与えてあげるか、バスに乗ってる時間を無視してよいとするか Fは100分6問のFならもっと解かれたはず
解けそうなやつがGにいっただけ 同程度の難易度の問題が500と600にあったらコスパ良い600の方が解かれるのは当然
600の方がちょっと難しかったとしても、つまり難易度は逆転していないとしても、diffが逆転することは全然ありうるよな
そういう意味でdiffを重視しすぎるのはどうかと思う 今回のE問題までのほぼ直線的に解いていくしかないような問題配置以外では、diffは問題難度を評価する指標として微妙だとは思う 確かにこの難易度帯が解ける人にとっては実装が重そうなこの問題よりも発想さえ出来れば解ける得点が高い方に流れるか
そうなると問題数増えて時間同じままだから、実装重い問題は忌避されていくんだろうなあ 問題単体の難易度をより正確に評価できるようなdiffに代わる指標ってありうるかな？
diffの定義式にちょっと変更を加えるとかでも 昨日のE解けなかったのめちゃくちゃ悔しいわ
だいぶ冷えた 昨日のE解けなかったのめちゃくちゃ悔しいわ
だいぶ冷えた Eは俺はTDPC-Rグラフの変形だと思って解いたね
全頂点対だとO(N^3 logK)だけど一頂点対についての問題だから大分計算量節約できそう的な tdpc-rってsccしてdag作ってトポロジカルソートするやつじゃなかったっけ？
共通点が見えんけど Heuristicの方ってABC全完できるくらいの地力ないと難しいかな？
楽しそうだけど実装の方針がよく分からないです 多分 EDPC R と間違えてる
自分には補グラフの形式で与えられてることが本質だと思った ■ このスレッドは過去ログ倉庫に格納されています
