■A - Tiny Arithmetic Sequence
std::sort
■B - Do you know the second highest mountain?
std::sort
■C - Secret Number
0000から9999まで全部試す。
■D - Game in Momotetsu World
ゲームの最適戦略苦手。
dp[i][j]:=(i,j)から始めてお互いが最適に行動したときの
始めた人からみた最大得点差
■E - Xor Distances
終了15分前に完全に方針が間違っていたことに気がつく。
そこから頑張って2分前AC
(x,y)の最短パスのxorは
(0,x)と(0,y)それぞれ最短パスのxorに等しい
理由は共通部分((0,lca(x,y)))が打ち消されるから
なので、すべての点に対して原点からのxorを求め、
各bit毎にこのbitが立つための条件を考える。
■F - Insertion Sort
セグ木dp
それぞれの人間は高々一回しか動かさない。
動かない人達の集合を決め打つ。
動かない人たちは、初期状態で既に最終状態と前後関係が一致している必要がある。
dp[i]:=Sに含まれる人の番号の最大値がiで、i以下の人を照準に並び替えるのに必要なコスト。
とすると
dp[i] = min(dp[j] + Σ(n=j + 1,i - 1)A[n] )
当然だが、iが最初の動かさない人のケースも考慮する必要がある
dpをセグ木にそのまま乗せずにdp-ΣA[n]として乗せる必要がある。
