2021 NYPC 예선 후기 + 풀이

지난 8월 26일 목요일, 8일간의 2021 NYPC 예선이 종료되었습니다. 작년에 이어 두 번째로 NYPC 예선에 참여하게 된 것이었는데, 작년은 대회의 존재를 종료 이틀 전에 알게 되어서 아쉬움이 많이 남았었고 제대로는 올해 처음 하게 되었네요.

 

사실 심심하니까 한 번 해봐야지~ 정도였는데 생각보다는 훨씬 열심히 한 것 같습니다. 3회차부터는 계속 이것만 붙들고 있었던 듯..

---

결과

borussiam의 2021 NYPC 예선 결과

제 기준에서는 믿을 수 없을 정도로 좋은 결과지만 분위기를 보아하니 본선은 무리인가 봅니다. 그래도 못 풀 문제 풀고, 못 긁을 서브태스크도 긁은 것이 참 많아서 위의 사진만 보면 참 뿌듯합니다. 1년 사이에 많이 성장한 것 같다고 느껴지네요...

---

풀이

*풀이는 과하게 자세한 부분과 과하게 미흡한 부분이 많이 있을 수 있습니다

*제 풀이가 좋은 풀이가 아닐 가능성이 높으니 다른 분들 글도 많이 참고해주세요

*코드는 NYPC에 제출했던 코드를 그대로 가져왔는데, 엄청 더러운 편이니 참고만 해주세요

 

[연습문제]

 1 최대구간합, 2 도토리를 주워라

연습문제는 과감히 넘어가도록 하겠습니다. 절대 2번 못 풀어서 그런 게 아니라 귀찮아서...

---

1회차

1회차는 저마저도 꽤 쉽다고 느낀 난이도였습니다. 구현 뇌절을 여러 번 하고, 놀면서도 몇 시간 이내에 5문제 전부 풀 수 있었습니다.

---

3 계단

$ 1 $층부터 $ M $ 층까지 있는 건물에서 $ F $층에 있는 배찌가 계단을 $ N $번 올라 제자리로 돌아오기 위해 엘리베이터를 최소 몇 번 타야 하는지 구하는 문제입니다.

 

$ F $층에서 꼭대기 층까지 올라가서 엘리베이터를 타고 $ 1 $층으로 간 뒤 다시 $ F $층으로 오면 $ M-1 $번 층계를 오른 것이고, 이것이 엘리베이터를 $ 1 $번 탈 때 오를 수 있는 층계의 최대 수입니다. $ 1 $에서 $ M-2 $번 오르는 것도 엘리베이터를 타고 내리는 위치를 조정한다면 전부 가능합니다. 따라서 답은 $ \left\lceil \frac{N}{M-1} \right\rceil $가 됩니다.

 

시간복잡도는 $ O(1) $입니다.

 

서브태스크는 따로 언급하지 않겠습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int M, F, N; cin >> M >> F >> N;
    cout << (N + M - 2) / (M - 1) << '\n';
    return 0;
}

---

4 레이스 기록 검증

로그 파일이 주어지면 그 기록이 올바른지, 올바르지 않은지를 판별하는 문제입니다.

 

기록이 시각 $ t $가 감소하지 않는 순서로 주어지므로, 현재 임의의 유저가 레이스를 언제 시작했는지, 또는 레이스를 시작하지 않은 상태인지를 기록한 뒤 문제 조건대로 판단해주면 됩니다. 아래 코드에서 저는 큐를 이용했는데, 정수로 되는 걸 가지고 왜 이랬는지는 잘 모르겠네요.

 

시간복잡도는 $ O(N+M) $입니다.

 

서브태스크는 따로 언급하지 않겠습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    bool ans = true;
    int N, M; cin >> N >> M;
    queue<int> q[N+1];
    while(M--){
        int t, i, s;
        cin >> t >> i >> s;
        if(s == 0){
            if(!q[i].empty()) ans = false;
            else q[i].push(t);
        }
        else{
            if(q[i].empty() || q[i].front() + 60 > t) ans = false;
            else q[i].pop();
        }
    }
    for(int i = 1; i <= N; i++){
        if(!q[i].empty()) ans = false;
    }
    if(ans) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}

---

5 근무표 짜기

개발자는 각각 반드시 며칠 출근해야 하고, 사무실은 매일 최대 근무 인원이 정해져 있을 때 조건을 만족하도록 근무표를 짜는 문제입니다.

 

그리디 문제임은 바로 알았습니다. 대충 개발자와 일(day)을 정렬한 뒤 가장 많이 출근해야 하는 개발자부터 가장 많은 인원이 근무할 수 있는 날부터 채워 넣고, 다음 개발자는 전 개발자가 마지막으로 채운 날의 다음 날부터 채워넣고, 일(day)의 마지막까지 가면 처음으로 돌아와서 반복하는 풀이를 생각했습니다. 하지만 이 경우 (예를 들어) 개발자의 출근 일수가 $ [3, 3, 3] $이고, 사무실 근무 인원수가 $ [3, 2, 1, 1, 1, 1] $일 때 근무표를 완성할 수 없습니다. 놀랍게도 서브태스크 1의 제한 조건은 $ N, K\le4 $로 이러한 반례가 존재하지 않고, 위 풀이가 통과합니다.

 

위 방법과 반대로, 가장 많은 인원이 근무할 수 있는 날부터 가장 많이 출근해야 하는 개발자를 채워 넣는다면, 항상 근무표를 작성할 수 있도록 입력이 주어진다는 조건과 함께 항상 근무표를 짤 수 있게 됩니다.

 

시간 복잡도는 $ O(NK) $입니다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
#define fi first
#define se second
#define pb push_back

const int MAX = 101;
int N, K;
pi dev[MAX], day[MAX];
vector<int> ans[MAX];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K;
    for(int i = 0; i < N; i++){
        cin >> dev[i].fi;
        dev[i].se = i+1;
    }
    for(int i = 0; i < K; i++){
        cin >> day[i].fi;
        day[i].se = i;
    }
    sort(dev, dev+N);
    sort(day, day+K);
    for(int i = K-1; i >= 0; i--){
        for(int j = N-1; j >= 0 && N-j-1 < day[i].fi; j--){
            if(dev[j].fi == 0) break;
            ans[day[i].se].pb(dev[j].se);
            --dev[j].fi;
        }
        sort(dev, dev+N);
    }
    // int cnt = K-1;
    // for(int i = N-1; i >= 0; i--){
    //     for(int j = 0; j < dev[i].fi; j++){
    //         if(ans[day[cnt].se].size() < day[cnt].fi){
    //             ans[day[cnt].se].pb(dev[i].se);
    //         }
    //         else --j;
    //         cnt = (cnt + K - 1) % K;
    //     }
    // }
    for(int i = 0; i < K; i++){
        cout << ans[i].size() << ' ';
        for(int j : ans[i]) cout << j << ' ';
        cout << '\n';
    }
    return 0;
}

---

6 파티

$ N $명의 친구들이 낸 돈 사이의 차가 $ 1 $ 이하가 되도록 만들 때, 전달하는 금액의 최솟값을 구하는 문제입니다.

 

$ i $번째 친구가 낸 돈을 $ M_{i},\;S=\sum\limits_{i=1}^{N} M_{i} $라고 하면, $ 0 $ 이상 $ N $ 미만의 어떤 정수 $ K $에 대해 다음과 같은 식이 성립합니다.

$$ S=\left(N-K\right)\left\lfloor\frac{S}{N}\right\rfloor+K\left(\left\lfloor\frac{S}{N}\right\rfloor+1\right) $$

이는 $ N-K $명이 $ \left\lfloor\frac{S}{N}\right\rfloor $원을 내고, $ K $명이 $ \left(\left\lfloor\frac{S}{N}\right\rfloor+1\right) $원을 낸 것이 돈을 재분배한 후 최종 상태가 된다는 뜻입니다. 그리고 돈을 이미 많이 낸 친구들이 1원 더 많이 낼 때 전달되는 돈이 최소가 됨을 알 수 있습니다.

따라서 가장 돈을 많이 낸 $ K $ 명의 친구들은 낸 돈이 $ \left\lfloor\frac{S}{N}\right\rfloor+1 $이 될만큼 받으면 되고, 그 외의 친구들은 $ \left\lfloor\frac{S}{N}\right\rfloor $이 될만큼 받으면 됩니다. 단, 이 과정에서 $ \left\lfloor\frac{S}{N}\right\rfloor+1 $ 또는 $ \left\lfloor\frac{S}{N}\right\rfloor $보다 낸 돈이 적은 친구에 대해서는 이 작업을 할 필요가 없는데, 더 많이 낸 친구들에게 돈을 주기만 하면 되기 때문입니다. 이는 전달된 돈에는 영향을 주지 않습니다.

 

시간복잡도는 $ O(N\log N) $입니다.

 

서브태스크는 따로 언급하지 않겠습니다.

 

*풀이를 적는 도중 코드에 대한 반례를 발견했습니다(5 / 1 1 1 1 4). 하지만 뚫는 것도 실력입니다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
#define fi first
#define se second
#define pb push_back

const ll MAX = 2e5+1;
ll N, M[MAX], sum = 0, lower, num, ans = 0;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> M[i];
        sum += M[i];
    }
    sort(M, M+N);
    lower = sum / N;
    for(num = 0; num < N; num++){
        if(lower * (N-num) + (lower+1) * num == sum) break;
    }
    for(int i = N-1; i >= 0 && M[i] >= lower; i--){
        if(num){
            ans += M[i] - (lower+1);
            --num;
        }
        else ans += M[i] - lower;
    }
    cout << ans << '\n';
    return 0;
}

 

---

7 페인트 칠하기

격자판의 행이나 열을 선택하여 한 가지 색으로 칠할 수 있고, 격자판의 최종 상태가 주어질 때 색을 칠하는 시행을 구하는 Output Only 문제입니다. 작년에는 Output Only 문제를 하나도 못 풀어서 조금 겁부터 먹었는데 역시 1회차인지 꽤 쉬운 문제였습니다.

 

언제나 격자판의 행과 열 중 적어도 하나는 같은 색으로 칠해져 있을 것이고, 이 행 또는 열을 마지막으로 칠한 것이라고 생각할 수 있습니다. 그 행 또는 열을 제거하고, 같은 시행을 반복한 뒤 결과를 역순으로 나타내면 답을 쉽게 구할 수 있습니다.

 

시간복잡도는 $ O(NM(N+M)) $입니다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
#define fi first
#define se second
#define pb push_back

const int MAX = 101;
int N, M, g[MAX][MAX];
stack<tuple<char, int, int> > ans;

int main()
{
    string filename("input_10.txt");
    int number[MAX*MAX+2];
    ifstream input_file(filename);
    if(!input_file.is_open()){
        cerr << "Could not open the file - '" << filename << "'\n";
        return EXIT_FAILURE;
    }
    int cnt = 0;
    while(input_file >> number[cnt]){
        ++cnt;
    }
    N = number[0];
    M = number[1];
    for(int i = 2; i < N*M+2; i++){
        g[(i-2)/M][(i-2)%M] = number[i];
    }
    // cout << N << ' ' << M << '\n';
    // for(int i = 0; i < N; i++){
    //     for(int j = 0; j < M; j++){
    //         cout << g[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    // return 0;
    // cin >> N >> M;
    // for(int i = 0; i < N; i++){
    //     for(int j = 0; j < M; j++){
    //         cin >> g[i][j];
    //     }
    // }
    while(true){
        // printf("loop\n");
        bool fin = true;
        for(int i = 0; i < N; i++){
            int curr = 0;
            for(int j = 0; j < M; j++){
                if(g[i][j]) fin = false;
                if(!curr && g[i][j]) curr = g[i][j];
                else if(curr && g[i][j] != 0 && curr != g[i][j]){
                    curr = -1;
                    break;
                }
            }
            if(curr > 0){
                ans.push({'H', i+1, curr});
                for(int j = 0; j < M; j++){
                    g[i][j] = 0;
                }
            }
        }
        if(fin) break;
        fin = true;
        for(int j = 0; j < M; j++){
            int curr = 0;
            for(int i = 0; i < N; i++){
                if(g[i][j]) fin = false;
                if(!curr && g[i][j]) curr = g[i][j];
                else if(curr && g[i][j] != 0 && curr != g[i][j]){
                    curr = -1;
                    break;
                }
            }
            if(curr > 0){
                ans.push({'V', j+1, curr});
                for(int i = 0; i < N; i++){
                    g[i][j] = 0;
                }
            }
        }
        if(fin) break;
    }
    cout << ans.size() << '\n';
    while(!ans.empty()){
        cout << get<0>(ans.top()) << ' ' << get<1>(ans.top()) << ' ' << get<2>(ans.top()) << '\n';
        ans.pop();
    }
    return 0;
}

---

2회차

2회차 문제가 열린 날에는 코드는 못 짜고 앉아서 생각만 할 수 있는 시간이 몇 시간 있었는데, 그동안 풀이가 거의 다 생각날 정도의 어렵지 않은 난이도였습니다. 뭐 생각했던 풀이가 틀린 것도 있지만...

---

8 폭탄 터뜨리기

값이 $ X $인 폭탄을 터뜨리면, 폭탄에 연속적으로 인접하면서 값이 $ X $ 이상 $ X+K $ 이하인 폭탄이 모두 터질 때 모든 폭탄을 터뜨리기 위한 최소 시행 횟수를 구하는 문제입니다.

 

은근 잘 생각이 안 나다가 한 가지 관찰(?)을 했는데, 값이 $ A_{i} $인 폭탄을 터뜨리는 시점에 값이 $ A_{i} $ 미만인 폭탄이 남아있다면 그 폭탄을 터뜨리기 위해 적어도 한 번의 시행이 필요하다는 것입니다. 그리고 값이 더 작은 폭탄을 먼저 터뜨릴 때 시행 횟수의 측면에서 손해를 보지 않습니다. 따라서 값이 작은 폭탄부터 순서대로 터뜨리면 최소 시행으로 모든 폭탄을 터뜨릴 수 있습니다.

 

시간복잡도는 $ O(N\log N) $입니다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
#define fi first
#define se second
#define pb push_back

const int MAX = 3e5+1;
ll N, K, A[MAX], ans = 0;
pi p[MAX];
bool chk[MAX];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K;
    for(int i = 0; i < N; i++){
        cin >> A[i];
        p[i].fi = A[i];
        p[i].se = i;
    }
    sort(p, p+N);
    for(int i = 0; i < N; i++){
        ll curr = p[i].fi;
        int l = p[i].se;
        int r = l;
        if(chk[l]) continue;
        chk[l] = true;
        // printf("%lld %d\n", curr, l);
        while(l > 0 && curr <= A[l-1] && A[l-1] <= curr+K) chk[--l] = true;
        while(r < N-1 && curr <= A[r+1] && A[r+1] <= curr+K) chk[++r] = true;
        ++ans;
    }
    cout << ans << '\n';
    return 0;
}

---

9 루트가 많은 트리?

유향 간선과 무향 간선으로 이루어진 (간선이 모두 무향이라면 트리가 되는) 그래프가 주어질 때, 무향 간선의 방향을 적절히 조절해서 트리의 루트가 될 수 있는 노드의 수를 구하는 문제입니다.

 

이 문제도 하나의 관찰을 통해서 쉽게 해결할 수 있는데, 문제의 조건을 만족하는 트리에서 루트를 제외한 모든 노드의 indegree 값이 $ 1 $이고, 루트는 $ 0 $이라는 것입니다. 따라서 주어진 유향 간선에 의해서 indegree 값의 상한선인 $ 1 $이 채워진 노드와 연결된 다른 모든 간선은 나가는 쪽으로 뻗어야 합니다. 만약 어떤 노드에 대해서 indegree 값이 $ 1 $ 초과인 상황이 강제된다면 그 경우에 주어진 그래프는 트리가 될 수 없는 것입니다.

 

방향이 강제되는 간선들을 모두 처리한 뒤, indegree 값이 $ 0 $인 모든 노드가 가능한 루트의 후보가 됩니다. 그리고 이 사실이 필요한지는 모르겠지만 루트의 후보가 되는 노드들은 전부 무향 간선으로 연결되어 있습니다. 그렇지 않고서는 문제의 트리 조건을 만족하면서 indegree 값이 $ 0 $이 될 수 없습니다.

 

시간복잡도는 $ O(N) $입니다.

 

서브태스크는 따로 언급하지 않겠습니다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
#define fi first
#define se second
#define pb push_back

const int MAX = 3e5+1;
int N, indegree[MAX], ans = 0;
bool bid[MAX];
vector<pi> adj[MAX];
queue<int> q;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    for(int i = 0; i < N-1; i++){
        int a, b, c;
        cin >> a >> b >> c;
        --a; --b;
        adj[a].pb({b, i});
        ++indegree[b];
        if(c == 0){
            bid[i] = true;
            adj[b].pb({a, i});
            --indegree[b];
        }
    }
    for(int i = 0; i < N; i++){
        if(indegree[i] > 1){
            cout << "0\n";
            return 0;
        }
        else if(indegree[i] == 1){
            q.push(i);
        }
    }
    while(!q.empty()){
        int curr = q.front();
        q.pop();
        for(pi &next : adj[curr]){
            if(bid[next.se]){
                bid[next.se] = false;
                if(++indegree[next.fi] == 1){
                    q.push(next.fi);
                }
                else if(indegree[next.fi] > 1){
                    cout << "0\n";
                    return 0;
                }
            }
        }
    }
    for(int i = 0; i < N; i++){
        if(indegree[i] == 0) ++ans;
    }
    cout << ans << '\n';
    return 0;
}

---

10 영역 나누기

원주 위의 $ 2N $개의 점을 양 끝 점으로 하는 현이 $ N $개 주어질 때, 이들에 의해 원이 최대 몇 개의 영역으로 나누어지는지를 구하는 문제입니다.

 

오일러 공식 $ V-E+F=1 $을 생각하면, 현들 사이의 교차점을 구하는 문제로 바뀜을 알 수 있습니다. (현들 사이의 교차점 수를 $ v $라고 하면, $ V=v+2N $이고, $ E=2v+3N $이므로 $ F=v+N+1 $입니다.)

사실 문제를 보자마자 최근에 풀었던 Codeforces 문제가 생각나서 날로 먹는 줄 알았으나... 저 문제는 제한이 $ N\le100 $이고 이 문제는 $ N\le500\,000 $이더라고요?

 

Inversion counting이랑 엄청 비슷한 것 같다고 생각을 계속 했는데, 결국은 세그먼트 트리를 짰습니다. 먼저 $ N $개의 현의 시작점 $ s $와 끝점 $ e $를 전부 연결시켜놓고, $ s $가 작은 현부터 $ e_{k} \in \left[s_{i}+1,\,e_{i}\right) \; \left(k\in[1,\,i-1]\right)$를 만족하는 $ k $의 수를 세서 교차점의 수에 더하고, 이후 세그먼트 트리에서 $ e_{i} $의 값을 $ 0 $에서 $ 1 $로 바꿔주는 과정을 반복하면 교차점의 총 수가 구해집니다. 이게 되는 이유는 지금까지 세그먼트 트리에 등록된 $ e $ 값들에 대응되는 $ s $ 값들은 전부 $ s_{i} $보다 작다는 것이 보장되므로, 교차한다는 것이 보장됩니다. 그리고 교차점을 중복해서 세는 일도 없기 때문에, $ 1 $번째 현부터 $ N $번째 현까지 반복하면 답이 나옵니다.

 

시간복잡도는 $ O(N\log N) $입니다.

 

서브태스크는 따로 언급하지 않겠습니다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
#define fi first
#define se second
#define pb push_back

const ll MAX = 5e5+1, MAX_ST = 1 << 22, start = MAX_ST / 2;
ll N, chk[MAX*2], seg[MAX_ST], ans = 0;
pl chord[MAX];

ll sum(int s, int e, int node = 1, int ns = 0, int ne = start)
{
    if(e <= ns || ne <= s) return 0;
    if(s <= ns && ne <= e) return seg[node];
    int mid = (ns + ne) / 2;
    return sum(s, e, node*2, ns, mid) + sum(s, e, node*2+1, mid, ne);
}

void upd(int loc)
{
    loc += start;
    seg[loc] += 1;
    while(loc > 0){
        loc /= 2;
        seg[loc] += 1;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    fill(chord, chord+N, make_pair(-1, 0));
    for(int i = 0; i < 2*N; i++){
        int a; cin >> a;
        --a;
        if(chord[a].fi == -1) chord[a].fi = i;
        else chord[a].se = i;
    }
    sort(chord, chord+N);
    for(int i = 0; i < N; i++){
        // cout << chord[i].fi << ' ' << chord[i].se << '\n';
        ans += sum(chord[i].fi+1, chord[i].se);
        // cout << ans << '\n';
        upd(chord[i].se);
    }
    // for(int i = 1; i <= 2*N; i++){
    //     int a; cin >> a;
    //     if(chk[a] > 0){
    //         ans += sum(chk[a]+1, i);
    //         cout << ans << '\n';
    //         upd(i);
    //     }
    //     else{
    //         chk[a] = i;
    //     }
    // }
    cout << ans+N+1 << '\n';
    return 0;
}

---

11 K-좀비

시각이 $ K $의 배수일 때만 인접한 칸을 지나갈 수 있는 $ K $-좀비들이 있는 방을 빠져나가는 이동 커맨드를 구하는 Output Only 문제입니다. 역시 쫄았지만 아주 어렵지는 않았습니다.

 

이 문제의 핵심은 좀비와 인접한 칸으로 둘러싸인 칸에 잘못 들어간다면 갇힐 수 있다는 것입니다. 따라서 계산을 잘 하고 들어가야 합니다. 예를 들어, 한 칸, 두 칸, 세 칸 앞에 각각 $ A $-좀비, $ B $-좀비, $ C $-좀비가 있다면 현재 시각을 $ A $로 나눈 나머지가 $ A-1 $, $ B $로 나눈 나머지가 $ B-2 $, $ C $로 나눈 나머지가 $ C-3 $이 될 때 진입해야 세 칸을 모두 통과할 수 있습니다.

미션7까지는 손으로 해보면서 문제를 파악했고, 8, 9, 10은 도저히 못할 것 같아서 따로 코드를 짜서 해결했습니다. 이동 커맨드의 길이는 $ 100\,000 $ 이하라는 보장이 있어서 될 때까지 루프를 도는 방식으로 풀었습니다. 미션10 답 길이가 딱 $ 100\,000 $이더군요.

 

좀비는 없지만 길이 미로스러운 미션2를 보고 일반적인 입력에 대한 코드를 짜긴 힘들겠다는 생각을 하고 미션8, 9, 10에 각각에 대해서 지도를 하드코딩했는데, 사실 그럴 필요도 없었을 것 같고 짜는 내내 후회막심이었습니다. 그래도 매크로를 좀 써서 가면 갈수록 코드가 좀 나아졌네요...

코드(미션8)

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
#define fi first
#define se second
#define pb push_back

int cnt[10];
string ans;

void move(string c, int n)
{
    for(int i = 0; i < n; i++) ans += c;
    for(int i = 2; i <= 9; i++) cnt[i] = (cnt[i] + n*(int)c.size()) % i;
    cout << ans;
    ans = string();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    move("D", 1);
    // cout << ans << "\n\n";
    // ans = string();
    // Down1
    while(!(cnt[3] == 2 && cnt[7] == 5 && cnt[5] == 2)) move("UD", 1);
    move("D", 5);
    // cout << ans << "\n\n";
    // ans = string();
    while(!(cnt[5] == 4 && cnt[3] == 1 && cnt[7] == 4)) move("UD", 1);
    move("D", 6);
    // cout << ans << "\n\n";
    // ans = string();
    while(!(cnt[3] == 2 && cnt[5] == 3 && cnt[7] == 4)) move("UD", 1);
    move("D", 5);
    // cout << ans << "\n\n";
    // ans = string();
    while(!(cnt[5] == 4 && cnt[3] == 1 && cnt[7] == 4)) move("UD", 1);
    move("DDDDDDRRUU", 1);
    // cout << ans << "\n\n";
    // ans = string();
    // Up1
    while(!(cnt[7] == 6 && cnt[3] == 1 && cnt[5] == 2)) move("DU", 1);
    move("U", 5);
    while(!(cnt[7] == 6 && cnt[5] == 3 && cnt[3] == 0)) move("DU", 1);
    move("U", 6);
    while(!(cnt[7] == 6 && cnt[3] == 1 && cnt[5] == 2)) move("DU", 1);
    move("U", 5);
    while(!(cnt[5] == 4 && cnt[7] == 5 && cnt[3] == 0)) move("DU", 1);
    move("UUUURR", 1);
    // cout << ans << "\n\n";
    // ans = string();
    // Down2
    while(!(cnt[3] == 2 && cnt[7] == 5 && cnt[5] == 2)) move("UD", 1);
    move("D", 5);
    while(!(cnt[7] == 6 && cnt[3] == 1 && cnt[5] == 2)) move("UD", 1);
    move("D", 6);
    while(!(cnt[5] == 4 && cnt[3] == 1 && cnt[7] == 4)) move("UD", 1);
    move("D", 5);
    while(!(cnt[3] == 2 && cnt[7] == 5 && cnt[5] == 2)) move("UD", 1);
    move("DDDDDDRRUU", 1);
    // cout << ans << "\n\n";
    // ans = string();
    // Up2
    while(!(cnt[5] == 4 && cnt[7] == 5 && cnt[3] == 0)) move("DU", 1);
    move("U", 5);
    while(!(cnt[7] == 6 && cnt[3] == 1 && cnt[5] == 2)) move("DU", 1);
    move("U", 6);
    while(!(cnt[5] == 4 && cnt[3] == 1 && cnt[7] == 4)) move("DU", 1);
    move("U", 5);
    while(!(cnt[5] == 4 && cnt[7] == 5 && cnt[3] == 0)) move("DU", 1);
    move("UUUURR", 1);
    // cout << ans << "\n\n";
    // ans = string();
    // Down3
    while(!(cnt[7] == 6 && cnt[5] == 3 && cnt[3] == 0)) move("UD", 1);
    move("D", 5);
    while(!(cnt[3] == 2 && cnt[7] == 5 && cnt[5] == 2)) move("UD", 1);
    move("D", 6);
    while(!(cnt[3] == 2 && cnt[7] == 5 && cnt[5] == 2)) move("UD", 1);
    move("D", 5);
    while(!(cnt[3] == 2 && cnt[7] == 5 && cnt[5] == 2)) move("UD", 1);
    move("DDDDDDRRUU", 1);
    // cout << ans << "\n\n";
    // ans = string();
    // Up3
    while(!(cnt[5] == 4 && cnt[7] == 5 && cnt[3] == 0)) move("DU", 1);
    move("U", 5);
    while(!(cnt[5] == 4 && cnt[7] == 5 && cnt[3] == 0)) move("DU", 1);
    move("U", 6);
    while(!(cnt[5] == 4 && cnt[7] == 5 && cnt[3] == 0)) move("DU", 1);
    move("U", 5);
    while(!(cnt[3] == 2 && cnt[5] == 3 && cnt[7] == 4)) move("DU", 1);
    move("UUUURR", 1);
    // cout << ans << "\n\n";
    // ans = string();
    // Down4
    while(!(cnt[5] == 4 && cnt[3] == 1 && cnt[7] == 4)) move("UD", 1);
    move("D", 5);
    while(!(cnt[5] == 4 && cnt[7] == 5 && cnt[3] == 0)) move("UD", 1);
    move("D", 6);
    while(!(cnt[5] == 4 && cnt[3] == 1 && cnt[7] == 4)) move("UD", 1);
    move("D", 5);
    while(!(cnt[7] == 6 && cnt[5] == 3 && cnt[3] == 0)) move("UD", 1);
    move("DDDDDDRRUU", 1);
    // cout << ans << "\n\n";
    // ans = string();
    // Up4
    while(!(cnt[3] == 2 && cnt[5] == 3 && cnt[7] == 4)) move("DU", 1);
    move("U", 5);
    while(!(cnt[7] == 6 && cnt[3] == 1 && cnt[5] == 2)) move("DU", 1);
    move("U", 6);
    while(!(cnt[3] == 2 && cnt[7] == 5 && cnt[5] == 2)) move("DU", 1);
    move("U", 5);
    while(!(cnt[7] == 6 && cnt[3] == 1 && cnt[5] == 2)) move("DU", 1);
    move("UUUURR", 1);
    // cout << ans << "\n\n";
    // ans = string();
    // Down5
    while(!(cnt[5] == 4 && cnt[7] == 5 && cnt[3] == 0)) move("UD", 1);
    move("D", 5);
    while(!(cnt[5] == 4 && cnt[7] == 5 && cnt[3] == 0)) move("UD", 1);
    move("D", 6);
    while(!(cnt[7] == 6 && cnt[3] == 1 && cnt[5] == 2)) move("UD", 1);
    move("D", 5);
    while(!(cnt[3] == 2 && cnt[7] == 5 && cnt[5] == 2)) move("UD", 1);
    move("DDDDDDRRUU", 1);
    // cout << ans << "\n\n";
    // ans = string();
    // Up5
    while(!(cnt[5] == 4 && cnt[7] == 5 && cnt[3] == 0)) move("DU", 1);
    move("U", 5);
    while(!(cnt[5] == 4 && cnt[3] == 1 && cnt[7] == 4)) move("DU", 1);
    move("U", 6);
    while(!(cnt[3] == 2 && cnt[7] == 5 && cnt[5] == 2)) move("DU", 1);
    move("U", 5);
    while(!(cnt[3] == 2 && cnt[7] == 5 && cnt[5] == 2)) move("DU", 1);
    move("UUUURR", 1);
    // cout << ans << "\n\n";
    // ans = string();
    // Down6
    while(!(cnt[5] == 4 && cnt[3] == 1 && cnt[7] == 4)) move("UD", 1);
    move("D", 5);
    while(!(cnt[5] == 4 && cnt[7] == 5 && cnt[3] == 0)) move("UD", 1);
    move("D", 6);
    while(!(cnt[7] == 6 && cnt[5] == 3 && cnt[3] == 0)) move("UD", 1);
    move("D", 5);
    while(!(cnt[7] == 6 && cnt[3] == 1 && cnt[5] == 2)) move("UD", 1);
    move("DDDDDDRRUU", 1);
    // cout << ans << "\n\n";
    // ans = string();
    // Up6
    while(!(cnt[5] == 4 && cnt[3] == 1 && cnt[7] == 4)) move("DU", 1);
    move("U", 5);
    while(!(cnt[3] == 2 && cnt[5] == 3 && cnt[7] == 4)) move("DU", 1);
    move("U", 6);
    while(!(cnt[3] == 2 && cnt[7] == 5 && cnt[5] == 2)) move("DU", 1);
    move("U", 5);
    while(!(cnt[7] == 6 && cnt[3] == 1 && cnt[5] == 2)) move("DU", 1);
    move("UUUURR", 1);
    move("D", 23);

    // cout << ans << '\n';
    return 0;
}

코드(미션9)

#include <bits/stdc++.h>
#define w4(i, j, k, l) while(!(cnt[i] == i-1 && cnt[j] == j-2 && cnt[k] == (k*2-4)%k && cnt[l] == (l*3-5)%l))
#define w6(a, b, c, d, e, f) while(!(cnt[a] == a-1 && cnt[b] == (b*2-3)%b && cnt[c] == (c*2-4)%c && cnt[d] == (d*3-6)%d && cnt[e] == (e*4-7)%e && cnt[f] == (f*5-9)%f))
#define w7(a, b, c, d, e, f, g) while(!(cnt[a] == a-1 && cnt[b] == b-2 && cnt[c] == (c*2-3)%c && cnt[d] == (d*2-4)%d && cnt[e] == (e*3-5)%e && cnt[f] == (f*3-6)%f && cnt[g] == (g*4-7)%g))
using namespace std;

int cnt[10];

void m(string c, int n)
{
    string s;
    for(int i = 0; i < n; i++) s += c;
    for(int i = 2; i <= 9; i++) cnt[i] = (cnt[i] + n*(int)c.size()) % i;
    cout << s;
}

int main()
{
    m("R", 1);
    w6(4, 7, 9, 5, 3, 4) m("LR", 1); m("R", 3); m("D", 4); m("R", 5);
    w6(4, 3, 7, 9, 5, 4) m("LR", 1); m("R", 3); m("U", 4); m("R", 5);
    w6(8, 7, 9, 5, 3, 4) m("LR", 1); m("R", 3); m("D", 4); m("R", 2); m("D", 2); m("L", 1);
    w6(4, 3, 7, 9, 5, 8) m("RL", 1); m("L", 3); m("D", 4); m("L", 5);
    w6(8, 7, 9, 5, 3, 4) m("RL", 1); m("L", 3); m("U", 4); m("L", 6); m("D", 10); m("R", 3);
    w6(4, 3, 5, 9, 7, 4) m("LR", 1); m("R", 3); m("U", 4); m("R", 5);
    w6(4, 5, 9, 7, 3, 8) m("LR", 1); m("R", 3); m("D", 4); m("R", 4); m("D", 2); m("L", 1);
    w6(4, 3, 7, 9, 5, 4) m("RL", 1); m("L", 3); m("D", 4); m("L", 5);
    w6(4, 5, 9, 7, 3, 4) m("RL", 1); m("L", 3); m("U", 4); m("L", 6); m("D", 4); m("R", 2); m("U", 2); m("R", 1);
    w4(4, 9, 7, 4) m("LR", 1); m("R", 8);
    w4(4, 7, 9, 4) m("LR", 1); m("R", 9); m("U", 6); m("L", 3);
    w4(8, 9, 7, 4) m("RL", 1); m("L", 8);
    w4(4, 5, 9, 4) m("RL", 1); m("L", 7); m("U", 6); m("R", 1);
    w4(4, 9, 5, 8) m("LR", 1); m("R", 8);
    w4(8, 7, 9, 4) m("LR", 1); m("R", 9); m("U", 6); m("L", 1);
    w4(4, 9, 5, 8) m("RL", 1); m("L", 8);
    w4(4, 7, 9, 4) m("RL", 1); m("L", 8);
    w4(4, 9, 5, 4) m("RL", 1); m("L", 6); m("D", 3); m("R", 1); m("D", 1);
    w7(3, 8, 7, 6, 5, 4, 9) m("UD", 1); m("D", 10);
    w7(9, 4, 5, 6, 7, 8, 3) m("UD", 1); m("D", 8); m("R", 22);
}

코드(미션10)

#include <bits/stdc++.h>
#define w2(i, j) while(!(cnt[i] == i-1 && cnt[j] == j-2))
#define w3(i, j, k) while(!(cnt[i] == i-1 && cnt[j] == j-2 && cnt[k] == k-3))
#define w4(i, j, k, l) while(!(cnt[i] == i-1 && cnt[j] == j-2 && cnt[k] == k-3 && cnt[l] == l-4))

using namespace std;

int cnt[10];

void m(string c, int n)
{
    string s;
    for(int i = 0; i < n; i++) s += c;
    for(int i = 2; i <= 9; i++) cnt[i] = (cnt[i] + n*(int)c.size()) % i;
    cout << s;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    m("R", 1);
    w4(5, 9, 8, 7) m("LR", 1); m("R", 6);
    w4(8, 5, 9, 7) m("LR", 1); m("R", 6);
    w4(7, 9, 8, 5) m("LR", 1); m("R", 6);
    w3(9, 5, 8) m("LR", 1); m("RRRRRDDL", 1);

    w3(8, 5, 9) m("RL", 1); m("L", 5);
    w4(5, 8, 9, 7) m("RL", 1); m("L", 6);
    w4(7, 9, 5, 8) m("RL", 1); m("L", 6);
    w4(7, 8, 9, 5) m("RL", 1); m("LLLLLLDD", 1);

    w4(7, 8, 9, 5) m("UD", 1); m("R", 6);
    w4(5, 7, 9, 8) m("LR", 1); m("R", 6);
    w4(9, 8, 5, 7) m("LR", 1); m("R", 6);
    w4(5, 8, 7, 9) m("LR", 1); m("RRRRRRDDL", 1);

    w4(9, 7, 8, 5) m("RL", 1); m("L", 6);
    w4(7, 5, 8, 9) m("RL", 1); m("L", 6);
    w4(8, 9, 7, 5) m("RL", 1); m("L", 6);
    w4(5, 9, 8, 7) m("RL", 1); m("LLLLLDD", 1);
    
    w4(5, 7, 9, 8) m("UD", 1); m("R", 6);
    w4(9, 8, 5, 7) m("LR", 1); m("R", 6);
    w4(5, 8, 7, 9) m("LR", 1); m("R", 6);
    w4(7, 5, 9, 8) m("LR", 1); m("RRRRRRDDL", 1);

    w4(8, 9, 5, 7) m("RL", 1); m("L", 6);
    w4(9, 7, 8, 5) m("RL", 1); m("L", 6);
    w4(7, 5, 8, 9) m("RL", 1); m("L", 6);
    w4(8, 9, 7, 5) m("RL", 1); m("LLLLLDD", 1);
    
    w4(7, 8, 9, 5) m("UD", 1); m("R", 6);
    w4(5, 7, 9, 8) m("LR", 1); m("R", 6);
    w4(9, 8, 5, 7) m("LR", 1); m("R", 6);
    w4(5, 8, 7, 9) m("LR", 1); m("RRRRRRDDL", 1);

    w4(9, 7, 8, 5) m("RL", 1); m("L", 6);
    w4(7, 5, 8, 9) m("RL", 1); m("L", 6);
    w4(8, 9, 7, 5) m("RL", 1); m("L", 6);
    w4(5, 9, 8, 7) m("RL", 1); m("LLLLLDD", 1);
    
    w4(5, 7, 9, 8) m("UD", 1); m("R", 6);
    w4(9, 8, 5, 7) m("LR", 1); m("R", 6);
    w4(5, 8, 7, 9) m("LR", 1); m("R", 6);
    w4(7, 5, 9, 8) m("LR", 1); m("RRRRRRDDL", 1);

    w4(8, 9, 5, 7) m("RL", 1); m("L", 6);
    w4(9, 7, 8, 5) m("RL", 1); m("L", 6);
    w4(7, 5, 8, 9) m("RL", 1); m("L", 6);
    w4(8, 9, 7, 5) m("RL", 1); m("LLLLLDD", 1);

    w4(7, 8, 9, 5) m("UD", 1); m("R", 6);
    w4(5, 7, 9, 8) m("LR", 1); m("R", 6);
    w4(9, 5, 7, 8) m("LR", 1); m("R", 12); m("D", 1);
    w2(5, 9) m("UD", 1); m("D", 1); m("L", 7);

    w4(8, 7, 5, 9) m("RL", 1); m("L", 6);
    w4(8, 9, 7, 5) m("RL", 1); m("L", 6);
    w4(5, 9, 8, 7) m("RL", 1); m("LLLLLDDR", 1);

    w3(8, 9, 5) m("LR", 1); m("R", 5);
    w4(5, 7, 9, 8) m("LR", 1); m("R", 6);
    w4(9, 5, 7, 8) m("LR", 1); m("R", 10);
    w2(9, 5) m("LR", 1); m("R", 2);
    return 0;
}

---

3회차

2회차 문제까지는 어떻게 당일 새벽까지 마무리를 지었지만, 3회차부터는 저한테는 정말 어려웠습니다. Batch 문제는 4회차 문제가 공개되기 직전에 다 풀 수 있었고, Output Only 문제는 끝까지 만점은 받지 못했습니다.

---

12 다양성이 힘이다

$ N $개의 수 $ X_{0},\,X_{2},\,...,\,X_{N-1} $ 중 연속한 $ K $개를 고르고 고른 수들 중 임의의 두 수의 차 $ |X_{i}-X_{j}| $의 합을 실력이라고 할 때, 가능한 실력의 최댓값을 구하는 문제입니다.

실력을 $ A $로 표현하겠습니다.

 

서브태스크 1: $ K\le 10 $ (8점)

정의대로 $ A $를 계산하는 데 드는 시간복잡도는 $ O(K^{2}) $이지만, 이 경우에는 $ K $가 매우 작기 때문에 $ O(NK^{2}) $의 완전탐색 풀이가 통과합니다.

 

서브태스크 2: $ X_{i}\le 10 $ (21점)

$ X_{i} $의 범위가 제한된다면 실력을 더 쉽게 구할 수 있습니다. 길이 $ K $의 구간에 대해서 $ 1,\, 2,\,...,\,10 $의 개수를 $ n_{1},\, n_{2},\, ...,\,n_{10} $라고 하면, 실력은 다음과 같이 나타낼 수 있습니다.

$$ A=\sum_{i=1}^{10}\sum_{j=1}^{i-1} n_{i}n_{j}(i-j) $$

구간의 시작점을 한 자리씩 옮기면서 $ n $을 업데이트해주고, 위 식을 활용하면 매 구간에 대해 $ O(1) $에 실력을 계산할 수 있습니다.

 

시간복잡도는 $ O(N-K) $입니다.

 

서브태스크 3: $ N\le5\,000 $ (17점)

$ \left[X_{s},\, X_{s+1},\, ...,\, X_{s+K-1} \right] \; \left(s \le N-K\right) $을 정렬한 배열을 $ \left[Y_{s},\, Y_{s+1},\, ...,\, Y_{s+K-1} \right] $라고 정의하면, 다음과 같이 정리할 수 있습니다.

$$ A(s)=\sum_{i=s}^{s+K-1}\sum_{j=i+1}^{s+K-1}{|X_{i}-X_{j}|}=\sum_{i=0}^{K-1}\left(2i-K+1\right)Y_{s+i} $$

이는 $ A(s) $를 정의대로 쭉 전개해봤을 때 몇 번 더해지고 몇 번 빼지는지를 확인해보면 유도할 수 있습니다. 아래 서브태스크 4의 그림을 보시면 이해가 더 잘 될 것 같네요. 이와 같이 정리를 한 후에는 정렬에 $ O(K\log K) $, 계산에 $ O(K) $만이 듭니다.

 

$ A $를 구하는 방법을 이렇게 변경하여 완전탐색을 하는 데 드는 시간복잡도는 $ O(NK\log K) $입니다.

 

서브태스크 4: 추가적인 제한 조건이 없음. (54점)

만점 풀이는 서브태스크 3의 아이디어로부터 얻을 수 있습니다. 서브태스크 3에서 시간이 오래 걸리는 지점은 구간을 변경할 때마다 정렬을 해주고 계산하는 부분이었습니다. 구간을 한 칸 옮길 때는 원래 수 하나가 빠지고 새로운 수 하나가 들어올 뿐인데, 정렬을 새로 하는 것은 조금 아깝다는 생각이 듭니다. 이때 머지 소트 트리(Merge Sort Tree)를 사용하면 이 과정을 단축 내지 생략(?)할 수 있습니다.

먼저 서브태스크 3의 실력 계산법에서 어떤 수를 넣거나 뺄 때 무엇을 알아야 하는지에 대해 생각해보겠습니다.

 

빨간 구간에서 초록 구간으로 이동하면서 일어나는 실력의 변화

위 그림은 $ K=5 $인 예시를 나타낸 것입니다. $ X $의 첫 수인 $ 2 $가 빠지면, $ 2 $보다 큰 수들이 $ Y $ 상에서 한 칸씩 앞으로 당겨져 옵니다. 이 과정에서 원래 실력에 빠지는 수 자신이 기여하는 값$ (2\times(-2)) $을 빼고, 당겨지는 원소들의 합$ \times 2\;((4+5+7)\times 2) $를 빼주면 중간 상태의 실력이 구해집니다. 다시 $ X $의 $ 6 $번째 수인 $ 6 $이 자신의 위치로 들어가면 $ 6 $보다 큰 원소들은 한 칸씩 뒤로 밀립니다. 이 과정에서 실력의 변화는 원소를 뺄 때와 비슷하게, 들어가는 수 자신이 기여하는 값$ (6\times2) $을 더하고, 밀리는 원소들의 합$ \times 2\;((7)\times 2) $를 더해주면 새로운 실력이 구해집니다.

이 계산을 위해서는 넣거나 빼려는 수가 해당 구간을 정렬한 배열에서 몇 번째에 위치해있는지, 그리고 자신보다 큰 원소들의 합이 얼마인지를 알아야 합니다.

머지 소트 트리를 이용하면 임의의 구간에서 어떤 수보다 큰 수의 개수를 $ O(\log^{2} N) $에 구할 수 있습니다. 그리고 머지 소트 트리를 만들면서 머지 소트 트리의 각 노드에 대해 부분합(prefix sum)을 계산해두면 임의의 구간에서 어떤 수보다 큰 수들의 합도 $ O(\log^{2} N) $에 구할 수 있습니다.

처음 실력의 값은 서브태스크 3과 같이 직접 정렬 후 구하고, 이 과정을 $ N-K $번 반복하면서 실력의 최댓값을 찾으면 됩니다.

 

시간복잡도는 $ O((N-K)\log^{2} N) $입니다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
#define fi first
#define se second
#define pb push_back

const ll MAX = 1e5, MAX_ST = 1<<20, start = MAX_ST / 2;
int N, K;
ll ans = 0, tans = 0;
vector<ll> mst[MAX_ST], mst_psum[MAX_ST], X;

int gt(int s, int e, ll k, int node = 1, int ns = 0, int ne = start)
{
    if(e <= ns || ne <= s) return 0;
    if(s <= ns && ne <= e){
        return mst[node].end() - upper_bound(mst[node].begin(), mst[node].end(), k);
    }
    int mid = (ns + ne) / 2;
    return gt(s, e, k, node*2, ns, mid) + gt(s, e, k, node*2+1, mid, ne);
}

ll gt_sum(int s, int e, ll k, int node = 1, int ns = 0, int ne = start)
{
    if(e <= ns || ne <= s) return 0;
    if(s <= ns && ne <= e){
        int l = mst[node].end() - mst[node].begin();
        int r = upper_bound(mst[node].begin(), mst[node].end(), k) - mst[node].begin();
        return mst_psum[node][l] - mst_psum[node][r];
    }
    int mid = (ns + ne) / 2;
    return gt_sum(s, e, k, node*2, ns, mid) + gt_sum(s, e, k, node*2+1, mid, ne);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    for(int i = 0; i < MAX_ST; i++) mst_psum[i].pb(0);
    cin >> N >> K;
    X.resize(N);
    for(int i = 0; i < N; i++){
        cin >> X[i];
        mst[start+i].pb(X[i]);
        mst_psum[start+i].pb(X[i]);
    }
    for(int i = start-1; i > 0; i--){
        vector<ll> &c = mst[i], &d = mst_psum[i], &l = mst[i*2], &r = mst[i*2+1];
        c.resize(l.size() + r.size());
        d.resize(l.size() + r.size() + 1);
        for(int j = 0, p = 0, q = 0; j < c.size(); j++){
            if(q == r.size() || (p < l.size() && l[p] < r[q])){
                c[j] = l[p++];
            }
            else c[j] = r[q++];
            d[j+1] = d[j] + c[j];
        }
    }
    // for(int i = 1; i < MAX_ST; i++){
    //     printf("%d: ", i);
    //     for(int j : mst[i]) printf("%d ", j);
    //     printf("\n ");
    //     for(int j : mst_psum[i]) printf("%d ", j);
    //     printf("\n");
    // }
    vector<ll> Y(X.begin(), X.begin()+K);
    sort(Y.begin(), Y.end());
    for(int i = 0; i < K; i++){
        tans += (2*i - K + 1) * Y[i];
    }
    ans = tans;
    for(int i = K; i < N; i++){
        ll ol = X[i-K], nw = X[i];
        int l1 = gt(i-K+1, i, ol), l2 = gt(i-K+1, i, nw);
        tans -= (K - 2*l1 - 1) * ol;
        tans -= 2 * gt_sum(i-K+1, i, ol);
        tans += (K - 2*l2 - 1) * nw;
        tans += 2 * gt_sum(i-K+1, i, nw);
        ans = max(ans, tans);
    }
    cout << ans << '\n';
    return 0;
}

---

13 원룸 구하기

$ K $종류의 가게 $ N $개가 직선 위에 분포해 있을 때, $ M $개의 원룸에 대해 $ K $종류의 가게와 그 원룸을 모두 포함하는 구간의 최소 길이인 '필수 생활 거리'를 각각 구하는 문제입니다.

 

계속 원룸의 위치 기준으로 생각을 하다가 시간을 많이 뺏겼습니다. 전체적으로 원룸을 아예 배제하고 생각하니까 풀이 떠올리기가 훨씬 수월하더라고요..

 

서브태스크 1: $ N,\, K,\, M \le 500 $ (8점), 서브태스크 2: $ N,\, K,\, M \le 5\,000 $ (21점)

 

먼저 $ N $개의 가게를 위치 기준으로 정렬하고, 각 가게에 대해 자신을 가장 왼쪽 끝점으로 가지면서, $ K $종류의 가게를 모두 포함하는 구간을 구합니다. 이 작업을 하는 데는 여러 방법이 있겠지만 나이브한 방법으로, 그냥 $ K $종류의 가게를 모두 포함하게 될 때까지 한 가게씩 오른쪽으로 이동해도 됩니다. 완성되지 않는 구간들은 적절히 제외해주면 됩니다.

이제 $ N $개 이하의 구간이 있을 텐데, 각 원룸에 대해 모든 구간과 대응해보면서 최소인 길이를 구할 수 있습니다. 원룸과 구간의 위치 관계에 유의해야 합니다.

 

시간복잡도는 $ O(N^{2}+NM) $입니다.

 

서브태스크 3: $ K \le 10 $ (15점)

원래 이 서브태스크를 따로 생각하고 풀이를 생각했었고 49점을 맞은 기록도 있지만, 의도한 대로 구현하기 전에 100점 풀이를 생각해낸 것으로 기억을 해서 100점 풀이와 다른 점만 간단히 설명하고 넘어가겠습니다.

$ K $가 굉장히 작기 때문에, 구간을 구할 때 현재 가게보다 오른쪽에 있는 가장 가까운 $ i $번 가게를 $ K-1 $번의 이분탐색(lower_bound)으로 구하는 것이 시간적으로 가능합니다. 이렇게 한다면 구간을 구하는 부분의 시간복잡도는 $ O(NK\log N) $이 됩니다.

 

서브태스크 4: 추가적인 제한 조건이 없음. (51점)

$ N,\, K,\, M \le 500\,000 $이라는 조건을 만족시키기 위해서는 구간을 구하는 부분에 대해서도 개선이 필요하고, 원룸마다 필수 생활 거리를 구하는 부분에 대해서도 개선이 필요합니다.

 

구간을 구하는 부분은 서브태스크 3과 비슷하지만, 스위핑을 이용해 더 빠르게 구하는 것이 가능합니다. 먼저 서브태스크 3의 방법을 이용해 맨 왼쪽 가게에 대해 구간을 구해놓습니다. 이제 다음 가게에 대해서 구간을 구해야 하는데, 이번에는 냅다 구하지는 말고 바로 전에 구한 구간에서 첫 가게만 한 번 빼봅니다. 지금 보고 있는 구간에는 방금 뺀 종류의 가게가 있을 수도, 없을 수도 있습니다. 있다면 그대로 조건을 만족하는 구간인 것이고, 아니라면 다음으로 가까운 가게를 찾아서 구간을 넓혀줘야 합니다. 현재 위치에서 빠진 가게의 종류에 대해서 lower_bound를 때려서 가장 가까이 있는 가게의 위치를 구하면 이 가게가 구간 내에 있는지에 대한 판단을 할 수 있습니다.

이렇게 가능한 모든 구간을 $ O(N\log N) $에 구할 수 있습니다.

 

원룸마다 필수 생활 거리를 구하기 전에 구간들에 대해 어떤 처리를 해줘야 합니다. 구간을 구하는 과정을 살펴보면서 알아차리셨을 수 있겠지만, 구간들 사이에 포함관계가 존재할 수 있고, 한 구간이 다른 구간을 포함한다면 그중 큰 구간은 고려할 필요가 없습니다. 원룸이 어떤 위치에 있더라도 큰 구간 대신 작은 구간을 선택하면 필수 생활 거리가 길어지지 않기 때문입니다.

포함관계에 있는 구간들 중 큰 구간을 전부 지워주면, 구간들은 수직선 상에서 아래 그림과 비슷한 위치 관계만을 나타낼 것입니다. 지우는 과정은 구간들을 끝점을 기준으로 정렬한 뒤 시작점이 단조증가하지 않는 경우 지워주면 됩니다.

구간들 사이의 위치 관계의 예시

 

이제 각 원룸에 대해서 필수 생활 거리를 구할 준비가 됐습니다.

원룸의 위치를 포함하는 구간에 대해서 필수 생활 거리의 후보는 구간의 길이 그 자체이니 전부 비교해줍시다.

원룸의 위치를 포함하지 않는 구간을 조사할 때 앞서 해준 처리가 빛을 발하는데, 왼쪽, 오른쪽으로 가장 가까운 구간 하나씩만 비교해주면 됩니다. 그 이유는, 두 번째로 가까운 구간은 시작점과 끝점 둘 다 가장 가까운 구간보다 원룸과 더 멀리 있기 때문에 절대 최소가 될 수 없습니다. 그림을 보시면 더 이해가 잘 될 것 같습니다.

X 친 것은 후보가 될 수 없기에 고려할 필요가 없다

X 친 것은 필수 생활 거리의 후보가 될 수 없기에 고려할 필요가 없고, O 친 것, 그러니까 좌우로 가장 가까운 하나씩만 고려해주면 됩니다.

 

자연스럽게 넘어갔지만, 사실 이 풀이에는 치명적인 문제가 한 가지 있습니다. 바로 원룸의 위치를 포함하는 구간의 개수가 최대 $ N $개라는 것이죠! 이미 최적화를 상당히 한 것처럼 보이지만 최악의 경우에는 여전히 $ O(NM) $의 시간복잡도를 보여주고, 시간 초과를 받게 됩니다. 그런데 맞았네요? 역시 뚫는 것도 실력입니다.

 

뚫린 건 진짜지만 장난이고, 저는 당연히 시간 초과가 날 줄 알고 생각해둔 최적화가 하나 더 있긴 합니다. 원룸의 위치를 포함하는 구간들의 경우, 필수 생활 거리의 후보가 원룸의 위치와 무관하게 구간의 길이 자체인 것을 이용합니다.

먼저 앞서 구한 구간의 길이들로 이루어진 min 세그먼트 트리를 만듭니다. 또, 이분탐색(lower_bound, upper_bound)을 적절히 사용해서 각 원룸에 대해서 '자신의 위치를 포함하는 구간'의 구간을 구할 수 있습니다. '자신의 위치를 포함하는 구간'의 구간 내의 최솟값을 min 세그먼트 트리를 이용해 구할 수 있습니다. 이렇게 처리할 경우, $ O(M\log N) $의 시간복잡도가 보장됩니다.

시간이 좀 여유가 있었다면 이것도 짜 봤을 텐데, 3회차부터는 정말 문제 푸느라 바빠서 따로 짜지는 못했습니다. 대회가 끝난 지금도 딱히 짜 보고 싶지는 않네요...

 

아래 있는 코드의 시간복잡도는 $ O(N\log N+NM) $이고, 따로 서술한 정상적인 풀이의 시간복잡도는 $ O((N+M)\log N) $입니다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
#define fi first
#define se second
#define pb push_back

const ll MAX = 5e5+1, INF = 1e15;
ll N, K, M, r[MAX];
pl a[MAX];
vector<pl> s[MAX], seg;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K >> M;
    for(int i = 0; i < N; i++){
        cin >> a[i].fi >> a[i].se;
        --a[i].se;
    }
    a[N] = {INF, INF};
    sort(a, a+N);
    for(int i = 0; i < N; i++) s[a[i].se].pb({a[i].fi, i});
    // for(int i = 0; i < N; i++) printf("%lld ", a[i].fi); printf("\n\n");
    for(int i = 0; i < K; i++){
        sort(s[i].begin(), s[i].end());
        s[i].pb({INF, N});
        // for(pi j : s[i]) printf("(%lld %lld) ", j.fi, j.se); printf("\n\n");
    }
    for(int i = 0; i < M; i++) cin >> r[i];




    ll ldx = 0, rdx = 0;
    for(int i = 0; i < K; i++){
        if(i == a[0].se) continue;
        int idx = lower_bound(s[i].begin(), s[i].end(), make_pair(a[ldx].fi, -INF)) - s[i].begin();
        if(a[rdx].fi < s[i][idx].fi) rdx = s[i][idx].se;
    }
    for(; ldx < N; ldx++){
        seg.pb({a[ldx].fi, a[rdx].fi});
        int prev = a[ldx].se;
        int idx = lower_bound(s[prev].begin(), s[prev].end(), make_pair(max(a[ldx].fi+1, a[ldx+1].fi), -INF)) - s[prev].begin();
        if(a[rdx].fi < s[prev][idx].fi) rdx = s[prev][idx].se;
    }




    sort(seg.begin(), seg.end(), [&](pl &a, pl &b){
        return a.se == b.se ? a.fi > b.fi : a.se < b.se;
    });
    // for(pl &i : seg) printf("%lld %lld\n", i.fi, i.se); printf("\n");
    ll left = -INF;
    for(pl &p : seg){
        if(p.se == INF){
            p.fi = INF;
            continue;
        }
        if(left < p.fi) left = p.fi;
        else p.fi = p.se = INF;
    }
    sort(seg.begin(), seg.end());
    int tmp = lower_bound(seg.begin(), seg.end(), make_pair(INF, INF)) - seg.begin();
    seg.resize(tmp);
    // for(pl &i : seg) printf("%lld %lld\n", i.fi, i.se); printf("\n");
    for(int i = 0; i < M; i++){
        ll ans = INF;
        int ldx = upper_bound(seg.begin(), seg.end(), make_pair(INF, r[i]), [&](pl a, pl b){
            return a.se == b.se ? a.fi < b.fi : a.se < b.se;
        }) - seg.begin() - 1;
        if(ldx < 0) ldx = 0;
        int rdx = lower_bound(seg.begin(), seg.end(), make_pair(r[i], -INF)) - seg.begin();
        if(rdx >= seg.size()) rdx = seg.size()-1;
        for(int j = ldx; j <= rdx; j++){
            ans = min(ans, max(r[i], seg[j].se) - min(r[i], seg[j].fi));
        }
        cout << ans << '\n';
    }
    return 0;
}

---

14 생존 신호

격자의 경계에 난 구멍으로 빛을 쏴서 적당히 반사시켜 다시 밖으로 나오게 하는 최대 길이의 경로를 구하는 Output Only 문제입니다.

95.5점 만을 받았습니다.

 

코드? 알고리즘? 그런 거 없이 그냥 손으로 95.5점까지만 긁었습니다.

 

정해는 connection profile dp라고 하는데 뭔지 잘 모르겠어요..

거울을 설치할 수 있는 파란 점을 그래프의 노드로 본 뒤, 오일러 경로를 만들기 위해 홀수 차수 점들을 적당히 지워나가는 작업을 하면 손으로 어렵지 않게 최대 길이 경로를 구할 수 있다고 합니다.

코드

 

---

4회차

1~3회차의 1200점 중에서는 1195.5점을 얻었지만 4회차의 300점 중에서는 177점 만을 얻었습니다.

세 문제 전부 처음 봤을 때는 풀릴 기미가 안 보였던 걸 생각하면 나름 선방한 것 같습니다.

---

15 선물 상자

$ N $명의 사람이 원형으로 둘러앉아 있을 때, 원을 따라 사람을 세어 $ M $번째 사람에게 사탕을 주는 것을 반복하는데, $ i $번째 사람이 받은 사탕이 $ D_{i} $개가 되면 원에서 빠집니다. 이때 마지막까지 남아있는 사람이 누구인지 구하는 문제입니다.

 

서브태스크 2: $ M=1 $ (8점)

매우 매우 쉬운 서브태스크입니다. 건너뛰지 않고 모든 사람을 연속적으로 지나므로, $ D_{i} $가 가장 큰 사람의 인덱스가 답이 됩니다. 가장 큰 $ D_{i} $를 가지는 사람이 둘 이상이라면 인덱스가 더 큰 사람이 마지막까지 남습니다.

 

시간복잡도는 $ O(N) $입니다.

 

서브태스크 1: 모든 $ i $에 대해 $ D_{i} \le 10 $ (9점)

나이브보다 아주 약간 나은 구현으로 해결할 수 있는 서브태스크입니다. $ 1 \le M \le 1\,000\,000\,000 $이기 때문에 매번 $ M $번씩 이동하는 것은 당연히 안되고, $ M $을 현재 원에 남아있는 사람의 수로 나눈 나머지만큼 이동해주면 됩니다. 참고로 $ N \le 2\,000 $이기 때문에 vector::erase 등을 사용해도 문제가 되지 않습니다.

 

시간복잡도는 $ O(ND) $ (단, $ D = \sum\limits_{i=1}^{N}D_{i} $)입니다.

 

서브태스크 3: 추가적인 제한 조건이 없음. (83점)

이번에는 주기를 구한다는 느낌으로 접근해주면 됩니다. 시작점 $ s $에서 $ M $명씩 건너뛰면서 사탕을 주는 것을 반복하다 보면, 언젠가는, 조금 더 정확하게는 $ N $번 안에는 $ s $로 돌아오게 됩니다. 그렇다면 이제 방금 거쳤던 점들 중 사탕의 수가 $ D_{i} $가 되는 점이 나오기 전까지는 계속해서 같은 순서로 같은 점들을 반복해서 거치게 될 것입니다. 이를 이용해 $ O(N) $에 한 사람을 제거하는 방법은 다음과 같습니다.

 

1. $ s $에서 $ M $명씩 건너뛰면서 사탕 수에 $ 1 $을 더해주고, 사탕 수가 $ D_{i} $가 되기까지 남은 사탕의 수의 최솟값 $ m $과 그 위치 $ idx $를 기록한다.

2. 1. 도중 $ s $에 다시 돌아오지 않았는데 사탕 수가 $ D_{i} $가 된 사람이 있다면 그 사람을 제거하고, $ s $를 현재 위치에 맞춰 재설정한 뒤 1.로 돌아간다.

3. $ s $로 돌아왔다면 1. 을 멈추고, $ idx $까지 같은 방법으로 이동한다. 이때 $ idx $에 위치한 사람의 사탕 수가 $ D_{i} $가 되기까지 남은 사탕의 수의 최솟값도 $ m $에서 $ m-1 $로 $ 1 $ 감소한다.

4. $ idx $로부터 정확히 한 주기를 돌면서 사탕 수에 $ m-1 $를 더하고, $ idx $는 제거한다.

 

$ idx $는 가장 먼저 제거될 사람을 뜻합니다. 4. 는 $ idx $를 제거하기 위해 $ m-1 $주기를 도는 과정을 한 번에 처리한 것입니다. 전 과정을 걸쳐 이동 횟수는 $ 3N $번을 넘지 않습니다. 따라서 무리 없이 $ N-1 $명을 제거할 수 있습니다.

 

시간복잡도는 $ O(N^{2}) $입니다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
#define fi first
#define se second
#define pb push_back

const ll MAX = 2001;
ll N, M, mx = 0, idx;
vector<int> v, d;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    v.resize(N);
    d.resize(N);
    for(int i = 0; i < N; i++) v[i] = i+1;
    for(int i = 0; i < N; i++){
        cin >> d[i];
        if(mx <= d[i]){
            mx = d[i];
            idx = i;
        }
    }
    if(M == 1){
        cout << idx+1 << '\n';
        return 0;
    }
    int idx = ((M % N) + N - 1) % N;
    while(v.size() > 1){
        // printf("%d\n\n", idx);
        // for(int i : v) printf("%d ", i);
        // printf("\n");
        // for(int i : d) printf("%d ", i);
        // printf("\n\n");
        bool flag = false;
        int start = idx, mnidx = idx;
        ll mnd = d[idx];
        // end at first
        if(mnd == 1){
            v.erase(v.begin() + idx);
            d.erase(d.begin() + idx);
            --N;
            --idx;
            idx = (idx + (M % N) + N) % N;
            continue;
        }
        idx = (idx + (M % N) + N) % N;
        while(idx != start){
            // end before one loop
            if(d[idx] == 1){
                flag = true;
                mnidx = idx;
                break;
            }
            if(mnd > d[idx]){
                mnd = d[idx];
                mnidx = idx;
            }
            idx = (idx + (M % N) + N) % N;
        }
        // end before one loop
        if(flag){
            idx = start;
            while(idx != mnidx){
                --d[idx];
                idx = (idx + (M % N) + N) % N;
            }
            v.erase(v.begin() + idx);
            d.erase(d.begin() + idx);
            --N;
            --idx;
            idx = (idx + (M % N) + N) % N;
            continue;
        }
        // go to minimal index, decrease each d along the way
        while(idx != mnidx){
            --d[idx];
            idx = (idx + (M % N) + N) % N;
        }
        // decrease d of minimal index
        --d[idx];
        idx = (idx + (M % N) + N) % N;
        while(idx != mnidx){
            d[idx] -= mnd-1;
            idx = (idx + (M % N) + N) % N;
        }
        // erase minimal index
        v.erase(v.begin() + idx);
        d.erase(d.begin() + idx);
        --N;
        --idx;
        idx = (idx + (M % N) + N) % N;

        // if(M % n == 0){
        //     v.erase(v.begin() + idx);
        //     d.erase(d.begin() + idx);
        //     --idx;
        //     continue;
        // }

        // --d[idx];
        // if(d[idx] == 0){
        //     v.erase(v.begin() + idx);
        //     d.erase(d.begin() + idx);
        //     --idx;
        // }
    }
    cout << v[0] << '\n';
    return 0;
}

---

16 파스칼 삼각형

$ 1 \le K \le 10^{18} $인 $ K $가 주어질 때, 무한한 크기의 파스칼 삼각형에 포함된 정삼각형 중 안의 수의 합이 정확히 $ K $인 경우가 몇 가지인지를 구하는 문제입니다.

63점 만을 받았습니다. (서브태스크 1, 2, 3)

 

서브태스크 1: $ K \le 8\,000 $ (17점), 서브태스크 2: $ K \le 1\,000\,000 $ (17점)

$ {K \choose 1} = {{K-3} \choose 0} + {{K-2} \choose 0} + {{K-2} \choose 1} = K $이므로 $ K=1,\,2,\,3 $을 제외하면 안의 수의 합이 $ K $인 삼각형은 적어도 $ 2\times 2 = 4$개 존재합니다. 이제 그 외의 경우에는 $ {n \choose r}\;(r \ge 2) $꼴의 수가 삼각형에 반드시 들어가 있을 것입니다. 그런데 $ n \choose 2 $만 하더라도 대략 $ n^2 $에 비례하는 값이기 때문에 검사해야 할 파스칼 삼각형의 최대 깊이가 크게 줄어든다는 것을 알 수 있습니다.

$ {n \choose 2} \gt max(K) $를 만족하는 $ n $을 적당히 구한 뒤 $ n $ 이하의 깊이의 파스칼 삼각형을 DP를 이용해 구할 수 있습니다. 물론 오버플로우가 매우 쉽게 나기 때문에 특정 콤비네이션 값이 $ max(K) $보다 커진다면 더해도 오버플로우가 나지 않으면서 $ max(K) $보다는 큰 상수로 고정시켜 뒀습니다. 여기서 $ n $은 $ \sqrt{2K} $와 비슷한 값을 가집니다.

정삼각형의 최대 변 길이는 $ 2^{m}-1 \le K $를 만족하는 최대의 $ m $이고, 서브태스크 2의 경우 $ m=19 $로 꽤 작습니다. 이제 구해둔 파스칼 삼각형으로 가능한 모든 정삼각형을 시도해보면 됩니다.

딱히 필요하지 않은 것 같지만 정삼각형 내 수의 합을 DP를 이용해 한 변의 길이가 $ d $인 경우 $ O(d) $에 구할 수 있게 했습니다.

 

시간복잡도는 계산이 쉽지 않지만 $ O(K\log^{2} K) $정도인 것으로 보입니다.

 

서브태스크 3과는 구현 방식이 조금 달라서 코드도 따로 첨부합니다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
#define fi first
#define se second
#define pb push_back

const ll MAX = 1e6+1, SQRT_MAX = 1416;
ll T, K, c[SQRT_MAX][SQRT_MAX], tr[SQRT_MAX][SQRT_MAX][21];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    for(int i = 0; i < SQRT_MAX; i++){
        for(int j = 0; j <= i; j++){
            if(j == 0 || j == i) c[i][j] = 1;
            else{
                c[i][j] = c[i-1][j-1] + c[i-1][j];
                if(c[i][j] >= MAX) c[i][j] = MAX;
            }
            tr[i][j][0] = c[i][j];
        }
    }
    for(int d = 1; d < 21; d++){
        for(int i = d; i < SQRT_MAX; i++){
            for(int j = d; j <= i; j++){
                tr[i][j][d] = tr[i-1][j-1][d-1];
                for(int k = j-d; k <= j; k++){
                    tr[i][j][d] += c[i][k];
                }
                if(tr[i][j][d] >= MAX) tr[i][j][d] = MAX;
            }
        }
    }
    cin >> T;
    while(T--){
        cin >> K;
        if(K == 1){
            cout << "-1\n";
            continue;
        }
        if(K == 2){
            cout << "1\n";
            continue;
        }
        if(K == 3){
            cout << "3\n";
            continue;
        }
        ll ans = 4;
        int n = SQRT_MAX-1;
        while(n*(n-1)/2 > K) --n;
        for(; n >= 0; n--){
            for(int r = 2; r <= n; r++){
                if(tr[n][r][0] > K) break;
                for(int d = 0; d <= min(r, 20); d++){
                    if(tr[n][r][d] > K) break;
                    if(tr[n][r][d] == K){
                        if((r-d)*2 == n-d) ans += 1;
                        else if((r-d)*2 < n-d) ans += 2;
                        // printf("%d %d %d\n", n, r, d);
                    }
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

 

서브태스크 3: $ K \le 10^{12} $ (25점)

서브태스크 2에 비해서 $ K $가 제곱으로 불어났습니다. 시간도 문제긴 하지만 더 큰 문제는 아무래도 메모리였습니다.  메모리가 발목을 잡으면 보통 그 풀이는 틀린 풀이인데, 다행히도 어떻게 추하게 뚫는 데 성공했습니다.

앞선 경우에는 $ {0 \choose 0} $부터 $ {n \choose n} $까지 약 $ n^{2} / 2 $개의 수를 전부 저장했지만, 이번에는 $ n $조차도 $ 1\,000\,000 $을 훌쩍 넘어가서 파스칼 삼각형을 구성하는 모든 수를 저장할 수는 없습니다. 또, 앞에서는 가능한 정삼각형 내 수의 합을 전부 저장해뒀는데, 이것도 나름 $ n^{2} $에 비례하는 숫자라서 그렇게 할 수 없습니다.

그래서 이번에는 꼭 필요한 수만을 저장하고, 정삼각형 내 수의 합을 저장할 필요가 없도록 합을 한 번 구한 뒤 $ T $개의 $ K $ 전부에 대해 일치하는지를 한 번에 확인하는 방법을 사용했습니다.

 

굉장히 공 들여서 더러운 커팅을 한지라 시간복잡도는 정말 잘 모르겠고 proof by AC 했습니다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
#define fi first
#define se second
#define pb push_back

const ll T_MAX = 4001, MAX = 1e12+1, SQRT_MAX = 1414216;
const ll RT_MAX[39] = {1414216, 18174, 2216, 658, 303, 180, 124, 95, 78, 67, 60, 55, 52, 49, 48, 46, 45, 45, 45, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44};
ll T, ans[T_MAX];
pl K[T_MAX];
vector<ll> c[SQRT_MAX], tr[SQRT_MAX];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> T;
    for(ll i = 0; i < T; i++){
        cin >> K[i].fi;
        K[i].se = i;
    }
    sort(K, K+T);

    for(int i = 0; i < RT_MAX[0]; i++){
        // printf("\n%lld: ", i);
        for(int j = 0; j <= i; j++){
            if(j == 0 || j == i){
                c[i].pb(1);
            }
            else{
                if(j >= c[i-1].size()) break;
                ll tmp = c[i-1][j-1] + c[i-1][j];
                if(tmp > K[T-1].fi) break;
                c[i].pb(tmp);
                if(j == 1 || j == i-1) continue;
                int idx = lower_bound(K, K+T, make_pair(tmp, 0ll)) - K;
                while(idx < T && K[idx].fi == tmp){
                    if(2*j == i) ans[K[idx].se] += 1;
                    else if(2*j < i) ans[K[idx].se] += 2;
                    ++idx;
                }
            }
            // printf("%lld ", c[i][j]);
            // tr[i][j][0] = c[i][j];
        }
    }




    for(int d = 2; d < 41; d++){
        // if(d == 2){
        //     for(int i = 2; i < RT_MAX[d-2]; i++){
        //         // bool end = false;
        //         for(int j = 1; j*2 <= i; j++){
        //             if(c[i+2].size() < j+2){
        //                 break;
        //             }
        //             ll tmp = c[i][j] + c[i+2][j+1];
        //             int idx = lower_bound(K, K+T, make_pair(tmp, 0ll)) - K;
        //             if(idx == T){
        //                 break;
        //             }
        //             while(idx < T && K[idx].fi == tmp){
        //                 if(2*j == i) ans[K[idx].se] += 1;
        //                 else if(2*j < i) ans[K[idx].se] += 2;
        //                 ++idx;
        //             }
        //         }
        //     }
        //     continue;
        // }
        for(int i = 0; i < RT_MAX[d-2]-d; i++){
            if(d == 2 && (i == 0 || i == 1)) continue;
            for(int j = 0; j*2 <= i; j++){
                if(d == 2 && j == 0) continue;
                if(c[i+d].size() < j+d) break;
                ll tmp = c[i][j];
                for(int k = 1; k < d; k++){
                    tmp += c[i+d][j+k];
                }
                int idx = lower_bound(K, K+T, make_pair(tmp, 0ll)) - K;
                if(idx == T) break;
                while(idx < T && K[idx].fi == tmp){
                    if(2*j == i) ans[K[idx].se] += 1;
                    else if(2*j < i) ans[K[idx].se] += 2;
                    ++idx;
                }
            }
        }
    }




    for(int i = 0; i < T; i++){
        if(K[i].fi == 1) ans[K[i].se] = -5;
        else if(K[i].fi == 2) ans[K[i].se] = -3;
        else if(K[i].fi == 3) ans[K[i].se] = -1;
        else if(K[i].fi == 4) ans[K[i].se] = 0;
    }
    for(int i = 0; i < T; i++){
        cout << ans[i]+4 << '\n';
    }
    return 0;
}

---

17 낙하 데미지

2차원 평면에 x축에 평행인 여러 선분들이 공중에 떠 있을 때, 각 선분에서 바닥까지 떨어지면서 받는 낙하 데미지의 최솟값을 구하는 문제입니다.

14점 만을 받았습니다. (서브태스크 1)

 

서브태스크 1: $ N \le 2\,000 $ (14점)

이 문제에서 유일하게 푼 서브태스크입니다. $ dp[i] $를 $ i $번째 선분에서 바닥까지 떨어질 때 받는 낙하 데미지의 최솟값으로 정의하면, 다음과 같은 식이 성립합니다.

$$ dp[i]=min_{j \in adj[i]}\left(dp[j]+(y[i]-y[j])^{2}+c[j]\right) $$

$ y[i] $, $ c[i] $, $ adj[i] $는 각각 $ i $번째 선분의 높이, 고유 낙하 데미지, 그리고 $ i $번째 선분에서 떨어져 착지할 수 있는 선분들의 집합을 뜻합니다. $ adj[i] $의 최대 크기가 $ N $이기 때문에 시간복잡도를 딱히 $ O(N^{2}) $보다 줄일 방법은 없어 보입니다.

모든 $ i $에 대한 $ adj[i] $를 따로 구하지는 않고, 재귀적인 DP로 구현했습니다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
#define fi first
#define se second
#define pb push_back

struct Line{
    ll y, s, e, c;
    bool operator <(const Line &a){
        return y == a.y ? e < a.e : y < a.y;
    }
};

const ll MAX = 2e5+1, INF = 1e9+1, INFINF = 4e18;
ll N, damage[MAX];
Line L[MAX];

inline bool inter(Line &a, Line &b)
{
    return ((a.s <= b.e && b.e <= a.e) || (a.s <= b.s && b.s <= a.e) || (b.s <= a.s && a.e <= b.e));
}

ll f(int curr)
{
    ll &ret = damage[curr];
    if(ret != -1) return ret;
    ret = INFINF;
    for(int j = 0; j <= N; j++){
        if(L[curr].y > L[j].y && inter(L[curr], L[j])){
            ret = min(ret, f(j) + (L[curr].y - L[j].y)*(L[curr].y - L[j].y) + L[j].c);
        }
        // printf("%lld ", damage[i]);
    }
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    fill(damage, damage+N+1, -1); damage[0] = 0;
    L[0] = {0, 0, INF, 0};
    for(int i = 1; i <= N; i++) cin >> L[i].y >> L[i].s >> L[i].e >> L[i].c;
    // sort(L, L+N+1);
    for(int i = 1; i <= N; i++){
        // printf("\n");
        cout << f(i) << '\n';
    }
    return 0;
}