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

2022/12/26(月) 12:47:37.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/

※前スレ
競技プログラミング総合スレ 64
https://mevius.5ch.net/test/read.cgi/tech/1664700238/

VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

2023/02/19(日) 14:04:10.80

想像しているようなそっくりな問題を解いたことがあるみたいな話ではないけど（多分上位層は初見でも2分で解ける）、何個かの要素に分解できるところはあるかな

・偶奇に注目、二つ裏返すということは1は偶数個じゃなきゃダメ
・自明な下界を考える、2つ以上離れた1のペアを作れれば達成できる
・1が2個のときはコーナーケースっぽい、特に小さいケースについてはなるべく注意した方がいい

こういうのをできる人は無意識に一瞬でやってるから、何をいまさら言語化しているんだって感じだろうけど

2023/02/19(日) 14:13:36.32

ある意味ARC典型みたいなところがあるかな
Cも自明な下界を考える問題だったし、Bは貪欲にある数まで下から埋めたあと分配する問題で、賢い筋を一つ見つけて他の筋を枝刈りするタイプの問題が多い

2023/02/19(日) 15:26:29.04

AはARC-Aに置かれてると条件は基本的にシンプルになるけどたまに場合分けを要求されるみたいな雰囲気を感じ取れる(いつかのこどふぉで全く同じコーナーケースに注意すべき問題もあった)し、Bも条件の厳しいものからあらかじめ決めておいて残りは重複組み合わせ等で簡単に処理するっていう考え方をARCで何回か既に見たからARC典型みたいなのは問題を解き進めてるうちに身につくと思う
Aのパリティとか不変量とか上界下界に注目するみたいな典型考察も含めて(鉄則本とかにも書かれてるくらい典型だからもう既に知ってる人の方が多そうだけど)

2023/02/19(日) 16:44:56.04

>>634
貴重な情報ありがとうございます

ARC-Aクラスの難易度はまだ無理ですが
ABC-Cならなんとか解けることもあるので

＞＞問題を解き進めてるうちに身につく

ことを信じて自力で解ける範囲で少しづつやってみます

2023/02/19(日) 17:45:36.48

緑だけどARCは不出場になった、青以上じゃないと時間の無駄になる気が

2023/02/19(日) 18:07:28.78

昨日のC、類以度いくつ達成できそうかは手元で実験してすぐ分かったけど、
すべてのケースで条件満たす構築が結局コンテスト中にできなかった
どうやって思いつくのあれ

2023/02/19(日) 18:34:54.00

類以度が2以上になるのはどういうときかを考えたら思い付いた

2023/02/19(日) 19:58:25.28

パスの場合1通りしか答えないからその理由考えて適当に一般化

2023/02/19(日) 20:02:27.76

パス上でオリジナルの数字とPで変換して出てくる数字で被りがあるとうざそう→適当に木を二分割して移し替えればよくね？→頂点数の偏りが少ない分割がほしいから重心を使う
パス上でオリジナルの数字とペアとPで変換して出てくる数字のペアの相対的な前後関係が一致してるとうざそう→重心からの位置関係がオリジナルと反転してればよくね？

想定解はちゃんと読んでない

2023/02/19(日) 20:04:27.80

>>636
今回のAは解ける問題だった気がするが

2023/02/19(日) 20:10:26.59

400点のARC-Aは厳しい問題な可能性が高いな
なんなら500点のARC-Bより人によってはとっつきにくい
300点のARC-Aはそこまで異常問題ではないことが多いはず
ABC-Cよりはずっとムズいけど

2023/02/19(日) 22:40:53.59

5完
Dでバグりすぎた…

2023/02/19(日) 22:43:01.55

Eまで早解き出来てFもO(N)で求められる式の導出までは出来たのにそこからの式変形がダメだった　勿体無い

2023/02/19(日) 22:46:42.14

FよりGの方が簡単かな

2023/02/19(日) 22:52:00.36

Gは貪欲でよさそうなことにさえ気付ければ実装も楽でかなり解きやすいな

2023/02/19(日) 22:55:52.45

Fもいわゆる自明な上界問題っぽいし、今回も結構ARCチックだった
地味にDもこの位置では難しいのかも？と思ったけど結構みんな解けてるね

2023/02/19(日) 22:57:21.27

そしてExがかなりの難問っぽいね

2023/02/19(日) 22:59:11.51

Gの貪欲が証明できん
これしかないだろと思って投げたから通りはしたが

2023/02/19(日) 23:02:45.64

俺も証明してない
とりあえず、深さ2ぐらいまでf(x,n)（n個の部分木と接続したままxを作るときの最小コスト）みたいなのを考えたらnがなるべく小さいほうがいいことに気付いて、またxで単調減少しそうだから、どうせ親にも性質が伝播するんだろうなあみたいな考えでやった

2023/02/19(日) 23:03:01.88

F非想定解とはいえ畳み込みやらFPSやらをやればO(N)の式を高速化出来たっぽいしちゃんと履修すべきだったな
自分は普段はFくらいまでしか解けないからまだ要求されないもんだと思って後回しにしてたけどこういう時に殴れないの勿体ない

2023/02/19(日) 23:04:53.51

DのサンプルだけACしたけど
そりゃ提出しても愚直解だとTLEですよね
解説見たけどこんな条件気づける気がしない
考え方の方向性は間違ってないけどここまでが自力の限界ぽい

2023/02/19(日) 23:06:53.95

知識を取り入れてABCでレート上げるのはARC/AGCでレート上げるより楽なので、どんどん高度な知識を取り入れていいと思うな

2023/02/19(日) 23:09:33.70

>>652
Dは典型ではあるからこれを機に知っておくといいと思うよ
(N/GCD(N,D))*Dで初めてNで割ったときあまり0のところに戻ってくる
こういう操作はかなり頻出だと思う

2023/02/19(日) 23:14:10.61

OEIS使う裏技は知ってたけどwolfram alpha使う裏技もあるんだな
wolfram alpha の計算式にはガンマ関数とかsqrt(pi)が出てきたから自分で更に式変形する必要はあるけど今度から使えそうな場面では試してみよう

2023/02/19(日) 23:15:02.27

ありがとうございます
解説見ても頭に入ってこないというか難解過ぎて咀嚼出来ない？ので
時間のある時に落ち着いてじっくり考察してみます

2023/02/19(日) 23:22:11.62

D、解説が難しいし何の役にも立たないので理解する気力がわかない・・・

2023/02/19(日) 23:22:37.30

wolfram alphaを使うプレースタイルだとΓ(1/2) = √πみたいな知識も役に立つのかな
総合格闘技感があって面白い

2023/02/19(日) 23:34:24.39

Dは例えばN = 15, D = 6としよう
〇××××××××××××××
一旦、x+1に移るルールを無視して、4移動してマーキングするというルールで考える
〇×××××〇××××××××
〇×××××〇×××××〇××
〇××〇××〇×××××〇××
〇××〇××〇××〇××〇××
〇××〇××〇××〇××〇××
〇××〇××〇××〇××〇××

と、間隔3の場所を延々と巡ることになる
NとDが他の値でも似たようなことが起きて、この間隔が実はGCD(N,D)で簡単に出せる

2023/02/19(日) 23:35:10.23

>>659
ミス、4移動じゃなくて6移動

で、実際のルールでは、マーキング済みのところについたら1ズレるわけだけど
実はいつも最初は0に戻ってくることが分かって、
〇〇×〇××〇××〇××〇××
って感じ
上のと同じ動き方で1と間隔3で離れている場所が全部埋まる
〇〇×〇〇×〇〇×〇〇×〇〇×
全部埋まった後に1に戻ってきて今度は2に移って同じことをする

2023/02/19(日) 23:40:08.29

何の役に立つかというと、直接的に役に立つ気はしなくて、頭の体操感あるかなあ
でもこういう比較的複雑ではない方のアルゴリズムに慣れておくと、複雑なアルゴリズムを頭の中ですぐイメージできるような気がするね

2023/02/19(日) 23:42:32.81

Dのax-by=0みたいな式を立てた上でgcd(a,b)で全体を割ることで互いに素であることが利用できるようになって一般解が求まる、みたいなのはABCのD、Eくらいで何回も出題されてるだけでなく受験数学でも典型ではありそう

2023/02/19(日) 23:44:04.64

例えば今回のEまではパターンマッチングで瞬殺だけどそれだと寒色止まりだしつまりはそういうことだ

2023/02/19(日) 23:44:43.08

>>661
あ、すまん、文章のパースミスってて、D問題が何の役にも立たない話かと思った
解説で理解できないって話ね

2023/02/19(日) 23:46:01.21

Gも貪欲でいいという点で確かにARCっぽいのかな？

2023/02/20(月) 00:48:04.55

微積分も知らずに青まで行ける方がヘンだと思うので特殊関数も出すべきじゃ

2023/02/20(月) 20:17:16.00

>>659
分かりやすい解説ありがとうございます

こういう図解が解説に無い時に
解説の文章にある数式（今回だとgcd(n,d)など）から
自力で何をしているのかシミュレーションを想像するまで辿り着けないんですよね
時々図解がある解説見るとスッと頭に入ることあるのでそういう時は助かります
単純に競プロや難易度に必要な基礎学力や経験が足りてないんだとは思います

2023/02/20(月) 20:19:39.00

過去問題だとほぼ解説動画あるので大体解説動画見てますね

2023/02/20(月) 23:07:52.80

Dは@kyopro_friends氏がtwitterに図説を上げてるよ
あと解説放送も今やってるよ
最近はコンテスト翌日ぐらいにやってることが多い

2023/02/23(木) 07:31:29.61

>>669
ありがとうございます

＞＞最近はコンテスト翌日ぐらいにやってることが多い
それは知りませんでした
お忙しいので動画無いのかなとか思ってました
あと@kyopro_friends氏さんってatcoder内部の方ですか？

やっとAB問題埋め全完了して
C問題を順番にやろうと思ったけどテーマがバラバラなので集中出来ないと思ったので
鉄則本を少しづつ進めつつそのテーマに沿ったtagに集中するようにしたら
勉強がやりやすくなった気がします

ただ時間が中々取れないので週末だけだと覚えたと思ってたこともすぐに忘れてしまう
生まれつき記憶力のある人が羨ましい

2023/02/23(木) 15:59:11.87

フレンズさんは作問バイトの一人のはず
内部の人ではないけど作問には関わってる

2023/02/23(木) 21:26:34.11

バイトは内部の人とちゃうの

2023/02/23(木) 22:20:45.10

バイトも雇用契約を結んでる従業員なんだから、立派な内部のひとだろ
バイトを外部のひと扱いにしたら世の中が大変なことになるぞ

2023/02/23(木) 22:42:49.92

必要なのはAIのエンジニアであって、競プロerなんて時代遅れだよ
今後は機械学習を開発する力を面接でも重視する
そういう方針にするからこそレガシーエンジニアのレイオフを思い切ってやれてる

2023/02/23(木) 22:51:30.93

chatGTPに使われてるtransfomerは全く教プロと関係ない。
強化学習はヒューリスティックで活用できる人がいるかもくらいで、ノーマルコンテストには縁がない。

**674** (ﾍﾞｰｲﾓ MM2b-L4qV) · 2023/02/23(木) 23:01:59.48

誤爆ですごめんなさい

2023/02/24(金) 17:34:08.73

>>671
やはりそうでしたか
解説動画が出る前に要点がまとめられていて図解があって分かりやすくて良いですね
これ見てすぐに理解できないならまだその問題を解くレベルに達していないと判断しやすいです

2023/02/24(金) 17:45:00.38

GCJが無くなるってことはどういうことなんでしょうか？
Googleが教プロは将来的に継続する程の費用対効果が得られないと判断したという解釈とか？
上位入賞者に米国人がいなくて海外勢特に中国人だらけだから面白くないとか？
ChatGPTに対抗する為にコストやリソースをそっちに集中したいとか？

2023/02/24(金) 18:05:59.77

すべてありえそうだけど最大の理由は「そもそも採用に力を入れていない」でしょうね
レイオフしまくってるし

2023/02/24(金) 19:02:57.49

>>679
なるほどですね
昨年からだと世界的に数十万人レイオフですか
上位数%の優秀な人しかいらないってことなのかな

2023/02/24(金) 20:55:11.73

コロナ禍にIT投資が過熱して採り過ぎちゃったし
いまは急に市況が悪くなって人件費と今後しばらくのリターンが見合わないから、解雇するんすよ

日本にいるとそれほど意識しないかもしれないけど
世界的にはこれから長い長い不景気に突入する空気感

2023/02/24(金) 21:47:19.51

寂しいけどGoogleがもう普通に兢プロに価値見出してないだけだと思うよ

2023/02/25(土) 00:41:17.79

フレームワークとライブラリが充実してきたので
あまりレベルの高い仕事はなくなってきたという感じか

2023/02/25(土) 23:00:26.14

ARCギャンブル初参加して約50分くらいでまぐれのA解けてラッキー
最速の人1分20秒と毎度のことながら驚愕

Bも行けそうかと手を付けたけどやはり難解過ぎて頭から湯気が出そう
残り時間も無いし解法も思いつかないので順位表見てたら
B飛ばしてCやってる人が多かったから多分Bは考えて解くのは難しいのだろう

Cも覗いてみたけど典型のテンプレ持っていれば解けるんだろうな
準備してなかったけど迷路探索のテンプレで
全探索してY隣接の最大値更新して間に合うのかな
でも流石にARCだから高速化を考えないと解けないようになってるのかな

時間切れまで暇つぶしの感想書いてみた

2023/02/25(土) 23:04:01.00

C、Bよりも簡単だった気がする(Bは罠が多すぎてWA複数回踏んだ)
Cの上位互換みたいな問題が数ヶ月前のABC-Gで出題されてたしそれ思い出したらすぐだった

2023/02/25(土) 23:13:22.62

普段のARCと比べると解きやすいが、AとBはコーナーケース踏んで死んだ

2023/02/25(土) 23:14:19.32

Cの解法は典型的な思考法ではあるが、典型のテンプレ持ってるから解けるみたいな話じゃないぞ

2023/02/25(土) 23:16:03.43

むずいよー

2023/02/25(土) 23:19:38.16

>>687
おっしゃる通りでございますね
解説見て無理だと悟りました

これはどんなに勉強しても理解出来るレベルに達する内容じゃないです
解説見て理解出来ないんだから本番で思いつくはずがない

2023/02/25(土) 23:19:52.87

ARC二連続で爆死して橙が遠退いた

2023/02/25(土) 23:32:25.54

やっと入茶出来たみたいです
まぐれARC1完で+60以上出てラッキー
直近がABC3完でも+5前後とかだったからびっくり
なんかもう入茶出来たから満足しちゃった

2023/02/25(土) 23:40:02.41

writerの人の印象から勝手にグラフアルゴリズムや最適化回になるかと思ったけど、数え上げメイン回だった
Fがそういうものなのかな？

2023/02/25(土) 23:41:12.36

>>691
おめでとう
典型パターンに習熟していないうちはARCの方がパフォーマンスが跳ねやすいと思う

2023/02/25(土) 23:49:34.61

鬼のように数え上げを出してくる某writer以外は出題分野そんな偏らない気がする
なんとなく個性は見えるけど

2023/02/25(土) 23:52:25.38

>>693
ありがとうございます
まぐれギャンブルで貰った+60なので
ABCずっと参加してC落としたりすればすぐに適正に収束すると思いますので
400切らないように頑張ります

2023/02/25(土) 23:56:17.38

こいつの日記になっとるな

2023/02/26(日) 00:29:44.52

>>695
今日のA解けたんならABC-Cは慣れれば安定して解けるようになると思う

2023/02/26(日) 01:15:14.28

Bの全てXかつK=0のケースが3つも入ってるっぽいんだけど注意力勝負すぎるしK>=1でも良かっただろとは思う
全てXとYを例外とさせるのはまだわかるけど

2023/02/26(日) 08:38:18.60

>>697
ありがとうございます
色々な勉強法あると思いますがマイペースが大事ぽいので
ストレスにならない程度に気長にコツコツやってみます

2023/02/26(日) 10:43:52.85

前半はコーナーケースを詰める力そのものを聞いてるんだろ、それ無かったらやるだけだし
自分もBは4ペナしたけど、この問題のコンセプト自体は否定しないぞ
好きか嫌いかなら嫌いだが

2023/02/26(日) 13:58:36.43

シンプルな問題設定と非自明なコーナーケース、もはやARC典型

2023/02/26(日) 14:00:40.00

2、3分でスモールテストケースでの愚直実験一通り回せるぐらいの腕力が欲しいところだな

2023/02/26(日) 22:41:20.91

6問早解き大会だった

2023/02/26(日) 22:41:34.84

ABC3完は出来ましたがみんなAC速すぎてパフォーマンスが出ないですね
参加してる人のレベルが高いというか
諦めて参加しなくなった人が多いのかな
参加人数も1万人いた頃に比べたら今アクティブ7千人弱くらいだし

Dって過去問か他コンステストで類題ありましたか？
C飛ばしてD速い段階でACしてるのにその人達がC解けないって意味が分からないから
もしかしたら有名な典型問題だったのかなと

2023/02/26(日) 22:45:10.92

Fまでの早解きゲーになっちゃったけどF1100人近くも通すもんなんだな
下振れた時が怖いしこれくらいの正答数のG、EXなら解ける域に早く達したい

2023/02/26(日) 22:47:09.49

Exでこんなにきれいに重心分解がそのまま出るとは意外だった

2023/02/26(日) 22:49:22.15

Gの方が考察の難易度的に難しいと思うけど、重心分解は知識レベルとしては高度という判断なのかな

2023/02/26(日) 22:51:29.63

今回のFはEと同じくらいの難易度だな
500点同士と600点同士で同程度の難易度の珍しいコンテスト

2023/02/26(日) 22:56:31.58

>>704
Dはかなり典型的なDPの問題だから類題はたくさんあるけど、Cより解きやすくなるってことはない気がするかなあ
まあでも問題の相性はあるからね

2023/02/26(日) 23:00:00.31

こんなん重心分解でしかないやろで投げたけど、ちゃんと証明してなかったな

2023/02/26(日) 23:07:18.29

>>709
そうなんですね
DPはチラ見したことありますが数問やって全く理解出来なかったので保留してます
まだ累積和とか二分探索すらよく分からないので鉄則本が全然進まない状態です
気長に理解できそうなとこからやってみます

2023/02/26(日) 23:08:10.19

xorやandやorの相互変換もたまに効く典型の印象
あと1bitの場合andが普通の積と一緒になるのも畳み込みと併用することを考えるとありがたいね

2023/02/26(日) 23:10:24.52

>>711
EDPCというコンテストの一番簡単なやつから理解していくのがいいかな
DPは慣れるまでが結構難しくて、慣れたらABCだとそんなに頭使わなくて済むようになる

2023/02/26(日) 23:14:40.03

Fって一般DAGでも解けるのか

2023/02/26(日) 23:16:04.01

D問題最初誤読して「全てのカードの表面に書かれてる数が異なる」って思って一瞬焦ったけどこの場合も解けたりする？既出っぽい気もするけど

2023/02/26(日) 23:20:28.91

>>713
ありがとうございます
今やりかけのもの終わったらまた少しDP覗いてみます

2023/02/26(日) 23:28:04.31

>>715
とりあえずグラフを考えて、カードをA_iとB_iをつなぐ辺とみなす
このグラフの各連結成分を見て、なもり木なら閉路部分の割当で2通り、木になってるんなら木DPでうまく数え上げて、それ以外は0通りみたいな感じにして、総積を取る感じか？
なんか既出感がすごいな

2023/02/26(日) 23:30:03.03

なもり木って書いたがなもりグラフか

2023/02/26(日) 23:37:20.19

>>717
カードの表裏をグラフの辺に帰着させて連結成分ごとに頑張るみたいな考え方で確かに出来そうだし典型的な考え方な気もするからこの設定の場合もABC-E、Fくらいに置いてあれば違和感無いな
今回はABC-Dだったからすぐ誤読に気づけたけど

2023/02/26(日) 23:39:18.11

Fで出て青diffのどこかって雰囲気の問題に見える

2023/03/02(木) 21:21:27.03

DP練習問題などいくつか試してみましたがほとんど理解出来ませんでした
シンプルな典型問題を解説写経ACするだけの繰り返しになっていて
初見の問題を見る都度解法が全く思いつかないしDPを全く組めません
コピペしても通るような典型くらいしかAC出来ませんので
本番初見問題では役に立たないと思います

EDPCは解説の入力が省略されていたり
写経してもDPや入力の配列の添字が分からずその間違いでWAやRE多発してしまいます
解説をコピペしても通らないものもあってかなり時間ロスしました
アルゴ式は導入問題くらいは図解も毎回あって分かるのですが
応用問題になると解説が概要とコードだけなので何故そうなるのかさっぱり理解出来ませんでした

多分相当長いこと典型をやり続けてひたすら慣れるしか無いのでしょうが
時間対効果というか達成感が全く無くストレスが貯まる一方でモチベが続かないので
やはりDPは後回しにすることにします

DPが理解できずに苦労したとか覚えるの大変とは聞いていましたが
やってみてそのとおりだと痛感しました

2023/03/02(木) 21:42:44.71

そうなんだおじさん「そうなんだ」

2023/03/03(金) 00:13:18.97

いちいちここで報告する必要ないんだよカス

2023/03/03(金) 01:13:35.32

いや、無駄に煽って荒らしたいやつのほうがカスだろ

2023/03/03(金) 01:29:49.23

カスを擁護するカスまで現れた
自演かもしれんが

2023/03/03(金) 01:42:44.95

解説を見ても理解できないDP練習問題ってなんだ？気になる

2023/03/03(金) 02:43:36.86

「判りませんでした。私は頭が悪いです。わーんわーんわん」って泣き言いう前に分からないとことか問題を貼ろう

2023/03/03(金) 03:46:50.79

多分初めのうちは、どういう時にDPを使ったら良いのか分からないって感じだと思うんだけど、
自分は昔「2^nの全探索が無理ならDP」って覚えた(最近だとABC291Dとかもこれ他にもたくさんあると思う)
2^nの全探索の処理を考えたら、添字に何持たせたら良いのか出てくる気がする
bitDPとか区間DPなどの○○DPは初めのうちにやると混乱するから、まずは↑を出来るようにすると良いと思う
あと、dp配列の定義をきちんと決めることが大事で、ふわふわしたままコードを書くと当然上手くいかない
例えば「dp[i][j]: [0, i)でj個選んだ時の最大値」みたいにコードを書く前にきちんと決める
(dp[i]は「[0, i](閉区間)の答え」とするよりも「[0, i)(開区間)の答え」とした方がコードが綺麗になることが多い)
後は問題をたくさん解けば慣れるはず

2023/03/03(金) 06:19:46.91

DPは、状態をまとめて管理したり、操作した結果部分問題に帰着するって考えるとわかりやすいと思う
たとえばそれぞれについて選ぶか選ばないかで 2^N 通りあると、選ぶ・選ばないを決めると 2 つの新しい部分問題に分かれて、
その結果を合成する必要があるけど、結局見るべき「状態」の種類は少ないからメモ化して突破できる～って感じ
添字はfor文の端っこを意識するとバグりにくくなると思う

2023/03/03(金) 06:51:28.66

EDPCはHがクソ簡単だからそこから始めるのも手だと思う
部分問題の合成結果が最終的な答えになるって感覚がわかりやすいし

2023/03/03(金) 09:26:45.13

わかるまで考える習慣がないだけじゃないの