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

ソートして二分探索。

SRM536 Div1 Medium

500

http://community.topcoder.com/stat?c=problem_statement&pm=11797&rd=14728

(総和の半分) or (総和 - 最大値)

(総和の半分)はすぐに思いつく。
(総和 - 最大値)は分からなかったので小さいケースをいくつか手で試した。

SRM528 Div1 Medium

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

memo[一方をどこまで作った][もう一方をどこまで作った]

s[x[k]] = s[y[k]] の条件を満たしうる長さN/2の文字列を全て生成して数え上げる。
候補の文字列をtとして、memo[i][j]に注目している時、t[i]かt[j]のどちらかに文字を割り当てる。
割り当てられる文字はs[i + j]。

(2^20)*(20^2)は無理だろうと思ってひたすら別解法を考えたけど、結局はこれだった。
あまり手を抜くとTLEする。