最高レート更新
ABCトーナメント初参加
■A - Tires
s[s,size()-1]だけ見ればいい
■B - Mongeness
4重ループを回す
■C - Triangle?
3重ループ。
２点を通る直線を求めて、もう一点がその直線上
とやったが、普通に面積求めて0じゃないかで十分。
■D - 8 Puzzle on Graph
実装問題
どの頂点になにの駒があるか(空頂点も含め)
をstringで表してbfsを行えばいい
■E - Integers on Grid
逆から考える
列行ごとに、現在の最大を保持しておけばいい。
ただし、aは同じなことがあり得るので、更新タイミングに注意する。
■F - Problem where +s Separate Digits
手元でサンプル１を書き出してみる。
1=1
1+2,12=15
1+2+3,1+23,12+3,123=168
末尾のものは10倍される可能性があるので別でもってみる
つまり
0+1
1+14
16+152
これをもう少し考えてみると
16 = 1 + 15
152 = 14 * 10 + 3 * 4
というとがわかる
実際に続けて見ると
184 = 1 + 15 + 168
1552=152 * 10 + 4 * 8
となりサンプル1の1736を得る。
■G - Roll or Increment
戦略がわかれば解ける。
操作１をするゾーンと操作２をするゾーンを分ける。
とs<=tの場合は
e,e,e,e,3a,2,a,0,e,e,e,e,e
のような期待値の並びになり
e = (e+e+e+3a+2a......+e)/n+bなのでeが求まる
これを立式すると相加相乗が扱える形になるので極値付近を考えればいい。
■H - Security Camera 2
LP双対というらしい。
max cx,Ax<=b,x>=0
と
min by,tAy>=c,y>=0
が双対になるらしい。
問題で聞かれているのは下の最小値なので双対を取って上の形にすると
ぐっと睨むとフローな見た目なので最小費用流が求まればいい。
負辺を補正して、あとはaclにおまかせする
