백준25259 Art Collections

작성일 | In

문제 링크

  • http://icpc.me/25259

문제 출처

  • 2022 Baltic OI A번

풀이

inversion의 개수를 이용해 배열을 정렬하는 인터랙티브 문제입니다.

Subtask 2 ($Q \leq 2N^2$, 20점)

알고리즘 과목에서 배우는 정렬 알고리즘들은 대부분 비교 기반 알고리즘입니다. 이왕이면 우리가 알고 있는 정렬 알고리즘을 사용하는 것이 편하니까 두 수를 비교하는 방법을 생각해 봅시다.
어떤 두 수 $A[u], A[v] (u < v)$를 교환하면 $A[u] < A[v]$일 때 inversion의 개수가 증가하고 $A[u] > A[v]$일 때 inversion의 개수가 감소합니다. 이 점을 이용하면 2번의 쿼리로 두 수를 비교할 수 있습니다. 따라서 원하는 $O(N^2)$ 정렬 알고리즘을 이용해 해결할 수 있습니다.

Subtask 3 ($Q \leq 2N\log_2 N$, 35점)

비교 연산을 최대 $N \log_2 N$번 수행하는 합병 정렬이나 힙 정렬을 사용하면 됩니다.

Subtask 4 ($Q \leq N\log_2 N$, 50점)

사실 잘 생각해 보면 비교를 할 때마다 2번의 쿼리를 사용할 필요가 없습니다. 맨 처음에 배열 $\left{ 1, 2, 3, \cdots, N \right}$의 inversion 개수를 알고 있다면, 쿼리를 1번만 사용해서 비교를 할 수 있습니다. 따라서 최대 $N \log_2 N$번의 쿼리를 사용할 수 있습니다.

Subtask 5 ($Q \leq 2N$, 70점)

비교 기반 정렬의 하한이 $\Omega(N \log N)$이라는 것은 잘 알려져 있습니다. 따라서 $O(N)$번의 쿼리를 이용해 문제를 해결하기 위해서는 다른 방법을 사용해야 합니다.

정렬된 배열 $\left{ A_1, A_2, A_3, \cdots, A_N \right}$을 생각해 봅시다. $x$번째로 작은 수 $A_x$를 맨 앞으로 옮긴 배열 $\left{ A_x, A_1, \cdots, A_{x-1}, A_{x+1}, \cdots, A_N \right}$은 $x-1$개의 inversion을 갖고 있습니다. 반대로 $A_x$를 맨 뒤로 옮긴 배열 $\left{ A_1, \cdots, A_{x-1}, A_{x+1}, \cdots, A_N, A_x \right}$는 $N-x$개의 inversion을 갖고 있습니다.

$A_x$를 제외한 다른 원소들을 섞은 배열, 즉 $\left{ A_x, A_{p_1}, \cdots , A_{p_{N-1}} \right}$과 $\left{ A_{p_1}, \cdots, A_{p_{N-1}}, A_x \right}$에서는 어떨까요? $A_x$를 제외한 부분의 inversion의 개수를 $y$라고 하면, $A_x$가 앞에 있을 때는 $y+x-1$개, 뒤에 있을 때는 $y+N-x$개일 것입니다.
$y$값은 배열마다 매번 다를 수 있기 때문에 없애고 싶습니다. 앞에 있는 값에서 뒤에 있는 값을 빼면 $(y+x-1) - (y+N-x) = 2x-N-1$이 되고, 결국 이 값에 대한 오름차순으로 원소를 정렬하면 된다는 것을 알 수 있습니다.

$2x-N-1$이 값을 구하기 위해 각 수마다 2번의 쿼리가 필요하므로 $2N$번의 쿼리가 필요합니다.

Subtask 6 ($Q \leq N$, 100점)

Subtask 5에서 수행하는 연산은 각 $x$마다 $\left{x, 1, \cdots, x-1, x+1, \cdots,N\right}$과 $\left{1,\cdots,x-1,x+1,\cdots,N,x\right}$의 inversion을 구하는 것입니다. 이는 배열의 cyclic shift와 같기 때문에 $N$개의 배열의 inversion 개수만 알아도 문제를 해결할 수 있습니다.
이 방법을 이용하면 100점을 받을 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include "art.h"
#include <bits/stdc++.h>
using namespace std;

void solve(int n){
    vector<int> cost(n+1);
    vector<int> v(n);
    iota(v.begin(), v.end(), 1);
    for(int i=1; i<=n; i++){
        cost[i] = publish(v);
        rotate(v.begin(), v.begin()+1, v.end());
    }
    vector<int> res(n);
    iota(res.begin(), res.end(), 1);
    sort(res.begin(), res.end(), [&](int a, int b){ return cost[a] - cost[a%n+1] < cost[b] - cost[b%n+1]; });
    answer(res);
}