랜덤 마라톤 11주차 (최종)

11주간의 마라톤 끝에 드디어 450km를 찍었다. 특별한 동기가 없는 한 더 이상 마라톤을 지속하지는 않을 것 같다.

앞으로 마라톤을 풀지 않으니 점점 난이도가 떨어질 텐데, 난이도 변경폭을 최소로 바꿔 놓으려고 한다.

 

A. Расписание

기초적인 그리디 문제로, 가장 작은 수부터 차례대로 $1$부터 수를 붙여 주면 된다.

 

나는 $O(n^2)$에 풀었고, 그 이하의 시간 복잡도로도 풀 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int arr[102];
int ans[102];

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
    for(int t=1; t<=n; t++){
        int i = min_element(arr+1, arr+n+1) - arr;
        ans[i] = t;
        arr[i] = 1e9;
    }
    for(int i=1; i<=n; i++) printf("%d ", ans[i]);
}

B. Crazy tea party

원탁에 있는 $n$개의 수들을 최소 횟수의 (인접한 수) 교환으로 역순으로 배치하는 문제이다. 이때 역순이 여러 가지일 수 있다는 사실이 중요하다. (정확히는, $1$번 사람의 위치가 고정되어 있지 않기 때문에 총 $n$가지 경우의 수가 있다.)

 

사람을 반씩 나눈 뒤 각 부분에서 $a(a-1)/2$번의 swap으로 뒤집는 것이 최적일 것 같다고 추정했고, 실제로 제출해 보니 맞았다.

 

여담으로 BOJ 2117과 같은 문제라고 한다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t;
ll n;

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%lld", &n);
        if(n <= 2) printf("0\n");
        else{
            ll a = n/2, b = (n+1)/2;
            printf("%lld\n", a*(a-1)/2 + b*(b-1)/2);
        }
    }
}

C. Kingdom Roadmap

두 노드 $x$와 $y$를 이었다고 해 보자. 이때 어떤 효과가 생겼는지를 생각해 보면, 트리 상에서 $x$에서 $y$로 가는 간선 중 아무거나 하나가 지워져도 $x-y$ 간선이 대체할 수 있게 된 것이다. 따라서, 이 문제는 최소한의 개수의 경로를 선택해 트리 간선 전체를 덮는 문제가 된다.

 

이 문제는 굉장히 유명한 문제였던 걸로 기억하는데, 정석적인 풀이는 잊어버렸고, 내가 생각한 풀이는 다음과 같다. 일단 당연히 리프 노드끼리 잇는 것이 최적이다. 그리고 리프 노드의 수를 $s$라고 할 때 답은 최소 $\lceil \frac{s}{2} \rceil$ 이상임을 알 수 있다. (왜냐하면, 리프 노드와 인접한 모든 간선을 덮어야 하기 때문이다. $n=2$인 최소 케이스를 제외하고, 이 간선들은 모두 서로 다르다. $n=2$라고 해도 위 식이 성립하므로 문제는 없지만, 편의상 $n=2$인 경우는 사전에 처리해 준다고 생각하자.)

 

이제 정확히 $\lceil \frac{s}{2} \rceil$ 개의 새로운 간선을 추가하는 최적해가 있음을 보일 것이다. 먼저 트리의 센트로이드 $c$를 찾을 것이다. 그러나 여기서 센트로이드 $c$의 정의를 조금 바꿔, $c$에서 어떤 서브트리를 보더라도 리프 노드의 수가 $\frac{s}{2}$를 넘지 않는 정점이라고 하자. 이러한 정점이 항상 존재함을 증명하는 것은 기존 센트로이드의 존재성을 증명하는 것과 같은 방식으로 증명할 수 있다. 센트로이드를 계산할 때, 리프 노드를 센트로이드로 고르지 않도록 주의하자.

 

이제 해당 센트로이드 $c$를 기준으로, $t$개의 서브트리가 존재해, 각 서브트리에 있는 노드의 개수를 $s_1, s_2, \cdots, s_t$라고 하자. 편의상 $s_1 \le s_2 \le \cdots \le s_t$라고 하고, 만약 $s$가 홀수라면 가장 작은 $s_i$에 $1$을 더해 저 오름차순 조건을 만족하도록 설정하자. 실제 구현에서는, 리프의 수가 가장 적은 서브트리 쪽의 리프 목록에서 한 개를 복제한다고 생각하면 된다. 이것은 전체 리프 노드의 개수를 짝수로 맞춰 간선으로 모두 연결할 수 있게 하기 위함이다. 이제 여기서 서로 다른 집합에서 두 개씩 골라 짝짓는 것은 쉽고(아이디어는 쉽지만 효율적인 구현 아이디어를 내는 것은 조금 까다롭다), 문제를 $O(n)$ 정도의 시간 복잡도에 해결할 수 있다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
vector<int> link[100002];
bool isLeaf[100002];
int leafcnt[100002];

void sts(int x, int p=-1){
    leafcnt[x] = isLeaf[x];
    for(int y: link[x]){
        if(y==p) continue;
        sts(y, x);
        leafcnt[x] += leafcnt[y];
    }
}

int findCentroid(int x, int p, int lim){
    for(int y: link[x]){
        if(y==p) continue;
        if(leafcnt[y] >= lim) return findCentroid(y, x, lim);
    }
    return x;
}

int k;
vector<int> leafs[100002];
vector<int> sizes[100002];

void getLeafs(int x, int p, vector<int> &v){
    if(isLeaf[x]) v.push_back(x);
    else for(int y: link[x]){
        if(y==p) continue;
        getLeafs(y, x, v);
    }
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(y);
        link[y].push_back(x);
    }

    if(n==2){
        printf("1\n1 2\n");
        return 0;
    }

    for(int i=1; i<=n; i++) isLeaf[i] = ((int)link[i].size() == 1);
    int S = count(isLeaf+1, isLeaf+n+1, true);
    int st = 1;
    while(isLeaf[st]) st++;
    sts(st);
    int c = findCentroid(st, -1, S/2+1);

    k = (int)link[c].size();
    for(int i=0; i<(int)link[c].size(); i++){
        getLeafs(link[c][i], c, leafs[i]);
    }

    if(S % 2){
        int tmp = 0;
        for(int i=1; i<k; i++) if(leafs[i].size() < leafs[tmp].size()) tmp = i;
        S++;
        leafs[tmp].push_back(leafs[tmp].back());
    }

    for(int i=0; i<k; i++){
        sizes[leafs[i].size()].push_back(i);
    }

    int A = S, B = S;
    vector<pair<int, int> > ans;
    while(S){
        while(sizes[A].empty()) A--;
        while(sizes[B].empty() || (A==B && (int)sizes[A].size() == 1)) B--;

        S-=2;
        int x = sizes[A].back(); sizes[A].pop_back();
        int y = sizes[B].back(); sizes[B].pop_back();
        if(A) sizes[A-1].push_back(x);
        if(B) sizes[B-1].push_back(y);
        ans.push_back(make_pair(leafs[x].back(), leafs[y].back()));
        leafs[x].pop_back();
        leafs[y].pop_back();
    }

    printf("%d\n", (int)ans.size());
    for(pair<int, int> &p: ans) printf("%d %d\n", p.first, p.second);
}

D. Windmill Pivot

저 컨셉을 이용하는 IMO 문제를 유튜브에서 봤던 기억이 있다.

 

일단 이 문제에서 가장 중요한 사실은 직선 왼쪽에 있는 점의 수와 직선 오른쪽에 있는 점의 수가 항상 일정하게 유지된다는 것이다. 따라서 이 두 값 $L$과 $R$ ($L+R=n-1$)을 고정하면 각 점이 promote되는 횟수 역시 결정된다. 이때 점 $x$가 promote되는 횟수는 360도의 구간 중에서 점 $x$가 왼쪽에서부터 $L+1$번째 점이 되는 시선각의 구간의 개수라는 사실을 알 수 있다.

 

여기서 풀이의 아이디어를 얻을 수 있다. Bulldozer Trick처럼 각도 스위핑을 하면서, 두 점의 위치가 바뀔 때를 주목하자. 이때, 어떤 점 $x$가 왼쪽에서 $p$번째 위치가 된 횟수를 세어 $cnt[x][p]$로 저장한다. 두 점의 위치가 바뀔 때만 $cnt$를 1씩 올려 준다는 사실을 주의하자. 이제 모든 연산이 끝나면, $cnt[x][p]$는 $L$의 값을 $p-1$로 정했을 때 $x$가 promote되는 횟수를 의미하게 된다. 따라서 $cnt$의 최댓값이 답이 된다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct vector2{
    ll x, y;
    int idx;
    vector2(){}
    vector2(ll x, ll y): x(x), y(y){}

    vector2 operator-(const vector2 &r)const{
        return vector2(x-r.x, y-r.y);
    }

    bool operator<(const vector2 &r)const{
        if(x != r.x) return x<r.x;
        return y>r.y;
    }

    ll cross(const vector2 &r)const{
        return x*r.y-y*r.x;
    }
};

ll ccw(vector2 a, vector2 b){
    return a.cross(b);
}

ll ccw(vector2 a, vector2 b, vector2 c){
    return (b-a).cross(c-a);
}

const pair<ll, ll> ORG (0, 0);
struct Edge{
    vector2 dir;
    int a, b;
    Edge(){}
    Edge(vector2 dir, int a, int b): dir(dir), a(a), b(b){}

    bool operator<(const Edge &r)const{
        if((make_pair(dir.x, -dir.y) > ORG) != (make_pair(r.dir.x, -r.dir.y) > ORG)){
            return make_pair(dir.x, -dir.y) > ORG;
        }
        return ccw(dir, vector2(0, 0), r.dir) < 0;
    }
};

int n;
vector2 arr[2002];
int loc[2002], cnt[2002][2002];
int ans;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld", &arr[i].x, &arr[i].y);
        arr[i].idx = i;
    }

    vector<Edge> vec;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i==j) continue;
            vec.push_back(Edge(arr[j] - arr[i], i, j));
        }
    }
    sort(vec.begin(), vec.end());

    sort(arr+1, arr+n+1);
    for(int i=1; i<=n; i++) loc[arr[i].idx] = i;

    for(Edge &p: vec){
        int a = p.a, b = p.b;
        assert(loc[a] + 1 == loc[b]);
        swap(loc[a], loc[b]);
        cnt[a][loc[a]]++;
        cnt[b][loc[b]]++;
    }

    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) ans = max(ans, cnt[i][j]);
    printf("%d", ans);
}

E. 나이트의 이동

일단 mod를 1 000 007 (합성수) 로 설정해 둔 출제자의 악의에 경의를 표한다.

 

사실 뭐 크게 중요한 건 아니고, 그냥 두 가지 mod로 풀고 중국인의 나머지 정리를 쓰면 되어서 크게 어려운 부분은 아니다. 하나의 mod에 대해서 풀어 보자. $n$이 주어지면 $k$에 따라 특정 선형 점화식 꼴로 나올 텐데, 여기서 Berlekamp-Massey를 쓰면 답을 구할 수 있다.

 

berlekamp massey 코드는 구사과님의 블로그에서 가져왔다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int xx[]={-2, -2, -1, 1, 2, 2, 1, -1}, yy[]={-1, 1, 2, 2, 1, -1, -2, -2};
const ll MOD1 = 29;
const ll MOD2 = 34483;
const ll MOD = 1'000'007;

int t;
int n; ll k;

void init();
void solve(int, ll);

int main(){
    init();
    scanf("%d", &t);
    while(t--){
        scanf("%d %lld", &n, &k);
        solve(n, k);
    }
}

ll mpow(ll x, ll y, ll mod){
    if(!y) return 1;
    if(y&1) return mpow(x, y-1, mod) * x % mod;
    ll tmp = mpow(x, y/2, mod);
    return tmp * tmp % mod;
}
ll modInv(ll x, ll mod){
    return mpow(x%mod, mod-2, mod);
}

ll mod;
using lint = long long;
lint ipow(lint x, lint p){
    lint ret = 1, piv = x;
    while(p){
        if(p & 1) ret = ret * piv % mod;
        piv = piv * piv % mod;
        p >>= 1;
    }
    return ret;
}
vector<int> berlekamp_massey(vector<int> x){
    vector<int> ls, cur;
    int lf, ld;
    for(int i=0; i<x.size(); i++){
        lint t = 0;
        for(int j=0; j<cur.size(); j++){
            t = (t + 1ll * x[i-j-1] * cur[j]) % mod;
        }
        if((t - x[i]) % mod == 0) continue;
        if(cur.empty()){
            cur.resize(i+1);
            lf = i;
            ld = (t - x[i]) % mod;
            continue;
        }
        lint k = -(x[i] - t) * ipow(ld, mod - 2) % mod;
        vector<int> c(i-lf-1);
        c.push_back(k);
        for(auto &j : ls) c.push_back(-j * k % mod);
        if(c.size() < cur.size()) c.resize(cur.size());
        for(int j=0; j<cur.size(); j++){
            c[j] = (c[j] + cur[j]) % mod;
        }
        if(i-lf+(int)ls.size()>=(int)cur.size()){
            tie(ls, lf, ld) = make_tuple(cur, i, (t - x[i]) % mod);
        }
        cur = c;
    }
    for(auto &i : cur) i = (i % mod + mod) % mod;
    return cur;
}
int get_nth(vector<int> rec, vector<int> dp, lint n){
    int m = rec.size();
    vector<int> s(m), t(m);
    s[0] = 1;
    if(m != 1) t[1] = 1;
    else t[0] = rec[0];
    auto mul = [&rec](vector<int> v, vector<int> w){
        int m = v.size();
        vector<int> t(2 * m);
        for(int j=0; j<m; j++){
            for(int k=0; k<m; k++){
                t[j+k] += 1ll * v[j] * w[k] % mod;
                if(t[j+k] >= mod) t[j+k] -= mod;
            }
        }
        for(int j=2*m-1; j>=m; j--){
            for(int k=1; k<=m; k++){
                t[j-k] += 1ll * t[j] * rec[k-1] % mod;
                if(t[j-k] >= mod) t[j-k] -= mod;
            }
        }
        t.resize(m);
        return t;
    };
    while(n){
        if(n & 1) s = mul(s, t);
        t = mul(t, t);
        n >>= 1;
    }
    lint ret = 0;
    for(int i=0; i<m; i++) ret += 1ll * s[i] * dp[i] % mod;
    return ret % mod;
}
int guess_nth_term(vector<int> x, lint n){
    if(n < x.size()) return x[n];
    vector<int> v = berlekamp_massey(x);
    if(v.empty()) return 0;
    return get_nth(v, x, n);
}

vector<int> coef1[14], coef2[14];
vector<int> poly1[14], poly2[14];

ll DP[302][24][24];
ll poly[302];

void init(){
    mod = MOD1;
    for(int n=4; n<=24; n+=2){
        memset(DP, 0, sizeof(DP));
        memset(poly, 0, sizeof(poly));

        const int TURNS = 300;
        DP[0][0][0] = poly[0] = 1;
        for(int turn = 1; turn <= TURNS; turn++){
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    for(int d=0; d<8; d++){
                        int ti = i + xx[d], tj = j + yy[d];
                        if(ti<0 || ti>=n || tj<0 || tj>=n) continue;
                        DP[turn][i][j] += DP[turn-1][ti][tj];
                    }
                    DP[turn][i][j] %= mod;
                }
            }
            poly[turn] = poly[turn-1] + DP[turn][0][0] + DP[turn][0][n-1] + DP[turn][n-1][0] + DP[turn][n-1][n-1];
            poly[turn] %= mod;
        }

        vector<int> values (poly, poly + TURNS + 1);
        vector<int> minpol = berlekamp_massey(values);

        poly1[n/2] = values;
        coef1[n/2] = minpol;
    }

    mod = MOD2;
    for(int n=2; n<=24; n+=2){
        memset(DP, 0, sizeof(DP));
        memset(poly, 0, sizeof(poly));

        const int TURNS = 300;
        DP[0][0][0] = poly[0] = 1;
        for(int turn = 1; turn <= TURNS; turn++){
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    for(int d=0; d<8; d++){
                        int ti = i + xx[d], tj = j + yy[d];
                        if(ti<0 || ti>=n || tj<0 || tj>=n) continue;
                        DP[turn][i][j] += DP[turn-1][ti][tj];
                    }
                    DP[turn][i][j] %= mod;
                }
            }
            poly[turn] = poly[turn-1] + DP[turn][0][0] + DP[turn][0][n-1] + DP[turn][n-1][0] + DP[turn][n-1][n-1];
            poly[turn] %= mod;
        }

        vector<int> values (poly, poly + TURNS + 1);
        vector<int> minpol = berlekamp_massey(values);

        poly2[n/2] = values;
        coef2[n/2] = minpol;
    }
}

void solve(int n, ll k){
    mod = MOD1;
    ll val1 = get_nth(coef1[n], poly1[n], k);
    mod = MOD2;
    ll val2 = get_nth(coef2[n], poly2[n], k);

    ll v1 = MOD1 * modInv(MOD1, MOD2) * val2;
    ll v2 = MOD2 * modInv(MOD2, MOD1) * val1;
    ll ret = (v1 + v2) % MOD;
    printf("%lld\n", ret);
}

F. Expected LCP

어떤 문자열 $n$개의 pairwise maximum LCP가 $k$일 확률을 $p(k)$라고 하고, $k$ 이하일 확률을 $s(k) = p(0) + p(1) + \cdots + p(k)$라고 하자. 이때 pairwise maximum LCP가 $k$ 이하라는 것은 앞 $k+1$자리가 모두 같은 문자열이 없다는 것을 의미한다. 즉, 이러할 확률은 $2^{k+1} = C$라는 수로 치환했을 때, 앞 $k+1$자리를 정하는 경우의 수 $C^n$ 중 앞 $k+1$자리가 모두 다른 경우의 수 ${}_C P_{n}$이므로 $\frac{C!}{(C-n)! \times C^n}$이다.

 

$r(k)$를 답이 $k$ 이상일 확률로 정의하자. 이때 $r(k) = 1 - s(k-1) = 1 - \frac{(2^k)!}{(2^k-n)! \times 2^{kn}}$이다. 우리가 구하고자 하는 답은 $\sum_{k \ge 0} k p(k)$인데, 이것은 항의 순서를 달리하면 $\sum_{k \ge 1} r(k)$로도 쓸 수 있다. 여기서 식을 정리해 보자.

$$
\begin{align}
r(k) &= 1 - \frac{(2^k)!}{(2^k-n)! \times 2^{kn}} \\
&= 1 - (2^k) (2^k-1) \cdots (2^k-n+1) \left( \frac{1}{2^{k}} \right) ^n \\
&= 1-\frac{2^k}{2^k} \frac{2^k-1}{2^k} \cdots \frac{2^k-n+1}{2^k} \\
&= 1 - \left( 1 - \frac{0}{2^k} \right) \left( 1 - \frac{1}{2^k} \right) \cdots \left( 1-\frac{n-1}{2^k} \right) \\
\end{align}
$$

위와 같은 형태로 쓴 뒤, 이항계수를 이용해 전개하자. 다음과 같은 다항식을 생각한다.

$$
p_k(x) = 1 - \left(1 - \frac{0}{2^k} x \right) \left(1 - \frac{1}{2^k} x \right) \cdots \left(1 - \frac{n-1}{2^k} x \right)
$$

이때 상수항은 소거되고, 1차항부터 $n$차항까지가 남는다. 여기서 $i$차항의 계수를 계산하고자 한다. $0$부터 $n-1$까지 $n$개의 수 중 임의의 $i$개를 선택해 곱한 것의 합을 $V_i$라고 하자. 이때 $i$차항의 계수는 $-(-1)^i \frac{V_i}{2^{ik}}$가 된다.

 

중요한 점은 저 $v_i$는 $k$에 무관한 상수라는 것이다. $n$이 주어지면 저 값들을 어떻게든 계산할 수 있다고 생각해 보자. 여기서 편의를 위해 $p_k$를 $V_i$를 이용해 써 보면,

$$
p_k(x) = -\sum_{i=1}^{n} (-1)^i \frac{V_i}{2^{ik}} x^i
$$

이고 여기서 $x = 1$인 경우의 값이 $r(k)$가 된다. 우리가 구하고자 하는 것은 $\sum_{k \ge 1} r(k)$이므로, 다음과 같이 쓸 수 있다.

$$
\begin{align}
\sum_{k\ge 1} r(k) &= \sum_{k = 1}^\infty \left( - \sum_{i=1}^\infty (-1)^i \frac{V_i}{2^{ik}} \right) \\
&= - \sum_{k=1}^\infty \sum_{i=1}^n (-1)^i \frac{V_i}{2^{ik}}
\end{align}
$$

답이 수렴한다는 것을 알고 있으므로, 두 $\sum$의 위치를 바꿔 보자. (이것이 수학적으로 얼마나 엄밀한지는 잘 모르겠다.)

$$
\begin{align}
\sum_{k \ge 1} r(k) &= - \sum_{i=1}^n \sum_{k=1}^\infty (-1)^i \frac{V_i}{2^{ik}} \\
&= -\sum_{i=1}^n (-1)^i V_i \left( \sum_{k=1}^\infty \frac{1}{2^{ik}} \right)\\
&= -\sum_{i=1}^n (-1)^i V_i \frac{1}{2^i-1}
\end{align}
$$

이제 남은 것은 $2^i$와 $V_i$를 모두 $\bmod 10^9+7$로 계산해 답을 찾는 것이다. $2^i$야 그냥 하면 되고, $V_i$는 DP를 통해 계산하면 된다. 시간 복잡도는 $O(n^2)$이다.

 

#include <bits/stdc++.h>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;

typedef modint1000000007 ll;

ll DP[2][10002];
ll V[10002], p2[10002];

ll ans;

int main(){
    int n;
    scanf("%d", &n);

    p2[0] = 1;
    for(int i=1; i<=n; i++) p2[i] = p2[i-1] * 2;

    DP[0][0] = 1;
    for(int i=1; i<=n; i++){
        int d = i%2;
        DP[d][0] = 1;
        for(int j=1; j<=i; j++){
            DP[d][j] = DP[!d][j] + DP[!d][j-1] * (i-1);
        }
//        for(int j=1; j<=i; j++) printf("%d %d: %u\n", i, j, DP[d][j].val());
    }

    for(int i=0; i<=n; i++) V[i] = DP[n&1][i];

    for(int i=1; i<=n; i++){
        ll sgn = i%2 ? 1 : -1;
        ll val = sgn * V[i] / (p2[i] - 1);
        ans += val;
    }
    cout << ans.val();
}

 

이 문제를 풀고 마라톤 450km 뱃지를 얻었다. 11주간의 마라톤 여정은 이렇게 종료되었다.

 

 

11주간 많은 문제들을 풀었다. 그 중에서는 분명 좋은 문제들도 있었고 더러운 문제들도 있었다. 어찌됐건 앞으로 나갈 대회에는 어떤 문제든지 나올 수 있고, 다양한 문제들에 대비되어 있어야 한다고 생각한다. 그런 면에서 랜덤 디펜스는 이런 동기을 가진 사람들에게 좋은 도구로 사용될 수 있다고 생각한다.