[Codeforces] Round #573 (Div. 2) C. Tokitsukaze and Discard Items

問題

方針

題意

\( 1 \) から \( n \) までの数字があり、\( k \) 個ごとに仕切りがあります。初期の配置では、仕切り \( i \) には、\( ik \) から \((i + 1)k\) までの数字が存在しています。

ここで、\( p_i \) の数字を次の手順で消していきます。仕切りを小さい方から調べていき、\( p_i \) が含まれる仕切り \( j \) とすると、\( j \) に含まれる数字の最大値まで、\( p_{i} \) 以降の数字を一度に消すことができます。また、数字を消した後、後ろの前に詰めていきます。これらを全ての \( p_i \) について行います。

仕切りに含まれる最大値を考える

仕切りに含まれる最大値を \( r \) とします。一番最初のページの仕切りは、\( r_1 = k \) となりますが、\( k < p_1 \) のとき、

\[p_1 \leq km\]

を満たす最小の \( m \) を \( m^{*} \) とすると、\( r_1 = km^{*} \) となります。

次に、\( r_1 \) 以下の \( p_i\) の個数を数えます。このとき、\( r_1 \) 以下の \( p_i \) は一回の操作で消すことができます。この個数を \( t_1 \) とし、\( r < p_j \) のとき、操作回数が \( 1 \) 増加し、\( r_2 = r_1 + t_1 \) とします。また、このとき、\( r_2 < p_j \) のとき、

\[r_2 \gets \lceil \dfrac{p_j – r_2}{k} \rceil k + r_2\]

と更新します。

コード