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

■ このスレッドは過去ログ倉庫に格納されています
2022/12/26(月) 12:47:37.63ID:CkzYHyzir
!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/26(日) 23:07:18.29ID:P5+y9Ehh0
>>709
そうなんですね
DPはチラ見したことありますが数問やって全く理解出来なかったので保留してます
まだ累積和とか二分探索すらよく分からないので鉄則本が全然進まない状態です
気長に理解できそうなとこからやってみます
2023/02/26(日) 23:08:10.19ID:KteJNFXu0
xorやandやorの相互変換もたまに効く典型の印象
あと1bitの場合andが普通の積と一緒になるのも畳み込みと併用することを考えるとありがたいね
2023/02/26(日) 23:10:24.52ID:KteJNFXu0
>>711
EDPCというコンテストの一番簡単なやつから理解していくのがいいかな
DPは慣れるまでが結構難しくて、慣れたらABCだとそんなに頭使わなくて済むようになる
2023/02/26(日) 23:14:40.03ID:FFsIOXN5M
Fって一般DAGでも解けるのか
2023/02/26(日) 23:16:04.01ID:EjsCh+nAp
D問題最初誤読して「全てのカードの表面に書かれてる数が異なる」って思って一瞬焦ったけどこの場合も解けたりする?既出っぽい気もするけど
2023/02/26(日) 23:20:28.91ID:P5+y9Ehh0
>>713
ありがとうございます
今やりかけのもの終わったらまた少しDP覗いてみます
2023/02/26(日) 23:28:04.31ID:FFsIOXN5M
>>715
とりあえずグラフを考えて、カードをA_iとB_iをつなぐ辺とみなす
このグラフの各連結成分を見て、なもり木なら閉路部分の割当で2通り、木になってるんなら木DPでうまく数え上げて、それ以外は0通りみたいな感じにして、総積を取る感じか?
なんか既出感がすごいな
2023/02/26(日) 23:30:03.03ID:FFsIOXN5M
なもり木って書いたがなもりグラフか
2023/02/26(日) 23:37:20.19ID:x0T0FVaip
>>717
カードの表裏をグラフの辺に帰着させて連結成分ごとに頑張るみたいな考え方で確かに出来そうだし典型的な考え方な気もするからこの設定の場合もABC-E、Fくらいに置いてあれば違和感無いな
今回はABC-Dだったからすぐ誤読に気づけたけど
2023/02/26(日) 23:39:18.11ID:KteJNFXu0
Fで出て青diffのどこかって雰囲気の問題に見える
2023/03/02(木) 21:21:27.03ID:krvD26HF0
DP練習問題などいくつか試してみましたがほとんど理解出来ませんでした
シンプルな典型問題を解説写経ACするだけの繰り返しになっていて
初見の問題を見る都度解法が全く思いつかないしDPを全く組めません
コピペしても通るような典型くらいしかAC出来ませんので
本番初見問題では役に立たないと思います

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

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

DPが理解できずに苦労したとか覚えるの大変とは聞いていましたが
やってみてそのとおりだと痛感しました
2023/03/02(木) 21:42:44.71ID:spiXxYvqr
そうなんだおじさん「そうなんだ」
2023/03/03(金) 00:13:18.97ID:mfKjEfhRa
いちいちここで報告する必要ないんだよカス
2023/03/03(金) 01:13:35.32ID:ZUR2cvxRM
いや、無駄に煽って荒らしたいやつのほうがカスだろ
2023/03/03(金) 01:29:49.23ID:mfKjEfhRa
カスを擁護するカスまで現れた
自演かもしれんが
2023/03/03(金) 01:42:44.95ID:o7jNKaWI0
解説を見ても理解できないDP練習問題ってなんだ?気になる
2023/03/03(金) 02:43:36.86ID:RMDCzs1h0
「判りませんでした。私は頭が悪いです。わーんわーんわん」って泣き言いう前に分からないとことか問題を貼ろう
728デフォルトの名無しさん (ワッチョイ 5a10-UQ7i)
垢版 |
2023/03/03(金) 03:46:50.79ID:CKnG+JfY0
多分初めのうちは、どういう時にDPを使ったら良いのか分からないって感じだと思うんだけど、
自分は昔「2^nの全探索が無理ならDP」って覚えた(最近だとABC291Dとかもこれ 他にもたくさんあると思う)
2^nの全探索の処理を考えたら、添字に何持たせたら良いのか出てくる気がする
bitDPとか区間DPなどの○○DPは初めのうちにやると混乱するから、まずは↑を出来るようにすると良いと思う
あと、dp配列の定義をきちんと決めることが大事で、ふわふわしたままコードを書くと当然上手くいかない
例えば「dp[i][j]: [0, i)でj個選んだ時の最大値」みたいにコードを書く前にきちんと決める
(dp[i]は「[0, i](閉区間)の答え」とするよりも「[0, i)(開区間)の答え」とした方がコードが綺麗になることが多い)
後は問題をたくさん解けば慣れるはず
729デフォルトの名無しさん (ワッチョイ 6951-wWxq)
垢版 |
2023/03/03(金) 06:19:46.91ID:2nUF2qs80
DPは、状態をまとめて管理したり、操作した結果部分問題に帰着するって考えるとわかりやすいと思う
たとえばそれぞれについて選ぶか選ばないかで 2^N 通りあると、選ぶ・選ばないを決めると 2 つの新しい部分問題に分かれて、
その結果を合成する必要があるけど、結局見るべき「状態」の種類は少ないからメモ化して突破できる~って感じ
添字はfor文の端っこを意識するとバグりにくくなると思う
2023/03/03(金) 06:51:28.66ID:cgS4S0K80
EDPCはHがクソ簡単だからそこから始めるのも手だと思う
部分問題の合成結果が最終的な答えになるって感覚がわかりやすいし
2023/03/03(金) 09:26:45.13ID:gIW+HSjV0
わかるまで考える習慣がないだけじゃないの
2023/03/03(金) 12:17:26.75ID:qJ9yKeqra
おちんぽこぴーーーーーーーーーー
2023/03/03(金) 12:46:35.40ID:synOrNZV0
>>726
EDPCだとA~Iまで試してみて自力で解けたのはCとHの2問だけでした
他の練習問題などでやった記憶があってそれをコピペしたら動いたってだけでした
なので何故そのようなDPを組んで正解が出るのか理解してるとは言えない状態です
つまりEDPCほぼ全てで解説を見ても理解できないということです

>>728-730
丁寧なアドバイスありがとうございます
2023/03/03(金) 12:48:06.16ID:synOrNZV0
せっかく丁寧なアドバイス頂いていて恐縮なのですが
NGして無視してるとは言えどうしても目に入ってしまう非人間的な誹謗中傷もストレスになってますし
自分は頭が悪くて理解できないこと自体がストレスになっているので
DP含めて競プロ全般理解出来ないものは素直に諦めることにします

それでも解けそうで解けないものが解けた時は嬉しかったり
分かる範囲のものを勉強している時は楽しいので
マイペースで出来るものだけでも少しづつ試してみます

あと知人が誹謗中傷で亡くなっています
昨今のニュースなどでも誹謗中傷で亡くなる方も多いと見聞きします
誹謗中傷してる方は軽い気晴らしのつもりなのでしょうが
間接的に殺人に加担してることを理解して欲しいです
2023/03/03(金) 13:25:43.57ID:KvE4f0GAa
このカスなに被害者ぶってんだろね
自分が荒らしと自覚してないんだな
2023/03/03(金) 13:45:39.68ID:+mc9SOeYa
喧嘩するなって
ここは競プロスレだろう?
競プロの話だけしようや
2023/03/03(金) 14:28:51.14ID:o7jNKaWI0
このスレの荒らしは高度アルゴリズム関連を一切呟かず、延々と他者を下げるから分かりやすいのよな
個人的にはDPは漸化式、が高校数学の延長になって一番分かりやすかった、配る方が立式できないのがネックだけど……
貰う方なら、例えばEDPC-Bならdp(0)=0, dp(i)=∑[j=max(0, i-K), i-1] dp(j)+|h_i-h_j|と書けば後はコードにするだけだし
2023/03/03(金) 22:34:24.89ID:XfM0EojcM
貰うってf(x)をaだけ平行移動するとf(x-a)的な添字の難しさを感じる
2023/03/03(金) 22:38:28.74ID:caemo4Qqp
自分も「貰うDP+累積和」よりも「配るDP+imos法」の方が添字ミス減る気がする
2023/03/03(金) 23:21:34.43ID:3ciSJAS40
俺はプログラマだから、DPは順番が違うだけでメモ化再帰とほぼ同じ、ってのが最初にしっくりきたな
関数型言語をやってると再帰はごくごく当たり前に理解できてるからね
まあ漸化式だとか再帰だとかいろんなイメージ付けをしていくことでDPへの理解が深まっていろんなのが解けるようになっていくもんだと思うわ
2023/03/03(金) 23:29:36.68ID:1hMfTn3h0
俺も再帰でシミュレーションすれば答出るけど時間足りないって時に
配列に答置いとけばいいんだっていうのが最初だったな
2023/03/04(土) 00:16:45.91ID:12eSXtYNp
自分は更新順序とか何の値が既に確定してなくちゃいけないかとかを考えるのがだいぶしっくり来たかな
2023/03/04(土) 00:21:42.50ID:12eSXtYNp
基本は漸化式(特に受験数学の確率漸化式)みたいな気持ちだけど更新順序が非自明な時はメモ化再帰でやると楽みたいな
2023/03/04(土) 03:48:50.15ID:7GCZL+pYM
EDPCで初見で解ける問題があるだけ上等じゃねえの
ただ、解説読んで理解できないのは今後あらゆる問題で差し支えるから、それはどうにかした方がいいな
まずEまでは理解できるようにした方がいい
2023/03/04(土) 14:44:05.85ID:BpTmjwzWr
メモ化再帰は普通自分で再発明するよね
2023/03/04(土) 15:17:22.32ID:K6gP6y8f0
お前らずっとマウント取ってるな
寒色の癖に
747デフォルトの名無しさん (オッペケ Sr45-4pPF)
垢版 |
2023/03/04(土) 16:18:10.94ID:mfmYzmTvr
安倍ちゃんですら黄色なのにな……
748デフォルトの名無しさん (ワッチョイ 1355-QeO8)
垢版 |
2023/03/04(土) 19:09:59.50ID:gYn7OIv60
安倍ちゃんって誰ですか?
2023/03/04(土) 21:07:09.47ID:XAdL2dlO0
vscodeがバグってて何も出来ない
急になんでだろ
2023/03/04(土) 22:43:31.90ID:+svXFhc70
幾何が分からなさすぎてExに逃げてしまった、競プロ脳……
2023/03/04(土) 22:53:55.86ID:XAdL2dlO0
Cは典型でしょうか?
典型だとして何というジャンルになるのでしょうか?数学の典型?
これ知らずに初見で考えてわかる人凄いですね
2023/03/04(土) 22:53:56.10ID:Y7UnjEky0
Fは気合いでO(1)
2023/03/04(土) 22:56:55.74ID:yGMb+RWK0
結局6完
久しぶりの幾何でπをcos(-1)とかしてて時間ロス
2023/03/04(土) 23:00:47.56ID:OQrMsS1R0
Fだけ意味わかんね(´・ω・`)
2023/03/04(土) 23:02:35.00ID:4/7hcXX60
Gみたいな細かい要素はそんなに難しくないけど複合してめんどくさくなってるタイプのDP好き
2023/03/04(土) 23:04:57.32ID:4/7hcXX60
>>751
何か二つの積がN以下みたいな条件の時に、片方は√Nまでしか探索しなくて済むというのはかなり頻出の典型だよ
2023/03/04(土) 23:10:57.18ID:XAdL2dlO0
>>756
ありがとうございます
2023/03/04(土) 23:11:59.93ID:4/7hcXX60
Eは推移閉包の問題だったけど、これに関連する発展的な話題で思い出すのはDilworthの定理かな
他には何かあったっけ
2023/03/04(土) 23:12:16.41ID:53hV4Kxfa
C問題、手元で動かしてみたら明らかに2秒越えてるのにダメ元で提出してみたら500msで通った
2023/03/04(土) 23:13:27.02ID:OQrMsS1R0
A * Bの結果を数え上げておくとN - (A * B)を利用してすぐ答えがでるからそう解いた
2023/03/04(土) 23:14:18.60ID:KuhIh+bI0
Fは受験数学思い出して鬱病だった
2023/03/04(土) 23:23:47.86ID:KuhIh+bI0
今回のDiff体感よりも0.5〜1色低いくらいな気がするんだけどやっぱり環境が整ってきて参加者の実力がインフレしてるのかな
2023/03/04(土) 23:26:28.07ID:XAdL2dlO0
挫折して離れる人がいて
残って実力が伸びる人がいるので
どんどん濃度が濃くなってる気がします

新規はすぐに離脱して強い人しか残らないスパイラルみたいな感じ?
2023/03/05(日) 00:08:17.62ID:KLgsW+HB0
ぶっちゃけそれはあるよね
新規の人が来ないとある色に上がる難易度が上がっていくと思う
ただ、現状のABCだったらまだ時間を十分にかければ特殊な才能がなくてもレートを上げていけるゲームではあるかな?
2023/03/05(日) 00:19:06.70ID:2J+JlFQp0
うわあ~
AB2完で灰色に降格ww

vscodeバグって40分ロスしたとはいえキツイですね
時間あってもこの問題じゃ解法思いついてないか

まぁARCのラッキーボーナス+60貰ってたのでこれが適正帯ということでしょう
一瞬でも茶色になって茶色の実力があると勘違いした自分が恥ずかしいです

毎回ABC3完でも+5前後なので
たまにC落としてAB2完でガクっと削られることを繰り返すようなペースだと
一進一退で茶色に成れないかもしれない
2023/03/05(日) 00:21:04.48ID:2J+JlFQp0
>>764
灰色→茶色は努力でなんとかなると信じてやってますが
それすら厳しいかもしれないんじゃないかなと思い始めています
2023/03/05(日) 00:29:23.01ID:KLgsW+HB0
そんな卑屈になることはないと思うけど、コーディング環境とかの問題は再発防止して平均的なレートを上げていこう
2023/03/05(日) 00:52:57.39ID:2J+JlFQp0
>>再発防止

IntelliSenseが効かなくなって何度再起動しても数分後にエラー吐いてPC暴走気味で意味不明でした
IntelliSenseが効かないだけでコードは書けたのでABはそれで提出しました
その後急にまたIntelliSenseが効いていたのでコンテスト終了まで使って今再起動何度しても大丈夫なのですが
原因不明なので様子見するしかない状態です

>>平均的なレートを上げていこう
そうですね
マイペースでもコツコツやるしか無いですね
まずはC問題までを確実に解けるように数をこなすようにします
DPや苦手なものは後回しにして解るものだけやってみます
2023/03/05(日) 12:06:06.58ID:qK/s259X0
最悪に備えてエディタは2つは用意しておくといいかもね
2023/03/05(日) 12:22:19.66ID:W8PCnpO50
端末2つとか回線2つとか家2つとかに拡張できそう
2023/03/05(日) 14:01:29.11ID:Z11rw7p50
体2つもアリ
2023/03/06(月) 02:07:59.12ID:IMTAa66y0
体2つは規約に反しそう
2023/03/06(月) 20:14:35.30ID:GwbNz+dV0
繰り上げり連絡きたけど最高でも6完までの人がToyotaコンの決勝に行ってもいいものかしら
2023/03/06(月) 21:11:51.99ID:pGNY7lCA0
特定しました
2023/03/06(月) 21:23:10.81ID:q41/a1BC0
俺はヴィーガンが諦めるまで肉を食うよ
2023/03/06(月) 22:29:16.06ID:lXUe4Tg6M
決勝イベントって何しに行くの?
2023/03/08(水) 12:06:12.57ID:Pvw6Vf/L0
俺とえっちするんだよね
2023/03/08(水) 12:21:39.73ID:PpYMQDcgM
やっぱオフパコ目的か
2023/03/09(木) 16:51:49.14ID:0rBAUemd0
ホモ祭りってこと?
2023/03/09(木) 18:42:38.65ID:u1SLlFkxr
ホモじゃないんだなァ……
お前がメスになるんだからなぁ
2023/03/11(土) 22:41:50.81ID:lSh5LMLL0
今回いつにも増して知識問題で笑った
特にEとG
2023/03/11(土) 22:42:57.49ID:lSh5LMLL0
というかパフォ予測渋いけど前みたいにバグってるだけだよね?
2023/03/11(土) 22:43:50.50ID:0te2Mpv80
ABCDEG6完
持ってて良かったライブラリ
784デフォルトの名無しさん (ワッチョイ 0eca-L2/A)
垢版 |
2023/03/11(土) 22:45:15.03ID:OCLTPK230
難しくなりすぎ、3完
2023/03/11(土) 22:45:15.83ID:RFB9Zjn2M
predictorはバグっとるな
2023/03/11(土) 22:46:47.19ID:RFB9Zjn2M
やっぱりMoやるだけだと、かなりの人が解けるようになってるな
2023/03/11(土) 22:55:20.20ID:6tpkFNrCa
正解数見る限りむしろ簡単回では
788デフォルトの名無しさん (ワッチョイ 0eca-L2/A)
垢版 |
2023/03/11(土) 23:09:18.64ID:OCLTPK230
D,方針はすぐわかったけど色のインデックスつけたグラフを探索して1時間以上通せなかったり罠が・・・
2023/03/11(土) 23:17:12.24ID:21MPESrtM
Dは色いらんのかーい!wってところが逆に解きづらい可能性がある
2023/03/12(日) 00:28:02.32ID:JKM4V2Et0
全く使わない入力がある問題を見たのはABC126以来かな
2023/03/12(日) 00:53:45.24ID:5bUKmC3Q0
こどふぉとかだとまあまあ見かける気はする
まあカモフラージュとしては良い案だと思う
2023/03/12(日) 02:58:21.52ID:BK530g0z0
本番ではCをDPだと思い込んで苦戦して結局時間切れのAB2完で-4ポイント
HW左上から右下への全通りの作り方が分からず
DFSとbitとnext聞いたことあるけど本番で実装に使うという発想が湧かないのが痛い
いつまた出題されるかわからないけどこいうものを随時テンプレ化することをみんなやってるのかな

本番後D問題は見てもさっぱり分からないので解説動画でDSUでも解けると聞いたので
自分の提出済みのグラフ関連のコード漁ってたら先週の問題の応用でいけそうと思って
先週のD問題に追加3行の計算とロープの色入力追加だけで解けちゃった

ただ解説見るとあっけなく解けることもあるけど
初見の問題だとまず解法が思いつかないし
何を勉強すれば良いのか分からないのはいつものことで
ひたすら過去問解いてコンテストに参加するしか無いの繰り返しなんだろうな
成長の実感が無い期間がしばらく続きそう
2023/03/12(日) 09:25:04.97ID:+XiJVNUi0
>>792
> DFSとbitとnext聞いたことあるけど本番で実装に使うという発想が湧かないのが痛い

全探索の時はその2つを真っ先に思い浮かべればいい
C問題までは計算量考えない全探索でほぼほぼ行ける

問題をたくさん解くというのはこういうことを学ぶことで別に別にたくさん解かなくても学べる
今日は2つ学んだから成長したぞ
今まで時間内に解けなかったC問題がいくつか解けるようになったはずだ
2023/03/12(日) 10:10:16.92ID:kO4IbZOj0
制約から全探索が間に合うかどうか確認しておくといいよ
実装については類題解いて慣れるしかないと思うけど
2023/03/12(日) 10:36:02.54ID:BK530g0z0
>>793-794
ありがとうございます
このスレにいる方って本当にポジティブな方が多くて励みになります
2023/03/12(日) 11:03:35.64ID:NGnXWmzma
>>794
Cでアップアップしてるやつにそれができないことを知りながら誰でもできるみたいな感じでマウント取るんじゃねえよ寒色のくせに
2023/03/12(日) 11:39:08.26ID:0uSJS7hH0
>>792
今回のC問題みたいなのについてはテンプレ化は難しいと思う

とはいえ、DFSによる全探索は大体どれも似たようなパターンでは書けるから、何個か類題解いてみて自分に合った型を身に付けられるといいかな
2023/03/12(日) 13:20:46.12ID:NGnXWmzma
ChatGPT昨日の問題全部解きやがった
2021年までのデータしかないんじゃなかったのかよ
2023/03/12(日) 15:49:18.88ID:bJsXlPlwM
どこまで行っても補助輪がついてる競プロ界の中でテンプレがどうこう言う話なのかなあ?
800デフォルトの名無しさん (ワッチョイ f951-S+nL)
垢版 |
2023/03/12(日) 17:15:31.72ID:JeedQz+W0
テンプレというか、この手の移動が「W-1回の右移動とH-1回の下移動」の順列と一対一対応するのが典型では(ABC034-C とか)
2023/03/12(日) 20:06:45.55ID:BK530g0z0
ありがとうございます

>>797
これを機会にDFSに触れてみます

>>800
本質を言語化して頂いて助かります
2023/03/12(日) 23:05:04.03ID:J7t2DN8P0
3完
いつか800点解きたい
2023/03/12(日) 23:14:16.32ID:Gruze9YMp
B問題未証明で適当に通した人多そうだしあまり好きじゃない
誤差とかも嫌だし
2023/03/13(月) 00:42:27.93ID:tAERM5Ax0
DFSで解けるらしいというヒントだけで初見のC問題をDFSで実装して解けたけど4時間半掛かりました
すぐに分からないものを出来るまでやった方が良いみたいなことをどこかで見聞きしたので試してみたけど
もの凄い疲労感とちょっとだけ達成感
さっさと解説ACでどんどん数こなすのとどっちが効率良いんでしょうね
問題やその人の好みってことだと思いますが・・・
2023/03/13(月) 16:05:40.89ID:7mT2rAwv0
解説ACするかは、記憶力に自信があるかじゃないかな
頑張って自力で解いた経験が無いと覚えられないならちゃんと取り組むべきだし、解説を次々開いても一読しただけで暗記できるなら解説ACの方が効率が良い
まぁ解説ACつっても典型要素のエッセンスはちゃんと復習してるけどな

あなたの場合、そもそも解説を読むだけではどこが典型か理解できないみたいだから、ちゃんと問題に取り組む時間を設けないとダメだと思う
2023/03/13(月) 17:01:54.47ID:jAvU5ud0a
明らかに向いてなさそうだが競プロやってる理由はなんなんだ?
807デフォルトの名無しさん (ワッチョイ ce5b-lsaJ)
垢版 |
2023/03/13(月) 23:46:41.51ID:vLo5AekE0
この界隈、全体的にネット上の立ち回りが下手くそ
特にトッププレーヤー
2023/03/14(火) 00:37:56.19ID:oPoU3rtzM
おぼえると言う意味が分からない


考えられない、理解してないと言うことだろ
809デフォルトの名無しさん (アウアウウー Sa89-6iC+)
垢版 |
2023/03/15(水) 10:30:29.06ID:62k5ZXIga
ガイジスレ終了
2023/03/15(水) 11:04:08.82ID:6RV0HXN90
293C、どうやって書いてもREが出ます。
サンプルの2題だけ通ってあとは全部REになります。

何が原因だと思われますか?
他の提出車を見てもREばっかりで
2023/03/15(水) 11:29:42.07ID:cgh9EpJX0
ここが次スレということです
みなさんよろしくお願いいたします
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。

ニューススポーツなんでも実況