2024년 9월 넷째 주 PS 일지

9/23 월요일

11694 님 게임

 

9/24 화요일

USACO 2023 December Contest Gold

31057 Flight Routes

31059 Haybale Distribution: 모르는 삼분 탐색 알고리즘이라 풀지 않았습니다.

나머지 한 문제는 나중에 풀 예정입니다.

 

27546 Typing Contest: 여름학교 모의고사에 출제됐었던 문제라서 업솔빙을 했습니다.

여름학교 모의고사 당시에는 효율적인 브루트 포스로 뚫렸던 32점?까지 긁었었던 것 같습니다.

이후 풀이 시간에 비트 필드 DP라는 사실은 들었는데 디테일은 잘 기억나지 않아 업솔빙을 하고자 했습니다.

 

서브테스크 7

$dp[x]$를 집합 $x$에 포함된 글자들이 키보드에 배치됐을 때 최소 비용이라 정의해줍니다.

그리고 $cnt[x][y]$를 정의해주는데 이 배열에는 글자 $x$와 $y$가 이 순서로 이웃한 개수를 저장해줍니다. 이는 $O(N)$으로 전처리 가능합니다.

 

그러면 $dp[x]=min(dp[x-i]) + \displaystyle \sum_{i\in x, j\notin x} (cnt[i][j]*R+cnt[j][i]*L)$가 되므로 문자열의 서로 다른 글자 개수가 $K$라고 할 때 $O(K^{2}2^K)$ 시간복잡도로 해결해 줄 수 있습니다.

#include <bits/stdc++.h>
#define int long long

#define MAX 2000000
#define MAX_K 21
#define INF 0x7f7f7f7f7f7f7f7f
#define endl '\n'

using namespace std;
typedef pair<int, int> pr;
typedef array<int, 3> tp;

int dp[MAX], cnt[MAX_K][MAX_K];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int N, Q, A, L, R, K = 0, res = 0, val;
    string S;

    cin >> N >> S;

    for (int i = 1; i <= N; i++)
        K = max(K, S[i - 1] - 'A' + 1ll);

    for (int i = 1; i < N; i++)
        cnt[S[i - 1] - 'A'][S[i] - 'A']++;

    dp[0] = 0;

    cin >> Q;
    while (Q--) {
        cin >> A >> L >> R;
        res = A * N;

        for (int i = 1; i < (1 << K); i++) {
            dp[i] = 0;
            for (int j = 0; j < K; j++) {
                for (int k = 0; k < K; k++) {
                    if ((i & (1 << j)) && !(i & (1 << k)))
                        dp[i] += cnt[j][k] * R + cnt[k][j] * L;
                }
            }

            val = INF;
            for (int j = 0; j < K; j++) {
                if (!(i & (1 << j)))
                    continue;
                val = min(val, dp[i ^ (1 << j)]);
            }

            dp[i] += val;
        }

        cout << res + dp[(1 << K) - 1] << '\n';
    }

    return 0;
}

서브테스크 9

여기부터는 도저히 생각이 나지 않아 에디토리얼을 깠습니다. 하나의 더 관찰이 필요한데 문자열 양 끝에 있는 문자들이 각각 키보드의 $i$번째, $j$번째 자리에 있을 때 왼쪽으로 이동하는 경우의 수가 오른쪽으로 이동하는 경우의 수보다 $i-j$만큼 크다는 것입니다. 이를 이용해서 각 $i, j$에 대하여 $dp[x]$에 최소 비용 대신 최소 왼쪽 이동 횟수를 저장해주면 됩니다. 그러면 $dp$ 채우는 시간복잡도는 $O(N+K^{3}2^K)$가 걸리고, 이는 아주 여유롭습니다.

그리고 쿼리당 $K^2$가지 경우에 대해서 $L$과 $R$을 잘 집어넣어 계산해 주면, 전체 $O(N+K^{3}2^K+QK^2)$의 시간복잡도로 해결해 줄 수 있습니다.

#include <bits/stdc++.h>
#define int long long

#define MAX 2000000
#define MAX_K 21
#define INF 2147483647
#define endl '\n'

using namespace std;
typedef pair<int, int> pr;
typedef array<int, 3> tp;

int dp[MAX], cst[MAX], cnt[MAX_K][MAX_K], val[MAX_K][MAX_K];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int N, Q, A, L, R, K = 0, res = 0, X;
    string S;

    cin >> N >> S;

    for (int i = 1; i <= N; i++)
        K = max(K, S[i - 1] - 'A' + 1ll);

    for (int i = 1; i < N; i++)
        cnt[S[i - 1] - 'A'][S[i] - 'A']++;

    for (int i = 0; i < (1 << K); i++) {
        for (int j = 0; j < K; j++) {
            for (int k = 0; k < K; k++) {
                if ((i & (1 << j)) && !(i & (1 << k)))
                    cst[i] += cnt[j][k];
            }
        }
    }

    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            fill(dp, dp + (1 << K), INF);
            dp[0] = 0;

            for (int x = 1; x < (1 << K); x++) {
                X = __builtin_popcount(x) - 1;
                for (int y = 0; y < K; y++) {
                    if ((X == i && y != S[0] - 'A') || (X == j && y != S[N - 1] - 'A'))
                        continue;
                    if (x & (1 << y))
                        dp[x] = min(dp[x], dp[x ^ (1 << y)] + cst[x]);
                }
            }

            val[i][j] = dp[(1 << K) - 1];
        }
    }

    cin >> Q;
    while (Q--) {
        cin >> A >> L >> R;
        res = 0x7f7f7f7f7f7f7f7f;

        for (int i = 0; i < K; i++) {
            for (int j = 0; j < K; j++) {
                if (val[i][j] == INF)
                    continue;
                res = min(res, val[i][j] * R + (val[i][j] + i - j) * L);
            }
        }

        cout << res + N * A << '\n';
    }

    return 0;
}

 

9/25 수요일

31060 Bovine Acrobatics

 

9/26 목요일

27174 Урок физкультуры

 

9/27 금요일

Codeforces Round 975 (Div. 2)

코포를 쳤습니다. 역대급으로 문제가 잘 풀렸고 최종적으로 145위, 오렌지 퍼포먼스가 떴습니다.

 

14469 소가 길을 건너간 이유 3

 

9/28 토요일

INU 코드페스티벌 2024 Open Contest

백준 대회를 치렀고 11문제 중 10솔을 해 5등을 차지했습니다.

 

31058 Minimum Longest Trip: 해싱으로 풀려다가 더 쉬운 방법을 찾아 해결했습니다. 

8986 전봇대: 삼분 탐색을 배웠습니다.

31059 Haybale Distribution: 삼분 탐색을 필요로 했던 유사코 문제를 해결했습니다.

 

9/29 일요일

14916 거스름돈

 

Codeforces Round 976 (Div.2)

기숙사 코포를 했습니다.