Hello World!

2 분 소요

#1 도입

방학동안 약15번 가량의 Contest를 참가했는데 제대로 upsolving을 한적이 없다는 사실을 학교가는 길에 깨달았다. 소잃고 외양간을 고쳐보자

codeforces Round969 (Div. 2)

D. Iris and Game on the Tree

  1. 어떤 문자열 110101111000 이 있을때, 이전과 같은 숫자는 의미가 없기에 101010 으로 생각한다
  2. 101010에서 101과 같이 1에서0을갔다가 다시1로오면 상쇄되므로 101이나 010 1과 0으로 봐도 된다.
  3. 문자열을 치환하다보면 맨앞과 맨뒤가 다르면 합산 1or-1 , 맨앞맨뒤가 같으면 합산0 임을 알 수 있다.
  4. 즉 루트와 리프에 어떤값이 들어가는지가 score를 결정한다.

배운점

  1. 함수 인자로 벡터나 배열을 전달할 때에는 참조자를 붙이는 것을 까먹지 말자.

  2. 루트와 리프는 트리에서 자신을 제외한 1가지의 노드에게만 연결된다. 따라서

    if(adj[i].size()==1)

    과 같이 간단한 코드로 리프인지를 판단할 수 있다.

  3. 랭커들의 코드를 보고 게임 이론을 구현하는 스타일에 대해 공부해보았다

    while(root==2 || cnt[2]>0) {
            if(it==0) {//첫번째 플레이어
                if(root==2) {
                    if(cnt[0]==cnt[1] && skip%2==1) {
                        //player1 차례에 skip이 홀수개이고 리프의 0과1 개수같다면 상대가 선택할
                        //때까지 skip을 고르는게 이득이므로 skip을 선택한다
                        //짝수일때는 서로 의미가 없으므로 바로0으로 만들어도 상관이 없다.
                        skip=0;
                    }
                    else {
                        root = (cnt[0]>cnt[1] ? 1 : 0);
                    }
                }
                else {
                    //root와 반대되는 숫자를 리프에 넣어준다
                    cnt[2] -= 1;
                    cnt[root ^ 1]++;
                }
            }
            else {
                if(root ==2) {
                    root = (cnt[0]>cnt[1] ? 1:0);
                }
                else {
                    //player2는 root와 같은 숫자를 리프에 넣는다
                    cnt[2]--;
                    cnt[root]++;
                }
            }
            //다음순서로 바꾸어준다
            it ^=1;
        }
    • 삼항연산자로 코드를 간단히 하는 습관을 들이자
    • a^1 은 짝수면 1을 더하고 홀수면 1을뺀다 이를 이용해 0과1을 번갈아 이동할 수 있다.

E. Iris and the Tree

  1. 트리가 dfs order를 가지기 때문에, 연속한 노드 사이거리 합은 모든 간선을 오직 2번씩 더한 값이다. (내려갈때 올라갈때)

  2. $i$→ $p_i$ 가중치를 사용하는 경우는 $(i-1)$→ $i$ 과 $i$ 의 subtree 에서 가장 큰값에서 다음으로 이동하는 두가지 경우뿐이다.
  3. 노드 사이거리 합을 구하는 각 step에서 결정되지 않은 간선은 $w$를 지키는 선에서 마음대로 정할 수 있으니, 아무 간선도 주어지지 않은 상태에서 최대값은 $n*w$ 이다.
  4. (2)에 의해 가중치가 주어지면, $(i-1)$→ $i$ 의 값은 고정이 된다.
    그러나 $i+s_i−1$ → $i+s_i$ 의 경우 경로에 간선이 여러개 존재 할 수 있으므로, cnt배열을 관리하여 $cnt[i+s_i-1]==0$ 이 되는 경우에 고정이 되는 것으로 한다.


DFS구현 방식과 최댓값 계산식은 코드를 보며 이야기 해보자

int cur = 0;
vector<vector<int>> f(n); //f[i] : i→pi 간선을 사용하는 2가지 출발 노드 저장
vector<int> cnt(n); //cnt[i] : i→i+1 가는 길에 존재하는 간선 개수

void dfs(int v) {
    cur++;
    for(auto nxt : adj[v]) { //nxt는 v의 자식노드
        f[nxt].push_back(cur-1);
        cnt[cur-1]++;
        dfs(nxt);
        f[nxt].push_back(cur-1);
        cnt[cur-1]++;
    }
}

트리를 순회하면서, $i$→ $p_i$가중치가 영향을 미치는 출발지가 어디인지 알아내야 하고, 각 노드사이에 몇개의 간선이 있는지 알아내야 한다.

  • 리프가 아니라면 f[i]에 i-1을 넣고 i의 자식을 dfs에 넣고 호출한다.
  • 리프에 도달하면 $i+s_i-1$ 과 $i+s_i$ 의 LCA까지 cnt[i+s_i-1]을 증가시킨다.


ll sum = 0;
        int tot = n; 
        for(int i=1;i<n;i++) {
            ll x,y; cin>>x>>y; x--;
            for(auto k : f[x]) {
                cnt[k]--;
                if(cnt[k]==0) tot--;
            }
            sum +=y; 
            cout<<tot*w + sum *(2-tot)<<' ';
        }
  • y의 길이는 2가지 경로에서만 사용되고, 나머지 미확정 경로에서는 y만큼 전부 감소해야 한다.


배운점

  1. 전역 배열의 사이즈를 미지수로 놓으면 안된다. Error가 안떠서 찾기가 어려웠다.
  2. dfs 함수처럼 여러가지 배열을 이용할 때, 어떤식으로 구현해야 테케마다 리셋문제나 호출문제를 간단하게 처리 할 수 있을까?

카테고리:

업데이트:

댓글남기기

참고