CSA Round #65 (Div. 2 only) (2ページ目)

フェリン @ferin_tech15

CSAやらかしたんですか

2018-01-18 02:04:01

satanic@研究💪 @satanic0258

1時間寝坊して参加したので…

2018-01-18 02:04:19

olphe @_olphe

えーほんとだ

2018-01-18 02:04:50

satanic@研究💪 @satanic0258

Dわかったのに時間が足りないね(それはそう)

2018-01-18 02:05:03

フェリン @ferin_tech15

あとこだのやらかし率の低さすごい

2018-01-18 02:05:19

satanic@研究💪 @satanic0258

CSAおつでした

2018-01-18 02:06:07

iwashi31 @iwashi31

C こんなに解かれるもんなのか

2018-01-18 02:08:29

けんちょん @drken1215

CSA、DはきっとBIT版実家DPなんだろうなと思いつつ詰め切れなかった

2018-01-18 02:09:27

iwashi31 @iwashi31

木の直径の長さ引くだけやん！と思ったけどパス求めるフェーズが無理だった

2018-01-18 02:09:52

olphe @_olphe

CSA苦手すぎる

2018-01-18 02:10:12

satanic@研究💪 @satanic0258

A:s[i]=t[s[i]-'a'] B:両方の木で(u,v)が繋がってるペアの個数 C:木の直径上のパスでは後戻りしないようにすると最適 D(未):dp[i][j]:=位置iまで見て最後に位置jで0を使ったときの場合の数としてDPだけどそのままだとO(N^2)なのでセグ木で纏めるようにするとO(NlogN)になる

2018-01-18 02:11:45

けんちょん @drken1215

DとEを考えてなかなかできず、途中でCにうつってやって、A, Bやった感じになった。結果論で言うと戦略をミスってて、Dから解くなら、Cに移り気せずに何が何でもDを解き切る意思が必要だった。

2018-01-18 02:13:00

けんちょん @drken1215

結果として、素直にA, B, Cと順番に解いた場合に比べて、最初にDとEを考えていた時間の分だけペナルティが増えただけの状態になってしまった。

2018-01-18 02:14:31

sumoru @sumoooru

Cを早解きできたと思ったら嘘解法だった。たぶんunrated 直径の端から端まで、往復の距離が短い順に辿るとかで解けるのかな

2018-01-18 02:14:49

けんちょん @drken1215

実家DPに慣れてなさすぎるのがよくわかったから、またいっぱい練習するのん！！！

2018-01-18 02:16:48

satanic@研究💪 @satanic0258

Cの実装，・予め直径の両端p,qから各点vへの距離d_p(v),d_q(v)を求めておく・直径上でd_p(v)+d_q(v)=直径長となる頂点をsetで持つ・dfsで直径上にある頂点uは最後に探索するようにする・dfs関数を抜ける際に，自身vとその前の頂点parが共に直径上になければ後戻りするのでparを配列に入れるとかで pic.twitter.com/8XKWrJcqMA

2018-01-18 02:18:50