[AtCoder] ARC 106 C – Solutions

問題

方針

ある区間の集合を \( S \) として、\( i \) 番目の区間を \( S_i = [L_i, R_i] \) とします。このとき、高橋君の点を \( T(S) \) とし、青木君の点数を \( A(S) \) とします。また、

\[ M = T(S) – A(S) \]

です。

\( N = M \) のとき

このとき、\( T(S) = N \wedge A(S) = 0\) となりますが、\( A(S) = 0 \) となるような \( S \) は存在しません。

\( M = 0 \) のとき

このとき、\( T(S) = A(S) \) となればいいので、\( S_i = [2i, 2i + 1] \) とすればよいです。このとき、\( L_i < L_{i + 1} \wedge R_i < R_{i + 1} \) となるので、高橋君と青木君のプログラムによる \( S \) の並び替えは起こりません。したがって、\( T(S) = A(S) \) となります。

\( M = N – 1 \wedge M \neq 0\) のとき

\( A(S) \geq 1 \) であることは明らかなので、\( T(S) = N \wedge A(S) = 1\) を満たす \( S \) が存在するかを考えます。\( T(S) = N \) より、全ての区間が重なっていないので、\( A(S) = 1 \) となるような \( S \) は存在しません。\( A(S) = 1 \) のとき、区間が重なっている必要があるので矛盾します。

\( 1 \leq M \leq N – 2 \) のとき

\( T(S) = N – 1 \wedge A(S) = N – M – 1\) を満たす \( S \) が存在するかどうかを考えます。まず初めに、\( N \) 個の区間を \( S_i = [2i, 2i + 1] \) とします。このとき、\( T(S) = A(S) = N \) です。

\( T(S) = N – 1 \) より、\( S \) から \( 1 \) つだけ区間を選び、\( T(S) = N – 1\) となるように区間の値を変更します。ここで、\( j \) 番目の区間の \( R_j \) を \( R_j = 3N \) とし、\( L_j < L_i \ (i \neq j)\) となるような \( L_i, L_j \) が存在するとき、\( T(S) = N – 1 \) となります。これは、\(R_i \) を昇順に並び替えた時、\( R_j \) は \( N \) 番目の区間となるからです。

なので、\( L_j < L_i \ ( i \neq j) \) を満たし、\( A(S) = N – M – 1 \) となるような \( L_j \) が存在するかを考えます。

\( A(S) = N – M – 1 \) より、\( j = N – M -1 \) として、\( L_i < L_{j}  \ ( 1 \leq i \leq N – M – 1) \) を満たすとき、\( A(S) = N – M – 1 \) となります。これは、\( R_j = 3N \) より、\( L_{j + 1} \) 以降の区間を選ぶことはできません。これは、\( L_i \) を昇順に並び替えたとき、\( L_j \) は \( N – M -1 \) 番目の区間となるからです。

したがって、\( S_{N – M – 1} = [2(N – M – 1), 3N] \) と更新すればいいです。

\( M < 0 \) のとき

このとき、\( T(S) < A(S) \) を満たす必要があります。青木君が選んだ区間の集合を \( S^* \) とします。\( S^* \) を \( L_i \) の昇順に並べたときの \( i \) 番目の区間を \( S^*_i = [L^*_i, R^*_i]\) とします。このとき、

\[ R^*_i < L^*_{i + 1} \]

となります。同様に、高橋君が選んだ区間を \( S^{\prime} \) とすると、

\[ R^{\prime}_i < R^{\prime}_{i+1}\]

となります。このとき、\( 1 \) つめの区間の終端は、\( R^{\prime}_1 \leq R^{*}_1 \) となるので、次の区間の候補は高橋君の方が多いことが分かります。したがって、帰納的に \( A(S) \leq T(S) \) が言えそうです。これは、区間スケジューリング問題と呼ばれるそうです。

コード