Codeforces Round 873 (Div. 2)
A. Divisible Array (800)
$\displaystyle \sum_{i=1}^n i = \dfrac{n(n+1)}{2}$이므로 $2, 4, 6, 8, \dots$ 처럼 해주면 된다.
B. Permutation Swap (900)
$a_i=j$ 라고 할 때, $j$가 원래 있어야 할 위치는 $j$인데 $i$에 있는 것이므로 $p$는 $p \mid \vert j-i \vert$ 여야된다.
따라서 모든 $j$에 대하여 $\vert j-i \vert$들의 GCD가 정답이다.
C. Counting Orders (1100)
$b_i$가 큰 순서대로 보면 $a$에 남아있는 $b_i$ 보다 큰 것의 개수를 정답에 곱해준다.
그리고 $a$에서 큰 것부터 하나씩 삭제한다.
이것이 가능한 이유는 $a$에서 남은 것 중 $b_i$ 보다 큰 것중에 아무거나 써도 정답의 경우의 수에 영향을 미치지 않기 때문이다.
D1. Range Sorting (Easy Version) (2000)
D1. Range Sorting (Easy Version)
이 문제는 아이디어가 어렵지 개수를 세는건 자료구조를 써서 쉽게 구현할 수 있다.
D2. Range Sorting (Hard Version) (2400)
D2. Range Sorting (Hard Version)
두 가지 관찰은 성공했지만 정확한 정답의 정의와 정답을 구하는 방법은 구하지 못해서 에디토리얼을 참고했다.
Observation 1
구간 $[l, r]$ 을 고려할 때, 최적의 해에선 어떤 교차하는 두 구간은 없다. 그렇다면 항상 그 두 구간을 하나로 합쳐주는 것이 이득이다.
Observation 2
구간 $[l, r]$에서 $l \le p < r$ 이 존재해 $\text{Max}{i=l}^p a_i < \text{Min}{i=p+1}^r a_i$ 라면 $[l, p]$와 $[p+1,r]$ 구간의 정답을 독립적으로 구해서 더해줄 수 있다.
Idea
Observation 2에서와 같이 구간을 둘로 쪼갤 수 있는 pivot $p$를 찾았다면 우린 무조건 정답을 $r-l$에서 $1$감소시켜줄 수 있다.
즉, 가능한 $p$의 개수가 구간 $[l, r]$에 몇개가 있는지를 알면 $r-l$ 에서 그걸 뺀 것이 $[l, r]$ 에서의 beauty이다.
위 조건을 만족하는 $(l,p,r)$ 쌍들 중에 $0 \sim n-1$의 $i$에 대해 $\text{Min}(a[p+1, r])=a_i$ 인 $i$들을 고려한다.
즉, $[p+1, r]$ 구간에선 $a_i$가 가장 작고 $a_p$는 $a_i$ 보다 작아야 하므로 $i$의 왼쪽에서 $a_k < a_i$ 를 만족하는 가장 큰 $p$를 고려한다.
여기서 정의된 $p$를 $B$라고 하고 $i$를 $C$ 라고 하자. 그럼 모든 $i$마다 $(B,C=i)$ 를 구할 수 있다.
스택을 써서 $O(n)$에 구하자.
$A, D$를 정의해 $a_A>a_C, \ A < B$ 를 만족하는 $A$ 중 $B$와 가장 가까운 것으로,
$a_D < a_C \quad D > C$ 를 만족하는 $D$중 $C$ 와 가장 가까운 것이라고 하자.
$(l, p, r)$ 을 봤을 때 $A < l \le B$ 그리고 $C \le r < D$ 인 것이 위의 조건을 만족한다.
다시말해, 정답에 $(B-A) \cdot (D-C)$ 를 빼줄 수 있다.
처음에 정답은 모든 가능한 $r-l$의 합이다.
Idea 분석
$(B-A)(D-C)$ 가 정답에서 빼지게 되는 이유는 다음과 같다.
$(A,B,C,D)$ 가 있다면, $[A+1, B]$ 에서 아무거나 고르고 $[C, D-1]$ 에서 아무거나 고르고 그걸 $B', C'$라고 할 때
$(B-A)(D-C)$개의 구간들은 모두 $B$를 $p$로 하나씩 갖게 되는 것이다.
구현
$A$를 찾는데는 $B$에서부터 왼쪽으로 $C$ 보다 작은것까지 계속 진행해야하므로 Sparse Table 을 쓸 수 있다.
$C$를 갖고 $B,D$ 를 찾는건 스택으로 가능하다.
시간복잡도는 $O(n \log n)$인데 $B$도 두 개의 스택으로만 찾아서 $O(n)$ 도 가능하다고 한다.
못 푼 원인
$(l, p, r)$ 이 있을 때 $(l, r)$ 을 고정시키고 $p$가 몇개인지를 구할 수 없는 문제였다.
반대로 $p$를 기준으로 $l, r$ 이 어디까지 이어지는지를 파악해야 했다.
경우의 수 문제에서 이처럼 $[l,r]$에서 $x$가 몇개가 있는가를 구하는 문제에서 $x$ 를 가질 수 있는 구간 $[l, r]$ 은 어디일까를 반대로 생각하는 것은 중요한 테크닉같다.
void solve() {
int n, ans = 0;
cin >> n;
vi a(n + 2);
a = vi(n + 2);
for (int i = 1; i <= n; i++) {
cin >> a[i];
ans += i * (i - 1) / 2;
}
a[0] = -2e15;
a[n + 1] = -2e15;
int LOG = 20;
vvi mx(LOG, vi(n + 2));
for (int i = 0; i <= n; i++) mx[0][i] = a[i];
for (int k = 1; k < LOG; k++)
for (int i = 0; i + (1 << k) - 1 <= n; i++)
mx[k][i] = max(mx[k - 1][i], mx[k - 1][i + (1 << (k - 1))]);
vi left_first_small(n + 2), right_first_small(n + 2);
stack<int> s;
s.push(0);
for (int i = 1; i <= n; i++) {
while (a[s.top()] > a[i]) s.pop();
left_first_small[i] = s.top();
s.push(i);
}
s = stack<int>();
s.push(n + 1);
for (int i = n; i >= 1; i--) {
while (a[s.top()] > a[i]) s.pop();
right_first_small[i] = s.top();
s.push(i);
}
for (int C = 1; C <= n; C++) {
int B = left_first_small[C];
if (B != -1) {
int A = B;
for (int k = LOG - 1; k >= 0; k--)
if (A - (1 << k) >= 0 && mx[k][A - (1 << k) + 1] < a[C])
A -= (1 << k);
int D = right_first_small[C];
ans -= (B - A) * (D - C);
}
}
cout << ans << endl;
}
Comments