13325 - 이진 트리

https://www.acmicpc.net/problem/13325

2016 ACM-ICPC 한국 인터넷 예선 A번

각 노드에서 리프 노드까지의 거리가 (왼쪽으로 가든지, 오른쪽으로 가든지) 같도록 조정하는 것이므로 재귀를 생각할 수 있다.

이를 해결할 작은 문제로 재귀의 중간 과정부터 생각했다.

왼쪽과 오른쪽의 길이가 달라져서 조정이 필요한 상황은 "왼쪽 != 오른쪽" 이다. 이를 조정하는 작업은 더 작은 쪽에 가중치를 증가시키는 것이다.

가중치는 보정을 위해 추가하는 것이므로, 맞추고자 하는 차이만큼 증가시키면 된다.

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

typedef long long lld;

int n;
int a[(1<<21)+1];

int leftPos(int pos){ return 2*pos+1; }
int rightPos(int pos){ return leftPos(pos)+1; }

int f(int pos){
    int l = leftPos(pos), r = rightPos(pos);
    // is leaf
    if(l > n || r > n) return a[pos];
    
    int lsum = f(l), rsum = f(r);
    if(lsum < rsum){
        a[l] += rsum - lsum;
    }
    else if(lsum > rsum){
        a[r] += lsum - rsum;
    }
    
    return a[pos] + max(lsum, rsum);
}

int main(){
    int k;
    scanf("%d", &k);
    n = (1<<(k+1))-1-1;
    for(int i=1; i<=n; ++i) scanf("%d", &a[i]);
    f(0);
    int ans = 0;
    for(int i=1; i<=n; ++i) ans += a[i];
    printf("%d", ans);
    return 0;
}

11581 - 구호물자

https://www.acmicpc.net/problem/11581

2015 인하대학교 프로그래밍 경시대회 G번

처음에는 BFS를 돌면서 다시 방문하는 정점이 있는 경우 NO CYCLE을 출력하고 끝내려했는데, 코딩 미스인건지 오답을 맞았다. (이거 BFS로는 안되는건가요? 누가 댓글로 답변 바람) (참고로 다들 DFS로 푼 것 같다..)

딱히 좋은 아이디어는 안 떠올라서 플로이드 와샬로 정점과 정점이 이동 가능한지 저장했다. 그리고 1번 정점에서 $i$번 정점까지 방문 가능한 것들 중에 $i$번 정점에서 $i$번 정점으로 다시 돌아올 수 있는 (싸이클이 생기는) 경우가 있다면 CYCLE을 출력하도록 했다.

입출력 몇 개를 예로 적어놔야겠다.

예제 #1

6
2 2 3
2 4 6
1 4
1 5
1 3

CYCLE

예제 #2

6
2 2 6
1 6
1 4
2 2 5
1 3

NO CYCLE

10971 - 외판원 순회 2

https://www.acmicpc.net/problem/10971

어떤 지점 s에서 출발해서 모든 정점을 거치고 다시 s로 돌아오는 경우를 모두 탐색했다. $O(N!)$
매 번 "모든 정점을 방문했는가?" 를 확인하면서 모두 방문했다면 현재가 s인가(출발점 == 종료점)를 판별해서 그렇다면 그때의 값이 최소가 되게 했다.

이동할 때마다 가중치를 더한다. 모든 정점을 방문했을 때 자신으로 돌아온게 아니라면 답이 아니도록 했다.

어떤 지점 s는 어디건 상관없다. 출발점과 도착점이 같은 지점을 찾는다면, 그 지점이 어디건 정답인 경우의 경로는 똑같이 나온다.

1208 - 부분집합의 합 2

1182 - 부분집합의 합 에서 시간 제한이 N=20 에서 N=40 으로 확장된 문제이다.

$2^{20}$ 은 약 100만이라 시간이 충분했지만, $2^{40}$ 은 1조에 가깝다.

문제를 아무리 봐도 좋은 생각이 안 나다가, 주변에서 몇가지 힌트를 받고 해결할 수 있었다.

N개의 정수로 이루어진 배열 a에서 모든 부분집합을 살피려면 위에 말한것과 같이 $2^{40}$ 이라 굉장히 힘들다. 하지만 반으로 나눠서 부분 집합을 살핀다면 이 문제를 해결할 수 있다.

배열 a를 반으로 나눈다. 즉, $ a_0, a_1, \dots a_n $ 을 $ a_0, a_1, \dots a_{n/2} $ 와 $ a_{n/2 +1}, \dots a_n $ 으로 나눈다.

그리고 $ a_0, a_1, \dots a_n $ 에서 나올 수 있는 부분 집합의 합을 A 라 하고 나머지 $ a_{n/2 +1}, \dots a_n $ 나올 수 있는 부분 집합의 합을 B 라 하자.

그럼 문제의 정답은 (A의 원소로만 가능한 경우) + (A+B로 가능한 경우) + (B로만 가능한 경우) 로 나타낼 수 있다.
각각의 배열을 만드는 시간은 $2^{20}$ 을 두 번 하면 되고, "A+B로 가능한 경우"는 배열 B에 S-A[i]의 원소가 있는 지를 확인하면 된다.

S=0 이고 a = [ -7, -3, -2, 5, 8 ] 같은 경우는 A = { [-7, -3] 으로 나타낼 수 있는 부분 집합들 } 이고 B = { [-2, 5, 8] 으로 나타낼 수 있는 부분 집합들 } 이다. 이를 자세히 적는다면 A = [ -7, -3, -10 ], B = [ -2, 5, 8, 3, 6, 11 ] 이다.
여기서 답은 (A의 원소로만 가능한 경우 = 0) + (A+B로 가능한 경우는 -3+3=0 으로 1개) + (B로만 가능한 경우 = 0) 으로 1 이다.

주의해야 할 점은, 원소가 같은 것이 여러 개 있을 수 있다. 예를 들어 A = [0, 2, 2], B = [2, 2, 4] 라면 각 숫자는 서로 다르기 때문에 따로 세어야하고 A+B 로 만들어지는 2+2 의 경우들도 모두 서로 다르게 조합된 것들이기 때문에 모두 세어야 한다. 같은 2+2 이지만 $A_1 + B_0$ 은 2 + 2 인 것이고, $A_2 + B_0$ 은 (0+2) + 2 이기 때문이다.

10216 - Count Circle Groups

개인적으로 재미있게 풀었다. 알고스팟 남극기지 문제처럼 좌표평면과 범위가 있어서 엄청 어려워보였다. (주의. 남극기지와는 다른 문제이다!)

시간 제한이 8초인건 나중에 봤고, N이 3,000 이하이길래 충분하다고 생각하고 코딩을 시작했다.

아이디어는 이랬다. (사실 문제에서 말한 그대로 하는거라 아이디어랄 것도 없다.)

아군의 통신 영역이 서로 닿거나 겹친다면 통신 가능하고, 통신이 가능한 부대끼리는 하나의 그룹처럼 이동한다. 여기서 그룹의 개수를 헤아리는 문제인데, 그렇다면 진영을 하나의 노드로 본다면, "몇 개의 그래프가 존재하는가"로 문제를 바꿔 생각할 수 있다.

정점 $A_i$ 에서 $A_j$ 로 통신 가능하다면 이동하도록 인접 리스트를 만든다. ( $O(N^2)$ )
각 정점에서 연결된 모든 정점을 방문하고 개수를 센다. (여기서 하나의 그래프를 발견) . 방문하지 않은 나머지 정점을 확인한다. ( $O(N^2)$ )

그래프를 세는 부분을 코드로 표현하면 아래와 같다.

bool dfs(vector<int> adj[], int pos){
    if(visit[pos]) return false;
    visit[pos] = true;
    for(int i=0; i<adj[pos].size(); ++i)
        dfs(adj, adj[pos][i]);
    return true;
}

memset(visit, false, sizeof(visit));
int count=0;
for(i=0; i<N; ++i){
    count += dfs(adj, i);
}
printf("%d\n", count);

지금 생각해보니 분리집합(Disjoint-set) 으로 했어도 괜찮았을것 같다.