제1회 천하제일 코딩대회 본선 (해설 미완성)

A. B. 걷다보니 신천역 삼 (Small)/(Large)

  단순 dynamic으로 생각할 수 있다.

  마지막 수에 대해서 0,1,2가 들어갈 수 있으므로 현재 k자리 수에 대해서 3*dp[k]를 처리해주면 된다. 단 int의 경우 3개를 더했을 경우 오버플로가 발생할 수 있으니 유의.

?

1 2 3 4 5 6 7 8 9 10 11

#include <cstdio> #define MOD 1000000009 int main() {     long long N,R=0;     scanf("%lld", &N);     if (N > 1) R = 2;     while (N-- > 2)         R = ((R + R) % MOD + R) % MOD;     printf("%lld", R);     return 0; }

C. 나는 행복합니다 ~

  규칙이 있는 2차원에서 해싱을 할 수 있는지 물어보는 문제.

  가로로 순서대로 적혀지기 때문에 가로에 대해서 처리해주면 된다.

?

1 2 3 4 5 6 7

#include<cstdio> int main() {     int N, M, K;     scanf("%d%d%d", &N, &M, &K);     printf("%d %d", K / M, K%M);     return 0; }

D. 너의 이름은

  

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

#include <cstdio> int main() {     char P[10001];     int N, K, Q, A[26] = {1},R,M[10001],i;     scanf("%d%d%d", &N, &K, &Q);       for(i=1;i<=K;i++)         scanf("%d %c\n", &M[i], &P[i]);       if (!M[Q]) {         printf("-1"); return 0;     }       for (i = 1; i <= K; i++)         if(M[Q] <= M[i]) A[P[i] - 'A'] = 1;       for (int i = 0; i < N; i++)         if (!A[i]) printf("%c ", 'A' + i);           return 0; }

E. 스테판 쿼리

  쭉 순회하며 가장 긴 연승의 회수를 계산해준다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#include <cstdio>   int isAW(int a, int b) {     if (a % 3 == (b + 1) % 3) return 1;     if (b % 3 == (a + 1) % 3) return -1;     return 0; }   int main() {     int N, A[310], B[310],i,WA=0,WB=0,CW=1,R=1;     scanf("%d", &N);     for (i = 0; i < N; i++) scanf("%d", &A[i]);     for (i = 0; i < N; i++) scanf("%d", &B[i]);     for (i = 0; i < N; i++) {         WA = isAW(A[i], B[i]);         if (!WA) WA = WB*-1;         (WA == WB) ? (CW++) : (CW = 1, WB = WA);         R = R > CW ? R : CW;     }     printf("%d", R);     return 0; }

F. 욱제는 도박쟁이야!!

  그냥 주어지는 모든 정수를 양수로 바꿔주기면 된다..

?

1 2 3 4 5 6 7 8 9 10 11 12

#include <cstdio> #include <cstdlib> int main() {     int N, i, R = 0, D;     scanf("%d", &N);     for (i = 1; i <= 2*N; i++) {         scanf("%d", &D);         R += abs(D);     }     printf("%d", R);     return 0; }

G. 조교는 새디스트야!!

  순서대로 제대로 서있는지 확인한다.

?

1 2 3 4 5 6 7 8 9 10 11

#include <cstdio> int main() {     int N, i,C=0,D;     scanf("%d", &N);     for (i = 1; i <= N; i++) {         scanf("%d", &D);         if (D != i) C++;     }     printf("%d", C);     return 0; }

H. 준오는 최종인재야!!

  트리의 지름을 구하는 문제다. 단 지름을 구하되, 가능한 지름 중에 가장 적은 시간을 갖는 것을 가져와야 한다.

  필자는 두 가지 방식으로 해결했다. 어차피 트리의 지름을 구하는 대표적인 방법을 쓴 것 뿐이다.

1. BFS 2번 사용

2. Tree dp로 해결

H-1. BFS 2번 사용

  BFS를 통해 먼저 임의로 설정된 노드(arbitrary node)를 기준으로 가장 먼 노드를 찾고, 다음 그 노드에서 다시금 BFS로 먼 곳을 찾는 것이다. 단, 방문된 노드의 수에 대해서 더 높은 것을 선호하도록 하고, 그 방문 노드 수가 같다면 시간이 적게 드는 곳을 선호하게 구현을 진행한다

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

#include <cstdio> #include <vector> #include <queue> using namespace std;   struct DD {     int idx, V, D; }; int C[50001],WA[500001],N; vector<pair<int, int>> V[50001];   int bfs(int n) {     for (int i = 0; i <= N; i++) WA[i] = C[i] = 0;     C[n] = 1;     WA[n] = 0;     int D;     queue<int> Q;     Q.push(n);     while (!Q.empty()) {         n = Q.front();         Q.pop();         for (int i = 0; i < V[n].size();i++) {             int E = V[n][i].first;             int W = V[n][i].second;             if (C[E] != 0) continue;             C[E] = C[n]+1;             WA[E] = WA[n]+W;             Q.push(E);             D = C[E];         }     }     return D; } int main() {     int T,i,S,E,W,D,TV,Ri=1;     scanf("%d%d", &N, &T);     for (i = 0; i < N-1; i++) {         scanf("%d%d%d", &S, &E,&W);         V[S].push_back(make_pair(E, W));         V[E].push_back(make_pair(S, W));     }     D = bfs(1);     TV = 50000 * 1000;     for (i = 1; i <= N; i++) {         if (D == C[i]) {             if (TV > WA[i]) {                 Ri = i;                 TV = WA[i];             }         }     }     D = bfs(Ri);     TV = 50000 * 1000;     for (i = 1; i <= N; i++) {         if (D == C[i]) {             if (TV > WA[i]) {                 Ri = i;                 TV = WA[i];             }         }     }     printf("%d", TV / T + (TV%T == 0 ? 0 : 1));     return 0; }

H-2. Tree dp로 해결

  트리의 지름이 되기 위해선 종만북에 있던 내용처럼

1. root에서 leaf

2. leaf에서 leaf

  둘 중 하나 밖에 없음을 생각하며 접근한다.

dfs 설계는 반환값은 "방문하는 노드를 반드시 포함하며 시작한 루트노드와 연결되어 있다고 가정한다."를 나타낸다.

내용으로는 먼저 root와 현재 노드와 현재 노드의 자식 노드를 연결했을 때를 계산해준다. 그 후에 O(N^2)으로 자식 간, 즉 leaf to leaf가 지름이 될 수 있기에 이를 계산해준다. 마지막으로 dfs를 마치면 root to leaf와 leaf to leaf 중 문제에 맞는 큰 값을 답으로 낸다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#include<cstdio> #include<vector> using namespace std; const int INF = 1e9; struct _d { int v, t; }; struct _ret {     int cnt, time;     bool operator>(const _ret& oth) const {         if (cnt != oth.cnt) return cnt > oth.cnt;         else return time < oth.time;     } } root2leaf, leaf2leaf, ans; vector<vector<_d>> adj; bool *vi; _ret dfs(int n) {     vi[n] = 1;     _ret ret, child;     vector<_ret> childs;     ret.cnt = 0, ret.time = INF;     for(_d& e : adj[n])         if (!vi[e.v]) {             child = dfs(e.v);             child.time += e.t;             if (child > ret)                 ret = child;             childs.push_back(child);         }     ret.cnt += 1;     if (ret.time == INF) ret.time = 0;           for (int i = 0; i < childs.size(); i++)         for (int j = 0; j < i; j++) {             child.cnt = childs[i].cnt + childs[j].cnt + 1;             child.time = childs[i].time + childs[j].time;             if (child > leaf2leaf)                 leaf2leaf = child;         }     return ret; }     int main() {     int N, T, u, v, t,i;     scanf("%d%d", &N,&T);     vi = new bool[N] {};     adj.resize(N);     for (i = 0; i < N - 1; i++) {         scanf("%d%d%d", &u, &v, &t);         u--, v--;         adj[u].push_back(_d{ v,t });         adj[v].push_back(_d{ u,t });     }     leaf2leaf.cnt = 0, leaf2leaf.time = INF;     root2leaf = dfs(0);     if (leaf2leaf > root2leaf) ans = leaf2leaf;     else ans = root2leaf;     printf("%d", ans.time / T + (ans.time%T ? 1 : 0));     return 0; }

I. 하늘에서 별똥별이 빗발친다.

https://www.acmicpc.net/problem/2492 참고

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

#include <cstdio> int max_v(int a, int b) { return a > b ? a : b; } struct _p { int x, y; }; int main() {     _p board[100];     int W, H, T, K,i,j,k,res=0,tmp,x,y;     scanf("%d%d%d%d", &W, &H, &K, &T);     for (i = 0; i < T; i++)         scanf("%d%d", &board[i].x, &board[i].y);     for(i=0;i<T;i++)         for (j = 0; j < T; j++) {             x = board[i].x, y = board[j].y;             tmp = 0;             for (k = 0; k < T; k++)                 if (x <= board[k].x && board[k].x <= x + K                     && y <= board[k].y && board[k].y <= y + K) tmp++;             res = max_v(res, tmp);         }     printf("%d", T-res);     return 0; }

J. 한조서열정리하고옴ㅋㅋ

  한 방향만 나아간다는 점을 이용하여 O(N)로 해결할 수 있다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

#include <cstdio> using namespace std;   int main() {     int N, D,i,C,R=0,RC=0;     scanf("%d%d", &N,&C);     for (i = 1; i < N; i++) {         scanf("%d",&D);         if (C < D) {             R = R > RC ? R : RC;             RC = 0;             C = D;         }         else RC++;     }     R = R > RC ? R : RC;     printf("%d", R);     return 0; }