ARC122感想戦
ARC122 の感想です。といっても、NoSub撤退してしまいましたが。画像はコンテスト中に書いていたメモです。
A問題は、とりあえず、ありえる符号の並びを $N=4$ のときに書いてみました。
なんとなくDPであることはすぐに見えて、前から $i$ 番目の符号が $+$, $-$ のときの個数を数えればよさそう、というのはわかりました。
ただ、それでわかるのは、一番最後の符号が何個ずつあるかだけで、途中の符号の個数を求めるにはどうすればいいのかがわからず。ここで30分以上は時間を使ってしまいました。
ちなみに、コンテストの翌日も考えて、かなり時間を使ってようやく解けました。個数だけじゃなくて和も持ちながらDPするのが自然なんですね。なんか、解説もあまりそこは書かれてないので、自明すぎることなんでしょう。
B問題は、実はこちらはすぐに解けました。
$x+A_i-\min(A_i, 2x)$ の期待値を最小化したい、という問題です。この期待値は、次のように変形できます。
\begin{eqnarray} & & \frac{1}{N}\sum_{k=1}^N \left(x+A_i-\min(A_i,2x)\right) \\ &=& x+\frac{\sum A_i}{N} -\frac{1}{N}\sum_{k=1}^N \min(A_i,2x) \\ &=& x+\frac{\sum A_i}{N} +\frac{1}{N}\sum_{k=1}^N \max(-A_i,-2x) \\ &=& x+\frac{\sum A_i}{N} +\frac{1}{N}\sum_{k=1}^N \left( \frac{-A_i-2x}{2} + \frac{|A_i-2x|}{2} \right) \\ &=& \frac{\sum A_i}{2N} +\frac{1}{2N}\sum_{k=1}^N |A_i-2x| \\ \end{eqnarray}
途中の、$\max$ からの変形は、 \begin{eqnarray} \max(a,b) = \frac{a+b}{2} + \frac{|b-a|}{2} \end{eqnarray}であることを使っています。$a,b$ の大きい方とは、中間から、差の半分だけ大きい値、という変形です。
こうしてみると、結局、与えられた数列に対して、 $2x$ との差の絶対値の和が一番小さくなるときを考えればよく、これは数列の中央値のときだとわかります。
このことから、数列をソートして半分番目のところを見て、その値を半分にしたものを $x$ とすれば、欲しい答えが得られます。
Cは、まったくわからず。行列を使って書いたり試行錯誤しましたが、特に何も思いつかず。D以降は見てもなく終了です。