AWC 0109

AWC는 전형적인 문제들이 많다보니 백준 푸는 느낌도 나고 가볍게 참여하기 좋은 것 같습니다.

이번에는 D번 제한을 꼼꼼히 안읽어서 풀이를 다 생각해놓고 시간을 너무 많이 쓴게 조금 아쉽네요.

A. Organizing the Bookshelf

책을 왼쪽부터 최대한 서로 가깝게 놓으면 됩니다.

$S$ 에 $K + D_i$ 를 더하는 것을 반복하면 시간 복잡도 $O(N)$ 에 해결할 수 있습니다.

코드 (C++)

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int D[101010];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N, S, K;
    cin >> N >> S >> K;
 
    for (int i = 1; i <= N; i++) cin >> D[i];
 
    ll ans = S;
    for (int i = 1; i <= N; i++) ans += K + D[i];
 
    cout << ans;
 
    return 0;
}

B. Organizing Strings

뭘 먼저 지우는지는 중요하지 않고, 지울 수 있는게 없을 때 까지 계속 지우면 됩니다.

증명

간단한 증명

뭘 먼저 지우는지에 따라 순서가 달라지려면, 어떤 쌍 $(i, i + 1)$ 을 지우는 대신 오른쪽(혹은 왼쪽)이 지워지고 나서 합쳐졌을때 $(i + 1, i + 2)$ 을 지우는 경우를 생각해 볼 수 있습니다.

오른쪽과 합쳐진 경우 순간적으로 $i$ , $i + 1$ , $i + 2$ 의 문자가 모두 같은데, $(i, i + 1)$ 을 지우나 $(i + 1, i + 2)$ 를 지우나 결과는 똑같습니다.

왼쪽이나 좌우 모두 합쳐진 경우도 같은 방식으로 결과가 똑같음을 알 수 있습니다.

엄밀한 증명

어떤 순서로 쌍을 지우더라도 항상 같은 결과로 수렴함을 수학적 귀납법을 이용해 증명해 보겠습니다.

먼저 $S$ 에서 임의의 쌍을 지운 모든 문자열에 대해 위 가정이 성립한다고 합시다.

$S$ 에서 $(i, i + 1)$ 을 지워서 $_iS$ 라 하고, $S$ 에서 $(j, j + 1)$ 을 지워서 $_jS$ 라고 합시다.

일반성을 잃지 않고 $i \leq j$ 라 합시다.

만약 $i = j$ 혹은 $i + 1 = j$ 라면 $_iS = {}_jS$ 이므로 $_iS$ 와 $_jS$ 는 같은 결과로 수렴합니다.

그렇지 않다면 $_iS$ 에서 쌍 $(j, j + 1)$ 을 항상 지울 수 있습니다.

또한 $_jS$ 에서도 쌍 $(i, i + 1)$ 을 항상 지울 수 있으므로 $_iS$ 와 $_jS$ 는 항상 같은 결과로 수렴합니다.

따라서 모든 문자열 $S$ 는 어떤 순서로 쌍을 지우든 똑같은 결과로 수렴합니다.

Naive하게 구현하면 $O(|S|^2)$ 이지만, 스택을 이용하면 $O(|S|)$ 에 해결할 수 있습니다.

$S$ 를 순회하면서 스택에 문자를 넣고, 스택의 맨 위 두 글자가 같으면 제거하는 방식으로 구현하면 됩니다.

코드 (C++)

#include <bits/stdc++.h>
using namespace std;
 
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
 
    string S;
    cin >> S;
 
    vector<char> stk;
    for (int i = 0; i < S.length(); i++) {
        stk.push_back(S[i]);
 
        if (stk.size() >= 2 and stk[stk.size() - 2] == stk.back()) {
            stk.pop_back();
            stk.pop_back();
        }
    }
 
    cout << stk.size();
 
    return 0;
}

C. Membership Registration at the Premium Shop

모든 가입 신청은 서로 다른 사람이 제출하므로 한번 가입된 사람이 다른 곳에 가입함으로 인해서 가입자 수가 줄어드는 경우는 생각할 필요가 없습니다.

따라서 모든 상점은 멤버십 가입자 수가 감소하지 않습니다.

멤버십 가입자 수가 증가하는 경우는 오직 가입자 수가 최대 한계보다 작은 경우입니다.

따라서 우선순위는 전혀 고려할 필요가 없고, 상점의 가입자 수가 한계이면 무시, 아니면 $1$ 증가시키면 정답을 얻을 수 있습니다.

코드 (C++)

#include <bits/stdc++.h>
using namespace std;
 
int A[201010], C[201010];
int cnt[201010];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N, M, Q;
    cin >> N >> M >> Q;
 
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= M; i++) cin >> C[i];
 
    while (Q--) {
        int P, D;
        cin >> P >> D;
 
        cnt[D] = min(cnt[D] + 1, C[D]);
    }
 
    for (int i = 1; i <= M; i++) cout << cnt[i] << ' ';
 
    return 0;
}

D. Selection of Gems

만약 weight-reduction이 없었다면 일반적인 배낭 문제입니다.

일반적인 배낭 문제의 공간 $dp[i][j]$ 에서 weight-reduction을 수행한 횟수를 추가해 $dp[i][j][k]$ 형태로 작성하면 됩니다.

점화식은 간략하게 다음과 같이 쓸 수 있습니다.

dp[i][j][k] = \min(dp[i - 1][j][k], dp[i - 1][j - W_i][k] + B_i, dp[i - 1][j - W_i / 2][k - 1] + B_i)

시간 복잡도가 $O(NCK)$ 이지만 $N(K + 1)(C + 1) \leq 2 \times 10^7$ 이므로 시간 내에 해결할 수 있습니다.

코드 (C++)

$N(K + 1)(C + 1)$ 크기의 3차원 배열을 선언했더니 시간 초과가 나서 토글링을 사용해 최적화했습니다.

배낭 문제 점화식 특성상 탐색 순서만 잘 조정해주면 $(K + 1)(C + 1)$ 크기의 배열만으로도 문제를 푸는 것이 가능합니다.

#include <bits/stdc++.h>
using namespace std;
 
template <typename T> bool minimize(T &target, T candidate) {
    return target > candidate ? (target = candidate, true) : false;
}
template <typename T> bool maximize(T &target, T candidate) {
    return target < candidate ? (target = candidate, true) : false;
}
 
using ll = long long;
 
int B[101010], W[101010];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N, C, K;
    cin >> N >> C >> K;
 
    for (int i = 1; i <= N; i++) cin >> B[i] >> W[i];
 
    vector<vector<vector<ll>>> dp(2, vector(C + 1, vector(K + 1, 0LL)));
 
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= C; j++) {
            for (int k = 0; k <= K; k++) {
                dp[i & 1][j][k] = dp[(i - 1) & 1][j][k];
 
                if (j - W[i] >= 0)
                    maximize(dp[i & 1][j][k], dp[(i - 1) & 1][j - W[i]][k] + B[i]);
                if (k and j - W[i] / 2 >= 0)
                    maximize(dp[i & 1][j][k],
                                dp[(i - 1) & 1][j - W[i] / 2][k - 1] + B[i]);
            }
        }
    }
 
 
    ll ans = 0;
    for (int j = 0; j <= C; j++) {
        for (int k = 0; k <= K; k++) {
            maximize(ans, dp[N & 1][j][k]);
        }
    }
 
    cout << ans;
 
    return 0;
}

E. Stress Meter

$N$ 의 크기가 조금 작습니다.

제곱근 분할법을 이용해서 문제를 해결할 수 있습니다.

스트레스 레벨 $G = s$ 로 시작해서 버킷의 모든 task를 처리하고 난 후의 $C$ 와 $G$ 를 구해줍니다.

스트레스 $G < K$ 이므로 스트레스의 경우는 많아봤자 $K$ 개입니다.

이는 $O(KN)$ 에 모두 전처리할 수 있습니다.

이후 쿼리를 처리할 때는 버킷에 걸쳐있는 부분은 직접 계산해주고, 완전히 포함되는 부분은 전처리한 값을 이용해주면 $O(\sqrt N)$ 에 답을 구할 수 있습니다.

전체 시간 복잡도는 $O(KN + Q\sqrt N)$ 입니다.

코드 (C++)

#include <bits/stdc++.h>
using namespace std;
 
int A[60606], B[60606];
int limitCnt[333][333], stress[333][333];
 
int N, K, Q;
 
pair<int, int> processTasks(int l, int r, int G) {
    int C = 0;
 
    for (int i = l; i <= r; i++) {
        G += A[i] - B[i];
        G = max(G, 0);
 
        if (G >= K) {
            C++;
            G = 0;
        }
    }
 
    return {C, G};
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> N >> K >> Q;
 
    int sz = sqrt(N);
 
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
 
    for (int b = 0; b * sz < N; b++) {
        for (int s = 0; s <= K; s++) {
            tie(limitCnt[b][s], stress[b][s]) =
                processTasks(b * sz, min(N, (b + 1) * sz) - 1, s);
        }
    }
 
    while (Q--) {
        int L, R;
        cin >> L >> R;
        L--, R--;
 
        int lBucket = L / sz;
        int rBucket = R / sz;
 
        int C = 0;
        int G = 0;
 
        if (lBucket == rBucket) {
            auto [c, g] = processTasks(L, R, 0);
            C += c;
            G = g;
        } else {
            auto [c, g] = processTasks(L, (lBucket + 1) * sz - 1, 0);
            C += c;
            G = g;
 
            for (int b = lBucket + 1; b < rBucket; b++) {
                C += limitCnt[b][G];
                G = stress[b][G];
            }
 
            tie(c, g) = processTasks(rBucket * sz, R, G);
            C += c;
            G = g;
        }
 
        cout << C << ' ' << G << '\n';
    }
 
    return 0;
}

AWC는 전형적인 문제들이 많다보니 백준 푸는 느낌도 나고 가볍게 참여하기 좋은 것 같습니다.

이번에는 D번 제한을 꼼꼼히 안읽어서 풀이를 다 생각해놓고 시간을 너무 많이 쓴게 조금 아쉽네요.

A. Organizing the Bookshelf

책을 왼쪽부터 최대한 서로 가깝게 놓으면 됩니다.

$S$ 에 $K + D_i$ 를 더하는 것을 반복하면 시간 복잡도 $O(N)$ 에 해결할 수 있습니다.

코드 (C++)

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int D[101010];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N, S, K;
    cin >> N >> S >> K;
 
    for (int i = 1; i <= N; i++) cin >> D[i];
 
    ll ans = S;
    for (int i = 1; i <= N; i++) ans += K + D[i];
 
    cout << ans;
 
    return 0;
}

B. Organizing Strings

뭘 먼저 지우는지는 중요하지 않고, 지울 수 있는게 없을 때 까지 계속 지우면 됩니다.

증명

간단한 증명

오른쪽과 합쳐진 경우 순간적으로 $i$ , $i + 1$ , $i + 2$ 의 문자가 모두 같은데, $(i, i + 1)$ 을 지우나 $(i + 1, i + 2)$ 를 지우나 결과는 똑같습니다.

왼쪽이나 좌우 모두 합쳐진 경우도 같은 방식으로 결과가 똑같음을 알 수 있습니다.

엄밀한 증명

어떤 순서로 쌍을 지우더라도 항상 같은 결과로 수렴함을 수학적 귀납법을 이용해 증명해 보겠습니다.

먼저 $S$ 에서 임의의 쌍을 지운 모든 문자열에 대해 위 가정이 성립한다고 합시다.

$S$ 에서 $(i, i + 1)$ 을 지워서 $_iS$ 라 하고, $S$ 에서 $(j, j + 1)$ 을 지워서 $_jS$ 라고 합시다.

일반성을 잃지 않고 $i \leq j$ 라 합시다.

만약 $i = j$ 혹은 $i + 1 = j$ 라면 $_iS = {}_jS$ 이므로 $_iS$ 와 $_jS$ 는 같은 결과로 수렴합니다.

그렇지 않다면 $_iS$ 에서 쌍 $(j, j + 1)$ 을 항상 지울 수 있습니다.

또한 $_jS$ 에서도 쌍 $(i, i + 1)$ 을 항상 지울 수 있으므로 $_iS$ 와 $_jS$ 는 항상 같은 결과로 수렴합니다.

따라서 모든 문자열 $S$ 는 어떤 순서로 쌍을 지우든 똑같은 결과로 수렴합니다.

Naive하게 구현하면 $O(|S|^2)$ 이지만, 스택을 이용하면 $O(|S|)$ 에 해결할 수 있습니다.

$S$ 를 순회하면서 스택에 문자를 넣고, 스택의 맨 위 두 글자가 같으면 제거하는 방식으로 구현하면 됩니다.

코드 (C++)

#include <bits/stdc++.h>
using namespace std;
 
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
 
    string S;
    cin >> S;
 
    vector<char> stk;
    for (int i = 0; i < S.length(); i++) {
        stk.push_back(S[i]);
 
        if (stk.size() >= 2 and stk[stk.size() - 2] == stk.back()) {
            stk.pop_back();
            stk.pop_back();
        }
    }
 
    cout << stk.size();
 
    return 0;
}

C. Membership Registration at the Premium Shop

따라서 모든 상점은 멤버십 가입자 수가 감소하지 않습니다.

멤버십 가입자 수가 증가하는 경우는 오직 가입자 수가 최대 한계보다 작은 경우입니다.

따라서 우선순위는 전혀 고려할 필요가 없고, 상점의 가입자 수가 한계이면 무시, 아니면 $1$ 증가시키면 정답을 얻을 수 있습니다.

코드 (C++)

#include <bits/stdc++.h>
using namespace std;
 
int A[201010], C[201010];
int cnt[201010];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N, M, Q;
    cin >> N >> M >> Q;
 
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= M; i++) cin >> C[i];
 
    while (Q--) {
        int P, D;
        cin >> P >> D;
 
        cnt[D] = min(cnt[D] + 1, C[D]);
    }
 
    for (int i = 1; i <= M; i++) cout << cnt[i] << ' ';
 
    return 0;
}

D. Selection of Gems

만약 weight-reduction이 없었다면 일반적인 배낭 문제입니다.

일반적인 배낭 문제의 공간 $dp[i][j]$ 에서 weight-reduction을 수행한 횟수를 추가해 $dp[i][j][k]$ 형태로 작성하면 됩니다.

점화식은 간략하게 다음과 같이 쓸 수 있습니다.

dp[i][j][k] = \min(dp[i - 1][j][k], dp[i - 1][j - W_i][k] + B_i, dp[i - 1][j - W_i / 2][k - 1] + B_i)

시간 복잡도가 $O(NCK)$ 이지만 $N(K + 1)(C + 1) \leq 2 \times 10^7$ 이므로 시간 내에 해결할 수 있습니다.

코드 (C++)

$N(K + 1)(C + 1)$ 크기의 3차원 배열을 선언했더니 시간 초과가 나서 토글링을 사용해 최적화했습니다.

배낭 문제 점화식 특성상 탐색 순서만 잘 조정해주면 $(K + 1)(C + 1)$ 크기의 배열만으로도 문제를 푸는 것이 가능합니다.

#include <bits/stdc++.h>
using namespace std;
 
template <typename T> bool minimize(T &target, T candidate) {
    return target > candidate ? (target = candidate, true) : false;
}
template <typename T> bool maximize(T &target, T candidate) {
    return target < candidate ? (target = candidate, true) : false;
}
 
using ll = long long;
 
int B[101010], W[101010];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N, C, K;
    cin >> N >> C >> K;
 
    for (int i = 1; i <= N; i++) cin >> B[i] >> W[i];
 
    vector<vector<vector<ll>>> dp(2, vector(C + 1, vector(K + 1, 0LL)));
 
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= C; j++) {
            for (int k = 0; k <= K; k++) {
                dp[i & 1][j][k] = dp[(i - 1) & 1][j][k];
 
                if (j - W[i] >= 0)
                    maximize(dp[i & 1][j][k], dp[(i - 1) & 1][j - W[i]][k] + B[i]);
                if (k and j - W[i] / 2 >= 0)
                    maximize(dp[i & 1][j][k],
                                dp[(i - 1) & 1][j - W[i] / 2][k - 1] + B[i]);
            }
        }
    }
 
 
    ll ans = 0;
    for (int j = 0; j <= C; j++) {
        for (int k = 0; k <= K; k++) {
            maximize(ans, dp[N & 1][j][k]);
        }
    }
 
    cout << ans;
 
    return 0;
}

E. Stress Meter

$N$ 의 크기가 조금 작습니다.

제곱근 분할법을 이용해서 문제를 해결할 수 있습니다.

스트레스 레벨 $G = s$ 로 시작해서 버킷의 모든 task를 처리하고 난 후의 $C$ 와 $G$ 를 구해줍니다.

스트레스 $G < K$ 이므로 스트레스의 경우는 많아봤자 $K$ 개입니다.

이는 $O(KN)$ 에 모두 전처리할 수 있습니다.

전체 시간 복잡도는 $O(KN + Q\sqrt N)$ 입니다.

코드 (C++)

#include <bits/stdc++.h>
using namespace std;
 
int A[60606], B[60606];
int limitCnt[333][333], stress[333][333];
 
int N, K, Q;
 
pair<int, int> processTasks(int l, int r, int G) {
    int C = 0;
 
    for (int i = l; i <= r; i++) {
        G += A[i] - B[i];
        G = max(G, 0);
 
        if (G >= K) {
            C++;
            G = 0;
        }
    }
 
    return {C, G};
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> N >> K >> Q;
 
    int sz = sqrt(N);
 
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
 
    for (int b = 0; b * sz < N; b++) {
        for (int s = 0; s <= K; s++) {
            tie(limitCnt[b][s], stress[b][s]) =
                processTasks(b * sz, min(N, (b + 1) * sz) - 1, s);
        }
    }
 
    while (Q--) {
        int L, R;
        cin >> L >> R;
        L--, R--;
 
        int lBucket = L / sz;
        int rBucket = R / sz;
 
        int C = 0;
        int G = 0;
 
        if (lBucket == rBucket) {
            auto [c, g] = processTasks(L, R, 0);
            C += c;
            G = g;
        } else {
            auto [c, g] = processTasks(L, (lBucket + 1) * sz - 1, 0);
            C += c;
            G = g;
 
            for (int b = lBucket + 1; b < rBucket; b++) {
                C += limitCnt[b][G];
                G = stress[b][G];
            }
 
            tie(c, g) = processTasks(rBucket * sz, R, G);
            C += c;
            G = g;
        }
 
        cout << C << ' ' << G << '\n';
    }
 
    return 0;
}

AWC 0109

A. Organizing the Bookshelf

B. Organizing Strings

간단한 증명

엄밀한 증명

C. Membership Registration at the Premium Shop

D. Selection of Gems

E. Stress Meter

댓글

AWC 0109

A. Organizing the Bookshelf

B. Organizing Strings

간단한 증명

엄밀한 증명

C. Membership Registration at the Premium Shop

D. Selection of Gems

E. Stress Meter

댓글