서론

문제 지문과 공식 풀이는 NYPC 아카이브에서 확인할 수 있습니다. 채점은 BIKO에서 받을 수 있습니다.

제가 생각하는 난이도(solved.ac 기준)는 다음과 같습니다.

Round 1
- 버튼
- [S?] 같이 던전 도실래요?
- [S?] 등차수열
- [S?] 이모티콘 출력
- [G2] 잃어버린 섬 여행
- [G5] 같은 자리 같은 값
- [P3] 최강 장비 세트 (output only)
- [P4] 최대한 빠르게 (output only)
- [-] K주년 (풀이 준비 중)
- [P1] 블루홀 다이빙 챌린지
Round 2-A
- [S2] 중복
- [P4] 완벽한 음악 연주 시각 찾기
- [D4] 완전한 승리
- [D3] 청소
Round 2-B
- [S1] 버블
- [G1] 트리의 모든 부분 트리의 크기 합
- [G1] 로봇들의 모험
- [D?] 토벤머리 용사의 스타포스 강화

PC 화면으로 보는 분들은 우측 사이드바를 이용해 원하는 문제로 빠르게 이동할 수 있습니다.

Round 1

1. 버튼

버튼을 $t$번 누른 뒤에 실패하게 되는 경우의 수를 $f(t)$라고 합시다. 문제의 정답은 $K + \sum_{t=1}^{K} t \times f(t)$ 입니다.

$t = 1$일 때는 최악의 경우 $N$번째 시도에서 올바른 버튼을 찾을 수 있으므로 $f(1) = N-1$입니다. $t = 2$일 때는 버튼 하나를 후보에서 제거할 수 있으므로 최대 $N-2$번 실패할 수 있고, 마찬가지로 $t = 3$일 때는 최대 $N-3$번 실패할 수 있습니다. 즉, $f(t) = N - t$입니다.

따라서 $K + \sum_{t=1}^{K} t \times (N-t)$를 출력하면 문제를 해결할 수 있습니다. $K+\frac{NK(K+1)}{2}-\frac{K(K+1)(2K+1)}{6}$을 출력하면 반복문을 사용하지 않고 해결할 수도 있습니다.

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

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    ll N, K, R=0; cin >> N >> K;
    for(int i=1; i<=K; i++) R += i * (N - i);
    cout << R + K;
}

2. 같이 던전 도실래요?

두 사람의 플레이 가능 시간을 각각 $A_i, A_j$라고 하면, 파티 시너지는 $A_i + A_j - \vert A_i - A_j \vert$, 던전 클리어 횟수는 $\lfloor \frac{\min(A_i,A_j)}{M} \rfloor$입니다. 잘 생각해 보면 파티 시너지는 $2\times\min(A_i,A_j)$로 계산할 수 있으므로, 최종 스코어를 최대화하기 위해서는 $\min(A_i,A_j)$를 되도록 크게 만들어야 한다는 사실을 알 수 있습니다.

$N$명의 사람을 $A_i$ 오름차순으로 정렬한 뒤, 인접한 두 사람을 같은 팀으로 만들면 최종 스코어의 합을 최대화할 수 있습니다. 전체 시간 복잡도는 $O(N \log N)$입니다.

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

ll N, M, A[202020], R;

ll f(ll x, ll y){
    ll synergy = 2 * min(x, y);
    ll clear = min(x, y) / M;
    return synergy * clear;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M; N *= 2;
    for(int i=1; i<=N; i++) cin >> A[i];
    sort(A+1, A+N+1);
    for(int i=2; i<=N; i+=2) R += f(A[i-1], A[i]);
    cout << R;
}

3. 등차수열

공차가 $d$인 등차수열 $\lbrace A_1,A_2, \cdots, A_N\rbrace$은 $A_i$에서 $i\cdot d$를 빼면 모두 같은 값이 됩니다. 이 성질을 이용해서 문제의 풀이를 찾아봅시다.

주어진 수열을 잘 조작해서 공차가 1인 등차수열을 만드는 것이 목표고, 수열의 각 항에 1 또는 -1을 최대 한 번 더할 수 있습니다. 이는 $A_i - i$에 1 또는 -1을 최대 한 번 더해서 모든 원소의 값이 같아지도록 만드는 문제입니다.

항상 공차가 1인 등차수열을 만들 수 있는 경우만 주어진다고 했으므로 $A_i - i$의 최솟값과 최댓값의 차는 2 이하입니다. 따라서 차가 0일 때, 1일 때, 2일 때로 나누어 문제를 해결하면 됩니다.

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

int N, A[101010];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=N; i++) A[i] -= i;

    int mn = *min_element(A+1, A+N+1), c1 = count(A+1, A+N+1, mn);
    int mx = *max_element(A+1, A+N+1), c2 = count(A+1, A+N+1, mx);
    if(mn == mx) cout << 0;
    else if(mx - mn == 1) cout << min(c1, c2);
    else /*mx - mn == 2*/ cout << c1 + c2;
}

4. 이모티콘 출력

단순 구현 문제입니다.

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

int N, L;
string A[11], S;
vector<string> R;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> L;
    for(int i=1; i<=N; i++) cin >> A[i];
    cin >> S;

    for(int i=0; i<S.size(); i++){
        int match = -1;
        for(int j=1; j<=N; j++){
            if(S.substr(i, A[j].size() + 2) == ":" + A[j] + ":") match = j;
        }
        if(match == -1) R.push_back(string(1, S[i]));
        else R.push_back("[" + A[match] + "]"), i += A[match].size() + 1;
    }
    for(int i=0; i<R.size(); i++){
        cout << R[i];
        if((i + 1) % L == 0) cout << "\n";
    }
}

5. 잃어버린 섬 여행

$0\rightarrow 1\rightarrow 0 \rightarrow \cdots$와 $1\rightarrow 0\rightarrow 1\rightarrow \cdots$ 패턴으로 섬을 방문하는 두 가지 방법에서의 방호복 교체 횟수를 각각 구한 뒤 둘 중 더 작은 값을 출력하면 됩니다.

각 방호복마다 갈 수 있는 모든 섬을 방문해야 하는데, 일부 섬들 사이에 DAG 형태의 선후 관계가 주어져 있습니다. 어떤 섬에 갈 수 있다는 것은 정점의 in degree가 0이라는 것을 의미하므로, 위상 정렬을 할 때와 비슷하게 각 정점의 in degree를 관리하면서, 매번 방문할 수 있는 섬을 모두 방문하는 식으로 구현하면 됩니다. 시간 복잡도는 위상 정렬과 동일하게 $O(N+M)$입니다.

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

int N, M, A[202020], In[202020];
vector<int> G[202020];

int f(int flag){
    memset(In, 0, sizeof In);
    for(int i=1; i<=N; i++) for(auto j : G[i]) In[j]++;

    int res = 0; queue<int> que[2];
    for(int i=1; i<=N; i++) if(!In[i]) que[A[i]].push(i);
    while(true){
        while(!que[flag].empty()){
            int v = que[flag].front(); que[flag].pop();
            for(auto i : G[v]) if(!--In[i]) que[A[i]].push(i);
        }
        if(que[0].empty() && que[1].empty()) break;
        else res++, flag ^= 1;
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1,s,e; i<=M; i++) cin >> s >> e, G[s].push_back(e);
    cout << min(f(0), f(1));
}

6. 같은 자리 같은 값

$A$에서의 시작 위치가 $i$, $B$에서의 시작 위치가 $j$인 두 부분 수열에서 값이 매칭되기 위해서는 $A_{i+t} = B_{j+t}$인 두 원소가 존재해야 합니다. 반대로 이야기하면, 인덱스 차이가 $d = (i+t) - (j+t) = i - j$이면서 값이 같은 모든 원소는 시작 위치가 각각 $i, j$인 부분 수열에서 매칭됩니다.

결국 이 문제는 값이 같고 인덱스 차이가 $d$인 원소 쌍의 수를 모든 $-M < d < N$에 대해 구하는 것으로 해결할 수 있습니다. 일반적으로는 빠르게 풀기 어려운 문제(Convolution)지만, 문제 조건에 의해 두 수열 $A, B$를 통틀어서 같은 값은 최대 3번 등장하므로, $O(N+M)$ 시간에 모든 쌍을 찾을 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
constexpr int SZ = 1'000'000;

int N, M, A[202020], B[202020], C[404040];
vector<pair<int,int>> P[SZ+1];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=M; i++) cin >> B[i];
    for(int i=1; i<=N; i++) P[A[i]].emplace_back(1, i);
    for(int i=1; i<=M; i++) P[B[i]].emplace_back(2, i);
    for(int i=1; i<=SZ; i++){
        for(int j=0; j<P[i].size(); j++){
            for(int k=j+1; k<P[i].size(); k++){
                if(P[i][j].first != P[i][k].first) C[P[i][j].second-P[i][k].second+202020]++;
            }
        }
    }
    cout << *max_element(C, C+404040);
}

7. 최강 장비 세트

$i$번째 아이템을 선택하면 기본적으로 점수가 $A_i = s_iw_S + d_iw_D + h_iw_H$ 만큼 상승합니다. 만약 장착 부위와 장비가 속한 세트가 모두 같은 장비가 여러 개 있다면, $A_i$가 가장 큰 장비 하나만 남기고 나머지를 지워도 답은 변하지 않습니다.

서로 다른 세트끼리는 점수에 영향을 주지 않으므로, 캐릭터의 최종 스탯 점수는 각 세트마다 얻는 점수의 합으로 계산할 수 있습니다. 따라서 다음과 같은 DP를 생각해 볼 수 있습니다.

$\text{SetScore}(i, bit) :=$ $bit$에 속한 부위에 $i$번째 세트의 장비를 착용했을 때의 최대 점수
$D(i, bit) :=$ $1, 2, \cdots, i$번 세트의 장비로 $bit$에 속한 부위의 장비를 착용했을 때의 최대 점수

점화식은 $D(i, bit) = \max_{sub \subset bit} D(i-1, bit\setminus sub) + \text{SetScore}(i, sub)$를 이용해 계산할 수 있습니다. 9개의 원소로 구성된 총 $2^9$개의 집합의 부분 집합을 순회하는 데 걸리는 시간은 $O(3^9)$입니다(이항 정리). 따라서 전체 시간 복잡도는 $O(N + M\times 3^9)$입니다.

#include <bits/stdc++.h>
using namespace std;
constexpr int nINF = 0xc0c0c0c0;

int W[3];
int N, Slot[555], A[555][3], Set[555];
int M, B[222][10][3];

int BestIndex[222][9], BestScore[222][9]; // [set][slot] = id
int SetScore[222][1<<9], D[222][1<<9], P[222][1<<9];

void Input(){
    map<string, int> PART;
    PART["무기"] = 0; PART["장갑"] = 1; PART["상의"] = 2;
    PART["하의"] = 3; PART["신발"] = 4; PART["벨트"] = 5;
    PART["목걸이"] = 6; PART["모자"] = 7; PART["반지"] = 8;

    for(int i=0; i<3; i++) cin >> W[i];

    cin >> N;
    vector<string> set_name(N+1);
    for(int i=1; i<=N; i++){
        string slot, name;
        cin >> slot >> name >> A[i][0] >> A[i][1] >> A[i][2] >> set_name[i];
        Slot[i] = PART[slot];
    }

    cin >> M;
    map<string, int> set_id;
    for(int i=1; i<=M; i++){
        string name; cin >> name; set_id[name] = i;
        for(auto j : {3, 5, 7, 9}) for(int k=0; k<3; k++) cin >> B[i][j][k];
        for(int j=1; j<10; j++) for(int k=0; k<3; k++) B[i][j][k] += B[i][j-1][k];
    }

    for(int i=1; i<=N; i++) Set[i] = set_id[set_name[i]];
}

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

    memset(BestScore, 0xc0, sizeof BestScore);
    for(int i=1; i<=N; i++){
        int now = 0;
        for(int t=0; t<3; t++) now += W[t] * A[i][t];
        if(now > BestScore[Set[i]][Slot[i]]) BestIndex[Set[i]][Slot[i]] = i, BestScore[Set[i]][Slot[i]] = now;
    }

    for(int i=1; i<=M; i++){
        for(int bit=0; bit<(1<<9); bit++){
            bool flag = true;
            for(int j=0; j<9; j++) if((bit >> j & 1) && BestScore[i][j] == nINF) flag = false;
            if(!flag){ SetScore[i][bit] = -1e9; continue; }

            int cnt = __builtin_popcount(bit);
            for(int t=0; t<3; t++) SetScore[i][bit] += W[t] * B[i][cnt][t];
            for(int j=0; j<9; j++) if(bit >> j & 1) SetScore[i][bit] += BestScore[i][j];
        }
    }

    memset(D, 0xc0, sizeof D); D[0][0] = 0;
    for(int i=1; i<=M; i++){
        for(int bit=0; bit<(1<<9); bit++){
            D[i][bit] = D[i-1][bit]; P[i][bit] = 0;
            for(int sub=bit; sub; sub=(sub-1)&bit){
                int now = D[i-1][bit^sub] + SetScore[i][sub];
                if(now > D[i][bit]) D[i][bit] = now, P[i][bit] = sub;
            }
        }
    }

    int bit = max_element(D[M], D[M]+(1<<9)) - D[M], res[9] = {0};
    cout << D[M][bit] << "\n";
    for(int i=M, j=bit; i>=1; j^=P[i--][j]){
        int now = P[i][j];
        for(int k=0; k<9; k++) if(now >> k & 1) res[k] = BestIndex[i][k];
    }
    for(int i=0; i<9; i++) cout << res[i] << "\n";
}

8. 최대한 빠르게

$K \le 15$ 정도라면 TSP와 비슷하게 지금까지 획득한 아이템 집합을 비트 연산으로 관리하면서 BFS를 돌리면 $O(N^32^K)$ 정도에 문제를 해결할 수 있습니다. 또한 TSP를 생각했다면 $K > 15$일 때 일반적인 방법으로 풀기 어렵다는 것을 눈치챌 수 있을 것입니다.

$K \le 30$인 데이터에서도 만점을 받는 방법은 여러가지가 있는데, 가장 간단한 방법은 다음과 같습니다.

시뮬레이터를 통해 미로를 보면, 일자로 쭉 뻗은 경로가 그렇게 많지 않고, 경로 자체가 길지도 않습니다. 최대 길이가 약 20 정도이기 때문에 아이템은 그것의 절반인 10개 정도만 사용해도 될 것이라 추측할 수 있고, 실제로 모든 데이터에서 아이템을 10개 이하로 사용하는 최적해가 존재합니다. 이러한 추측을 했다면, 단순히 아이템을 무작위로 10개 선택한 뒤 $K = 10$인 문제를 해결하는 서브루틴을 수백 번 반복하는 것으로 최적해를 찾을 수 있습니다.

힐 클라이밍, 유전 알고리즘, 담금질 기법 등의 방법도 당연히 가능합니다.

#include <bits/stdc++.h>
using namespace std;
constexpr int di[] = {1, -1, 0, 0};
constexpr int dj[] = {0, 0, 1, -1};
const string DIR = "SWDA";
int Sign(int v){ return (v > 0) - (v < 0); }

pair<char, int> GetMove(pair<int,int> a, pair<int,int> b){
    for(int k=0; k<4; k++){
        int r = b.first - a.first, c = b.second - a.second;
        if(Sign(r) == di[k] && Sign(c) == dj[k]){
            return {DIR[k], abs(r) + abs(c)};
        }
    }
    assert(false);
}

struct Game{
    vector<vector<char>> a;
    int n, m, si, sj, ei, ej;
    vector<vector<int>> id;
    vector<pair<int,int>> item;

    Game(const vector<vector<char>> &input) : a(input) {
        n = a.size(); m = a[0].size();
        id = vector<vector<int>>(n, vector<int>(m));
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(a[i][j] == 'S') si = i, sj = j, a[i][j] = '.';
                if(a[i][j] == 'T') ei = i, ej = j, a[i][j] = '.';
                if(a[i][j] == '@') id[i][j] = 1 << item.size(), item.emplace_back(i, j);
            }
        }
    }

    bool bound(int i, int j) const {
        return 0 <= i && i < n && 0 <= j && j < m;
    }

    vector<pair<char,int>> solve() const {
        vector dst(n, vector(m, vector(1<<item.size(), -1)));
        vector prv(n, vector(m, vector(1<<item.size(), make_tuple(0,0,0))));

        int dest = -1;
        queue<tuple<int,int,int>> que;
        que.emplace(si, sj, 0); dst[si][sj][0] = 0;
        while(!que.empty()){
            auto [i,j,bit] = que.front(); que.pop();
            int pop = __builtin_popcount(bit);
            if(i == ei && j == ej){ dest = bit; break; }
            for(int k=0; k<4; k++){
                for(int d=1; d<=pop+1; d++){
                    int r = i + di[k] * d;
                    int c = j + dj[k] * d;
                    if(!bound(r, c) || a[r][c] == '#') break;
                    int f = bit | id[r][c];
                    if(dst[r][c][f] == -1){
                        dst[r][c][f] = dst[i][j][bit] + 1;
                        prv[r][c][f] = {i, j, bit};
                        que.emplace(r, c, f);
                    }
                }
            }
        }

        vector<pair<int,int>> pos;
        for(int r=ei, c=ej, bit=dest, d=dst[r][c][bit]; d>=0; d--){
            pos.emplace_back(r, c);
            if(d > 0) tie(r,c,bit) = prv[r][c][bit];
        }
        reverse(pos.begin(), pos.end());

        vector<pair<char,int>> res;
        for(int i=1; i<pos.size(); i++) res.push_back(GetMove(pos[i-1], pos[i]));
        return res;
    }
};

vector<vector<char>> Input(){
    int n, m, k; cin >> n >> m >> k;
    vector<vector<char>> a(n, vector<char>(m));
    for(int i=0; i<n; i++) for(int j=0; j<m; j++) cin >> a[i][j];
    return a;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    auto A = Input();
    Game G{A};

    if(G.item.size() <= 15){
        auto R = G.solve();
        cout << R.size() << "\n";
        for(auto [dir,dst] : R) cout << dir << " " << dst << "\n";
        return 0;
    }

    mt19937 rng(0x917917);

    auto V = G.item;
    vector<pair<char,int>> R;
    for(int iter=0; iter<300; iter++){
        shuffle(V.begin(), V.end(), rng);
        auto B = A;
        for(int i=10; i<V.size(); i++) B[V[i].first][V[i].second] = '.';
        auto vec = Game(B).solve();
        if(R.empty() || vec.size() < R.size()) R = vec;
    }

    cout << R.size() << "\n";
    for(auto [dir,dst] : R) cout << dir << " " << dst << "\n";
}

9. K주년 - TODO

풀이 준비 중

10. 블루홀 다이빙 챌린지

편의상 입력으로 주어진 $K$ 대신 $K+1$을 $K$로 사용합시다. 상대 좌표가 $(-2K, 0), (-K, -K), (-K, 0), (0, 0)$인 칸은 작살을 한 번 사용하여 공격할 수 있습니다. 이런 식으로 한 개의 작살로 공격할 수 있는 칸들끼리 서로 모은 새로운 보드를 만든다면, 새로운 보드마다 독립적으로 문제를 해결한 뒤에 합치는 것으로 전체 문제를 풀 수 있음을 알 수 있습니다. 구체적으로, $i_1 \equiv i_2 \pmod K, j_1 \equiv j_2 \pmod K, (i_1+j_1) \equiv (i_2+j_2) \pmod{2K}$인 칸끼리 모은 뒤에 해결하면 됩니다.

이 문제는 set cover 문제로 모델링할 수 있고, 일반적으로 set cover 문제는 빠르게 해결하는 것이 매우 어렵습니다(NP-Hard). NP-Hard 문제에는 NP-Hard에 알맞는 풀이를 찾아야 한다는 것을 머리 속에 넣어두고 생각을 전개해 봅시다.

설명과 구현의 편의를 위해 상대 좌표가 $(-2K, 0), (-K, -K), (-K, 0), (0, 0)$인 칸들을 상대 좌표가 $(-1, -1), (-1, 0), (0, -1), (1, 1)$이 되도록 격자를 잘 회전하고 압축합시다. 또한 이들을 공격할 수 있는 작살의 좌표 $(-K, 0)$은 구현의 편의를 위해 $(1, 1)$으로 옮겨줍시다. 이제 이 문제는 $2\times 2$ 크기의 정사각형을 이용해 모든 물고기를 덮는 문제로 바뀌었습니다. 또한 $K \ge 2$이므로 새로 만든 격자의 한 변의 길이는 $\lceil 25/2\rceil$ 이하가 되었습니다. 이런 상황은 비트 DP를 사용하기 매우 좋은 조건입니다. 따라서 격자를 잘 분리하고 변환했다면, 그다음에는 비트 DP와 역추적만 잘 구현하면 문제를 해결할 수 있습니다.

분리된 격자의 크기를 $M\times M$이라고 하면, 비트 DP와 역추적은 $O(M^2 2^M)$ 시간에 수행할 수 있고, $M \approx 13$ 정도로 작기 때문에 제한 시간 내에 문제를 해결할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
// bit & 1 => possible to use harpoon
// bit & 2 => there is a fish
const string X = "x.@O";

struct Pos{
    int i, j;
    Pos() : i(-1), j(-1) {}
    Pos(int i, int j) : i(i), j(j) {}
};

int N, K, A[25][25], U[25][25], R[25][25];
bool Bound(int i, int j){ return 0 <= i && i < N && 0 <= j && j < N; }

// 상대 좌표가 {(-2K,0), (-K,-K), (-K,K), (0,0)}인 것을
// 상대 좌표가 {(-1,-1), (-1,0), (0,-1), (1,1)}이 되도록 변환
vector<vector<Pos>> Convert(int si, int sj){
    auto conv = [&](int i, int j) -> pair<int,int> {
        int add = (i - si) / K, sub = (j - sj) / K;
        int r = (add + sub) / 2, c = (add - sub) / 2;
        return {r, c};
    };
    auto origin = [&](int r, int c) -> pair<int,int> {
        int add = r + c, sub = r - c;
        return {add * K + si, sub * K + sj};
    };

    vector<pair<int,int>> pos;
    int r1 = 0, r2 = 0, c1 = 0, c2 = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            int di = i - si, dj = j - sj;
            if(di % K != 0 || dj % K != 0 || (di + dj) % (2*K) != 0) continue;
            U[i][j] = 1;
            auto [r,c] = conv(i, j);
            pos.emplace_back(r, c);
            r1 = min(r1, r); r2 = max(r2, r);
            c1 = min(c1, c); c2 = max(c2, c);
        }
    }

    int row = r2 - r1 + 2, col = c2 - c1 + 2; // +1 buffer
    vector<vector<Pos>> coord(row, vector<Pos>(col));
    // (si, sj) -> (0, -c1)
    for(int r=0; r<row; r++){
        for(int c=0; c<col; c++){
            auto [i,j] = origin(r, c+c1);
            coord[r][c] = {i, j};
        }
    }
    return coord;
}

void Solve(int si, int sj){
    auto pos = Convert(si, sj);
    int n = pos.size(), m = pos[0].size();

    vector fish(n, vector(m, 0));
    vector item(n, vector(m, 0));
    vector item_pos(n, vector(m, Pos()));
    for(int r=0; r<n; r++){
        for(int c=0; c<m; c++){
            auto [i,j] = pos[r][c];
            item[r][c] = Bound(i-K, j) && (A[i-K][j] & 1);
            fish[r][c] = Bound(i, j) && (A[i][j] & 2);
            item_pos[r][c] = {i-K, j};
        }
    }

    int full = (1 << (m+1)) - 1;
    vector dp(n, vector(m, vector(full+1, make_pair(-1,-1)))); // {물고기, -1 * 작살}
    vector prv(n, vector(m, vector(full+1, make_pair(0,0)))); // {이전 비트, 작살 사용함?}

    auto upd = [&](int i, int j, int k, pair<int,int> dp_v, pair<int,int> prv_v){
        if(dp_v > dp[i][j][k]) dp[i][j][k] = dp_v, prv[i][j][k] = prv_v;
    };
    auto prv_coord = [&](int i, int j) -> pair<int,int> {
        return {i - !j, j ? j-1 : m-1};
    };

    dp[0][0][0] = {0, 0};
    if(item[0][0]) dp[0][0][1] = {fish[0][0], -1}, prv[0][0][1] = {0, 1};

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(i == 0 && j == 0) continue;
            auto [pi,pj] = prv_coord(i, j);
            for(int bit=0; bit<=full; bit++){
                upd(i, j, (bit<<1)&full, dp[pi][pj][bit], {bit, 0});
                if(!item[i][j]) continue;

                int cnt = 0, nxt_bit = (bit << 1) & full;
                if(i && j && fish[i-1][j-1] && (~bit >> m & 1)) cnt++;
                if(i && fish[i-1][j] && (~bit >> m-1 & 1)) cnt++, nxt_bit |= 1 << m;
                if(j && fish[i][j-1] && (~bit >> 0 & 1)) cnt++, nxt_bit |= 1 << 1;
                if(fish[i][j]) cnt++, nxt_bit |= 1;

                auto nxt_state = dp[pi][pj][bit];
                nxt_state.first += cnt; nxt_state.second -= 1;
                upd(i, j, nxt_bit, nxt_state, {bit, 1});
            }
        }
    }

    int i = n - 1, j = m - 1;
    int k = max_element(dp[i][j].begin(), dp[i][j].end()) - dp[i][j].begin();
    while(i >= 0){
        if(prv[i][j][k].second) R[item_pos[i][j].i][item_pos[i][j].j] = 1;
        k = prv[i][j][k].first; tie(i,j) = prv_coord(i, j);
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K; K++;
    for(int i=0; i<N; i++) for(int j=0; j<N; j++){ char c; cin >> c; A[i][j] = X.find(c); }
    for(int i=0; i<N; i++) for(int j=0; j<N; j++) if(!U[i][j]) Solve(i, j);
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++) cout << ".v"[R[i][j]];
        cout << "\n";
    }
}

Round 2-A

1. 중복

입력으로 주어진 $N$개의 수를 오름차순으로 정렬한 뒤 차례대로 $A_1, A_2, \cdots, A_N$이라고 합시다. 길이가 $K$인 구간 $[i, i+K-1]$을 모두 같은 값을 만들기 위한 최소 비용을 모든 $1 \le i \le N-K+1$에 찾는 방식으로 문제를 해결할 것입니다.

$A_i, A_{i+1}, \cdots, A_{i+K-1}$을 모두 어떤 값 $X$로 만들기 위해 필요한 연산의 횟수는 $f_i(X) = \sum_{k=i}^{i+K-1} \vert A_i - X \vert$이고, $X$가 $A_i, A_{i+1}, \cdots, A_{i+K-1}$의 중앙값일 때 $f_i(X)$가 최소가 됨이 잘 알려져 있습니다. 따라서 누적 합 배열을 이용하면 구간마다 상수 시간에 $f_i(X)$의 최솟값을 구할 수 있습니다.

입력으로 주어진 수를 정렬하는 데 $O(N \log N)$, 누적 합 배열을 만드는 데 $O(N)$, 구간마다 필요한 최소 연산 횟수를 구하는 데 $O(N)$ 만큼이 연산이 필요하므로 전체 시간 복잡도는 $O(N \log N)$입니다.

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

ll N, K, A[303030], S[303030], R=LLONG_MAX;

ll Sum(int l, int r){ return l <= r ? S[r] - S[l-1] : 0; }

ll Solve(int l, int r){
	ll res = 0;
	int m = (l + r) / 2;
	if(l <= m) res += A[m] * (m-l+1) - Sum(l, m);
	if(m+1 <= r) res += Sum(m+1, r) - A[m] * (r-m);
	return res;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	cin >> N >> K;
	for(int i=1; i<=N; i++) cin >> A[i];
	sort(A+1, A+N+1);
	partial_sum(A+1, A+N+1, S+1);
	for(int i=K; i<=N; i++) R = min(R, Solve(i-K+1, i));
	cout << R;
}

2. 완벽한 음악 연주시각 찾기

$D(i, j) :=$ $i$번째 음표까지 연주했고, $i$번째 음표를 연주한 시각이 $j$일 때의 최소 오차라고 정의합시다.

점화식은 $D(i, j) = \min_{L_{i-1} \le k \le \min(R_{i-1}, j-x)} D(i-1, k) + \vert j - P_i \vert$ (단, $L_i \le j \le R_i$)와 같이 나타낼 수 있으며, naive하게 계산하면 $O(NX^2)$이 되어 서브태스크 2를 해결할 수 있습니다.

$\min D(i-1, k)$를 구하는 것은 사실 $D(i-1, \ast)$의 시작점이 $L_{i-1}$인 prefix min을 구하는 것과 같습니다. 따라서 prefix min을 전처리하거나 $j$를 증가시키면서 누적 최솟값을 관리하는 것을 통해 $O(NX)$로 최적화할 수 있고, 서브태스크 3을 해결할 수 있습니다.

모든 $L_i \le j \le R_i$를 고려하는 대신 $L_i, T_i, R_i$만 확인해도 된다는 사실을 이용하면 좌표 압축을 통해 DP 테이블의 크기를 $3N^2$으로 줄일 수 있습니다. 이 경우 시간 복잡도는 $O(N^2)$이 되어 100점을 받을 수 있습니다.

$L_i, T_i, R_i$ 대신 $L_i - ix, T_i - ix, R_i - ix$를 사용하면 $D(i, j) = \min_{k \le j} + \vert j - P_i \vert$처럼 되어 최솟값을 구하는 구간의 형태가 간단해 집니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;

ll N, X, L[2020], P[2020], R[2020], D[2020][6060], Prv[2020][6060];
vector<ll> C;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> X;
    for(int i=1; i<=N; i++) cin >> L[i] >> P[i] >> R[i];

    for(int i=1; i<=N; i++) L[i] -= i * X, P[i] -= i * X, R[i] -= i * X;
    for(ll* arr : {L, P, R}) C.insert(C.end(), arr+1, arr+N+1);
    sort(C.begin(), C.end()); C.erase(unique(C.begin(), C.end()), C.end());
    for(ll* arr : {L, P, R}) for(int i=1; i<=N; i++) arr[i] = lower_bound(C.begin(), C.end(), arr[i]) - C.begin();

    // D[i][j] = min_{k<=j} D[i-1][k] + abs(j - P[i])
    memset(D, 0x3f, sizeof D);
    memset(Prv, -1, sizeof Prv);
    for(int i=L[1]; i<=R[1]; i++) D[1][i] = abs(C[i] - C[P[1]]);
    for(int i=2; i<=N; i++){
        ll mn = INF, pos = 0;
        for(int j=0; j<L[i]; j++) if(D[i-1][j] < mn) mn = D[i-1][j], pos = j;
        for(int j=L[i]; j<=R[i]; j++){
            if(D[i-1][j] < mn) mn = D[i-1][j], pos = j;
            D[i][j] = mn + abs(C[j] - C[P[i]]); Prv[i][j] = pos;
        }
    }

    int pos = min_element(D[N], D[N]+C.size()) - D[N];
    if(D[N][pos] == INF){ cout << -1; return 0; }

    vector<ll> res;
    for(int i=N, j=pos; i>=1; j=Prv[i--][j]) res.push_back(C[j] + i * X);
    reverse(res.begin(), res.end());

    cout << D[N][pos] << "\n";
    for(auto i : res) cout << i << " ";
}

3. 완전한 승리

모든 점 $(X, Y)$에 대해, 파란 점 $(x_b, y_b) \in B$는 $x_b \le X, y_b \le Y$, 빨간 점 $(x_r, y_r) \in R$은 $x_r > X, y_r > Y$가 되도록 만드는 최소 이동 횟수를 구하는 방식으로 접근합시다. 만약 한 번에 여러 개의 점을 이동시킬 수 있다면 $(X, Y)$에서의 정답은 $N$에서 (이동하지 않아도 되는 점의 개수)를 뺀 값, 즉 $N - #\lbrace (x_b,y_b) \in B; x_b \le X, y_b \le Y\rbrace - #\lbrace(x_r,y_r) \in R; x_r > X, y_r > Y\rbrace$ 입니다.

하지만 이 문제는 점을 한 번에 하나씩만 이동해야 합니다. 이 경우에는 $(X, Y)$의 좌하단 영역과 우상단 영역에 모두 빈 칸이 없을 때 정답이 1 만큼 증가하고, 그렇지 않은 경우에는 점을 여러 개 이동시킬 수 있는 문제에서의 정답과 같습니다.

$(X, Y)$를 $X$좌표가 증가하는 순서대로 보는 형태의 스위핑을 이용해 문제를 해결합시다. 각각의 $Y$좌표마다 분할점을 $(X, Y)$로 했을 때 옮기지 않아도 되는 점의 개수를 관리하면, 구간 최댓값 쿼리를 이용해 문제를 해결할 수 있습니다. 따라서 $Y$좌표마다 옮기지 않아도 되는 점의 개수를 세그먼트 트리로 관리합니다.

구체적으로, $X = -\infty$일 때는 $Y < y_r$이면 빨간 점 $(x_r, y_r)$을 옮기지 않아도 됩니다. 따라서 초기에 모든 빨간 점 $(x_r, y_r)$에 대해, $[1, y_r-1]$ 구간에 1씩 더한 상태로 시작합시다.

이후 $X$가 증가함에 따라 점의 정보를 갱신해야 합니다. $X = k$에서 $X = k+1$로 이동하면 $x_r = k+1$인 빨간 점은 모두 이동이 필요하며, $x_b = k+1$인 파란 점은 $Y \ge y_b$일 때 이동하지 않아도 됩니다. 따라서 $x_r = k+1$인 빨간 점이 있다면 $[1, y_r-1]$ 구간에 1을 빼고, $x_b = k+1$인 파란 점이 있다면 $[y_b, M]$ 구간에 1을 더해야 합니다.

이런 식으로 세그먼트 트리에 정보를 올바르게 저장했다면, 이제 고정된 $X$에 대해 가능한 $Y$에서의 최댓값을 구할 차례입니다. 파란 점이 있을 수 있는 $x$좌표 구간의 길이는 $X$이고, 파란 점이 있을 수 있는 $x$좌표 구간의 길이는 $M-x$입니다. 따라서 파란 점과 빨간 점의 개수를 각각 $C_b, C_r$이라고 하면 $\lceil C_b / X \rceil \le Y \le M - \lceil C_r / (M-X) \rceil$ 인 $Y$만 고려해야 합니다. 만약 이러한 $Y$가 존재하지 않으면 주어진 $X$에서 답이 존재하지 않는 것이고, $Y$가 존재하면 구간 최댓값 쿼리를 이용해 답을 구하면 됩니다.

이때 앞에서 이야기한 예외를 신경써야 하는데, $(X, Y)$의 좌하단 영역과 우상단 영역에 모두 빈 칸이 없는 경우를 잘 판별해야 합니다. 이는 처리하는 방법은 아래 코드의 63-65번째 줄을 참고하시길 바랍니다.

#include <bits/stdc++.h>
using namespace std;
constexpr int SZ = 1 << 20;

int T[SZ<<1], L[SZ<<1];
void Push(int node, int s, int e){
    if(!L[node]) return;
    T[node] += L[node];
    if(s != e) L[node<<1] += L[node], L[node<<1|1] += L[node];
    L[node] = 0;
}
void Add(int l, int r, int v, int node=1, int s=0, int e=SZ-1){
    Push(node, s, e);
    if(r < s || e < l) return;
    if(l <= s && e <= r){ L[node] += v; Push(node, s, e); return; }
    int m = (s + e) / 2;
    Add(l, r, v, node<<1, s, m); Add(l, r, v, node<<1|1, m+1, e);
    T[node] = max(T[node<<1], T[node<<1|1]);
}
int Get(int l, int r, int node=1, int s=0, int e=SZ-1){
    Push(node, s, e);
    if(r < s || e < l) return 0;
    if(l <= s && e <= r) return T[node];
    int m = (s + e) / 2;
    return max(Get(l, r, node<<1, s, m), Get(l, r, node<<1|1, m+1, e));
}

int N, M;
vector<array<int,3>> A;
vector<int> C, Max, Min;

void Compress(){
    for(const auto &[x,y,c] : A) for(int j=y-1; j<=y+1; j++) if(1 <= j && j <= M) C.push_back(j);
    sort(C.begin(), C.end()); C.erase(unique(C.begin(), C.end()), C.end());
    for(auto &[x,y,c] : A) y = lower_bound(C.begin(), C.end(), y) - C.begin();
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M; A.resize(N);
    for(auto &[x,y,c] : A){ char t; cin >> x >> y >> t; c = t == 'R'; }
    Compress();
    sort(A.begin(), A.end());

    int res = 1e9, total_blue = 0, total_red = 0;
    for(const auto &[x,y,c] : A) (c ? total_red : total_blue)++;
    for(const auto &[x,y,c] : A) if(c) Add(0, y-1, 1);

    Max.resize(N); Min.resize(N, M+1);
    for(int i=0; i<N; i++) Max[i] = Min[i] = C[A[i][1]];
    for(int i=1; i<N; i++) Max[i] = max(Max[i-1], Max[i]);
    for(int i=N-2; i>=0; i--) Min[i] = min(Min[i+1], Min[i]);

    auto solve = [&](int x, int pre_mx, int suf_mn){
        if(x == 0 || x == M) return;
        int y_blue = (total_blue + x - 1) / x;
        int y_red = (total_red + M-x - 1) / (M-x);
        if(y_blue + y_red > M) return;

        int lo = lower_bound(C.begin(), C.end(), y_blue) - C.begin();
        int hi = upper_bound(C.begin(), C.end(), M-y_red) - C.begin() - 1;
        int fix = Get(lo, hi), full = 0;
        if(fix < N && y_blue + y_red == M){
            if(y_blue * x == total_blue && y_red * (M-x) == total_red && pre_mx == y_blue && suf_mn == y_blue + 1) full = 1;
        }
        res = min(res, N - fix + full);
    };

    for(int i=0, j=0; i<N; i=j){
        solve(A[i][0]-1, i-1 >= 0 ? Max[i-1] : 0, Min[i]);
        while(j < A.size() && A[i][0] == A[j][0]) j++;
        for(int k=i; k<j; k++){
            if(A[k][2]) Add(0, A[k][1]-1, -1);
            else Add(A[k][1], C.size()-1, +1);
        }
        solve(A[i][0], Max[j-1], j < N ? Min[j] : M+1);
    }
    cout << (res < 1e9 ? res : -1);
}

4. 청소

2개의 점이 band의 한쪽 경계 위에 있는 최적해가 항상 존재함을 관찰합시다. 그러면 이 문제는 임의의 두 점을 연결하는 직선의 왼쪽(또는 오른쪽)에서, 직선과 거리가 $L$ 이하인 점의 개수를 세는 문제라고 생각할 수 있습니다.

이와 같은 문제를 해결하기 위해서는, 일단 주어진 기울기에 대해서 점들을 정렬한 뒤에 이분 탐색을 이용해 거리가 $L$ 이하인 점의 개수를 구해야 합니다. 불도저 트릭을 이용하면 가능한 $N(N-1)/2$가지 기울기에서의 정렬 순서를 $O(N^2 log N)$에 모두 구할 수 있고, 이후 이분 탐색을 이용해 각 기울기에 대해 $O(\log N)$에 답을 구할 수 있습니다. 따라서 전체 시간 복잡도는 $O(N^2 \log N)$입니다.

한 가지 조심해야 하는 점은, 실수 오차에 굉장히 민감한 문제입니다. $N = 3$에서도 double과 long double을 모두 터뜨리는 데이터를 만들 수 있으므로, 정수 타입만 이용해서 모든 계산을 수행해야 합니다. 구체적으로, 기울기의 법선 벡터 $\overrightarrow{n}(x, y)$와 그 벡터의 길이 $d = \sqrt{x^2+y^2}$가 주어지면, $\frac{\vert n \cdot p_i - n \cdot p_j \vert}{d} \le L$를 이용해 두 점 $p_i, p_j$의 거리가 $L$ 이하인지 판별할 수 있습니다. $d > 0$이므로 $d$를 오른쪽으로 넘긴 뒤 양변을 제곱하면 정수 타입만 이용해서 거리를 비교할 수 있습니다. 이때 계산 과정에서 등장하는 수의 크기가 좌표 범위의 네제곱 스케일까지 커질 수 있으므로 __int128_t와 같은 128비트 정수 자료형을 사용해야 합니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using LL = __int128_t;

struct point{
    ll x, y; point() = default;
    point(ll x, ll y) : x(x), y(y) {}
    ll len_sq() const { return x * x + y * y; }
    point rot90() const { return point(-y, x); }
    bool operator < (const point &p) const { return tie(x,y) < tie(p.x,p.y); }
    bool operator == (const point &p) const { return tie(x,y) == tie(p.x,p.y); }
    point operator + (const point &p) const { return {x + p.x, y + p.y}; }
    point operator - (const point &p) const { return {x - p.x, y - p.y}; }
    ll operator * (const point &p) const { return x * p.x + y * p.y; }
    ll operator / (const point &p) const { return x * p.y - y * p.x; }
    friend istream& operator >> (istream &in, point &p){ return in >> p.x >> p.y; }
};

struct segment{
    ll i, j, dx, dy; // dx >= 0
    segment(int i, int j, const point &pi, const point &pj) : i(i), j(j), dx(pj.x-pi.x), dy(pj.y-pi.y) { norm(); }
    void norm(){ ll g = __gcd(dx, abs(dy)); dx /= g; dy /= g; }
    bool operator < (const segment &l) const {
        return make_tuple(dy * l.dx, i, j) < make_tuple(dx * l.dy, l.i, l.j);
    }
    bool operator == (const segment &l) const {
        return dy * l.dx == dx * l.dy;
    }
};

ll N, L, P[1515], In[1515];
point A[1515];

LL FloorSqrt(LL x){
    if(x == 0) return 0;
    LL v = sqrtl(x);
    while((v+1) * (v+1) <= x) v++;
    while(v * v > x) v--;
    return v;
}

void Solve(){
    cin >> N >> L;
    for(int i=1; i<=N; i++) cin >> A[i];
    sort(A+1, A+N+1); iota(P+1, P+N+1, 1);
    if(N == 1){ cout << "1\n"; return; }

    vector<segment> V; V.reserve(N*(N-1)/2);
    for(int i=1; i<=N; i++) for(int j=i+1; j<=N; j++) V.emplace_back(i, j, A[i], A[j]);
    sort(V.begin(), V.end());

    int res = 1;
    for(int i=0, j=0; i<V.size(); i=j){
        while(j < V.size() && V[i] == V[j]) j++;
        for(int k=i; k<j; k++){
            int u = V[k].i, v = V[k].j; // point id, index -> P[id]
            swap(P[u], P[v]); swap(A[P[u]], A[P[v]]);
            if(P[u] > P[v]) swap(u, v);

            point normal = (A[P[u]] - A[P[v]]).rot90();
            ll limit = FloorSqrt(LL(normal.len_sq()) * L * L);

            int l = 1, r = P[v];
            while(l < r){
                int m = (l + r) / 2;
                if(normal * A[P[v]] - normal * A[m] <= limit) r = m;
                else l = m + 1;
            }
            res = max<int>(res, P[v] - r + 1);

            l = P[u]; r = N;
            while(l < r){
                int m = (l + r + 1) / 2;
                if(normal * A[m] - normal * A[P[u]] <= limit) l = m;
                else r = m - 1;
            }
            res = max<int>(res, l - P[u] + 1);
        }
    }
    cout << res << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int TC; cin >> TC;
    for(int tc=1; tc<=TC; tc++) Solve();
}

Round 2-B

1. 버블

$A_i$를 첫 번째 위치로 옮길 때, $N$번째 위치에 올 수 있는 최댓값을 구하는 식으로 문제를 해결합니다.

$A_i$를 첫 번째 위치로 옮기는 과정에서 $i-1$번의 교환이 필요하고, 이후 $A_j$ (단, $i \ne j$)를 $N$번째 위치로 옮길 때 $N-j-[j<i]$번의 교환이 필요합니다. 이때 $[\text{condition}]$은 아이버슨 괄호로, condition이 참이면 1, 거짓이면 0을 의미합니다. 따라서 $N-j-[j<i] \le K-(i-1)$을 만족하는 모든 $j$들 중 $A_j$의 최댓값을 구하면 문제를 해결할 수 있습니다.

$A_i$를 맨 앞으로 옮긴 뒤에 남은 교환 횟수인 $K-(i-1)$을 $r$이라는 문자로 치환한 뒤에 식을 정리하면, $r < N-i$ 이면 $A[N-r\cdots N]$의 최댓값, $r \ge N-i$ 이면 $A[N-rem-1\cdots N]$의 최댓값을 구하면 된다는 것을 알 수 있습니다. 주어진 수열 $A$의 suffix max를 전처리하면 $O(N)$ 시간에 답을 구할 수 있습니다.

똑같은 값이 첫 번째와 $N$번째에 모두 들어가게 되는 경우를 제외해야 하지 않냐는 의문이 생길 수 있는데, 그러한 동작을 하기 위해서는 $K \ge N-1$이어야 하고, $K \ge N-1$이면 정답이 항상 0 초과이기 때문에 따로 예외 처리를 하지 않더라도 계산 결과에 영향을 주지 않습니다.

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

int N, K, A[202020], Max[202020], R=-1e9;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=N; i>=1; i--) Max[i] = max(Max[i+1], A[i]);
    for(int i=1; i<=N; i++){
        int rem = K - i + 1;
        if(rem < 0) continue;
        int st = rem < N - i ? N - rem : N - rem - 1;
        R = max(R, Max[max(1,st)] - A[i]);
    }
    cout << R;
}

2. 트리의 모든 부분 트리의 크기 합

모든 정점의 자손의 수의 합은 모든 정점의 조상의 수의 합과 같습니다. 즉, 서브 트리 크기의 합을 구하는 대신 모든 정점의 높이의 합을 구하는 문제로 생각해도 괜찮습니다. 따라서 모든 $h$에 대해 높이가 $h$인 정점의 개수를 구하는 것으로 문제를 해결할 수 있습니다.

시간 복잡도는 트리의 높이에 비례하는데, $K \ge 2$이면 트리의 높이가 $O(\log_K N)$이 되어 괜찮지만 $K = 1$일 때가 문제입니다. $K = 1$일 때는 답이 $N(N+1)/2$임을 쉽게 알 수 있으므로 이 경우만 예외 처리하면 문제를 풀 수 있습니다. $P$가 짝수가 될 수 있음에 유의해야 합니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using L = __uint128_t;

void Solve(){
    ll N, K, P, R=0; cin >> N >> K >> P;
    if(K == 1){ cout << ll(L(N)*(N+1)/2 % P) << "\n"; return; }
    ll div_guard = N / K;
    for(ll h=1, v=1; N; h++, v=(v<=div_guard?v*K:N)){
        ll now = min(N, v); N -= now;
        R = (R + now % P * h) % P;
    }
    cout << R << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int TC; cin >> TC;
    for(int tc=1; tc<=TC; tc++) Solve();
}

3. 로봇들의 모험

가장 마지막에 사용하는 로봇은 $K_i \ge 0$을 만족해야 하고, 뒤에서 두 번째로 사용하는 로봇은 $K_i \ge 1$을 만족해야 합니다. 비슷하게, 뒤에서 $t$번째로 사용하는 로봇은 $K_i \ge t-1$을 만족해야 합니다. 이를 이용하면 $K_i$가 단조감소하도록 로봇을 사용하는 최적해가 항상 존재함을 증명할 수 있습니다. 이제부터는 $K_i$가 단조감소하는 해만 고려하겠습니다.

위에서 본 부등식을 생각해 보면, $K_i \ge N$인 로봇을 최대 1개, $K_i \ge N-1$인 로봇을 최대 1개, $\cdots$ , $K_i \ge 0$인 로봇을 최대 1개 선택하는 것으로 유효한 해를 만들 수 있고, 유효한 해는 항상 이런 식으로 만들 수 있다는 것을 알 수 있습니다. 따라서 $K_i$가 큰 로봇부터 차례대로 보면서 매번 아직 선택하지 않은 로봇 중 $D_i$가 가장 큰 로봇을 선택하는 그리디 전략이 성립하고, 우선순위 큐 등을 이용해 $O(N \log N)$ 시간에 문제를 해결할 수 있습니다.

이러한 그리디 전략이 성립하는 이유와, $K_i$가 작은 로봇부터 보면 안 되는 이유를 고민해 보면 좋을 것입니다.

로봇의 집합을 $S$, 유효한 해를 구성하는 로봇 집합들의 집합을 $I$라고 정의하면 $M = (S, I)$는 매트로이드 구조를 이룬다는 것을 이용한 풀이도 있습니다. 단, independence oracle을 $O(N)$보다 빠르게 구현해야 100점을 받을 수 있습니다.

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

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N, R=0; cin >> N;
    vector<pair<int,int>> A(N);
    for(auto &[a,b] : A) cin >> a >> b;
    sort(A.begin(), A.end(), greater<>());

    priority_queue<int> Q;
    for(int k=N, i=0; k>=0; k--){
        while(i < N && A[i].first == k) Q.push(A[i++].second);
        if(!Q.empty()) R += Q.top(), Q.pop();
    }
    cout << R;
}

4. 토벤머리 용사의 스타포스 강화

레벨이 $i$인 장비를 $N$으로 만들기 위해 필요한 비용의 기댓값을 $E(i)$라고 합시다. $E(N) = 0$이고, $E(0)$을 최소화해야 합니다.

현재 레벨이 $i$일 때 $i \rightarrow d$ 하락 방지 쿠폰을 구매하는 상황을 생각해 봅시다. 레벨이 $j$가 되는 이벤트가 발생했을 때 실제로 도달하게 되는 레벨을 $next(i,j,d)$라고 정의하면, $E(i)$는 다음과 같은 부등식이 성립함을 알 수 있습니다. 또한, 최적 전략에 해당하는 $d$에서 등호가 성립합니다. (단, $-1 \le d < i$; $D(i, -1) = 0$)

\[E(i) \le C_i + D(i, d) + \sum_{j=0}^N P_{i,j}E(next(i,j,d))\] \[E(i) - \sum_{j=0}^N P_{i,j}E(next(i,j,d)) \le C_i + D(i, d)\]

즉, $A_{t,0}E(0) + A_{t,1}E(1) + \cdots + a_{t,N-1}E(N-1) \le B_t$ 꼴의 부등식이 여러 개 주어지면, 모든 부등식이 참이 되도록 할 때 가능한 $E(0)$의 최댓값을 구하는 것으로 문제를 해결할 수 있습니다. (단, $E(i) \ge 0$; $E(N) = 0$)

이러한 형태의 문제를 선형 계획법(Linear Programming)이라고 부르고, Problem Solving 범위에서는 Simplex method를 이용해 해결하는 방법이 널리 알려져 있습니다. 따라서 Simplex method 구현체를 이용하거나, NYPC 채점 시스템에서 지원되는 SciPy의 scipy.optimize.linprog를 이용하면 문제를 해결할 수 있습니다.

from scipy.optimize import linprog

def next(i, j, d):
    if d == -1: return j
    return j if j > i else max(j, d+1)

def solve():
    N = int(input())
    C = list(map(int, input().split()))
    D = [[]] + [list(map(int, input().split())) for _ in range(N-1)]
    P = [list(map(int, input().split())) for _ in range(N)]
    P = [[p / 1_000_000 for p in row] for row in P]

    a, b, c = [], [], [-1] + [0] * (N-1)

    for i in range(N):
        for d in range(-1, i):
            coeff = [0] * (N+1)
            coeff[i] = 1
            for j in range(N+1): coeff[next(i,j,d)] -= P[i][j]
            a.append(coeff[:N])
            b.append(C[i] + (D[i][d] if d >= 0 else 0))

    bounds = [(0, None) for _ in range(N)]
    res = linprog(c=c, A_ub=a, b_ub=b, bounds=bounds)
    print('%.20f' % -res.fun)

for _ in range(int(input())): solve()

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

// Solves the canonical form: maximize c^T x, subject to ax <= b and x >= 0.
template<class T> // T must be of floating type
struct linear_programming_solver_simplex{
    int m, n; vector<int> nn, bb; vector<vector<T>> mat;
    static constexpr T eps = 1e-8, inf = numeric_limits<T>::max();
    linear_programming_solver_simplex(
        const vector<vector<T>> &a, const vector<T> &b, const vector<T> &c
    ) : m(b.size()), n(c.size()), nn(n+1), bb(m), mat(m+2, vector<T>(n+2)){
        for(int i=0; i<m; i++) for(int j=0; j<n; j++) mat[i][j] = a[i][j];
        for(int i=0; i<m; i++) bb[i] = n + i, mat[i][n] = -1, mat[i][n + 1] = b[i];
        for(int j=0; j<n; j++) nn[j] = j, mat[m][j] = -c[j];
        nn[n] = -1; mat[m + 1][n] = 1;
    }
    void pivot(int r, int s){
        T *a = mat[r].data(), inv = 1 / a[s];
        for(int i=0; i<m+2; i++){
            if(i != r && abs(mat[i][s]) > eps) {
                T *b = mat[i].data(), inv2 = b[s] * inv;
                for(int j=0; j<n+2; j++) b[j] -= a[j] * inv2;
                b[s] = a[s] * inv2;
            }
        }
        for(int j=0; j<n+2; j++) if(j != s) mat[r][j] *= inv;
        for(int i=0; i<m+2; i++) if(i != r) mat[i][s] *= -inv;
        mat[r][s] = inv; swap(bb[r], nn[s]);
    }
    bool simplex(int phase){
        for(auto x=m+phase-1; ; ){
            int s = -1, r = -1;
            for(auto j=0; j<n+1; j++) if(nn[j] != -phase) if(s == -1 || pair(mat[x][j], nn[j]) < pair(mat[x][s], nn[s])) s = j;
            if(mat[x][s] >= -eps) return true;
            for(auto i=0; i<m; i++){
                if(mat[i][s] <= eps) continue;
                if(r == -1 || pair(mat[i][n + 1] / mat[i][s], bb[i]) < pair(mat[r][n + 1] / mat[r][s], bb[r])) r = i;
            }
            if(r == -1) return false;
            pivot(r, s);
        }
    }
    // Returns -inf if no solution, {inf, a vector satisfying the constraints}
    //   if there are abritrarily good solutions, or {maximum c^T x, x} otherwise.
    // O(n m (# of pivots)), O(2 ^ n) in general.
    pair<T, vector<T>> solve(){
        int r = 0;
        for(int i=1; i<m; i++) if(mat[i][n+1] < mat[r][n+1]) r = i;
        if(mat[r][n+1] < -eps){
            pivot(r, n);
            if(!simplex(2) || mat[m+1][n+1] < -eps) return {-inf, {}};
            for(int i=0; i<m; i++){
                if(bb[i] == -1){
                    int s = 0;
                    for(int j=1; j<n+1; j++) if(s == -1 || pair(mat[i][j], nn[j]) < pair(mat[i][s], nn[s])) s = j;
                    pivot(i, s);
                }
            }
        }
        bool ok = simplex(1);
        vector<T> x(n);
        for(int i=0; i<m; i++) if(bb[i] < n) x[bb[i]] = mat[i][n + 1];
        return {ok ? mat[m][n + 1] : inf, x};
    }
};

int N, C[22], D[22][22];
ld P[22][22];

void Solve(){
    cin >> N;
    for(int i=0; i<N; i++) cin >> C[i];
    for(int i=1; i<N; i++) for(int j=0; j<i; j++) cin >> D[i][j];
    for(int i=0; i<N; i++) for(int j=0; j<=N; j++) cin >> P[i][j];
    for(int i=0; i<N; i++) for(int j=0; j<=N; j++) P[i][j] /= 1e6;

    vector<vector<ld>> a;
    vector<ld> b, c;

    // next(i, j, d) := j > i ? j : max(j, d+1)
    // X[i] <= C[i] + D[i][d] + sum_{j=0}^{N} P[i][j] X[next(i,j,d)] (-1 <= d < i)
    // X[i] - sum P[i][j] X[next(i,j,d)] <= C[i] + D[i][d]

    c.resize(N); c[0] = 1;
    auto f = [](int i, int j, int d) -> int {
        if(d == -1) return j;
        else return j > i ? j : max(j, d+1);
    };

    for(int i=0; i<N; i++){
        for(int d=-1; d<i; d++){
            vector<ld> coeff(N);
            coeff[i] = 1;
            for(int j=0; j<=N; j++) if(f(i,j,d) < N) coeff[f(i,j,d)] -= P[i][j];
            a.push_back(coeff);
            b.push_back(C[i] + (d >= 0 ? D[i][d] : 0));
        }
    }

    linear_programming_solver_simplex<ld> solver(a, b, c);
    cout << fixed << setprecision(20) << solver.solve().first << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);int TC; cin >> TC;
    for(int tc=1; tc<=TC; tc++) Solve();
}

2025 NYPC 예선 Round 1 / 2-A / 2-B 풀이

댓글