B - Intersection 解説 by en_translator
Since \(A_i\) and \(B_i\) are between \(1\) and \(1000\) (inclusive), \(x\) should be between \(1\) and \(1000\), too.
Therefore, it is sufficient to check for each \(x\) if it actually satisfies the given \(N\) conditions.
As another solution, the conditions where \(x\) should satisfy is equivalent to \(\max(A_1, A_2, A_3, \dots, A_N) \le x\le \min(B_1, B_2, B_3, \dots, B_N)\), so the answer can be found as \(\max(0, \min(B_1, B_2, B_3, \dots, B_N) - \max(A_1, A_2, A_3, \dots, A_N) + 1)\).
The complexity of the first solution is \(\Theta (N \max{B_i})\), while the other is \(\Theta(N)\), which is faster.
Sample Code (C)
#include <stdio.h>
#include <stdbool.h>
int ri() {
int n;
scanf("%d", &n);
return n;
}
int main() {
int n = ri();
int a[n];
for (int i = 0; i < n; i++) a[i] = ri();
int b[n];
for (int i = 0; i < n; i++) b[i] = ri();
int res = 0;
for (int i = 1; i <= 1000; i++) {
bool ok = true;
for (int j = 0; j < n; j++) if (i < a[j] || i > b[j]) ok = false;
if (ok) res++;
}
printf("%d\n", res);
return 0;
}
Sample Code (Python)
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
res = 0
for i in range(1, 1001) :
ok = True
for j in range(n) :
if i < a[j] or i > b[j] : ok = False
if ok : res += 1
print(res)
投稿日時:
最終更新: