[AtCoder] ABC 149 E – Handshake

2020年1月3日

問題

方針

一般ゲストの並びを変えても影響がないので、降順に並び替えます。つまり、\( A_{i}\geq A_{i + 1} \ (0 \leq i \leq N – 2)\) を満たすとします。

最終的な幸福度が最大値のとき、\( 1 \) 回の握手で増加する幸福度の最小値 \( x \)

最終的な幸福度が最大値を取るとき、\( 1 \) 回の握手で増加する最大値は \( 2A_0 \) ですが、ここでは\( 1 \) 回の握手で増加する幸福度の最小値 \( x \) を求めます。ここで、\( d(i) \) をパワーが \( i \) 以上の人数とします。これは、累積和を利用することで求めることができます。また、\( d(1) = N \) であることは明らかです。次に、\( x \) を二分探索によって求めます。\( x \ ( 1 \leq x \leq 2 \times 10^5)\) を固定したとき、\( x \) 以上を満たす握手のパターン \( s \) を求めます。これは、

\[ s = \sum_{k = 0}^{N – 1} d(\max(0, \ x – A_k)) \]

として計算できます。\( s \geq M \) を満たすとき、\( M \) 回の握手の中で、\( 1 \) 回の握手で \( x \) 以上の幸福度が得られることが保証されます。これは、最終的な幸福度の最大値が \( Mx \) 以上であり、少なくとも \( 1 \) 回以上 \( x \) を満たす握手が存在することが分かります。

握手のシミュレーション

\( x \) 以上の握手のパターンの中で、上位 \( M \) 個の握手を行います。 ここで、\( x + 1 \) 以上を満たす握手のパターンを先に行います。\( A_i \) の累積和 \( b_i \) を次のように定義します。\( b_0 = 0\) として、

\[ b_{i} = \sum_{k = 0}^{i – 1} A_k \ (1 \leq i \leq N )\]

とします。\( x + 1 \) 以上を満たす握手のパターンを行ったときの増加する幸福を \( f \) とします。これは、次のようにして求めることができます。ゲスト \( i \) と握手する人数を \( t_i \) とし、既に握手した人数を \( k \) とします。初期値は、\( k = 0 \) です。

  1. \( v_i =  \max(0, \ x + 1 – A_i) \)
  2. \( t_i = \max(0, \ \min(d(v_i), M – k)) \)
  3. \( f \leftarrow f + b(t_i) + t_i \times A_i \)
  4. \( k \leftarrow k + t_i \)
  5. \( i \leftarrow i + 1\) 1. に戻る

したがって、答えは、\( f  + x(M – k) \) となります。

また、最終的な \( k \) の値は \( k < M \) となります。これは、\( x + 1 \) 以上の握手のパターンが \( M \) 未満であり、\( x \) 以上のパターンが \( M \) 以上であるためです。

コード

感想

解説を読んでも解法のイメージができませんでしたが、コードを見て雰囲気は分かりました。握手のパターンと\( x + 1 \) 以上の握手を先に行うというのがポイントだと思いました。難しかったですね。