AtCoder Beginner Contest 070 (17ページ目)

LCAかな・・・

2017-08-13 11:45:22

@PlatypusSurface LCAは…分解…？(ごめんなさい使う場面に合ってないのでどんなものか覚えてないです) Bwam君はLCAを使ってた記憶がある

2017-08-13 11:46:31

@babcs2035 @Nafmo2 K可変の場合はLCAを使います。（chokudaiさんが解説放送のおまけでx->yを求める問題を解説してますが、それとほぼ同じです）

2017-08-13 11:46:44

platypus @platypus999

@Nafmo2 木を根付き木にすると親とか子とかできるのは知っていますか？

2017-08-13 11:47:13

完全に亀&横槍リプだった為

2017-08-13 11:48:05

@PlatypusSurface んーどうでしょう…？(1個根っこを決めるとそこから上下みたいなのができて親と子みたいなやつですか())

2017-08-13 11:48:42

@PlatypusSurface ２つの頂点の一番深い共通する親の頂点ですか？（説明が下手ですみません）

2017-08-13 11:48:52

解説放送で本当に言ってたか確認してたら普通に遅れてア

2017-08-13 11:49:06

@eiya5498513 @Nafmo2 計算量っていくつでしたっけ...?

2017-08-13 11:49:35

platypus @platypus999

@Nafmo2 そうですね。それを使うとできます(詳しくはそこら辺のブログを見たほうがわかりやすいと思うのでぜひ調べてみてください)

2017-08-13 11:50:23

@PlatypusSurface はい、分かります。以前それを利用して問題を解いたことがあると思います

2017-08-13 11:50:42

@PlatypusSurface わかりましたーありがとうございます！

2017-08-13 11:50:51

@babcs2035 ダブリングしてO(logN)（他は忘れたけど似たり寄ったりだったはず）

2017-08-13 11:51:05

Dの思考回路が†全方位木DP†=>†LCA†=>ダイクストラでお終い！ｗ=>DFSでも解けそうだけど面倒だから良いや=>(解説聞いて)「BFSだとスタックオーバーフローしないよ」なるほどなぁなので頭が悪すぎる

2017-08-13 11:53:20

@eiya5498513 なるほど、では全然余裕ですね。

2017-08-13 11:53:22

とりあえず帰ったら蟻本読もう(帰省に連れて行かれてるのでア)

2017-08-13 11:53:33

星見純那 @MochaLatvia

@eiya5498513 逆にDFSだとスタックオーバーフローしたんですか

2017-08-13 11:55:12

@MochaLatvia chokudaiさん曰く、「言語の設定によってはスタックが小さいので、スタックオーバーフローしてしまうことがある」だそうです。「C++なら安全」らしいですが。

2017-08-13 11:58:02

昨日のABC070 A:to_stringして回文判定スニペット貼り付けた(ア) B:max(0, min(b-d)-max(a,c)) C:全てのLCMを取る D:頂点kを根として，根から頂点vまでの距離を求める木DPしたらdp[xi]+dp[yi]が答え

2017-08-13 14:34:54

B問題，類題を直前で解いてたから素早くそれ書けて良かった

2017-08-13 14:38:53

ABC070-Bの類題です twitter.com/satanic_compro…

2017-08-13 14:41:00

satanic@解いた問題を報告します @satanic_compro

041 CodeThanksFestival2014A日程-D 定期券 …stival-2014-a-open.contest.atcoder.jp/submissions/15… (t-s-max(0, min(b, t) - max(a, s))) * 100が答え．

2017-08-12 15:33:43

AtCoderProblemsに昨日のABC登録されてなかったからもう一回解きなおしておいた

2017-08-13 14:58:58