[SCPC] 2020 1차 예선 풀이

Intro

대충 4시간 정도 때려 박아서 1~4번에서 만점을 받았고, 5번은 문제만 읽었습니다. 예전 SCPC 기출에 비해서는 확실히 난이도가 균일해진 것 같습니다(https://newdeal123.tistory.com/61 참조 요망). 제가 예상하는 Solved.ac 티어 난이도는 다음과 같습니다.

• 다이어트 (Silver 3)
• 카드 게임 (Platinum 3)
• 사다리 게임 (Platinum 3)
• 범위 안의 숫자 (Platinum 2)
• 우범 지역 (Diamond 2~3?)

1. 다이어트

다음과 같이 생각해봅시다. 일단 자명히 두 식단에서 칼로리가 낮은 순으로 K개만 먹어야 한다는 것을 알 수 있습니다. 이때 식단 A의 가장 큰 칼로리를 가지는 식사는 B의 어떤 식사랑 매칭시켜야 할까요? 당연히 B의 가장 작은 칼로리의 식사와 매칭시켜야 합니다. 이런 접근을 나머지 배열에 대해서 반복해 주면 A의 오름차순 배열과 B의 내림차순 배열을 보고 그 중 더한 값의 최소를 출력해야 한다는 것을 알 수 있습니다. 시간복잡도는 $O(N \lg N)$입니다.

#include <bits/stdc++.h>
#include <random>
#include <cassert>
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)
#define fileio() ifstream file_in("input.txt");ofstream file_out("output.txt")
/*#define cin file_in
#define cout file_out*/

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;

const int MOD = 1000000007;
const ll LMOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

void solve() {
    int n, k; cin >> n >> k;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    sort(all(a));
    sort(all(b));

    int ma = 0;
    for (int i = 0; i < k; i++)
        ma = max(ma, a[i] + b[k - i - 1]);
    cout << ma << endl;
}

int main() {
    fio();
    int tc; cin >> tc;
    for (int i = 1; i <= tc; i++) {
        cout << "Case #" << i << endl;
        solve();
        cout.flush();
    }
    return 0;
}

2. 카드 게임

게임 위에서 DP하는 건 흔히 알려진 접근이니, 그 접근만 잘 최적화해보도록 합시다. 구체적으로는 $DP[x][y]$를 왼쪽 카드 더미에 $x$장, 오른쪽 카드 더미에 $y$장이 남아 있을 때 선공이 이기면 1, 후공이 이기면 0으로 두고 상태 전이를 시도합니다. $DP[0][0]=1$입니다.

WLOG을 걸어 왼쪽 카드 더미를 제거한다고 합시다. 내가 카드를 적당히 가져가서 $x$장을 $j$장으로 만들 수 있다고 할 때, $\sum_{i=j}^{x-1} DP[j][y]$가 전부 1이라면 내가 무슨 짓을 해도 다음 턴의 선공, 즉 다른 사람이 이기게 됩니다. 오른쪽 카드 더미에 대해서도 같습니다. 이 두 경우를 따져줬을 때 모든 값이 1이라면 $DP[x][y]=0$이고 그렇지 않다면 $DP[x][y]=1$입니다.

그러면 이제 남은 것은 이 과정을 효율적으로 하는 방법입니다. 특정한 $x$에 대해 $j$를 찾아주는 것은 미리 투 포인터 느낌으로 $O(N^2)$에 전처리 해주면 $O(1)$에 할 수 있습니다. 마찬가지로 DP 배열이 모두 1인지 검사하는 것은 DP 배열을 채우는 과정에서 누적합을 같이 저장해주면, $O(1)$에 할 수 있습니다. 따라서 총 시간복잡도는 $O(N^2)$입니다.

#include <bits/stdc++.h>
#include <random>
#include <cassert>
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)
#define fileio() ifstream file_in("input.txt");ofstream file_out("output.txt")
/*#define cin file_in
#define cout file_out*/

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;

const int MOD = 1000000007;
const ll LMOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

int dp[3005][3005], pr[3005][3005], qr[3005][3005], px[3005], qx[3005], p[3005], q[3005];
void solve() {
    int n, k; cin >> n >> k;
    for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) dp[i][j] = pr[i][j] = qr[i][j] = 0;
    for (int i = 0; i <= n; i++) px[i] = qx[i] = 0;
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 1; i <= n; i++) cin >> q[i];

    dp[0][0] = 1;

    int l = 1, ls = 0;
    for (int i = 1; i <= n; i++) {
        ls += p[i];
        while (ls > k) ls -= p[l++];
        px[i] = l - 1;
    }
    l = 1, ls = 0;
    for (int i = 1; i <= n; i++) {
        ls += q[i];
        while (ls > k) ls -= q[l++];
        qx[i] = l - 1;
    }

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            int pt = 0, qt = 0;
            if (i) pt = pr[i - 1][j] - (px[i] ? pr[px[i] - 1][j] : 0);
            if (j) qt = qr[i][j - 1] - (qx[j] ? qr[i][qx[j] - 1] : 0);
            if (pt + qt != i - px[i] + j - qx[j]) dp[i][j] = 1;
            pr[i][j] = (i ? pr[i - 1][j] : 0) + dp[i][j];
            qr[i][j] = (j ? qr[i][j - 1] : 0) + dp[i][j];
        }
    }
    int s = 0;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            s += dp[i][j];
    cout << s << ends << (n + 1) * (n + 1) - s << endl;
}

int main() {
    fio();
    int tc; cin >> tc;
    for (int i = 1; i <= tc; i++) {
        cout << "Case #" << i << endl;
        solve();
        cout.flush();
    }
    return 0;
}

3. 사다리 게임

문제를 그래프에서의 최단거리 문제로 바꿔봅시다. 가로선 개수가 적다는 점에 주목해서 정점을 X번째 세로선에 존재하는 Y번째 교점을 통과한 직후의 위치로 잡습니다. 이러면 정점과 간선의 개수가 각각 $N$과 $k$에 비례하게 됩니다. 모든 $1 \le i \le N$에 대해서 $i$번째 세로선에서 시작해 다른 세로선으로 도착하는 최단거리를 구해봅시다. 그냥 정상적으로 가로선을 타고 가면 비용은 0이고, 가로선을 제거하면 비용은 1입니다. 다익스트라를 사용하면 한 번 수행에 $O(k\lg N)$정도가 나오겠지만 가중치가 0 또는 1이라는 점에 주목해 0-1 BFS를 사용해주면 $O(N+k)$에 할 수 있습니다. 이걸 $N$번 반복하니 총 복잡도는 $O(N^2 + Nk)$입니다.

#include <bits/stdc++.h>
#include <random>
#include <cassert>
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)
#define fileio() ifstream file_in("input.txt");ofstream file_out("output.txt")
/*#define cin file_in
#define cout file_out*/

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;

const int MOD = 1000000007;
const ll LMOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

int cnt[1505], ans[1505][1505];
vector<int> dist[1505];
vector<pii> adj[1505];

void solve() {
    int n, k, m;
    cin >> n >> k >> m;
    for (int i = 0; i <= n; i++) adj[i].clear(), cnt[i] = 0;
    for (int i = 0; i < k; i++) {
        int t1, t2; cin >> t1 >> t2;
        adj[t1].emplace_back(t2, cnt[t2]);
        adj[t2].emplace_back(t1, cnt[t1]);
        cnt[t1]++; cnt[t2]++;
    }
    for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) ans[i][j] = -1;

    for (int i = 1; i <= n; i++) {
        deque<pii> d;
        d.emplace_back(i, -1);
        for (int j = 1; j <= n; j++) dist[j].assign(cnt[j], INF);
        while (!d.empty()) {
            auto [x, y] = d.front(); d.pop_front();
            int bf = y == -1 ? 0 : dist[x][y];
            if (cnt[x] == y + 1) {
                ans[i][x] = bf;
                continue;
            }

            auto [tx,ty] = adj[x][y + 1];
            if (dist[tx][ty] > bf) {
                dist[tx][ty] = bf;
                d.emplace_front(tx, ty);
            }
            if (dist[x][y + 1] > bf + 1) {
                dist[x][y + 1] = bf + 1;
                d.emplace_back(x, y + 1);
            }
        }
    }
    int s = 0;
    for (int i = 0; i < m; i++) {
        int t1, t2; cin >> t1 >> t2;
        s += ans[t1][t2];
    }
    cout << s << endl;
}

int main() {
    fio();
    int tc; cin >> tc;
    for (int i = 1; i <= tc; i++) {
        cout << "Case #" << i << endl;
        solve();
        cout.flush();
    }
    return 0;
}

4. 범위 안의 숫자

어떤 수열에서 임의의 위치를 1로 바꾸면 영향을 받는 수는 최대 18개입니다. 모든 경우에서 매번 바꿔가면서 테스트해주면 됩니다. 범위 안의 숫자 최대를 구하는 것은 세그먼트 트리로 해 주면 되는데, 수 $x$가 추가될 경우 $[x-m,x]$에서 시작해 $[x,x+m]$에서 끝나는 구간에 숫자가 하나 늘어나게 됩니다. 따라서 $[x-m,x]$로 각 구간을 대표하게 한 다음 여기에 lazy propagation으로 수가 추가되면 1, 제거되면 -1을 더해주고 max 쿼리를 날려주면 됩니다. 수가 커서 Dynamic Segment Tree를 사용해야 겠다고 생각할 수 있는데, 요즘 트렌드를 따라가지 못하는 대회인지는 몰라도 메모리 제한이 꼴랑 256MB입니다. 좌표압축해줍시다.

#include <bits/stdc++.h>
#include <random>
#include <cassert>
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)
#define fileio() ifstream file_in("input.txt");ofstream file_out("output.txt")
/*#define cin file_in
#define cout file_out*/

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;

const int MOD = 1000000007;
const ll LMOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

int CM[10];
int n, k, m;

struct seg {
    vector<int> a, lz;
    seg(int _n) : a(_n * 4 + 4), lz(_n*4+4) {}
    void push(int nd, int s, int e) {
        if (!lz[nd]) return;
        a[nd] += lz[nd];
        if (s != e) {
            lz[nd << 1] += lz[nd];
            lz[nd << 1 | 1] += lz[nd];
        }
        lz[nd] = 0;
    }
    void update(int nd, int s, int e, int l, int r, int v) {
        push(nd, s, e);
        if (l <= s && e <= r) {
            lz[nd] += v;
            push(nd, s, e);
            return;
        }
        if (e < l || r < s) return;
        int mid = s + e >> 1;
        update(nd << 1, s, mid, l, r, v);
        update(nd << 1 | 1, mid + 1, e, l, r, v);
        a[nd] = max(a[nd << 1], a[nd << 1 | 1]);
    }
    int query(int nd, int s, int e) {
        push(nd, s, e);
        return a[nd];
    }
};

vector<int> f(vector<int>& a, int x) {
    int cnt = 0, r = 0;
    vector<int> t;
    for (int i = x - k + 1; i <= x + k - 1; i++) {
        if (i < 0 || i >= n) continue;
        if (cnt >= k) r -= a[i - k] * CM[k - 1];
        r *= 10; r += a[i];
        if (cnt >= k - 1) t.push_back(r);
        cnt++;
    }
    return t;
}

vector<int> p[50005], q[50005];

void solve() {
    cin >> n >> k >> m;
    string str; cin >> str;
    vector<int> a(n), v;
    for (int i = 0; i < n; i++) a[i] = str[i] - '0';
    for (int i = 0; i < n; i++)
        p[i].clear(), q[i].clear();

    int r = 0;
    for (int i = 0; i < k - 1; i++) {
        r *= 10; r += a[i];
    }
    for (int i = k - 1; i < n; i++) {
        if (i != k - 1) r -= a[i - k] * CM[k - 1];
        r *= 10; r += a[i];
        v.push_back(r);
        v.push_back(r - m);
    }
    v.push_back(0);

    for (int i = 0; i < n; i++) {
        p[i] = f(a, i);
        int sto = a[i];
        a[i] = 1;
        q[i] = f(a, i);
        a[i] = sto;

        for (int x : p[i]) v.push_back(x), v.push_back(x-m);
        for (int x : q[i]) v.push_back(x), v.push_back(x-m);
    }
    sort(all(v), greater<int>());
    while (v.back() < 0) v.pop_back();
    reverse(all(v));
    v.erase(unique(all(v)), v.end());

    seg S(v.size() + 1);
    int N = v.size();

    r = 0;
    for (int i = 0; i < k - 1; i++) {
        r *= 10; r += a[i];
    }
    for (int i = k - 1; i < n; i++) {
        if (i != k - 1) r -= a[i - k] * CM[k - 1];
        r *= 10; r += a[i];
        int i1 = lower_bound(all(v), max(0,r - m)) - v.begin();
        int i2 = lower_bound(all(v), r) - v.begin();

        S.update(1, 0, N, i1, i2, 1);
    }

    int ma = S.query(1, 0, N);
    for (int i = 0; i < n; i++) {
        for (auto x : p[i]) {
            int i1 = lower_bound(all(v), max(0, x - m)) - v.begin();
            int i2 = lower_bound(all(v), x) - v.begin();
            S.update(1, 0, N, i1, i2, -1);
        }
        for (auto x : q[i]) {
            int i1 = lower_bound(all(v), max(0, x - m)) - v.begin();
            int i2 = lower_bound(all(v), x) - v.begin();
            S.update(1, 0, N, i1, i2, 1);
        }
        ma = max(ma, S.query(1, 0, N));
        for (auto x : p[i]) {
            int i1 = lower_bound(all(v), max(0, x - m)) - v.begin();
            int i2 = lower_bound(all(v), x) - v.begin();
            S.update(1, 0, N, i1, i2, 1);
        }
        for (auto x : q[i]) {
            int i1 = lower_bound(all(v), max(0, x - m)) - v.begin();
            int i2 = lower_bound(all(v), x) - v.begin();
            S.update(1, 0, N, i1, i2, -1);
        }
    }
    cout << ma << endl;
}

int main() {
    fio();
    int tc; cin >> tc;
    CM[0] = 1;
    for (int i = 1; i <= 9; i++) CM[i] = CM[i - 1] * 10;
    for (int i = 1; i <= tc; i++) {
        cout << "Case #" << i << endl;
        solve();
        cout.flush();
    }
    return 0;
}

Outro

5번 풀이는 알아내는 대로 추가하겠습니다. Point in Triangle이나 대충 기하적 방법에 적절하게 확률론을 섞으면 되는 거 같은데 확률 계산에 매우 취약해서 Subtask 1조차 접근을 하나도 못 했습니다. 실망스러운 결과가 나온 만큼 공부를 좀 더 해봐야 될 것 같습니다.