UCPC 2022 예선 D-14 문제풀이 일지

목차

1. 오늘의 알고리즘 진도

- 1958번: LCS 3

- 13711번: LCS 4

- 13305번: 주유소

- 18258번: 큐 2

- 6064번: 카잉 달력

- 14500번: 테트로미노

- 11401번: 이항 계수 3

2. AtCoder Beginner Contest 256

- A번: 2^N

- B번: Batters

- C번: Filling 3x3 array

- D번: Union of Interval

3. Codeforces Round #801 (Div. 2)

- A번: Subrectangle Guess

- B번: Circle Game

- C번: Zero Path

---

오늘의 알고리즘 진도

오늘은 다양한 분류의 문제를 풀어보기로 했습니다.

C++ 코드 템플릿

혹시 제 코드를 참고하실 분들은 코드 최상단에 아래의 코드를 붙여넣어 주세요.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;
#define F first
#define S second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define forn(i, a, b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()

1958번: LCS 3

https://www.acmicpc.net/problem/1958

1958번: LCS 3

3차원 LCS 문제입니다. 원리는 2차원 LCS와 같아요.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string A, B, C;
    cin >> A >> B >> C;
    int a = A.size();
    int b = B.size();
    int c = C.size();
    vector<vector<vector<int>>> lcs(a, vector<vector<int>>(b, vector<int>(c)));
    forn(i, 0, a-1) {
        forn(j, 0, b-1) {
            forn(k, 0, c-1) {
                if (A[i] == B[j] && A[i] == C[k]) {
                    if (i > 0 && j > 0 && k > 0) lcs[i][j][k] = lcs[i-1][j-1][k-1] + 1;
                    else lcs[i][j][k] = 1;
                } else {
                    int I = i > 0 ? lcs[i-1][j][k] : 0;
                    int J = j > 0 ? lcs[i][j-1][k] : 0;
                    int K = k > 0 ? lcs[i][j][k-1] : 0;
                    lcs[i][j][k] = max(I, max(J, K));
                }
            }
        }
    }
    cout << lcs[a-1][b-1][c-1];

    return 0;
}

알고리즘 분류: 다이나믹 프로그래밍, 문자열

현 시점 난이도: 골드 III

13711번: LCS 4

https://www.acmicpc.net/problem/13711

13711번: LCS 4

LCS를... xxx로 풀 수 있다면 믿으시겠습니까?

사실 입력의 크기를 보면 대충 감이 오긴 합니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> A(N+1), B(N+1);
    forn(i, 1, N) {
        int a;
        cin >> a;
        A[a] = i;
    }
    forn(i, 1, N) cin >> B[i];
    vector<int> lis;
    forn(i, 1, N) {
        if (i == 1 || lis.back() < A[B[i]]) lis.PB(A[B[i]]);
        else {
            int lb = lower_bound(all(lis), A[B[i]]) - lis.begin();
            lis[lb] = A[B[i]];
        }
    }
    cout << lis.size();

    return 0;
}

알고리즘 분류: 가장 긴 증가하는 부분 수열: o(n log n)

현 시점 난이도: 골드 I

13305번: 주유소

https://www.acmicpc.net/problem/13305

13305번: 주유소

간단한 그리디 문제입니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> road(N-1), price(N);
    forn(i, 0, N-2) cin >> road[i];
    forn(i, 0, N-1) cin >> price[i];
    ll ans = 0;
    int current_price = 1e9;
    forn(i, 0, N-2) {
        if (price[i] < current_price) current_price = price[i];
        ans += (ll)current_price * road[i];
    }
    cout << ans;

    return 0;
}

알고리즘 분류: 그리디 알고리즘

현 시점 난이도: 실버 IV

18258번: 큐 2

https://www.acmicpc.net/problem/18258

18258번: 큐 2

간단한 큐 구현 문제입니다. '10845번: 큐' 문제보다 입력이 큽니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    queue<int> q;
    forn(i, 1, N) {
        string s;
        cin >> s;
        if (s == "push") {
            int X;
            cin >> X;
            q.push(X);
        } else if (s == "pop") {
            if (q.empty()) cout << "-1\n";
            else {
                cout << q.front() << "\n";
                q.pop();
            }
        } else if (s == "size") {
            cout << q.size() << "\n";
        } else if (s == "empty") {
            cout << int(q.empty()) << "\n";
        } else if (s == "front") {
            if (q.empty()) cout << "-1\n";
            else cout << q.front() << "\n";
        } else { // s == "back"
            if (q.empty()) cout << "-1\n";
            else cout << q.back() << "\n";
        }
    }

    return 0;
}

알고리즘 분류: 자료 구조, 큐

현 시점 난이도: 실버 IV

6064번: 카잉 달력

https://www.acmicpc.net/problem/6064

6064번: 카잉 달력

나머지와 관련된 문제입니다.

저는 중국인의 나머지 정리를 공부하고 풀었습니다. 더 쉬운 접근도 있지만 제 풀이가 시간 복잡도상 가장 효율적입니다.

pii extended_euclid(int M, int N) {
    if (N == 0) return {1, 0};
    pii E = extended_euclid(N, M % N);
    return {E.S, E.F - (M / N) * E.S};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int M, N, x, y;
        cin >> M >> N >> x >> y;
        // want to calculate a in:
        // a = x (mod M) = y (mod N)
        // if x != y mod gcd(M, N), invalid
        int g = gcd(M, N);
        if (x % g != y % g) {
            cout << "-1\n";
            continue;
        }
        // solve equation Mp + Nq = g by 'extended euclid algorithm'
        pii PQ = extended_euclid(M, N);
        // solve equation a = x*N/g*q + y*M/g*p (mod LCM(M, N))
        int l = lcm(M, N);
        ll ans = ((ll)x * N / g * PQ.S + (ll)y * M / g * PQ.F) % l;
        if (ans <= 0) ans += l;
        cout << ans << "\n";
    }

    return 0;
}

알고리즘 분류: 수학, 정수론, 중국인의 나머지 정리

현 시점 난이도: 실버 I

14500번: 테트로미노

https://www.acmicpc.net/problem/14500

14500번: 테트로미노

브루트포스, 빡구현의 중의 빡구현일 듯한 문제입니다.

그래프 탐색을 활용해도 예외 처리를 피할 수 없기에, 그냥 테트로미노의 가능한 경우의 수 19가지를 전부 배열에 넣어서 예외 처리 없이(?) 반복문을 돌리는 걸로 해결했습니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vector<vector<int>> g(N, vector<int>(M));
    forn(i, 0, N-1) forn(j, 0, M-1) cin >> g[i][j];
    vector<vector<pii>> tetro = {
            {{0, 3}, {0, 0},
             {0, 0}, {1, 0}, {2, 0}, {3, 0}},
            {{0, 0}, {0, 3},
             {0, 0}, {0, 1}, {0, 2}, {0, 3}},
            {{0, 1}, {0, 1},
             {0, 0}, {1, 0}, {0, 1}, {1, 1}},
            {{0, 1}, {0, 2},
             {0, 0}, {0, 1}, {0, 2}, {1, 2}},
            {{0, 2}, {0, 1},
             {0, 0}, {1, 0}, {2, 0}, {0, 1}},
            {{0, 1}, {0, 2},
             {0, 0}, {1, 0}, {1, 1}, {1, 2}},
            {{0, 2}, {-1, 0},
             {0, 0}, {1, 0}, {2, 0}, {2, -1}},
            {{0, 1}, {-2, 0},
             {0, 0}, {1, 0}, {1, -1}, {1, -2}},
            {{0, 2}, {0, 1},
             {0, 0}, {0, 1}, {1, 1}, {2, 1}},
            {{0, 1}, {0, 2},
             {0, 0}, {1, 0}, {0, 1}, {0, 2}},
            {{0, 2}, {0, 1},
             {0, 0}, {1, 0}, {2, 0}, {2, 1}},
            {{0, 1}, {0, 2},
             {0, 0}, {0, 1}, {1, 1}, {1, 2}},
            {{0, 2}, {-1, 0},
             {0, 0}, {1, 0}, {1, -1}, {2, -1}},
            {{0, 1}, {-1, 1},
             {0, 0}, {1, 0}, {0, 1}, {1, -1}},
            {{0, 2}, {0, 1},
             {0, 0}, {1, 0}, {1, 1}, {2, 1}},
            {{0, 2}, {0, 1},
             {0, 0}, {1, 0}, {1, 1}, {2, 0}},
            {{0, 1}, {-1, 1},
             {0, 0}, {1, 0}, {1, -1}, {1, 1}},
            {{0, 2}, {-1, 0},
             {0, 0}, {1, 0}, {2, 0}, {1, -1}},
            {{0, 1}, {0, 2},
             {0, 0}, {0, 1}, {0, 2}, {1, 1}},
    };
    int ans = 0;
    forn(i, 0, N-1) forn(j, 0, M-1) {
        for (vector<pii> t : tetro) {
            if (i < 0-t[0].F || i > N-1-t[0].S ||
                j < 0-t[1].F || j > M-1-t[1].S) continue;
            int sum = g[i+t[2].F][j+t[2].S]
                    + g[i+t[3].F][j+t[3].S]
                    + g[i+t[4].F][j+t[4].S]
                    + g[i+t[5].F][j+t[5].S];
            ans = max(ans, sum);
        }
    }
    cout << ans;

    return 0;
}

알고리즘 분류: 브루트포스 알고리즘, 구현

현 시점 난이도: 골드 V

11401번: 이항 계수 3

https://www.acmicpc.net/problem/11401

11401번: 이항 계수 3

이항 계수를 구하는 문제인데, 입력이 큽니다.

하지만 다행히 소수인 1,000,000,007로 나눈 나머지를 물었기 때문에, 나머지 연산의 성질을 이용해 풀 수 있습니다.

우선 N까지의 팩토리얼을 다이나믹 프로그래밍으로 모두 계산합니다. 여기에 O(N)의 시간이 걸립니다.

다음으로 이항 계수 공식의 분모에 해당하는 K!(N-K)!의 1,000,000,007에 대한 '나머지 연산의 곱셈 역원'을 페르마의 소정리를 이용하여 구합니다. 이를 위해 거듭제곱을 해줘야 하는데 분할 정복을 이용하면 O(logN)의 시간이 걸립니다.

모두 계산했다면 곱해주기만 하면 됩니다. 그래서 전체 시간복잡도는 O(N).

int P = 1e9 + 7;

ll power(int x, int n) {
    if (n == 0) return 1;
    ll u = power(x, n/2);
    u = u * u % P;
    if (n % 2) u = u * x % P;
    return u;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;
    vector<ll> fac(N+1, 1);
    forn(i, 2, N) {
        fac[i] = fac[i-1] * i % P;
    }
    ll A = fac[N];
    ll B = fac[K] * fac[N-K] % P;
    ll ans = A * power(B, P-2) % P;
    cout << ans;

    return 0;
}

알고리즘 분류: 수학, 정수론, 조합론, 분할 정복을 이용한 거듭제곱, 모듈로 곱셈 역원, 페르마의 소정리

현 시점 난이도: 골드 I

AtCoder Beginner Contest 256

개인 통산 2번째 ABC였습니다(한번 신청해놓고 안 봐서 사이트에는 3번으로 기록됨)

1번째 ABC를 3솔브했기 때문에 4솔브한 이번 결과에 어느 정도 만족합니다.

E를 푸는 흐름에 대한 아이디어는 있었지만 유니온 파인드를 몰랐기 때문에 풀 수는 없었습니다.

다음에는 그래프 알고리즘을 더 많이 알고 도전하고 싶습니다.

A번: 2^N

https://atcoder.jp/contests/abc256/tasks/abc256_a

A - 2^N

비트 연산이 가능한 범위의 입력이므로 매우 쉽습니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    cout << (1 << N);

    return 0;
}

B번: Batters

https://atcoder.jp/contests/abc256/tasks/abc256_b

B - Batters

문제에서 시키는 대로 구현하면 되는 문제인 것 같습니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> A(N);
    forn(i, 0, N-1) cin >> A[i];
    deque<int> sq(4);
    int P = 0;
    forn(i, 0, N-1) {
        sq[0] = 1;
        forn(k, 1, A[i]) sq.push_front(0);
        while (sq.size() > 4) {
            P += sq.back();
            sq.pop_back();
        }
    }
    cout << P;

    return 0;
}

C번: Filling 3x3 array

https://atcoder.jp/contests/abc256/tasks/abc256_c

C - Filling 3x3 array

처음에는 백트래킹으로 9개의 숫자에 대한 경우의 수를 전부 탐색하려고 했지만, 자세히 보니 4개만 탐색해도 나머지는 알아서 정해지더라고요.

vector<int> h(3), w(3), g(9);
int ans = 0;

void solve(int k) {
    if (k == 4) {
        g[2] = h[0] - g[0] - g[1];
        g[5] = h[1] - g[3] - g[4];
        g[6] = w[0] - g[0] - g[3];
        g[7] = w[1] - g[1] - g[4];
        g[8] = h[2] - g[6] - g[7];
        if (g[2] + g[5] + g[8] != w[2]) return;
        forn(i, 0, 8) if (g[i] <= 0) return;
        ++ans;
        return;
    }
    forn(i, 1, 28) {
        g[(k / 2) * 3 + k % 2] = i;
        solve(k+1);
        g[(k / 2) * 3 + k % 2] = 0;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    forn(i, 0, 2) cin >> h[i];
    forn(i, 0, 2) cin >> w[i];
    solve(0);
    cout << ans;

    return 0;
}

D번: Union of Interval

https://atcoder.jp/contests/abc256/tasks/abc256_d

D - Union of Interval

처음에는 감이 잘 오지 않았지만, 뭔가 '강의실 배정' 문제 풀듯이 그리디하게 접근할 수 있을 것 같았습니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<pii> HOI(N);
    forn(i, 0, N-1) {
        int L, R;
        cin >> L >> R;
        HOI[i] = {-R, L};
    }
    sort(all(HOI));
    stack<pii> ans;
    forn(i, 0, N-1) {
        if (i == 0) ans.push(HOI[i]);
        pii t = ans.top();
        if (t.S > HOI[i].S) {
            if (t.S > -HOI[i].F) ans.push(HOI[i]);
            else {
                ans.pop();
                ans.push({t.F, HOI[i].S});
            }
        }
    }
    while (!ans.empty()) {
        cout << ans.top().S << " " << -ans.top().F << "\n";
        ans.pop();
    }

    return 0;
}

Codeforces Round #801 (Div. 2)

그린 탈출이다~!

D가 매우 어려웠고 A~C를 제때 풀었기에 가능한 퍼포먼스가 아닐까 싶습니다.

C가 약간의 아이디어를 요구하는 DP 문제로 마침 최근에 BOJ에서 많이 풀었던 유형과 비슷했기에 풀 수 있었던 것 같아요.

이번 대회로 자신감을 조금 얻을 수 있었습니다!

A번: Subrectangle Guess

https://codeforces.com/contest/1695/problem/A

Problem - A - Codeforces

System Testing에서 많은 오답자를 낸 문제입니다.

최대값을 가진 원소의 위치를 어떤 경우에도 찾을 수 있도록 max 변수 초기값을 -1e9-1로 지정하는 등의 방법으로 코너케이스를 피해갈 수 있었습니다.

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m));
    tiii mx = {-1e9-1, -1, -1};
    forn(i, 0, n-1) forn(j, 0, m-1) {
            cin >> grid[i][j];
            if (get<0>(mx) < grid[i][j]) {
                mx = {grid[i][j], i, j};
            }
        }
    int _, x, y;
    tie(_, x, y) = mx;
    cout << max(x+1, n-x) * max(y+1, m-y) << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

B번: Circle Game

https://codeforces.com/contest/1695/problem/B

Problem - B - Codeforces

이거 설마 스프라그 그런디인가 뭔가 쓰는 거 아니겠지...? 의심했는데 당연히 Div. 2의 B번 문제니까 그건 아니지요.

n이 짝수일 때와 홀수일 때 상황이 완전히 달라지는 것을 잘 파악하면 게임 이론에 대한 지식 없이도 풀 수 있습니다.

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    pii mike_min = {1e9, 0}, joe_min = {1e9, 1};
    forn(i, 0, n-1) {
        cin >> a[i];
        if (i % 2) {
            if (joe_min.F > a[i]) joe_min = {a[i], i};
        } else {
            if (mike_min.F > a[i]) mike_min = {a[i], i};
        }
    }
    if (n % 2) cout << "Mike\n";
    else {
        if (mike_min > joe_min) cout << "Mike\n";
        else cout << "Joe\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

C번: Zero Path

https://codeforces.com/contest/1695/problem/C

Problem - C - Codeforces

DP문제일 것 같아서 어떻게 값을 저장할지를 고민을 하다가 각 칸에 도달할 때까지의 합의 최댓값, 최솟값을 저장하면 0이 합이 되는 것이 가능한지는 0이 최댓값과 최솟값 사이에 있는지만 판별하면 되겠다고 생각했습니다.

엄밀한 증명은 하지 않았지만 어차피 2씩 간격을 두고 구간 내의 모든 값이 합이 될 수 있을 거라는 판단이 들었어요.

그리고 m+n이 짝수일 때는 애초에 합이 홀수로만 나오니까 예외 처리를 해주면 되구요.

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m));
    forn(i, 0, n-1) forn(j, 0, m-1) cin >> grid[i][j];
    if ((m+n-1) % 2) {
        cout << "NO\n";
        return;
    }
    vector<vector<pii>> sum(n, vector<pii>(m)); // {min, max}
    forn(i, 0, m+n-2) forn(j, 0, i) {
            if (j >= n || i-j >= m) continue;
            if (i == 0) sum[0][0] = {grid[0][0], grid[0][0]};
            else {
                pii up = j > 0 ? sum[j-1][i-j] : MP(10000, -10000);
                pii left = i-j > 0 ? sum[j][i-j-1] : MP(10000, -10000);
                sum[j][i-j] = {min(up.F, left.F) + grid[j][i-j],
                               max(up.S, left.S) + grid[j][i-j]};
            }
        }
    if (sum[n-1][m-1].F <= 0 && sum[n-1][m-1].S >= 0) cout << "YES\n";
    else cout << "NO\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

---

BOJ 솔브 수가 적어서 아쉬웠지만 대회를 치면서 자신감이 오른 하루였습니다.

내일은 더 많은 문제를 풀고 싶네요.