レートがなかなか戻ってこない。
完全に自信を喪失した立ち回りをしている。
result:oooooo--
rateing:1866->1865
■A - Horizon
誤差で殺す系？と思いきや単純にやって問題なし
■B - Integer Division
負の割り算は面倒という話(c++)
場合分けをする
■C - Knight Fork
二回移動して到達できるか
■D - Prime Sum Game
高橋の手それぞれに対応する青木の手があるかどうか
■E - Subtree K-th Max
各頂点に対してmaxKの大きさのvectorを作成する。
■F - Construct Highway
方針は一瞬だがツメの甘さに30分を消費する。
dsuで連結成分に分解し、それぞれから次数が1と2以上のものを結ぶ。
当然次数が2のものは1になる。
これは適当にqueueなりstackでやればいい。
■G - Builder Takahashi
あと10分あれば解けた。
どう見ても最小カットの問題。
辺の張り方は頂点を倍にして
x0とx1の間にcostCを
a1とb0の間にINFを
b1とa0の間にINFを
辺が切られているかどうかは
g.min_cut(0)をして、受け取ったvectorのx0とx1の符号が異なればいい。
■Ex - Dice Product 2
工夫してメモ化再帰する問題
解説通りに式変形を行うと
f(x)=n/(n-1)*(1+1/n*Σf(x/i))ような形になり
x/iに合わられる数がsqrt(x)になるのは典型なので
遷移がまとめて行われる。
まとめたうえでの計算量は？という話になるが、これはO(x^(3/4))になるのでまにあう
ただし、mapでは間に合わないので、unordered_mapを使うなどする。
