読者です 読者をやめる 読者になる 読者になる

ARC002轟沈

C/C++ ARC/ABC

150点でした。B問題は99点とれてたみたいですけど。n>100でreturn 0;してたので、50点しか貰えなかったぽいです。計算量とか分からないです。
B問は尺取法、ググってもあんまり出てこないので、今日のスライドと頭いい人たちのコードでも見て勉強してきます。

C問題は木の直径ってのを求める問題みたいです。
DFSでもBFSでも解けるらしいですけど、どっちも実装できなかったです。
DFSとBFSはちゃんとかけるように練習してこないと
ABC007にBFSの問題が出てるようなので。
http://www.prefield.com/algorithm/graph/tree_diameter.html
ここら辺で木の直径の話があります。
あとはLCA(lowest common ancestor)よくわからないやつです。
木構造はぜんぜんわからないですね。

D問題は部分点で累積和を求める。完投は凸包の問題です。
数学はできません。
imos法とかいうやつらしいです。AOJの本戦でも出てます。
http://imoz.jp/algorithms/imos_method.html