6完90:58 + 1ペナ 230位
GのCHT忘れすぎてて思い出すのに時間かかった
A flip
さすがにやるだけですね～、めっちゃ簡潔にする方法も言語によってはありそう
(AC 2:15)
B レ
むず、問題文をほんとうに信じ込むことでBでUnionFindを使うことになりました
まあD問題と思えばいいだけなので、UnionFindして後ろからたどっていきます
(AC 6:22)
C Coverage
そういえば久しぶりのbit全探索ですね
考察自体はほとんどなく...
(AC 9:12)
D Step Up Robot
前回のDとの温度差よ
ほんとうにDPやるだけでした、これなら最短回数求めさせてもよさそうだけどね
(AC 13:31)
E Swap Places
これも過去に類題があるので考察もあんまりしなかった
上の問題を考えると、(高橋くんの位置、青木君の位置)をペアとした頂点をN^2個つくり、そこでBFSをすればいいことがわかります
辺もそんなに貼らなくてよさそうなので信じて投げると通ります
マルチテストケースなのに、初期化を忘れて1ペナ...
(AC 28:02)
F Teleporter Takahashi
順位表で全然解かれていない＆無限にペナを出しそうな見た目をしていたので避けました
こういうの時間内で解くの大変だよね
(AC --:--)
G Shopping in AtCoder store
解けそうな見た目しているので考えます
まずBをソートしても問題ないので、ソートしておきます
とりあえず全員に買ってもらうとすると、(B[1] + C[j]) × N円得ることができます
その状態から、i人分諦めたとしてどうなるか差分を考えてみましょう
諦めた人のぶん(B[1] + C[j]) × iはマイナスになります
一方で、N-i人はまだ買ってもらえるので、(B[i] - B[1]) × (N-i)だけプラスになります
よって、i人分諦めたときに「全員買ってもらう」状態からどのくらい得するか？は
(B[i] - B[1]) × (N-i) - (B[1] + C[j]) × iで表されます
ここで、jが関連しているのはC[j]×iの部分だけであることが分かります
つまり、Bを用いる部分は使いまわすことができます
ざっくりした式を考えると、(Bから計算できるもの) - C[j]×iになって、これを最大化すればよいです
複数の一次関数から最大化するこの形の問題は、CHT(Convex Hull Trick)で解けることが知られているので、それぞれの一次関数をあらかじめ計算してあげて、CHTでクエリに答えるとよいです
(AC 90:58)
総括
7完安定しない
