류나의 작은 DB

27살 류나의 바르고 다르게 살기

Programming/Algorithms

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

Ryuna (류준범) 2022. 6. 19. 03:19

목차

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

첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다.

www.acmicpc.net

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(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, [1, 2, 3]과 [1, 3, 2]의 LCS는 [1, 2] 또는 [1, 3]

www.acmicpc.net

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번: 주유소

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1

www.acmicpc.net

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

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

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지

www.acmicpc.net

간단한 큐 구현 문제입니다. '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번: 카잉 달력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다.

www.acmicpc.net

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

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

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번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변

www.acmicpc.net

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

그래프 탐색을 활용해도 예외 처리를 피할 수 없기에, 그냥 테트로미노의 가능한 경우의 수 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

자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

www.acmicpc.net

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

하지만 다행히 소수인 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

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

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

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

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

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

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

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

처음에는 백트래킹으로 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

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

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

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

 

codeforces.com

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

 

codeforces.com

이거 설마 스프라그 그런디인가 뭔가 쓰는 거 아니겠지...? 의심했는데 당연히 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

 

codeforces.com

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 솔브 수가 적어서 아쉬웠지만 대회를 치면서 자신감이 오른 하루였습니다.

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

 

1 2 3 4 5 6 7 ··· 35