競技プログラミング総合スレ 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/07/31(土) 17:02:23.83

確かに重い5を飛ばすかの駆け引きがありそうだね

2021/07/31(土) 17:08:23.85

4問から6問への移行のときも参加者増えてたし今日は少なくとも9000人は参加しそう
多けりゃ1万

2021/07/31(土) 17:11:58.52

4問から6問のときはrated対象変化のほうが大きそう
今回はそこまで変わらないと予想

2021/07/31(土) 17:36:59.59

問題数の多さに嫌気さして減るまであるかもね。実質何にも変わらないとしても

2021/07/31(土) 19:38:43.84

6解いて55に逆転の目があるの面白そう

2021/07/31(土) 20:22:45.64

解説放送、スタイル変えないなら深夜3時コースじゃん

2021/07/31(土) 20:57:07.06

snukeさんだけ貧乏くじか

2021/07/31(土) 22:47:17.01

問題多い方が満足感あるな

2021/07/31(土) 22:57:12.04

Fが実装難でGが数論の中レベル典型という感じで難度逆転か
数学問はAtCoderだとみんな解くからね

2021/07/31(土) 23:13:47.64

Fが実装辛すぎて震撼してたが、終わってみるとこれに数十分掛けてるようでは。。という気持ちになるんだよな
実装難問題はだいたいそうなんだけど

2021/07/31(土) 23:24:16.55

今日の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.79

つまらない実装ミスでF問題落として魂抜けた
ちゃんと大きめのサンプル作って試していればよかったのに

2021/07/31(土) 23:30:49.78

Aの提出者数8554 -> 7822か
700人くらい減ったな

2021/08/01(日) 01:22:54.26

ratedの人でGH解けてる人どれくらいいるのかな

2021/08/01(日) 02:31:32.43

G は知識があればなんとかなる
H は畳み込みをブラックボックスとして使ってた人は厳しいかも

2021/08/01(日) 09:27:39.31

rated だけど E までは簡単で考察も実装も F より G の方が軽かったし、G は無限人解けてそう
H は知らん

2021/08/01(日) 12:54:17.89

難易度若干シグモイドっぽいの解消して欲しいな(難しいとは思うが)

2021/08/01(日) 13:06:46.38

Gは位数とか原始根みたいなちょっと進んだ整数論を学んでたら知ってるような概念割とそのまんまなので、考察負荷も確かにそんな高くない
Fも考察の本体は「あるバスに乗ったあとに乗るバスがあるとすれば一意に定まる」に気づいて超頂点を作るだけな気がするけど、ダブリング二分探索みたいなおまけ部分が重い
AtCoderで重実装問の後ろに軽い数学問出したらそらそっちに流れるわなという

2021/08/01(日) 13:12:02.99

>>83
C茶、D緑、E水、F青を目指してたんだろうなと思ってる
CDEはその点ちょっとブレただけで割と悪くないのでは？
Fは運営がユーザーの実装力を過大評価してたといういつものやつ

2021/08/01(日) 13:16:27.48

>>85
いまグラフ作ってたんだけどまさにその通りだったわ

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

Fがもう少し低ければめちゃくちゃいい勾配のセットだったんだな、惜しい

2021/08/01(日) 13:52:43.24

>>86
やっぱFだけおかしいね
どうすりゃよかったんだろう
最初から逆有向森？みたいなのを明示的に与えてあげるか、バスに乗ってる時間を無視してよいとするか

2021/08/01(日) 14:19:38.51

Fは100分6問のFならもっと解かれたはず
解けそうなやつがGにいっただけ

2021/08/01(日) 14:28:11.54

fとgの逆転は120分にすれば解消されそうだけど

2021/08/01(日) 14:37:52.06

同程度の難易度の問題が500と600にあったらコスパ良い600の方が解かれるのは当然
600の方がちょっと難しかったとしても、つまり難易度は逆転していないとしても、diffが逆転することは全然ありうるよな
そういう意味でdiffを重視しすぎるのはどうかと思う

2021/08/01(日) 14:55:17.34

今回のE問題までのほぼ直線的に解いていくしかないような問題配置以外では、diffは問題難度を評価する指標として微妙だとは思う

2021/08/01(日) 15:02:20.30

確かにこの難易度帯が解ける人にとっては実装が重そうなこの問題よりも発想さえ出来れば解ける得点が高い方に流れるか

そうなると問題数増えて時間同じままだから、実装重い問題は忌避されていくんだろうなあ

2021/08/01(日) 15:34:31.35

問題単体の難易度をより正確に評価できるようなdiffに代わる指標ってありうるかな？
diffの定義式にちょっと変更を加えるとかでも

2021/08/01(日) 16:43:17.71

昨日のE解けなかったのめちゃくちゃ悔しいわ
だいぶ冷えた

2021/08/01(日) 16:43:25.60

昨日のE解けなかったのめちゃくちゃ悔しいわ
だいぶ冷えた

2021/08/01(日) 16:45:08.09

大事なことなので2回言いました

2021/08/01(日) 16:51:09.60

Eは俺はTDPC-Rグラフの変形だと思って解いたね
全頂点対だとO(N^3 logK)だけど一頂点対についての問題だから大分計算量節約できそう的な

2021/08/01(日) 17:26:18.55

tdpc-rってsccしてdag作ってトポロジカルソートするやつじゃなかったっけ？
共通点が見えんけど

2021/08/01(日) 17:27:02.35

Heuristicの方ってABC全完できるくらいの地力ないと難しいかな？
楽しそうだけど実装の方針がよく分からないです

2021/08/01(日) 17:29:40.55

多分 EDPC R と間違えてる
自分には補グラフの形式で与えられてることが本質だと思った

2021/08/01(日) 17:33:35.53

>>98
マジだ
すまん、EDPC-Rのwalkの方だな
どっちもRで大体この辺にあったグラフの問題だよなあって感じで覚えてて、問題開いてよく確認してないから間違えた

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になるから全完多めでも問題ないはずなんだよな