[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) \) が言えそうです。これは、区間スケジューリング問題と呼ばれるそうです。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int N, M; cin >> N >> M; if (M == 0) { for (int i = 1; i <= N; i++) { cout << 2 * i << " " << 2 * i + 1<< "\n"; } return 0; } if (M < 0 || N == M || M == N - 1) { cout << "-1\n"; return 0; } for (int i = 1; i <= N; i++) { if (i == N - M - 1) { cout << 2 * (N - M - 1) << " " << 3 * N<< "\n"; } else { cout << 2 * i << " " << 2 * i + 1 << "\n"; } } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません