랜덤 마라톤 6주차

이번 주는 처음으로 다이아 문제가 나왔다. 일주일에 한 티어씩 올라가는 느낌이다. 이번 주에 일정이 많아서 많은 시간을 투자하지 못했는데, 중간에 스페셜 저지 오류도 나오는 등 다사다난한 마라톤이었다.

 

• 리롤 기록: 1회 (H)

A. Undercut

구현 문제이다. 문제에 나온 대로 짜면 된다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int A[22], B[22];

int main(){
    while(true){
        scanf("%d", &n);
        if(!n) break;
        for(int i=1; i<=n; i++) scanf("%d", &A[i]);
        for(int i=1; i<=n; i++) scanf("%d", &B[i]);

        int a = 0, b = 0;
        for(int i=1; i<=n; i++){
            if(A[i] == B[i]) continue;
            else if(A[i] < B[i]){
                if(A[i] + 1 == B[i]) a += (A[i] == 1 ? 6 : A[i] + B[i]);
                else b += B[i];
            }
            else{
                if(B[i] + 1 == A[i]) b += (B[i] == 1 ? 6 : A[i] + B[i]);
                else a += A[i];
            }
        }

        printf("A has %d points. B has %d points.\n\n", a, b);
    }
}

B. Expansion Order

현재 접근할 수 있는 역의 목록을 배열로 관리하자. $chk[x]$는 현재 역 $x$에 접근할 수 있다면 $1$이고, 아니면 $0$이다. 이 배열은 초기에 $chk[1]=1$이고, 나머지는 모두 $0$이다.

이후 $m$개의 선로를 보며, 아직 시행하지 않은 계획 중 접근 가능한 역이 있는 계획을 선택한다. 이러한 계획이 여러 개라면 가장 앞에 있는 것을 그리디하게 고르면 된다. 만약 이 방식을 반복하여 $m$개의 계획을 모두 고를 수 없다면 불가능을 선언하면 된다.

시간 복잡도는 테스트 케이스당 $O(m^2n)$이다.

입력에서 한 줄을 통째로 받아야 하는 부분이 매우 악질적이라고 생각한다. 그래서 Python으로 코딩을 했다.

t = int(input())
for tc in range(1, t+1):
    n, m = map(int, input().split())
    arr = [None for i in range(m+1)]
    for i in range(1, m+1):
        arr[i] = list(map(int, input().split()))
    ans = []

    chk = [False for i in range(n+1)]
    chk[1] = 1
    for turn in range(m):
        pnt = 0
        for i in range(1, m+1):
            if arr[i] == None:
                continue
            good = False
            for x in arr[i]:
                if chk[x]:
                    good = True
                    break
            if good:
                pnt = i
                break
        if not pnt:
            break
        ans.append(pnt)
        for x in arr[pnt]:
            chk[x] = True
        arr[pnt] = None

    print('Data Set ' + str(tc) + ':')
    if len(ans) != m:
        print('Impossible\n')
    else:
        for x in ans:
            print(x)
        print()

C. Link-Cut Tree

간선의 길이가 $2^i$ 꼴로 지정되어 있으므로, 가장 길이가 짧은 사이클은 이진법으로 생각했을 때 가장 값이 작은 사이클, 즉 포함된 간선의 번호 중 최댓값이 가장 작은 사이클일 것이다.

$1$번 간선부터 차례로 보며, 최초로 사이클이 생기는 시점을 감지하자. 그러면 이때 추가한 간선은 단 하나의 사이클에 포함되어 있을 텐데, 이 사이클이 답이 된다. 이것을 빠르게 하려면 Union Find를 사용하면 된다. Union Find를 통해 간선의 양끝점이 속한 집합을 계속 합쳐 주다가, 이미 같은 집합에 속한 두 개의 정점을 잇는 간선이 나오면 그 때 멈추고 사이클을 찾아 반환하면 된다.

시간 복잡도는 테스트 케이스당 $O(n + m \log n)$이다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct UnionFind{
    int par[100002];

    void init(int n){
        for(int i=1; i<=n; i++) par[i] = i;
    }

    int find(int x){
        if(x == par[x]) return x;
        return par[x] = find(par[x]);
    }

    void merge(int x, int y){
        x = find(x), y = find(y);
        par[x] = y;
    }
} dsu;

int t, n, m;
vector<pair<int, int> > link[100002];

bool dfs(int x, int p, int g, vector<int> &v){
    if(x==g) return true;
    for(auto [y, e]: link[x]){
        if(y==p) continue;
        if(dfs(y, x, g, v)){
            v.push_back(e);
            return true;
        }
    }
    return false;
}

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &n, &m);
        dsu.init(n);
        for(int i=1; i<=n; i++) link[i].clear();

        vector<int> answer;
        for(int i=1; i<=m; i++){
            int x, y;
            scanf("%d %d", &x, &y);
            if(!answer.empty()) continue;
            if(dsu.find(x) == dsu.find(y)){
                dfs(x, -1, y, answer);
                answer.push_back(i);
                sort(answer.begin(), answer.end());
                continue;
            }
            link[x].push_back(make_pair(y, i));
            link[y].push_back(make_pair(x, i));
            dsu.merge(x, y);
        }

        if(answer.empty()) puts("-1");
        else{
            for(int x: answer) printf("%d ", x);
            puts("");
        }
    }
}

D. Kotrljanje

P4 문제 치고 정말 오래 고민했던 것 같다. 내 풀이는 P4

생각보다 많은 방법들이 통하지 않는다. 다음과 같은 방법을 생각해 보자.

• $Cn+D$ 꼴의 수에서 $n$을 $xM + y$ 꼴로 나타내 보자. $M$을 $b$의 거듭제곱꼴로 적당히 잡은 뒤, $b$진법에서 $Cn+D$를 썼을 때 $n$의 $y$ 부분과 $xM$ 부분이 서로 충돌하지 않도록 할 것이다.
  • 예를 들어 $b = 10$, $C = 113$, $D = 5$라고 생각해 보자. $M = 1000$으로 잡고, $y \le 8$로 제한하면 $Cy+D$는 아무리 커 봤자 세 자리 수이고, $CxM$은 $1000$의 배수이므로 두 부분이 서로 충돌하지 않는다.
• 이제 $x$와 $y$의 순서쌍을 적당히 골라 각 자리의 합이 같도록 시도해볼 것이다.

여기서 가장 큰 문제는 적당한 $M$ 값을 찾는 것이다. $M = b^t$ 꼴로 쓸 수 있을 텐데, 이때 $y$의 최댓값 $y_{max}$에 대해 $Cy_{max}+D < M$ 조건이 성립해야 한다. 또한 $xM + y \le 10^{15}$라는 조건이 추가적으로 성립해야 한다. 이를 고려해 입력을 받고 적당한 $M$ 값을 찾을 수 있도록 해 준다.

이후로는 각 $x$와 $y$의 범위에 대해 $Cy + D$와 $CxM$의 자릿수 합을 찾아 주고 배열에 저장해 둔다. 이후 이 두 배열에서 FFT를 해서 가장 자릿수 합이 많은 조합을 찾고, 해당 조합에서 답을 출력해 주면 된다.

여담으로 처음 백준에 제출했을 때 계속 틀렸다. 내 코드에 답을 확인하는 부분까지 assert로 넣어봤는데 문제가 없었고, 이후 oj.uz에서 AC를 받았다. BOJ 쪽 체커에 문제가 있었고, 이후 재채점해서 맞았다.

#include <bits/stdc++.h>
#include "atcoder/convolution"

using namespace std;
using namespace atcoder;

typedef __int128 ll;
const ll INF = 1'000'000'000'000'000;
const ll MAXT = 250'000;
const ll VSIZE = 30'000;

ll C, D, b, sz; /// cx+d
ll M = 1;

ll xmax, ymax;
ll xt[VSIZE], yt[VSIZE];
vector<ll> xex[VSIZE], yex[VSIZE];

inline int digitsum(ll x){
    int ret = 0;
    while(x) ret += x%b, x/=b;
    return ret;
}

int main(){
    {
        long long _a,_b,_c,_d;
        cin >> _a >> _b >> _c >> _d;
        C=_a,D=_b,b=_c,sz=_d;
    }

    ll MMax = 0, Mt = 0;
    M = 1;
    while(C+D>=M) M*=b;
    while(true){
        ll ymax = min((M - 1 - D) / C, MAXT);
        ll xmax = min((INF - ymax) / M, MAXT);
        if(xmax <= 0) break;
        ll cnt = xmax * ymax;
        if(MMax < cnt) MMax = cnt, Mt = M;

        if(M > INF / b) break;
        M *= b;
    }
    assert(MMax);

    M = Mt;
    ymax = min((M - 1 - D) / C, MAXT);
    xmax = min((INF - ymax) / M, MAXT);

    for(ll y=1; y<=ymax; y++){
        ll v = digitsum(C * y + D);
        yt[v]++;
        yex[v].push_back(y);
    }

    for(ll x=1; x<=xmax; x++){
        ll v = digitsum(C * x * M);
        xt[v]++;
        xex[v].push_back(x);
    }

    vector<long long> xv (xt, xt+VSIZE);
    vector<long long> yv (yt, yt+VSIZE);
    vector<long long> result = convolution_ll(xv, yv);

    ll loc = max_element(result.begin(), result.end()) - result.begin();
    if((ll)result[loc] < sz) return 1;

    vector<ll> ansVec;
    for(ll i=0; i<loc; i++){
        ll j = loc - i;
        for(ll x: xex[i]){
            for(ll y: yex[j]){
                ansVec.push_back(x*M+y);
                if(--sz == 0) break;
            }
            if(!sz) break;
        }
        if(!sz) break;
    }

    sort(ansVec.begin(), ansVec.end());
    for(ll v: ansVec) cout << (long long)(v) << ' ';

    /// answer check
    assert(sz == 0);
    for(ll v: ansVec) assert(1 <= v && v <= INF);
    for(ll v: ansVec) assert(digitsum(C*v+D) == loc);
    for(int i=1; i<(int)ansVec.size(); i++) assert(ansVec[i-1] < ansVec[i]);
}

E. 버그잡는 꿍

정해의 의도는 KMP를 이용하라는 것 같지만, 해싱을 이용해 풀었다. 입력의 크기가 꽤 크기 때문에 나머지 연산을 자주 하면 TLE가 나기 쉽다. mod를 $2^n$ 꼴로 설정하면 나머지 연산을 bitwise and 연산으로 교체할 수 있어 속도를 빠르게 만들 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = (1LL<<50) - 1;
const ll MULT = 131;

int t, n, l;
char s[2000005];
ll weight[2000005];
char bug[2000005];
ll val[2000005];

int main(){
    while(scanf("%d %s\n", &t, bug+1) != EOF){
        l = strlen(bug+1);
        ll key = 0;
        for(int i=1; i<=l; i++) key = (key * MULT + bug[i]) & MOD;
        ll pw = 1;
        for(int i=1; i<=l; i++) pw = (pw * MULT) & MOD;

        while(t--){
            fgets(s+1, 10'000'000, stdin);
            n = strlen(s+1);

            int pnt = 0;
            for(int i=1; i<=n; i++){
                s[++pnt] = s[i];
                val[pnt] = (val[pnt-1] * MULT + s[i]) & MOD;
                if(pnt >= l && key == ((val[pnt] - ((__int128(val[pnt-l]) * pw) & MOD) + MOD+1) & MOD)){
                    pnt -= l;
                }
            }
            for(int i=1; i<=pnt; i++) printf("%c", s[i]);
        }
    }
}

F. Divide and Conquer

만수르가 구간 $[l, r]$의 번호에 해당하는 금광을 보호할 수 있을 조건을 써 보면 다음과 같다.

• $x_r - x_l \le \sum_{l \le i \le r} d_i$

식의 형태를 맞춰주기 위해, $s_i = d_1 + \cdots + d_i$라고 하자. 그러면 아래와 같이 식을 바꿔쓸 수 있다.

• $x_r - x_l \le s_r - s_{l-1}$

여기서 이항을 하면, $l$만으로 이루어진 항과 $r$만으로 이루어진 항을 만들 수 있다.

• $s_{l-1} - x_l \le s_r - x_r$

즉, $l$을 고정하고 나면, $l \le r$인 $r$ 중 $s_r - x_r$이 $s_{l-1} - x_l$ 이상인 최대의 $r$을 구하기만 하면 된다.

$l$을 $N$부터 시작해 하나씩 내려 보자. 이때 적당한 자료구조 하나를 만들어, $l \le r$ 중 $s_r - x_r$이 특정 $v$ 이상인 것들 중 가장 큰 $r$을 구할 수 있어야 한다. 이를 위해 $(s_r - x_r, r)$ 쌍을 vector 형태로 관리한다.

새로운 $l$을 만났을 때, $(s_l - x_l, l)$ 쌍을 벡터에 추가할지의 여부를 결정해야 한다. 그런데 만약 이 $s_l - x_l$ 값 이상의 $s_r - x_r$이 이미 존재한다면, $r$ 쪽을 고르는 것이 무조건 이득이므로 굳이 추가할 필요가 없다. 그렇지 않다면 vector의 맨 끝에 추가한다. 이후, $v = s_{l-1} - x_l$ 이상의 first값을 가진 pair가 있는지를 보면 되는데, 삽입 알고리즘의 특성상 first값이 항상 오름차순으로 정렬되어 있으므로 lower_bound를 해 준 뒤 직후에 있는 원소의 second 값을 $r$로 취해 주면 된다.

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

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
ll x[100002], g[100002], d[100002], s[100002], gs[100002];
vector<pair<ll, int> > vec;
ll ans;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld %lld", &x[i], &g[i], &d[i]);
        s[i] = s[i-1] + d[i];
        gs[i] = gs[i-1] + g[i];
    }

    for(int i=n; i>=1; i--){ /// 왼쪽 끝점
        ll v = s[i] - x[i];
        if(vec.empty() || vec.back().first < v) vec.push_back(make_pair(v, i));
        auto it = lower_bound(vec.begin(), vec.end(), make_pair(s[i-1] - x[i], -1));
        assert(it != vec.end());
        ans = max(ans, gs[it->second] - gs[i-1]);
    }
    printf("%lld", ans);
}

G. Winter Olympic Games

만약 아무 문자도 제거하지 않는다면 맨 왼쪽에 $1$을 넣는 것이 최선이다. 이제 제거하는 경우를 살펴보자.

제거하는 가장 왼쪽 문자를 $l$번 문자라고 하자. 여기서부터 어디까지 제거해야 가장 이득인지를 생각해 보자. 어떤 두 후보 $r_1$, $r_2$가 있다고 해 보자. 이때, 각각의 경우 최종 문자열은

• $s[1 \dots l], 1, s[r_1+1 \dots n]$
• $s[1, \dots, l]$, $1$, $s[r_2+1 \dots n]$

이 되므로 결국 $r_1+1$부터의 접미사와 $r_2+1$부터의 접미사 중 더 큰 것이 후보가 된다. 접미사 배열을 관리하면 $l$ 이후의 접미사들 중 가장 사전순으로 큰 것을 고를 수 있고, 각 $l$마다 최선의 $r$을 구할 수 있다.

이제 문제는 어떤 $l$을 선택하는가이다. 만약 문자열의 맨 첫 자리가 $0$이라면, 앞에 있는 $0$들을 모두 지우는 것이 최적일 테니 $l = 1$로 두어야 할 것이다. 만약 $l \ge 2$라면 이미 첫 자리가 $0$이므로 더 안 좋은 해가 된다.

만약 문자열의 맨 첫 자리가 $1$이라면, 이 자리를 제외하고 생각하면 된다. 결론적으로 맨 처음으로 나오는 $0$의 자리를 $l$로 두면 된다.

결과적으로 문제를 $O(n \log^2 n)$ 시간 복잡도에 풀 수 있다. 접미사 배열을 더 빨리 만들면 더 빨리 풀 수 있다.

H. 격자 속의 직선 경로

문제가 별로 풀고 싶지 않게 생겨서 리롤했다.

H. 1-Color Coloring

문제

• $N$개의 정령이 있고 $i$번 정령의 색은 $i$이다. 이들은 임의의 순서로 원형으로 배치되어 있다.
• 다음 명령을 내릴 수 있다.
  • Color: 어떤 정령 $x$가 자신 앞에 있는 정령의 색을 자신의 색으로 바꾼다.
  • GetColor: 현재 정령들 중 특정 색 $x$를 가진 정령이 있는지를 물어본다. 이후 모든 정령의 색이 초기화된다.
• $N \le 100$이며, Color 연산을 $7300$회, GetColor 연산을 $200$회 미만으로 사용해 모든 정령의 색을 $1$로 만들어야 한다.

풀이

위 쿼리를 어떤 방식으로 이용할지에 대해 생각해 보아야 한다. 어떤 수열 $[S_1, S_2, \cdots, S_k]$에 대해 차례로 Color 연산을 한 번씩 수행하고 GetColor 연산을 $x$에 대해 하게 될 경우, 그 결과는 다음과 같다. 편의상 바로 앞의 정령을 $nxt(x)$, 바로 뒤의 정령을 $prv(x)$ 같은 함수로 표기하자.

일단 $N-1$ 번의 쿼리로 $prv(1)$을 알아낼 수 있다. 이후 배열 $P$를 만들자. $P$는 길이 $N-1$의 배열로 $[1, N]$의 수 중 $prv(1)$을 제외한 모든 수가 있으며, $P[1] = 1$이고 나머지 수는 무작위로 배치된 수열이다. 이 수열의 앞 원소부터 차례대로 Color 연산을 하는 것을 72회 반복한다.

$prv(1)$이 배열에 없으므로 $1$이 제거되는 일이 없으며, 조금 생각해 보면 왜 위 알고리즘이 높은 확률로 동작하는지 알 수 있을 것이다.

#include "coloring.h"
#include <bits/stdc++.h>

using namespace std;

int n;
int back;

void ColoringSame(int N){
    n = N;
    for(int i=2; i<=n; i++){
        Color(i);
        if(!GetColor(1)){
            back = i;
            break;
        }
    }
    vector<int> vec;
    vec.push_back(1);
    for(int i=2; i<=n; i++) if(i != back) vec.push_back(i);
    random_shuffle(vec.begin()+1, vec.end());

    for(int d=0; d<72; d++){
        for(int v: vec) Color(v);
    }
}