競技プログラミング総合スレ 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/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もなんだかんだで練習量でそこそこ溶けるまでは解ける
個別の練習はやってないや
2021/08/03(火) 19:55:24.31ID:Knm+pPdg0
✕　溶けるまでは解ける
◯　解ける
2021/08/03(火) 20:12:18.13ID:k75IS9uU0
>>119
https://www.oreilly.co.jp/books/9784873114057/
読んだことある？
2021/08/03(火) 20:41:09.91ID:S/rr5p7AM
>>123
結局演習量という話はよく聞くね

>>125
ありがとう、読んだことないや
目次を見たけどかなり競プロと相性がよさそうだね
2021/08/03(火) 22:19:00.93ID:0sSYM0/y0
なんかのめり込んでる時期はAGC全然勝てなかったけど一旦離れてたらいい感じに力抜けて苦手意識なくなったな
2021/08/04(水) 00:02:03.33ID:t30SArGP0
あるある
めちゃくちゃやってた時期よりもレート伸びてるわ今
2021/08/04(水) 13:37:25.83ID:PT9ISTH50
ここしばらくコンテストしか出てないけどレートなんやかんや上がってるわ
2021/08/04(水) 22:11:47.50ID:BC2fUSktM
エレガントな問題解決ポチった
数オリの問題も結構含まれてるっぽくて楽しみ
2021/08/05(木) 02:17:05.07ID:StUL0nUY0
>>130
英語版の公式サイトに解説マニュアルあるよ。載ってるのは選ばれた問題だけだけど
2021/08/05(木) 20:50:38.29ID:IgsNgOEp0
PaizaってAからやたら計算量ギリギリな問題が多くなる気がする...
TLEで一発終了なのがキツい
2021/08/06(金) 21:22:03.99ID:eJxIR3k1M
>>131
ありがとう
届いたから読んでるけどまさに算数パズルという感じの問題が集まってて面白い
普通に演習問題の中に難しいのも結構あるから世話になるかも
2021/08/07(土) 12:48:17.49ID:tc9pz7jrr
132だけどやっとA取れました...
茶色になった記念でpaizaに挑戦したけど意外と苦戦した

Aの美術館のセキュリティって問題でasin,acosが出てきて三角関数の逆関数の使い方を色々学べて楽しかった(これだけじゃネタバレにならんと思う)
asinは終域が-π/2〜π/2で全単射
acosは終域が0〜πで全単射だからモジュールの仕様で出てくるradianに気をつけないといけないんよね
2021/08/07(土) 14:56:20.68ID:xkx44HTf0
paizaの問題は話さん方がいいよ
2021/08/07(土) 15:00:37.61ID:m+E3Az4E0
ぶっちゃけアウト臭い書き込み
2021/08/07(土) 15:16:31.01ID:m3lfMST8M
解答の本質とは関係ないぐらいの書き込みなんだろうから直ちにアウトってレベルじゃないと信じるけど、事前に要求知識が分かるだけでも微妙なのでやめといた方がいいと思う
あれ提出までの時間も評価対象だし
2021/08/07(土) 15:32:05.34ID:zSH+M8IW0
一切言及しないほうが無難
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況