빡알수 Div.3 라운드 #1

리뉴얼 이후 첫 번째 연습이다.
일단 3시간으로 시간을 늘리고 문제 수는 4개로 줄인만큼 난이도를 높였다.

일단 좌셋이 되기는 했는데, 개인별 격차가 좀 있어서 다음은 실버1~골드3 정도로 낼 생각이다.

난 3위가 됐다.
B번은 문제를 읽는데 시간이 많이 걸렸고, 이해하고도 모르겠어서 건너뛰었다.

D번은 제출하고서 틀려가지고 도대체 다른 방법이 뭐가 있지? 하고 mjh님한테 여쭤봤다가
알고보니까 연습 때 고친 코드 Ctrl+C를 제대로 안 눌렀나 보다. 다시 제출하니 맞았다. (내 1솔 책임져 손가락아)

코드 질문은 댓글이나 Discord DM으로 남겨주세요~!!!

A. 부분수열의 합 2 (1208)

+) 냅색으로도 풀 수 있다고 한다

줄거리

모든 원소의 합이 주어진 값 $S$가 되게 하는 부분수열의 개수를 찾는 것이다.
'부분수열'의 정의를 헷갈릴 수 있다.

일반적으로 부분배열은 arr[1...n]이 있을 때, arr[i...j](1≤i≤j≤n) 같이 연속한 부분을 뜻한다.
반면, 부분수열은 연속하지 않아도 된다. 원 배열의 일부 원소를 지워서 만든 새로운 배열이라고 생각하면 된다.

접근법

부분배열이였다면, $N$이 매우 작으므로 누적 합 배열을 써도 되고, naive하게 구현해도 된다.
하지만 이 경우는 다르다.
일단 부분 수열에서 임의의 원소가 지워졌는지 아닌지를 모두 확인해야 한다.
예외는 없다.
그런데 $2^N$을 모두 계산하는 것은 절대로 무리이다.

그러면 전에 풀어보았던 합이 0인 네 정수의 아이디어를 이용하자.
만약 딱 떠올랐다! 하면 돌아가서 풀어보기를 추천한다.

따라서 부분수열을 앞에 있는 $\lfloor N/2\rfloor$개와 뒤에 있는 $N-\lfloor N/2\rfloor$개로 나누어서 생각을 해보자.
그러면 앞의 수열에서 임의의 부분수열을 잡고 그 수열의 합을 $L_i$이라고 하자.
마찬가지로 뒤쪽에 대해 $R_i$도 만들자.

그러면 각 원소 $L_i$에 대해, $R_j = S-L_i$가 몇 개 존재하는지를 세주면 답이 될 것이다.
근데 이 $i, j$를 전부 매칭하면 TLE가 뜰 것이다.
따라서! 이진 탐색을 이용해 빠르게 찾아내도록 하자!!

$2^{ \lfloor N/2 \rfloor}$와 뒤의 $2^{N-\lfloor N/2\rfloor}$로 나누어서 탐색해야 한다.
그럼 시간 복잡도는 $O(2^{\lfloor N/2 \rfloor}\times \log_22^{N-\lfloor N/2\rfloor}) = O(2^{N/2}\times (N-\lfloor N/2\rfloor)) = O(N\cdot 2^{N/2})$가 된다. $N$을 대입하면 $O(20\cdot 2^{20})=O(20\cdot 10^6)=O(10^7)$으로 시간 안에 해결이 가능하다.

코드

int n, s, arr[40], L[1<<20], R[1<<20];

void pre(int b, int i, int s, int e, int* sum) {
    if (s == e) return;
    *(sum+( b|(1<<i) )) = *(sum+ b ) + arr[s];
    
    pre(b|(1<<i), i+1, s+1, e, sum);
    pre(b,        i+1, s+1, e, sum);
}

void solve() {
    cin >> n >> s;
    for (int i = 0; i < n; ++i) cin >> arr[i];
    pre(0, 0, 0, n/2, L); pre(0, 0, n/2, n, R);

    sort(R, R+(1<<(n-n/2)));

    long long ans = 0;
    for (int i = 0; i < 1<<(n/2); ++i) {
        ans += 
        upper_bound(R, R+(1<<(n-n/2)), s-L[i])
        -lower_bound(R, R+(1<<(n-n/2)), s-L[i]);
    }
    cout << ans - (s == 0);
}

D. 정렬 (17432)

줄거리

버블 소트의 과정에서 swap이 일어나는 횟수를 구해보시오.
버블 소트의 순서만 살짝 주의하자.

접근법

관찰이 필요한 문제이다.
각 원소를 $a_i$라 하고, $a_j(1 \leq j < i)$에 대해 $a_j<a_i$인 $a_j$의 개수를 $G_i$라고 하자.
이 때, 문제의 답은 $\sum G_i = m$인 어떤 수열이다.

$a=[1,2,3,4,5]$

$i$	1	2	3	4	5
$a_i$	1	2	3	4	5
$G_i$	0	0	0	0	0

$\therefore \sum G_i=0$

---

$a=[5,4,3,2,1]$

$i$	1	2	3	4	5
$a_i$	5	4	3	2	1
$G_i$	0	1	2	3	4

$\therefore \sum G_i=10$

---

이 두 가지 경우에 대한 관찰을 바탕으로 알 수 있는 점이 있다.
1. $G_i\leq n-1$이다.
2. 그러면 $G_n$의 값을 조정하고 $n-1$에 대한 문제로 축소시킬 수 있다. 진법과 비슷한 원리이다. 축소 후에도 대소관계만 따진다는 속성을 생각하면 아무 무리가 없다는 것을 알 수 있다.

그러면 어떤 $m\; s.t.\;m\leq \frac{n(n-1)}{2}$에 대해 $m = 0\cdot b_1+1\cdot b_2+\cdots (n-1)\cdot b_n\;($단, $b_i=\{0,1\})$을 만족하는 $b_i$를 항상 찾을 수 있음이 증명되면 충분하다는 것을 알 수 있다.

하지만, 일단 이를 증명하는 것은 아래의 증명 목차에게 떠넘기도록 하자.

코드

void solve() {
    int n, m; cin >> n >> m;
    bool chk[n]; memset(cnt, 0, n);
    stack<int> s;
    for (int i = n-1; i >= 0; --i) {
        if (m >= i) {
            chk[n-i] = true;
            m -= i;
            s.push(n-i);
        }
    }
    for (int i = n; i >= 1; --i) if (!chk[i]) {
        s.push(i);
    }
    while (!s.empty()) {
        cout << s.top() << ' ';
        s.pop();
    }
    cout << '\n';
}

증명

수학적 귀납법을 열심히 사용하면 더 가독성이 떨어질 수 있다.
대신 다음의 자명한 수식들로 같은 결과를 이끌어내는 과정을 보자.