result:oooooo--
rateing:1875->1874
■A - Last Letter
cout << s[n - 1] << endl;
■B - Go Straight and Turn Right
現在地点のx,yとmode(向き)を持つ
modeはmod4で考えbfsで使うようなdxdyを用意しておく
■C - Yamanote Line Game
インタラクティブ？！
O(n^2)が間に合うので愚直に
■D - Swap Hats
初期状態を123として奇数回の操作で132,321,213に遷移が出来、
偶数回で312,231,123に遷移ができる。
初期値との一致箇所が1ならNG
■E - King Bombee
dp[i][j][k]:=i回移動した、現在地がj、xに到達した回数のmod2がk
■F - Shortest Good Path
巡回セールスマンっぽい+bfs
dp[i][j]:=今の状態がi、今の位置がjとする
■G - Construct Good Path
辺が大量にあるが、最小全域木のみ考えればいい。
まず適当に0を頂点にdfsをして各頂点を通る回数の遇奇を考える。
もう一度bfsを行い、葉から帳尻合わせを行う、頂点の遇奇が入力のsのと異なっていれば
親に一度戻り帰ってくれば、+1できる。
■Ex - Linear Maximization
凸包を動的に作る必要がある。
サイズが2^nの凸包を沢山持っておいて
追加ごとにマージしていく感じ。
マージの総計算量は、、、謎！
これさえできればクエリごとにlogQ個の凸包の最大値の累積最大を求めればよく、
最大値は黄金分割探索などで凸包ごとにlogQで行えるのでO(Q(logQ)^2)で求まる。
