VK Cup 2017 Round 1 / Codeforces Round #405

とさか2 @nanTosaka2

部分木の総和とmod kも持って全方位木dpしたけど無限にバグって死にたい...

agw @masashinakata

Div 2. D、終了3秒前に提出したんだけど、MLEェ…

btk @btk15049

69人しか出してないDをpretest通して1500人通してるCを通せない馬鹿がいるらしい

btk @btk15049

私だ

btk @btk15049

d2です

nyashiki @nyashiki

ここ数回レート真っ逆さま （もともと高くないが）

iray_tno@tanao @iray_tno

div2dわからん

とさか2 @nanTosaka2

最初なぜかDが簡単に解ける気がしてC飛ばしたの最悪だった

sigma @sigma425

B:長さmod Kの個数と総和をもって木DP C:V,K,それ以外のそれぞれの相対順は変える必要が無いので「a個,b個,c個使った,直前がV?」でDP D:高さ1だと左端決めると貪欲で、あとがわかんない E:ある点を決めて傾きが最も近いみたいな直線を列挙して凸包?

agw @masashinakata

あー、そうか。開始地点ごとに算出せにゃいかんのか…

nmnmnmnmnmnmnm @enuemuenuemuenu

div1Cのpretest 9って何やろ？

競技プログラミング @LatteMalta

A:はい(これ変な罠とかないよね) B:†全方位木dp† C:V,K,その他,の3種類の文字があるが、同じ文字間では順序を変えないので、あとは頑張ってdp

hogeover30 @hogeover30

Div2 A：ループ回す B：繋がってる頂点の辺の本数が同じ or not C：最初に全部違うのを作っといてs[i]==NOだったらres[i+k-1]=res[i]

pekempey @pekempey

AはYESなら適当に,NOならa[i]=a[i+K-1]。BはKが小さいので全方位木DP。Cはdp[pos][use V][use K]=転倒数。

btk @btk15049

d2dは何も考えずに木DPをすると頭は壊れますが解けます

btk @btk15049

@LatteMalta 全方位いる？

nmnmnmnmnmnmnm @enuemuenuemuenu

div1Aの1完なのでdiv2に落ちるやつですね。これは。

よすぽ @yosupot

@camypaper 本質は1次元上にたくさん区間が来て何個使えるかを管理することで、これはal <= bl < br <= arだったら当然[al, ar]は使用する意味がない、というのを入れると高々2個の区間に対するrange addになると思いました

競技プログラミング @LatteMalta

@btk15049 うまくやれば必要ないかもしれませんね(他に思いつかなかった)

nyashiki @nyashiki

見た瞬間unionfindだと思ったけど，そのあとできず

iray_tno@tanao @iray_tno

div2d、葉から見て行っていい感じにマージしつつカウントしていくのかなとおもったけど

競技プログラミング @LatteMalta

D:どうせ重み関数mongeやろ！ｗ →本当にそうでしょうか(どうなんだろう

よすぽ @yosupot

[0, 1] [3, 5] <- add [2, 4]の場合を忘れていた

null @ZG9uZG9fY3By

私のアルゴリズムだと、[a, a+k) がYES、[a-1, a+k-1) がNOのときに、ans[a-1]=ans[a+k-2] とすると、・・・・うまく説明できないけど私はそれで "Pretest" 6 に落ちた

kmjp @kmjp_pc

Cが時間あっても解けたか微妙なので結果的に出なくて正解か…？