SRM586 Div1 Easy

250

SRM585 Div1 Easy

250
http://community.topcoder.com/stat?c=problem_statement&pm=11361

ある頂点とその直接の子2つを移動する様な選び方が最適なはず。つまり、頂点3個毎を1塊。
木の頂点を高さごとに分けて考えたとして、根とその直接の親の部分のコストを付け足す様な DP になる。

SRM578 Div1 Medium

500
http://community.topcoder.com/stat?c=problem_statement&pm=12534&rd=15498

memo[前の前に配置した地点][前に配置した地点]
ある２点間が、ある1つの区間に含まれるかどうかを前もって作っておく。
あとは、今現在着目している地点をこれまで配置した2点と同様の区間にならない様に選んでいく。

SRM575 Div1 Medium

500
http://community.topcoder.com/stat?c=problem_statement&pm=12498&rd=15495

ある位置が部分列に選ばれる確率を計算する。
ある位置の数字が"最終的に"その場所にある確率を計算する。

こういう列の要素のスワップの問題って、"その位置"と"他の位置"に分けて考えるのが定番なの？

SRM583 Div1 Medium

500

グラフ中の最長パスを求める。もし両端を切り替える必要があるなら、そのパスで切り替える。
パスの両端の片方あるいは両方を木から取り除いて同様の操作を繰り返す。

もっと簡単にDFSやループだけで解けるらしい。

SRM583 Div1 Easy

250

WFとか。
range[i]が頂点の数より大きくなる場合がある。
(i - range[i] + V) % Vだと負になったりする。

SRM543 Div1 Medium

500
http://community.topcoder.com/stat?c=problem_statement&pm=11912&rd=14735

DP[どの島][どの港]
普通にループを回すと当然のがら間に合わない。

何分探索かして今注目している位置より左から適切な場所を探すのかと思ったけど、そんなことはなかった。
最小値あたりのインデックスを持っておいて、距離の近い方へと見ていく。

SRM582 Div1 Easy

250

ソートして二分探索。