Codeforces Round 870 (Div. 2)
A. Trust Nobody
$a$를 정렬 후 $l \coloneqq 0 \to n$ 까지 브루트포스 해보자.
$l$ 명이 거짓말쟁이라면 앞에서 $0 \sim l-1$ 사람들은 참이여야 하고 $l \sim n-1$ 사람들은 거짓이여야 한다.
참이여야 하는 사람들은 $a_i \le l$ 이여야 하고 거짓이여야하는 사람들은 $a_i > l$ 이여야 한다.
가능한 경우가 있는지 검사해주면 된다.
B. Lunatic Never Content
가 충족이 되어야 하므로
$\begin{aligned} a_1-a_n = k_1x\\ a_2-a_{n-1} = k_2x\\ \vdots \end{aligned}$ 처럼 되어서 결국 $x$ 는 $a_i-a_{n+1-i}$ 들의 최대공약수임을 알 수 있다.
C. Dreaming of Freedom
무한한 라운드를 만들기 위해서 계속 $2$개 이상 남길 수 있는 방법이 있는지 확인한다.
만약 $n=1 \text{~or~} m=1$ 이라면 한 가지밖에 선택 못하므로 항상 YES 이다.
그렇지 않다면 $n$의 최소소인수 $p$를 확인한다.
$p \le m$ 이라면 $\dfrac np$ 명 씩 $p$ 개의 옵션을 계속해서 선택할 수 있다는 뜻이므로 NO 이고, 아니면 YES 이다.
void solve() {
int n, m;
cin >> n >> m;
if (m == 1 || n == 1) {
cout << "YES\n";
return;
}
for (int d = 1; d * d <= n; d++) {
if (n % d == 0) {
int d2 = n / d;
if ((d != 1 && d <= m) || d2 <= m) {
cout << "NO\n";
return;
}
}
}
cout << "YES\n";
}
D. Running Miles
관찰하면 $b_{i_1}$과 $b_{i_3}$ 은 항상 구간에서 제일 큰 수 3개 중 두개임을 알 수 있다.
그렇지 않다면 구간을 좁혀서 그렇게 만들 수 있다.
세 개의 인덱스가 $l,m,r$ 이라고 한다면, $m$을 기준으로 $b_l+l$과 $b_r-r$ 이 최대가 되는 것을 각각 찾으면 되므로
$b_i+i, b_i-i$ 에대해 각각 왼쪽 오른쪽으로 구간합 최대값을 관리하며 쿼리한다.
E. Walk the Runway
bitset 으로 최적화를 해서 풀어야 하는 특이한 문제이다.
어떤 두 모델 $a,b$가 있다고 하자. 어떤 마을에서 $r_a < r_b$ 인데 다른 마을에서 $r_a > r_b$ 라면 어떤 순서로 넣어도 두 모델은 같이 존재할 수 없다.
이러한 관계성이 없이 존재할 수 있는 모델들을 구하자.
$a \to b$ 를 $a$가 모든 마을에서 $b$보다 레이팅이 낮은 관계라고 하고 그래프로 생각하자.
아무 마을을 기준으로 잡고 그 마을에서 레이팅을 기준으로 모델들을 오름차순 정렬하면 문제를 $O(N^2)$ DP 로 해결할 수 있게된다.
레이팅이 증가하는 순서로만 관계성이 있기 때문에 DAG가 되기 때문이다.
여하튼 $a \to b$ 같은 관계들을 어떻게 빨리 구하느냐가 문제의 핵심인데, naive하게는 $O(n^2m)$ 이므로 이건 bitset을 사용한다.
5000 길이의 bitset을 $N$개 만든다.
모든 마을을 순회하며 모델들의 인덱스를 그 마을에서의 레이팅 오름차순으로 정렬한다.
bitset 하나를 관리하고 모델들을 순회하며 각 모델들의 자리에 $1$을 채워준다.
이제 그 마을에서 어떤 모델이 봤을 때 $1$ 이 채워진 자리는 자기보다 레이팅이 낮은 모델들이다.
따라서 자신의 간선 집합에서 $O(\dfrac n{64})$ 를 업데이트 해줄 수 있다.
아래 코드는 구현이 반대이다.
using bs = bitset<5000>;
void solve() {
int m, n;
cin >> m >> n;
vi p(n);
fv(p);
vvi r(m, vi(n));
fv2(r);
vector<bs> edges(n, bs().set());
vi idx(n);
iota(all(idx), 0);
for (int i = 0; i < m; i++) {
sort(all(idx), [&](int a, int b) { return r[i][a] < r[i][b]; });
bs available = bs();
for (int j = 0, k = 0; j < n; j++) {
while (r[i][idx[k]] < r[i][idx[j]]) available[idx[k++]] = 1;
edges[idx[j]] &= available;
}
}
vector<ll> dp(n);
for (int i = n - 1; i >= 0; i--) {
int I = idx[i];
dp[i] += p[I];
for (int j = i - 1; j >= 0; j--) {
int J = idx[j];
if (edges[I][J]) dp[j] = max(dp[j], dp[i]);
}
}
cout << maxe(dp);
}
Comments