心が折れたので適当に書きなぐります。
■A - Make 10
自信がなかったので、正当性を真面目に考えるも結局確信は持てず
3は2セットないと駄目なので2,6,4で作るのと同じ
つまり1,2,3で5を作りたい
3,2
3,1,1
2,2,1
2,1,1,1
1,1,1,1,1の作り方がある
上から優先的に作る。
■B - Cross-free Matching
簡単に考えるため、頂点を共用してないとする。
pairでもってaでソートして見ると
ai < ajのときに bi < bjなら交わらない。
つまりLISを求めればいい。
本問は頂点を共有しているが、これはソートを少し工夫すればいい。
■C - Maximize GCD
本質的にできてた気がするのだけど山程TLEしてた。
gcdをxにするために必要な最小コストはいくら？
という問題を考える。
これは、全てを一番近いxの倍数に切り上げ、その差分がコストになる。
で、このコストをどうやっても求めればいいかという問題。
x(k-1) < ai <=x * kならx*k-aiがコストになる。
これをlowerboundなどで適当にやっていたのがTLEの原因で
普通にkを動かしていき
0 < ai<=kを満たすaiの数と和
k < ai<=2*kを満たすaiの数と和
を順々に求める。適当な累積和の前処理は必要。
計算量はO(Σai/x)とかなので十分に速い
■D - Pure Straight
解説を読んだ。
使う要素と移動先を決め打つと
操作にかかる回数は、Σ|移動先-移動元|+移動前の段階の転倒数
になる。
さらに移動元を固定すると移動先は
移動元の真ん中の要素と(偶数のときはどっちでもいい)移動先の真ん中の要素が一緒になるようなものが最適なものに含まれる。
サンプルで考える
4 3
3 1 2 1を
1 2 3 1にしたい
これはdist0+inv2=ans2となるわけだが
distの部分は
(1-1)-0
(1±0)-1
2-(1+1)が内訳で()の内部のものは、定数になる(厳密には偶数奇数で微妙に場合分けがいる)。
ここまで来るとあとはbitdpで転倒数とidxの部分を足しながら遷移させればいよい。
■E - Infinite Operations
解説を読んだ。
直感的に数列のすべての要素の差の絶対値の半分になりそうな気持ちには確かになる。厳密なことは公式解説。
ここまでわかれば配列が変更されたときに、絶対値の差がどうなるかを求まればいいだけになるので
これは座圧してセグメント木で頑張ればいい。
頭悪すぎ。昨日得たレートと自己肯定感が全部吹っ飛んだ。
ばーかばーか。
