랜덤 마라톤 8주차

현황은 아래와 같다.

• 리롤 기록: 1회(G), 2회(G)

A. 6174

문제에 나온 것을 그대로 구현하면 된다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t;
int n;

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        int ans = 0;
        while(n != 6174){
            string s = to_string(n);
            sort(s.begin(), s.end());
            n = -atoi(s.c_str());
            reverse(s.begin(), s.end());
            n += atoi(s.c_str());
            ans++;
        }
        printf("%d\n", ans);
    }
}

B. The Game of Efil

브루트포스로 모든 경우를 시도해 보면 된다. 경우의 수가 $2^{nm}$가직이고 한 가지 경우를 시험하는 데 $8nm$번 정도의 시행이 필요하므로 $O(nm 2^{nm})$에 문제를 맞을 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int xx[]={0, 1, 1, 1, 0, -1, -1, -1}, yy[]={-1, -1, 0, 1, 1, 1, 0, -1};

int n, m, k;
int arr[16][16];
int conf[16][16];
int ans;

void backtrack(int x, int y){
    if(x==n){
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                int cnt = 0;
                for(int d=0; d<8; d++){
                    int ti = (i+n+xx[d])%n, tj = (j+m+yy[d])%m;
                    if(conf[ti][tj]) cnt++;
                }
                bool b = (conf[i][j] && 2 <= cnt && cnt <= 3) || (!conf[i][j] && cnt == 3);
                if(b != arr[i][j]) return;
            }
        }
        ans++;
        return;
    }
    if(y==m) {backtrack(x+1, 0); return;}
    conf[x][y] = 0;
    backtrack(x, y+1);
    conf[x][y] = 1;
    backtrack(x, y+1);
}

int main(){
    for(int tc=1; ; tc++){
        scanf("%d %d", &n, &m);
        if(!n) break;
        scanf("%d", &k);
        memset(arr, 0, sizeof(arr));
        for(int i=1; i<=k; i++){
            int x, y;
            scanf("%d %d", &x, &y);
            arr[x][y] = 1;
        }

        ans = 0;
        backtrack(0, 0);
        printf("Case %d: ", tc);
        if(!ans) puts("Garden of Eden.");
        else printf("%d possible ancestors.\n", ans);
    }
}

C. Rising Tides

답에 대한 parametric search를 하고, bfs를 돌리면 된다. 시간 복잡도는 $O(nm \log X)$이다. 답이 시작하는 칸의 높이 이하여야 함에 주의하자.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 1e18;
const int xx[]={1, 0, -1, 0}, yy[]={0, 1, 0, -1};

int t;
int n, m;
ll arr[502][502];
ll dist[502][502];
int qx[250002], qy[250002], f, b;

inline void push(ll x, ll y){
    qx[b] = x, qy[b] = y, b++;
}

bool able(ll LIM){
    f=b=0;
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) dist[i][j] = INF;
    dist[1][1] = 0;
    push(1, 1);

    while(f<b){
        int x = qx[f], y = qy[f]; f++;
        if(x==n && y==m) return true;
        for(int d=0; d<4; d++){
            int tx = x+xx[d], ty = y+yy[d];
            if(tx < 1 || tx > n || ty < 1 || ty > m) continue;
            if(dist[tx][ty] != INF || arr[tx][ty] - (dist[x][y] + 1) < LIM) continue;
            dist[tx][ty] = dist[x][y] + 1;
            push(tx, ty);
        }
    }
    return false;
}

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &n, &m);
        for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) scanf("%lld", &arr[i][j]);

        ll L = 1, R = arr[1][1], ANS = 0;
        while(L<=R){
            ll M = (L+R)/2;
            if(able(M)) ANS = M, L = M+1;
            else R = M-1;
        }
        if(!ANS) puts("impossible");
        else printf("%lld\n", ANS);
    }
}

D. 행운쿠키 제작소

냅색 비슷한 DP를 돌려 주면 된다. $DP[x][a]$는 $1$번부터 $x$번 쿠키까지 어느 오븐에서 구울지를 선택했을 때, 1번 오븐에서 구워지는 시간의 총합이 $a$라면 2번 오븐에서 구워지는 시간의 최솟값이 얼마인지를 저장해 놓는다. 이 DP는 $O(100 n^2)$, 토글링을 하면 메모리 $O(100n)$에 전이할 수 있다. 이제 $max(DP[x][a], a)$의 최솟값이 답이 된다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 1e9;

int t;
int n;
int a[1002], b[1002], w[1002];
int DP[2][100002];

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        for(int i=1; i<=n; i++) scanf("%d %d", &a[i], &b[i]);

        for(int i=0; i<=n*100; i++) DP[0][i] = DP[1][i] = INF;
        DP[0][0] = 0;
        for(int i=1; i<=n; i++){
            int d = i%2;
            for(int j=0; j<=n*100; j++) DP[d][j] = min(DP[!d][j] + b[i], j >= a[i] ? DP[!d][j-a[i]] : INF);
        }

        int ans = INF;
        for(int i=0; i<=n*100; i++) ans = min(ans, max(i, DP[n&1][i]));
        printf("%d\n", ans);
    }
}

E. 숫자 카드 제거 게임

이 상태로 생각하면 조금 힘들다. 결국 중요한 건 인접한 수의 개수인데, 초기에는 $N$개의 수가 인접하다. 여기서 수 하나를 제거하면 인접한 수의 덩어리가 하나 또는 둘로 쪼개지게 된다. 따라서 한 덩어리의 길이를 해당 덩어리에 있는 수로 정의하면, 길이의 집합으로 게임의 상태를 정의할 수 있다. 게임판이 둘로 나눠지는 것은 sprague-grundy를 쓰면 계산할 수 있어 보인다.

 

이제 sprague-grundy를 실제로 돌려 보면 초반부를 제외하고 $34$ 주기의 사이클이 생기는 것을 확인할 수 있다. 이제 이 부분을 하드코딩해서 정답을 받을 수 있다.

 

이 문제는 코드가 정답과도 같으므로 코드를 첨부하지 않는다.

F. 바벨탑의 저주

어떤 정점 $x$가 저주 노드일 조건은 다음과 같다.

• 정점 $x$가 리프 노드이거나,
• 정점 $x$의 자식 노드 $c_1, \cdots, c_k$에 대해 ($k \ge 1$) 자식 $c_i$의 서브트리를 뒤집은 트리가 자식 $c_{k+1-i}$의 트리와 같다.

해싱을 통해 두 트리가 같은지 확인하는 방법을 알아보자. 두 트리가 같은지의 여부는 다음과 같이 나누어 생각하는 것이 편리하다.

• 두 트리의 구조가 같은가?
• 구조가 같다면, 각 노드에 쓰인 수가 같은가?

먼저 구조부터 생각해 보자. 모든 트리의 구조는 괄호 문자열로 나타낼 수 있다. 원래대로라면 tree isomorphism까지 생각해야 하지만, 이 경우 자식들의 순서가 정해져 있으므로 논의가 더 쉬워진다. 다음과 같은 구조를 따른다.

• 리프 노드는 ()으로 표현한다.
• 어떤 노드 $x$의 자식이 차례대로 $c_1, \cdots, c_k$이고, 이들의 서브트리의 representation이 각각 $f(c_1), \cdots, f(c_k)$라면, $x$의 representation은 $f(c_1) + \cdots + f(c_k)$를 괄호로 둘러싼 문자열로 표기한다.
  • 예를 들어, $k = 2$, $f(c_1)$이 (()), $f(c_2)$가 (()(()))라면, $f(x)$는 ((())(()(())))이 된다.

괄호 문자열은 이진 수열로도 볼 수 있으므로, 해당 문자열을 해싱해 저장하면 된다. 나는 (를 $1$, )를 $2$로 계산해 3진수로 인코딩했다.

 

수를 인코딩하는 것은 더 쉽게 가능하다. 괄호 문자열까지 가지 않아도 되고, 그냥 보는 순서대로 차례로 인코딩하면 된다. 이제 이 값들을 전부 비교해 주면 문제를 해결할 수 있다.

 

최초에 child 배열을 정렬해 주는 것을 잊지 말도록 하자.

#include <bits/stdc++.h>

using namespace std;

typedef __int128 ll;
//const ll MOD = 1'000'000'009, MOD2 = 1'300'000'003;
const ll MOD = 1000000000000000003, MOD2 = 1300000000000000027;
const ll MULT = 500'029, MULT2 = 500'041;

int n;
ll p3[1000002], pmult[1000002], pmult2[1000002];
ll arr[500002];
int par[500002], sz[500002];
vector<int> child[500002];
vector<int> ans;

ll str1[500002], str2[500002]; /// 앞에서부터, 뒤에서부터 구조 해싱. (: 1, ): 2
ll val1[500002], val2[500002];
ll valr1[500002], valr2[500002];

void dfs(int x){
    sz[x] = 1;
    for(int y: child[x]){
        dfs(y);
        sz[x] += sz[y];
    }

    /// str1, str2
    str1[x] = (p3[sz[x]*2-1] + 2) % MOD;
    int pos = sz[x]*2-1;
    for(int i=0; i<(int)child[x].size(); i++){
        int y = child[x][i];
        pos -= sz[y] * 2;
        str1[x] = (str1[x] + str1[y] * p3[pos]) % MOD;
    }

    str2[x] = (p3[sz[x]*2-1] + 2) % MOD;
    pos = sz[x]*2-1;
    for(int i=(int)child[x].size()-1; i>=0; i--){
        int y = child[x][i];
        pos -= sz[y] * 2;
        str2[x] = (str2[x] + str2[y] * p3[pos]) % MOD;
    }

    /// val1, val2
    val1[x] = pmult[sz[x]-1] * arr[x] % MOD;
    pos = sz[x]-1;
    for(int i=0; i<(int)child[x].size(); i++){
        int y = child[x][i];
        pos -= sz[y];
        val1[x] = (val1[x] + val1[y] * pmult[pos]) % MOD;
    }

    val2[x] = pmult[sz[x]-1] * arr[x] % MOD;
    pos = sz[x]-1;
    for(int i=(int)child[x].size()-1; i>=0; i--){
        int y = child[x][i];
        pos -= sz[y];
        val2[x] = (val2[x] + val2[y] * pmult[pos]) % MOD;
    }

    valr1[x] = pmult2[sz[x]-1] * arr[x] % MOD2;
    pos = sz[x]-1;
    for(int i=0; i<(int)child[x].size(); i++){
        int y = child[x][i];
        pos -= sz[y];
        valr1[x] = (valr1[x] + valr1[y] * pmult2[pos]) % MOD2;
    }

    valr2[x] = pmult2[sz[x]-1] * arr[x] % MOD2;
    pos = sz[x]-1;
    for(int i=(int)child[x].size()-1; i>=0; i--){
        int y = child[x][i];
        pos -= sz[y];
        valr2[x] = (valr2[x] + valr2[y] * pmult2[pos]) % MOD2;
    }

    /// 답 갱신
    if(str1[x] == str2[x] && val1[x] == val2[x] && valr1[x] == valr2[x]) ans.push_back(x);
}

int main(){
    p3[0] = pmult[0] = pmult2[0] = 1;
    for(int i=1; i<=1'000'000; i++){
        p3[i] = p3[i-1] * 3 % MOD;
        pmult[i] = pmult[i-1] * MULT % MOD;
        pmult2[i] = pmult2[i-1] * MULT2 % MOD2;
    }

    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        int x;
        scanf("%d", &x);
        arr[i] = x;
    }
    vector<ll> renumber (arr+1, arr+n+1);
    sort(renumber.begin(), renumber.end());
    renumber.erase(unique(renumber.begin(), renumber.end()), renumber.end());
    for(int i=1; i<=n; i++){
        arr[i] = lower_bound(renumber.begin(), renumber.end(), arr[i]) - renumber.begin() + 1;
    }
    for(int i=1; i<n; i++){
        int p, x;
        scanf("%d %d", &p, &x);
        par[x] = p, child[p].push_back(x);
    }
    for(int i=1; i<=n; i++) sort(child[i].begin(), child[i].end());

    dfs(1);

    sort(ans.begin(), ans.end());
    printf("%d\n", (int)ans.size());
    for(int x: ans) printf("%d ", x);
}

G. 초콜릿 비긴즈

조금 생각해 봤는데 구현이 복잡할 것 같아서 리롤했다.

G. 이상한 판 뒤집기 게임

리롤했는데 티어가 오른 경우는 이게 처음이었다. 꽤 고민해 봤는데 잘 모르겠어서 다시 리롤했다.

G. 원형 게임

Lazy Propagation Segment Tree를 이용하는 문제이다. 구현이 꽤나 복잡하다.

 

세그먼트 트리의 각 노드에 diff, lval, rval을 저장한다. 이들은 각각 구간 내의 최대 인접한 수 차이, 가장 왼쪽 수, 가장 오른쪽 수이다. 이렇게 저장해 두면 구간 내에서 인접한 수의 최대 차이를 계속 구할 수 있다.

 

그러나 업데이트가 들어올 수 있기 때문에 정보를 추가로 더 저장해야 한다. 위 diff, lval, rval을 총 네 개씩 저장할 것이다. 어떤 상태 $d$ ($0 \le d \le 3$)을 다음과 같이 정의하자.

• $d=0$: 모든 참가자가 참여하지 않는다.
• $d=1$: 현재 상태.
• $d=2$: 현재 참가자와 참가하지 않는 사람이 서로 뒤바뀐다.
• $d = 3$: 모든 사람이 참가한다.

이 네 경우에 대해 계속 diff, lval, rval 값을 관리하고 있으면 업데이트 쿼리가 주어졌을 때 이 값들을 모두 변경해줄 수 있다. 쿼리가 들어올 때는 $\text{diff}[1]$과 $abs(\text{lval}[1] - \text{rval}[1])$ 중 더 큰 값을 반환하면 된다. 시간 복잡도는 $O(Q \log N)$이다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int graph[4][4] = {
    0, 0, 3, 3,
    0, 1, 2, 3,
    0, 2, 1, 3,
    0, 3, 0, 3
};
inline int add(int a, int b){
    return (b==0 || b==3) ? b : (b==1 ? a : (a^3));
}

struct segTree{
    struct Node{
        int diff[4], lval[4], rval[4]; /// [00], [01], [10], [11] -> [0 들어오면], [현재], [거꾸로], [1 들어오면]
        Node(){}
        Node(int v){
            lval[0] = lval[2] = rval[0] = rval[2] = 0;
            diff[0] = diff[1] = diff[2] = diff[3] = 0;
            lval[1] = lval[3] = rval[1] = rval[3] = v;
        }
        Node operator+(const Node &r)const{
            Node ret;
            for(int d=0; d<4; d++){
                ret.diff[d] = max({diff[d], r.diff[d], (rval[d] && r.lval[d] ? abs(r.lval[d] - rval[d]) : 0)});
                ret.lval[d] = lval[d] ? lval[d] : r.lval[d];
                ret.rval[d] = r.rval[d] ? r.rval[d] : rval[d];
            }
            return ret;
        }

        void reflect(int l){
            if(!l){
                diff[1] = diff[0], lval[1] = lval[0], rval[1] = rval[0];
                diff[2] = diff[3], lval[2] = lval[3], rval[2] = rval[3];
            }
            else if(l==3){
                diff[1] = diff[3], lval[1] = lval[3], rval[1] = rval[3];
                diff[2] = diff[0], lval[2] = lval[0], rval[2] = rval[0];
            }
            else{ /// l=2
                swap(diff[1], diff[2]);
                swap(lval[1], lval[2]);
                swap(rval[1], rval[2]);
            }
        }
    } tree[1<<19];
    int lazy[1<<19];

    void init(int i, int l, int r, int* arr){
        lazy[i] = 1;
        if(l==r){
            tree[i] = Node(arr[l]);
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, arr);
        init(i*2+1, m+1, r, arr);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    void propagate(int i, int l, int r){
        if(lazy[i] == 1) return;
        tree[i].reflect(lazy[i]);
        if(l!=r){
            lazy[i*2] = graph[lazy[i*2]][lazy[i]];
            lazy[i*2+1] = graph[lazy[i*2+1]][lazy[i]];
        }
        lazy[i] = 1;
    }

    void update(int i, int l, int r, int s, int e, int v){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] = v;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e, v), update(i*2+1, m+1, r, s, e, v);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    int query(int i, int l, int r){
        propagate(i, l, r);
        return max(abs(tree[i].lval[1]-tree[i].rval[1]), tree[i].diff[1]);
    }
} tree;

int n, q;
int arr[200002];

int main(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
    tree.init(1, 1, n, arr);
    printf("%d\n", tree.query(1, 1, n));
    while(q--){
        int qx, ql, qr;
        scanf("%d %d %d", &qx, &ql, &qr);
        qx = vector<int> {-1, 0, 3, 2} [qx];
        if(ql <= qr) tree.update(1, 1, n, ql, qr, qx);
        else{
            tree.update(1, 1, n, 1, qr, qx);
            tree.update(1, 1, n, ql, n, qx);
        }
        printf("%d\n", tree.query(1, 1, n));
    }
}

H. 소수 피하기

옛날 아레나에 참가했을 때 못 푼 문제였고 다시 풀어봐야겠다고 생각만 하고 있었는데 못 풀고 있었다.

 

지금 리롤하면 영원히 업솔빙을 안 할 것 같아서

결국 에디토리얼을 보고 풀었다.

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

using namespace std;
using namespace atcoder;

typedef long long ll;
const int MX = 2'000'000;
const ll INF = 1e18;

int n, E, O;
bool isPrime[2000002];
int arr[205], even[205], odd[205];

bool isEven[205];

int main(){
    fill(isPrime+2, isPrime+MX+1, true);
    for(int i=2; i*i<=MX; i++){
        if(!isPrime[i]) continue;
        for(int j=i*i; j<=MX; j+=i) isPrime[j] = 0;
    }

    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i]);
        if(arr[i] % 2) odd[i] = arr[i], even[i] = arr[i] + 1;
        else even[i] = arr[i], odd[i] = arr[i] + 1;
    }
    E = n+1, O = n+2;

    mf_graph<ll> graph(n+3);
    for(int i=1; i<=n; i++){
        if(arr[i] % 2) graph.add_edge(i, O, 1);
        else graph.add_edge(E, i, 1);
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i==j) continue;
            if(isPrime[even[i] + odd[j]]) graph.add_edge(i, j, INF);
        }
    }
    if(count(arr+1, arr+n+1, 1) >= 2){
        for(int i=1; i<=n; i++){
            if(arr[i] == 1) graph.add_edge(E, i, INF);
        }
    }

    int flow = graph.flow(E, O);
    vector<bool> vec = graph.min_cut(E);
//    for(bool x: vec) printf("%d ", x);
//    puts("");
    for(int i=1; i<=n; i++){
        isEven[i] = vec[i];
    }

    vector<int> ans;
    for(int i=1; i<=n; i++) if(isEven[i] != (arr[i] % 2 == 0)) ans.push_back(i);

    printf("%d\n", (int)ans.size());
    for(int x: ans) printf("%d ", x);
}