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

■ このスレッドは過去ログ倉庫に格納されています
1デフォルトの名無しさん (ﾜｯﾁｮｲ 1f9f-qCnf)
垢版 |
2021/07/28(水) 21:58:48.02ID:nljYiy+l0
!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/07/29(木) 21:52:45.28ID:YihrRvviM
どう棲み分けされてんのこれ
2021/07/29(木) 22:09:03.33ID:PDupjLth0
向こうは競プロerヲチスレ、こっちは競プロスレ
2021/07/29(木) 23:08:45.28ID:8ZzMZHUN0
25分後くらいにこどふぉ div. 2 です
夜更かしする人は出ましょう
2021/07/29(木) 23:41:30.68ID:DDUZLlkb0
米ニューヨーク市
7月30日以降のワクチン接種者全員に
100ドルを配布するキャンペーン開始
2021/07/30(金) 01:42:19.51ID:bjmh4Zft0
nosub余裕でした
2021/07/30(金) 02:00:37.81ID:czlY0Bar0
質問いいですか
Ford-Fulkersonの計算量O(FE)の最大流量Fって何のことですか？具体的にどう見積もればいいのでしょうか
2021/07/30(金) 02:00:44.03ID:w6cU9sbP0
こどふぉのレートなんて溶かしても余裕じゃない？
橙から落ちるとかならありかもしれんが今日はDiv.2 only だし
2021/07/30(金) 02:05:56.79ID:06AAPmWW0
>>28
最大流量F ってのはそのままの意味で、 始点から終点へ流せる量の最大値
見積もりは難しいと思う。自明なカットで上界与えるくらいしかできないんじゃないかな
(辺容量の最大値) * (辺数) とか
2021/07/30(金) 02:41:39.83ID:czlY0Bar0
>>30
ありがとうございます！スッキリしました
AOJのVerify用問題も(辺容量の最大値)*(辺数)が10^7に収まるようになってるので取りあえずその見積もりで問題なさそうですね
（1/4とかの定数倍はつけてもよさそうですが）

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A&;lang=jp
32デフォルトの名無しさん (ﾜｯﾁｮｲ 4d90-nzU0)
垢版 |
2021/07/30(金) 03:05:30.73ID:uZitzRq40
最大流が青までの問題に出ない教プロに何の価値があるんだろうか
2021/07/30(金) 03:15:43.73ID:BzNzYO4rM
蟻本だと中級だからそんなに発展的な内容という位置づけではないわな
34デフォルトの名無しさん (ﾜｯﾁｮｲ 4d90-nzU0)
垢版 |
2021/07/30(金) 03:34:11.33ID:uZitzRq40
最大流とかグラフ系を増やしてしまうと進学校の数学の先生が激おこですからね
2021/07/30(金) 03:47:29.25ID:PogAvYGI0
IOIシラバスで明確に除外されてるものは黄色以降でいいだろ
36デフォルトの名無しさん (ﾜｯﾁｮｲ 4d90-nzU0)
垢版 |
2021/07/30(金) 04:22:03.94ID:uZitzRq40
こんなのがあるのか、有効グラフの連結分解が明確に除外ってw
https://www.ioi-jp.org/ioi/ioi-syllabus_jp.pdf

中高生の「事情」に一般人が配慮する一般向けコンテスト
2021/07/30(金) 05:40:51.76ID:IQSK5lVc0
>>35
これはどう考え方？
ARCで前提にするつもりのテクニックはABCで出しておかないと
ARCがそのテクニックを学ぶための教育的コンテンツになってしまうし、ARCの位置づけはそうではないと思うんだが
一切出さないかABCでも出すかの二択しかないと思っていた

それはそうと実はCodeChef LunchtimeはIOIのシラバスに沿うというルールなんだよな
言うほど守られていないが
2021/07/30(金) 08:21:33.11ID:PogAvYGI0
>>37
ABCの600点(解けたらABC卒業;黄diff〜)
に少し難しいアルゴリズムを出すことは否定しない
2021/07/30(金) 08:51:15.74ID:IQSK5lVc0
>>38
なるほどだけど、少し難しいアルゴリズムが結果的に青dif以下になるなら点数にはこだわらなくていい気がするなあ
本当にフロー流すだけ、とかはIOIで除外されてるけど青ボーダーくらいになりそうだし500点ででても違和感がない
(そんなん出すなよ、というのは一理はある)
2021/07/30(金) 09:39:45.05ID:eRLzqDP1d
ZebranessとかGrid and Tokensは黄diffだったねえ
2021/07/30(金) 11:57:16.76ID:LzoN76F4r
アルゴリズムってなんでこんな仰々しい名前多いんだろ
連鎖行列積問題とか行列積コスト最小化問題って書いてたら、何となくやってること分かりそうなのにわざわざ難しく書く
2021/07/30(金) 12:07:52.74ID:VWDfYKRnM
matrix chain multiplicationの直訳だからじゃない
日本語だと仰々しいが英語だと簡潔
どっちも最適化する対象が名前からわからんけど
2021/07/30(金) 12:30:35.89ID:bjmh4Zft0
そもそもそれDPでとける問題の名前であってアルゴリズムの名前じゃなくない？
2021/07/30(金) 12:48:41.93ID:/5sK49wcM
行列積コスト最小化問題だと行列が3つ以上あるように見えないな
英語のchain要素は欲しい
2021/07/30(金) 12:55:36.34ID:KIwi+fa+0
行列鎖積が限界じゃない
方鎖積とか言い出すと意味が取れなくなって危険
46デフォルトの名無しさん (ｱｳｱｳｳｰ Sa09-4g3S)
垢版 |
2021/07/30(金) 13:25:31.86ID:l/bfPV+ta
こっちのスレ快適すぎだろ
47デフォルトの名無しさん (ｱｳｱｳｳｰ Sa09-hwgF)
垢版 |
2021/07/30(金) 14:20:47.89ID:jPC1M8tJa
もうあっち見てもいない。いい感じで隔離できたね
2021/07/30(金) 16:15:27.35ID:VUDtfB7pr
あっちはゴリラ
こっちは人間
2021/07/30(金) 16:23:38.23ID:a+QHJ9jSa
8問楽しみだ
1問1問にどこまで固執して良いのかな見極めが重要そう
50デフォルトの名無しさん (ｱｳｱｳｳｰ Sa09-hwgF)
垢版 |
2021/07/30(金) 16:39:52.14ID:UIn/rcGPa
500点問題が俺でも解ける難易度になってて欲しい
2021/07/30(金) 16:53:52.14ID:BqYo6PZ7a
緑〜水difの問題生やすの難しそうだよな…Writerは頑張って欲しい
2021/07/30(金) 17:06:49.79ID:J3jLSZNL0
詰まらず、より早く解くのが求められそう
2021/07/30(金) 17:24:29.61ID:nNXXdoxJ0
D以降全部青以上とかいう地獄ありそう
2021/07/30(金) 18:12:36.05ID:r2r5v8sO0
どうせすぐに灰灰灰灰黄黄黄黄になるでしょ
55デフォルトの名無しさん (ﾜｯﾁｮｲ ce6f-ZkVx)
垢版 |
2021/07/30(金) 18:48:08.28ID:TtoKf80P0
そういえば4問ABCから6問ABCに変わった初回はunratedになったのを思い出した
今回も参加者増えてジャッジ詰まらないか心配
2021/07/30(金) 19:26:16.88ID:UeHBykXW0
今回参加者増える要因ある？
57デフォルトの名無しさん (ｵｯﾍﾟｹ Sr05-Czf9)
垢版 |
2021/07/30(金) 20:04:52.00ID:AkwBGTPYr
171 仕様書無しさん sage 2021/07/30(金) 19:51:47.26
IDありの方でいい感じに自演してるけど楽しい
こっち見てない人多そうだししばらくバレなそう
2021/07/30(金) 20:09:14.34ID:fkO8fI5R0
ここまで自演
2021/07/30(金) 20:11:41.00ID:06AAPmWW0
今日は yukicoder と Educational なこどふぉです
2021/07/30(金) 20:19:42.93ID:gwTMj6/EM
まあIDなしスレの方でこのスレについて適当に煽るやつが出てくるのも自然ななりゆきだな
61デフォルトの名無しさん (ｱｳｱｳｳｰ Sa09-hwgF)
垢版 |
2021/07/30(金) 20:25:20.61ID:8us7N61Da
20年前の2ちゃんねらーみたいなやつやな
2021/07/30(金) 20:49:35.78ID:YHXdGG5Q0
ABCとインド被ってて困る
2021/07/30(金) 22:55:21.88ID:06AAPmWW0
ABC unrated なら インド優先でいいんでないか
トーナメントは知らん
2021/07/31(土) 03:23:13.88ID:OipI3A3d0
直近コドフォAの考え方教えてください
自分は小中大のスライスの数が3:4:5なので、その辺りから必要な枚数をO(1)で導こうとしたのですがうまくいきませんでした
答えが小中大の枚数に関わらず(n+1)/2*5だなとわかった人はどんな発想でそうなったのか知りたいです
よろしくお願いします
ちなみに関係ないかも知れませんが女子中学生です
2021/07/31(土) 04:01:37.36ID:jolcKo8x0
>>64
小中大も単位枚数当たりにかかる時間が同じ

拡張ユークリッド互除法の観点から、ある程度大きな数の偶数は、6 と 8 のペアの組み合わせで作れるみたいなのがある (実際には 6 以上の整数すべてが 3 つのペアから作れる)
2021/07/31(土) 13:03:20.38ID:ZaIYwuCyM
8問ABCか
黄パフォラインは1-2-3-4-5-6の組み合わせで6完とかかな？
2021/07/31(土) 17:02:23.83ID:bng3vbJSa
確かに重い5を飛ばすかの駆け引きがありそうだね
2021/07/31(土) 17:08:23.85ID:ZSov+pKMr
4問から6問への移行のときも参加者増えてたし今日は少なくとも9000人は参加しそう
多けりゃ1万
2021/07/31(土) 17:11:58.52ID:yD4XB78k0
4問から6問のときはrated対象変化のほうが大きそう
今回はそこまで変わらないと予想
70デフォルトの名無しさん (ｱｳｱｳｳｰ Sa09-hwgF)
垢版 |
2021/07/31(土) 17:36:59.59ID:etGBbmq6a
問題数の多さに嫌気さして減るまであるかもね。実質何にも変わらないとしても
2021/07/31(土) 19:38:43.84ID:m+/rETnzM
6解いて55に逆転の目があるの面白そう
2021/07/31(土) 20:22:45.64ID:VGaEoFb90
解説放送、スタイル変えないなら深夜3時コースじゃん
73デフォルトの名無しさん (ｱｳｱｳｳｰ Sa09-hwgF)
垢版 |
2021/07/31(土) 20:57:07.06ID:ZzHXwKHIa
snukeさんだけ貧乏くじか
2021/07/31(土) 22:47:17.01ID:OqsC7QEbM
問題多い方が満足感あるな
2021/07/31(土) 22:57:12.04ID:OqsC7QEbM
Fが実装難でGが数論の中レベル典型という感じで難度逆転か
数学問はAtCoderだとみんな解くからね
2021/07/31(土) 23:13:47.64ID:eAG/1XYN0
Fが実装辛すぎて震撼してたが、終わってみるとこれに数十分掛けてるようでは。。という気持ちになるんだよな
実装難問題はだいたいそうなんだけど
77デフォルトの名無しさん (ﾜｯﾁｮｲ 917f-8s23)
垢版 |
2021/07/31(土) 23:24:16.55ID:6TJMuv8N0
今日の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)に替えたら全部通った。
ドンマイ、俺
2021/07/31(土) 23:26:47.79ID:xfGVog4d0
つまらない実装ミスでF問題落として魂抜けた
ちゃんと大きめのサンプル作って試していればよかったのに
2021/07/31(土) 23:30:49.78ID:yD4XB78k0
Aの提出者数8554 -> 7822か
700人くらい減ったな
2021/08/01(日) 01:22:54.26ID:toXZwxGF0
ratedの人でGH解けてる人どれくらいいるのかな
2021/08/01(日) 02:31:32.43ID:GpOyqzVF0
G は知識があればなんとかなる
H は畳み込みをブラックボックスとして使ってた人は厳しいかも
2021/08/01(日) 09:27:39.31ID:KMs8EVD40
rated だけど E までは簡単で考察も実装も F より G の方が軽かったし、G は無限人解けてそう
H は知らん
2021/08/01(日) 12:54:17.89ID:rnLvS3mlM
難易度若干シグモイドっぽいの解消して欲しいな(難しいとは思うが)
2021/08/01(日) 13:06:46.38ID:j6FSUO0IM
Gは位数とか原始根みたいなちょっと進んだ整数論を学んでたら知ってるような概念割とそのまんまなので、考察負荷も確かにそんな高くない
Fも考察の本体は「あるバスに乗ったあとに乗るバスがあるとすれば一意に定まる」に気づいて超頂点を作るだけな気がするけど、ダブリング二分探索みたいなおまけ部分が重い
AtCoderで重実装問の後ろに軽い数学問出したらそらそっちに流れるわなという
2021/08/01(日) 13:12:02.99ID:j6FSUO0IM
>>83
C茶、D緑、E水、F青を目指してたんだろうなと思ってる
CDEはその点ちょっとブレただけで割と悪くないのでは？
Fは運営がユーザーの実装力を過大評価してたといういつものやつ
2021/08/01(日) 13:16:27.48ID:rnLvS3mlM
>>85
いまグラフ作ってたんだけどまさにその通りだったわ

https://i.imgur.com/tQx8HP0.jpg

Fがもう少し低ければめちゃくちゃいい勾配のセットだったんだな、惜しい
2021/08/01(日) 13:52:43.24ID:j6FSUO0IM
>>86
やっぱFだけおかしいね
どうすりゃよかったんだろう
最初から逆有向森？みたいなのを明示的に与えてあげるか、バスに乗ってる時間を無視してよいとするか
2021/08/01(日) 14:19:38.51ID:yuCAK+tE0
Fは100分6問のFならもっと解かれたはず
解けそうなやつがGにいっただけ
2021/08/01(日) 14:28:11.54ID:4sSkABKe0
fとgの逆転は120分にすれば解消されそうだけど
2021/08/01(日) 14:37:52.06ID:eHM3Q9HLa
同程度の難易度の問題が500と600にあったらコスパ良い600の方が解かれるのは当然
600の方がちょっと難しかったとしても、つまり難易度は逆転していないとしても、diffが逆転することは全然ありうるよな
そういう意味でdiffを重視しすぎるのはどうかと思う
2021/08/01(日) 14:55:17.34ID:lPTv7IAJM
今回のE問題までのほぼ直線的に解いていくしかないような問題配置以外では、diffは問題難度を評価する指標として微妙だとは思う
2021/08/01(日) 15:02:20.30ID:rnLvS3mlM
確かにこの難易度帯が解ける人にとっては実装が重そうなこの問題よりも発想さえ出来れば解ける得点が高い方に流れるか

そうなると問題数増えて時間同じままだから、実装重い問題は忌避されていくんだろうなあ
2021/08/01(日) 15:34:31.35ID:WPaM0mKIM
問題単体の難易度をより正確に評価できるようなdiffに代わる指標ってありうるかな？
diffの定義式にちょっと変更を加えるとかでも
2021/08/01(日) 16:43:17.71ID:/zE4Aaexa
昨日のE解けなかったのめちゃくちゃ悔しいわ
だいぶ冷えた
2021/08/01(日) 16:43:25.60ID:/zE4Aaexa
昨日のE解けなかったのめちゃくちゃ悔しいわ
だいぶ冷えた
2021/08/01(日) 16:45:08.09ID:yuCAK+tE0
大事なことなので2回言いました
2021/08/01(日) 16:51:09.60ID:rylMcfQtM
Eは俺はTDPC-Rグラフの変形だと思って解いたね
全頂点対だとO(N^3 logK)だけど一頂点対についての問題だから大分計算量節約できそう的な
2021/08/01(日) 17:26:18.55ID:4sSkABKe0
tdpc-rってsccしてdag作ってトポロジカルソートするやつじゃなかったっけ？
共通点が見えんけど
2021/08/01(日) 17:27:02.35ID:wjFVnr2/0
Heuristicの方ってABC全完できるくらいの地力ないと難しいかな？
楽しそうだけど実装の方針がよく分からないです
2021/08/01(日) 17:29:40.55ID:GpOyqzVF0
多分 EDPC R と間違えてる
自分には補グラフの形式で与えられてることが本質だと思った
2021/08/01(日) 17:33:35.53ID:rylMcfQtM
>>98
マジだ
すまん、EDPC-Rのwalkの方だな
どっちもRで大体この辺にあったグラフの問題だよなあって感じで覚えてて、問題開いてよく確認してないから間違えた
2021/08/01(日) 17:41:14.99ID:rylMcfQtM
遷移の節約がメインって考えると確かに補グラフが本質か
むしろ行列累乗の発想を使えないからwalkの本質的な部分とは遠いかもしれない
そもそも俺はDPを一から生やすのが苦手な方だから、DPのテンプレとして既知問題が役に立ったという感じかな
2021/08/01(日) 17:47:22.80ID:rylMcfQtM
>>99
俺もheuristic全然できないけどそんなことはなさそう
基本的なアルゴリズムの組み合わせで解を探索してあげるのが主だからそんなに高度な知識はいらないって聞いたことがある
2021/08/01(日) 18:46:28.69ID:OuCRXDXt0
ナップサックだと嘘になるような貪欲でもheuristicだと十分な解法になり得る
ちゃんとした貪欲が書けるだけどもかなり強いよ
2021/08/01(日) 23:17:01.04ID:SzlISrEQ0
コドフォやります
2021/08/02(月) 00:06:59.46ID:HCiXaFZK0
>>99
Heuristicsは貪欲書けてBFSとDFSができれば何もできないってことはまずないと思う
あとは勇気を持って噓貪欲書いて、結果をビジュアライザで見ながら改善していけばいい
2021/08/02(月) 02:04:52.64ID:wQG5EWK+0
クエリのやつABCで復習したのですんなり解けてうれしい
2021/08/02(月) 02:24:36.26ID:9vrfDka+0
おめでとう
2021/08/02(月) 04:57:00.13ID:wQG5EWK+0
制約がn=2*10^5とかで想定解がO(n)なのって出題者の優しさでしょうか
それとも定数倍とかの関係？
O(nlogn)解で通った人←
2021/08/02(月) 05:19:48.94ID:9vrfDka+0
N と NlogN の区別はなかなか厳しいことが知られております
N 個の入力を与える問題なら問題を解くより入出力を捌く時間の方がネックになるなんてこともある
2021/08/02(月) 12:15:14.37ID:YwN/bnngM
入出力数がO(n)ならn=10^7とかにするとそこがボトルネックになって非本質ゲーになりがち
あと遅い言語でO(n log n)落としてO(n)通すように設計するとC++ではO(n log n)が普通に通るなんてことがある
logを落とす力を評価するコンテストサイトもあるっぽいけど、AtCoderは入出力ゲーとか言語格差とかそんなに好きじゃないのであまりそういう力は問わない
2021/08/02(月) 12:50:39.03ID:LBPYCkqw0
一応ABC189-Cがlogの有無を意図してるっぽい
2021/08/02(月) 14:48:31.21ID:ayT6z8jYr
POJで鍛えなさい
2021/08/02(月) 18:36:35.29ID:8AKddLB+0
logは2つつくとめちゃくちゃ速度落ちるよね
2021/08/02(月) 19:53:01.87ID:YwN/bnngM
セグ木上の二分探索とかlog二つをlog一つに落とせて嬉しいパターンが結構ある気がする
2021/08/02(月) 20:48:14.11ID:GApG+yr20
https://atcoder.jp/contests/abc208/tasks/abc208_f
これは割と変なlogつけると通らないんじゃないかな
2021/08/02(月) 22:33:06.34ID:LBPYCkqw0
logって2つあるほうが早いんじゃないんです？
2021/08/02(月) 23:02:50.81ID:Tt09fpMhH
log x × log xのことじゃね
log log xではなく
2021/08/03(火) 13:47:56.92ID:8JvOP1wgM
最近競プロで必要そうな知識を整理してて、集めるとそれなりの分量になるなと思った反面、AGCの難問には基本的な知識しか問わないけど難しいものが結構あるよね
多分知識入れただけじゃ解けるようにならなそう
どうやって練習してる？
2021/08/03(火) 19:10:08.89ID:0jHwVPOe0
天才以外お断りパズルコンテストだぞ
2021/08/03(火) 19:24:48.79ID:kh8UNFwQ0
高1でatcoder赤になった奴、東進全統高で上級生抑えて一位だな。
プログラミングと受験勉強の配分はどうなってるんだ?
2021/08/03(火) 19:48:26.20ID:S/rr5p7AM
全方向に才能が溢れていた結果としてAtCoder赤になったのであれば、受験勉強も軽くクリアできてもそんなに不思議じゃない
2021/08/03(火) 19:54:23.17ID:Knm+pPdg0
AGCもなんだかんだで練習量でそこそこ溶けるまでは解ける
個別の練習はやってないや
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況