競技プログラミングにハマるプログラマのスレ 185

**仕様書無しさん** · 2024/06/19(水) 17:59:26.60

競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ
次スレは>>950

AtCoder http://atcoder.jp/
yukicoder http://yukicoder.me/
Codeforces http://codeforces.com/
CodeChef http://codechef.com/
Project Euler http://projecteuler.net/
CLIST http://clist.by/
AtCoder Problems http://kenkoooo.com/atcoder/
AtCoder Clans http://kato-hiro.github.io/AtCoderClans/

前スレ
競技プログラミングにハマるプログラマのスレ 177
https://medaka.5ch.net/test/read.cgi/prog/1715758898/
競技プログラミングにハマるプログラマのスレ 178
https://medaka.5ch.net/test/read.cgi/prog/1716032602/
競技プログラミングにハマるプログラマのスレ 179
https://medaka.5ch.net/test/read.cgi/prog/1716138417/
競技プログラミングにハマるプログラマのスレ 180
https://medaka.5ch.net/test/read.cgi/prog/1716536571/
競技プログラミングにハマるプログラマのスレ 181
https://medaka.5ch.net/test/read.cgi/prog/1717047176/
競技プログラミングにハマるプログラマのスレ 182
https://medaka.5ch.net/test/read.cgi/prog/1717387089/
競技プログラミングにハマるプログラマのスレ 183
https://medaka.5ch.net/test/read.cgi/prog/1717847778/
競技プログラミングにハマるプログラマのスレ 184
https://medaka.5ch.net/test/read.cgi/prog/1718451650/

**仕様書無しさん** · 2024/06/22(土) 22:45:08.50

なぁ、重心分解のおすすめ記事教えて🥺
maspyさんのあれ以外で

**仕様書無しさん** · 2024/06/22(土) 22:45:32.79

重心分解要らない定期

**仕様書無しさん** · 2024/06/22(土) 22:46:52.13

audiaxlly treeってやつか？
もう何も分からないだね

**仕様書無しさん** · 2024/06/22(土) 22:47:47.82

auxiliary tree出しすぎじゃね？
そんな頻繁に出ないと思ってライブラリ化サボったんだけど持ってたらG一瞬だったのに

**仕様書無しさん** · 2024/06/22(土) 22:48:24.30

CDE典型だけど確かにいつもよりは難しかったな(勿論解けてます)

**仕様書無しさん** · 2024/06/22(土) 22:49:31.71

D問題なんで全人類bitDPしてるんだ

**仕様書無しさん** · 2024/06/22(土) 22:49:43.67

Cはいつもより難しいと思う
Eはstackに積みながらこねこね(長さを持つ)的なことをやれば簡単
CFで何度か見た気がする

**仕様書無しさん** · 2024/06/22(土) 22:50:31.86

auxiliary treeと重心分解、どっちも精進する
ジェネルシになりたい

**仕様書無しさん** · 2024/06/22(土) 22:52:13.45

圧縮木もやるか
知らないアルゴリズムだらけだぜ

**仕様書無しさん** · 2024/06/22(土) 22:52:39.64

今緑で毎回緑diffは解けてるのにレート下がっていくのだが...

**仕様書無しさん** · 2024/06/22(土) 22:53:08.07

圧縮木と同じだぞauxiliary tree

**仕様書無しさん** · 2024/06/22(土) 22:53:12.86

はあガイジはあガイガイ

**仕様書無しさん** · 2024/06/22(土) 22:53:23.81

俺ってこんなのも解けないんですよガイガイ

**仕様書無しさん** · 2024/06/22(土) 22:53:51.10

いやDの直前K個持つDPもEの単調stackもど典型なので解説されなくてもわかってます
この位置にしては難しいってだけ(Cとか特に)

**仕様書無しさん** · 2024/06/22(土) 22:54:22.01

Eのmonotonicstack棄却したんだがいけたんか？草

**仕様書無しさん** · 2024/06/22(土) 22:54:26.94

木のマージテク、どうやって使うの
分からない
根どうし意外もマージ出来る？

**仕様書無しさん** · 2024/06/22(土) 22:55:06.61

俺ってこんなのも解けないんですよ、びっくりしませんか？

**仕様書無しさん** · 2024/06/22(土) 22:55:31.90

このwriterまともすぎる

**仕様書無しさん** · 2024/06/22(土) 22:56:00.79

Fも自明DP高速化と思ったら普通に貪欲で良くてびっくり
Cが一番Fまでで難しいっていうかやりたくない

**仕様書無しさん** · 2024/06/22(土) 22:56:17.69

そんなことよりセックスしろ

**仕様書無しさん** · 2024/06/22(土) 22:56:18.72

いつものABCより質は良かった気がするな

**仕様書無しさん** · 2024/06/22(土) 22:57:43.08

C、WA出てたらキレてた
長方形の左に来るように+txが右に来るようにスワップで場合分け減らす実装が出来た点は良かった

**仕様書無しさん** · 2024/06/22(土) 22:59:21.08

Gまあ方針は自明だけど通されすぎじゃね

**仕様書無しさん** · 2024/06/22(土) 22:59:25.06

こんなのも解けないのガイジすぎる
ガイガイガイガイガイガイガイガイガイガイガイガイガイガイガイガイガイガイガイガイガイガイガイガイガイガイガイガイガイガイガイガイ

**仕様書無しさん** · 2024/06/22(土) 23:01:17.24

Gはどの方針を引いても解けるので
下位互換の類題も340Gで出たばかりなので

**仕様書無しさん** · 2024/06/22(土) 23:01:32.29

rated日本人でG解いてるの13人でワロタ
中国人は70人
ジャップさぁ...

**仕様書無しさん** · 2024/06/22(土) 23:01:59.97

チャイナインコ支配的

**仕様書無しさん** · 2024/06/22(土) 23:04:09.57

SSRS様のツイート

G、木の圧縮、マージテク、HLD、重心分解などいろいろな解法が流れてくる

どれも知らなかったので、解けませんでした

**仕様書無しさん** · 2024/06/22(土) 23:05:22.69

重心分解は見たことないがそれ以外はスレ既出

**仕様書無しさん** · 2024/06/22(土) 23:05:35.69

なんか遅解きだったのに結構順位良いなって思ったらペナ率高いのかな？

**仕様書無しさん** · 2024/06/22(土) 23:06:09.28

重心分解もスレ既出だろ

**仕様書無しさん** · 2024/06/22(土) 23:06:52.49

木のデータ構造問題飽きたから出すのやめてね

**仕様書無しさん** · 2024/06/22(土) 23:07:19.08

マ？覚えてないわ何年前？

**仕様書無しさん** · 2024/06/22(土) 23:07:40.19

>>489
SSRSそれのどれも知らずに赤とかマ？

**仕様書無しさん** · 2024/06/22(土) 23:08:10.84

C~Fはどれも1問抜け6完が割といそう

**仕様書無しさん** · 2024/06/22(土) 23:08:26.56

改行潰すな

**仕様書無しさん** · 2024/06/22(土) 23:08:37.74

データ構造は中国支配的だからやめてね

**仕様書無しさん** · 2024/06/22(土) 23:08:40.66

SSRS様のツイート

(SSRS)G、木の圧縮、マージテク、HLD、重心分解などいろいろな解法が流れてくる

(俺)どれも知らなかったので、解けませんでした

**仕様書無しさん** · 2024/06/22(土) 23:09:06.89

ガイジガイジガイジガイジこれで冷えるのガイガイガイガイ

**仕様書無しさん** · 2024/06/22(土) 23:09:21.33

>>499
紛らわしい

**仕様書無しさん** · 2024/06/22(土) 23:09:32.82

>>495
考察力ヤバすぎるな
河野並か

**仕様書無しさん** · 2024/06/22(土) 23:11:11.50

ガチで苦しいなぜ俺はこんなにもガイジなんだ

**仕様書無しさん** · 2024/06/22(土) 23:11:25.43

DE終わらしてからCに向かいました🤗
実験すると式が見えてくる系はCodeforceでお腹いっぱいだからいらないよ🤮

**仕様書無しさん** · 2024/06/22(土) 23:13:28.43

Cに実験要素ある？

**仕様書無しさん** · 2024/06/22(土) 23:14:07.06

どちらかというとEの方が実験みがある

**仕様書無しさん** · 2024/06/22(土) 23:16:43.54

どれも実験ではないだろ

**仕様書無しさん** · 2024/06/22(土) 23:16:57.41

インコ透けすぎ

**仕様書無しさん** · 2024/06/22(土) 23:17:46.46

実験かは知らんがCEFは頭使った
DGは頭使ってない

**仕様書無しさん** · 2024/06/22(土) 23:18:20.95

レーティング差分みると-50以上してる日本人大量にいて安心

**仕様書無しさん** · 2024/06/22(土) 23:18:26.39

E頭使う要素流石にない

**仕様書無しさん** · 2024/06/22(土) 23:19:06.96

EにはDGほどのやるだけ感はなかったので

**仕様書無しさん** · 2024/06/22(土) 23:19:41.35

Cはどうせ簡単な式で書けるから実験して式当てた方が速い気がする
それで10分以上かかったけど

**仕様書無しさん** · 2024/06/22(土) 23:21:21.82

制約でdpのキーまで指定してくれるDとライブラリでいかようにも殴れるGに比べてEは脳死要素が足りない

**仕様書無しさん** · 2024/06/22(土) 23:22:47.61

EFは初期AGCっぽさはある

**仕様書無しさん** · 2024/06/22(土) 23:23:11.46

そんなことしなくても図を見ればy合わせてから端合わせるだけでいいのは自明だろ　インコが方法論を語るな

**仕様書無しさん** · 2024/06/22(土) 23:23:26.67

>>510
BC崖のせいで2完爆死してる水青が結構いる

**仕様書無しさん** · 2024/06/22(土) 23:23:55.85

Cが解けない寒色いるんだふーん

**仕様書無しさん** · 2024/06/22(土) 23:24:12.51

幾何出してどうぞ

**仕様書無しさん** · 2024/06/22(土) 23:24:42.15

D典型ってことは似た問題過去に出てるん？

**仕様書無しさん** · 2024/06/22(土) 23:24:58.09

Cバカの崖じゃん草

**仕様書無しさん** · 2024/06/22(土) 23:25:40.32

>>520
295Dがまんまじゃね

**仕様書無しさん** · 2024/06/22(土) 23:27:34.47

>>522
昨日解いた問題で大爆笑
マジかー...同じに見えなかった

**仕様書無しさん** · 2024/06/22(土) 23:27:36.71

>>522
295Dって別系統じゃない？

**仕様書無しさん** · 2024/06/22(土) 23:28:16.12

ARC179Bもそうだしド典型といえばそう

**仕様書無しさん** · 2024/06/22(土) 23:28:24.87

直前数個の状態だけ持つDPは類題無限にあるから余裕でど典型(まあ置かれるとしたらABC-E辺りがちだけど)

**仕様書無しさん** · 2024/06/22(土) 23:29:36.33

ちょくちょく爆死してる水青がいてﾌﾌｯで笑いが出てくる

**仕様書無しさん** · 2024/06/22(土) 23:29:37.55

bitdpっぽくないbitdpじゃなしに直前数個を持つdpが知りたいんか

**仕様書無しさん** · 2024/06/22(土) 23:30:46.18

今回のをbitDP呼ばわりはやや本質捉えてないだろ

**仕様書無しさん** · 2024/06/22(土) 23:31:36.91

>>525
これもコンテスト中ずっと考えてた+復習もしてたのになぁ

>>526
なるほど...過去問精進が足りてない

**仕様書無しさん** · 2024/06/22(土) 23:33:21.91

そうか？
295dもそうやけん、状態をキーに持つdpをすべてbitdpだと呼んじょるから非本質と言われてもどこがとなるけん

**仕様書無しさん** · 2024/06/22(土) 23:34:27.09

DE逆転、普通によくわからない
C>E>>Dだと思ったので

**仕様書無しさん** · 2024/06/22(土) 23:35:33.58

295Dそもそもdpじゃなくない？

**仕様書無しさん** · 2024/06/22(土) 23:36:26.55

最近AB簡単でいい傾向だ
今までAI対策で難読化されてたけど

**仕様書無しさん** · 2024/06/22(土) 23:36:50.70

いうても雑魚向け問題でまんま同じ状態を外すdpは見たことないかもしれんわ
305GやtdpcQで出てるけどどっちもインコには無理だしな

**仕様書無しさん** · 2024/06/22(土) 23:37:06.59

Cみたいなのがgptに解けないのならもっと増やすべきだな

**仕様書無しさん** · 2024/06/22(土) 23:37:13.93

cは難しい要素あんまりないでしょ
実際たくさん解けてるんだし

**仕様書無しさん** · 2024/06/22(土) 23:39:14.51

Dは実装重そう＆回文や数え上げの文字が入るとアドホックそうに見えるとかで忌避されてそう

**仕様書無しさん** · 2024/06/22(土) 23:39:16.41

高2が入黄してて鬱
成長速度早すぎて鬱

**仕様書無しさん** · 2024/06/22(土) 23:41:51.91

>>533
dpij=S(0-k)を抜き出した列の偶奇がjとなるk<iの個数
でdpと言えんか？

**仕様書無しさん** · 2024/06/22(土) 23:42:44.98

今回はGPTどうなの？
ABが解けるくらい？

**仕様書無しさん** · 2024/06/22(土) 23:43:33.84

有名な名誉GPTerが爆死してたからBまでじゃねえの

**仕様書無しさん** · 2024/06/22(土) 23:45:14.76

>>540
確かに

**仕様書無しさん** · 2024/06/22(土) 23:51:18.04

GPTインコが爆死しても面白いし、GPTインコに他のインコが虐殺されてても面白い
最近本当にABCが面白くなってきた

**仕様書無しさん** · 2024/06/22(土) 23:51:48.12

面白くねえよ冷えたわカスカスカスカス

**仕様書無しさん** · 2024/06/22(土) 23:52:05.83

来週のARC予選突破するぞするぞするぞ

**仕様書無しさん** · 2024/06/22(土) 23:52:50.73

CみたいなのARC-Aに置かれるとやや苦しい気持ちになる(特にペナでたら)

**仕様書無しさん** · 2024/06/22(土) 23:52:51.49

Cで躓くのはともかく、青でDEどっちも解けないってヤバいだろ

**仕様書無しさん** · 2024/06/22(土) 23:53:21.81

はあ冷えはあガイジ
俺ってDE両方は解けないんですよガイジだから

**仕様書無しさん** · 2024/06/22(土) 23:53:59.29

Cここで使うくらいならARCで使えそれはそう

**仕様書無しさん** · 2024/06/22(土) 23:54:28.11

ARCであれ出たら嫌

**仕様書無しさん** · 2024/06/22(土) 23:54:35.33

学生選手権だからまるーんさんがWしてそう

**仕様書無しさん** · 2024/06/22(土) 23:54:45.62

アドホックという点では似てるんだけど、なんかARC-Aってもっとすっきり射精できる印象ある

**仕様書無しさん** · 2024/06/22(土) 23:55:57.31

CはARCでは絶対出ない印象がある

**仕様書無しさん** · 2024/06/22(土) 23:56:21.85

ARC300がすっきり射精なわけない
マグロ問かネトネトガチ不快問の二択

**仕様書無しさん** · 2024/06/22(土) 23:57:30.69

学生コン出たらスレ民の皆でオフ会しよう

**仕様書無しさん** · 2024/06/22(土) 23:57:37.52

マグロ問の意味するところが分からねえから反論できねえ

**仕様書無しさん** · 2024/06/22(土) 23:57:53.35

俺が出場できる確率、1%

**仕様書無しさん** · 2024/06/22(土) 23:57:54.60

マグロなら射精できずネトネト問は過呼吸になるため

**仕様書無しさん** · 2024/06/22(土) 23:58:31.82

虚無考察広義やるだけ不感問

**仕様書無しさん** · 2024/06/22(土) 23:58:48.51

無職ニートは出られないからガイジスレ民のマジョリティは無理だろ