駄目な回
■A - Weather Forecast
s[i-1]を見る
■B - qwerty
s += 'a' + n;
■C - Shapes
面倒
回転だけなら楽だけど並行移動も考える必要がある。
そのためには左上を起点にすればよい。
適当に(x,y)->(y,n-1-x)とでもして回転させたあと
sortすれば左上が一番前に来る。
■D - Rectangles
なんか一回tleした
左下と右上さえ決めれば残りの２つが決まる。
■E - Destruction
最小全域木。ただし負の辺はいらない。
■F - Blocked Roads
有向グラフですって。
辺がいっぱいあるので、毎回bfsするわけにはいかない。
0->n-1に使うへんは高々n-1本なので
それ以外は最短パスがそのまま答えになる。
残りは再びbfsしても計O(n*(n+m))なので十分に間に合う。
なので、一回bfsし、ある最小パスに含まれる辺の集合をset等で管理してやればいい。
■G - Game on Tree 2
dfsをする。
根っこまで到達すれば、中央値は決まる。
根っこ以外では分岐のどれを選ぶかを、プレイヤーの最善に従って選択すればいい。
中央値の管理は、座圧してセグ木にのせて二分探索をすれば良い
これはaclがあるので余裕。
■H - Red and Blue Lamps
Alien DPと言うらしい。
要するにグラフが凸なら
O(n^2)かかるようなDPをO(nlogn)で行える。
上に凸な関数f(x)がありf(r)を求めたいが直接的には計算量的に求められれない。
しかし、
g(x):=f(x)-kxなグラフ(これも上に凸)
の最大値を取るxと、その時の最大値g(x)は簡単なdpで求まる
もし、この最大値を取るxがrなら、g(x)+ k*rが答えになるので求まる。
みたいなことをやってるんだと思う。
グラフが凸というか変化量の差分が単調だから二分探索ができる
という性質が重要？
