Run@KAIST 2주차 연습 20160021 Hanpil Kang Mar 11 Mar 17, 2018 1 A to Z 쉬운 문제입니다. 가장 왼쪽에 있는 A와 가장 오른쪽에 있는 Z를 잡아서 부분문자열을 만들면 됩니다. #include<bits/stdc++.h> int N; char s[202020]; cin >> s; N = strlen(s); int a,z; for(int i=0; i<n;++i) if(s[i]== A ) a=i; break; for(int i=0; i<n; ++i) if(s[i]== Z ) z=i; cout << z-a+1 << endl; 2 직사각형 직사각형을 만들려면, 길이가 같은 막대를 모은 한 쌍이 두 개 필요합니다. 그런 쌍 들이 여러개 있다면, 그 중 가장 큰 2개를 고르는게 답이 됩니다. #include<bits/stdc++.h> int arr[100010]; bool chk[100010]; int n, i; scanf("%d", &n); for(i = 0; i < n; i++) scanf("%d", &arr[i]); 1
sort(arr, arr + n); int a, b; a = b = -1; for(i = n - 2; i >= 0; i--) if(!chk[i + 1] && arr[i] == arr[i + 1]) if(a == -1) a = arr[i]; else b = arr[i]; break; chk[i] = 1; if(b == -1) printf("0"); else printf("%lld", 1LL * a * b); 3 음식 맛있게 먹기 Dn 을, An 에서 끝나게 연속한 음식을 먹는 방법중 맛있음이 가장 최대의 것이라고 합시다. 그러면 Dn 은, n 1번째 음식을 먹거나, 안먹는 두가지의 경우가 있습니다. n 1번째 음식을 먹을 경우에는, n번째 음식을 포함해서 n 1번째 에서 최대의 맛있음을 가지는 음식까지를 먹으면 됩니다. n번째 음식을 먹는 경우는 한 가지밖에 없습니다. 그래서 이 두개의 최댓값을 구해주시면 Dn 이 나오게 되고, D1 부터 DN 까지 차례로 구한 후 최댓값이 답이 되게 됩니다. 아래의 코드의 d가 Dn 의 역할을 하게 됩니다. #include <cstdio> long long maxsum(int N, int A[]) long long ans = A[0], d = 0; for(int i=0; i<n; ++i) d += A[i]; if(ans<d) ans = d; if(d<0) d = 0; return ans; int N; scanf("%d", &N); int *A = new int[n]; for(int i=0; i<n; ++i) scanf("%d", A+i); printf("%lld\n", maxsum(n, A)); 2
4 조상 트리를 구간으로 바꾸는 테크닉을 알면 쉽습니다. 트리의 루트로 부터 시작해서, dfs를 돌면서 dfs-order를 기억해 줍시다. 어떤 노드에서 dfs를 시작해서, dfs를 나갈 때 dfs-order를 A, B라 하면, 그 노드의 subtree 에 있는 수는 [A, B] 구간이 되게 됩니다. 이것을 이용해서, 하나가 다른 하나의 포함되는지로 조상인지 아닌지의 여부를 판단할 수 있습니다. #include <vector> #include <cstdio> const int MAX_N = 1e5 + 10; vector<int> Ed[MAX_N]; int L[MAX_N], R[MAX_N], TN; void dfs(int v, int p) L[v] = ++TN; for(int w : Ed[v]) if(w!= p) dfs(w, v); R[v] = TN; void init(int N, int R, int P[]) for(int i=0; i<n; i++) if(i+1!= R) Ed[i+1].push_back(P[i]); Ed[P[i]].push_back(i+1); dfs(r, 0); bool isancestor(int A, int B) return L[A] <= L[B] && R[B] <= R[A]; int N, R, Q; scanf("%d%d%d", &N, &R, &Q); int *P = new int[n]; for(int i=0; i<n; ++i) scanf("%d", P+i); init(n, R, P); for(int i=0; i<q; ++i) int A, B; scanf("%d%d", &A, &B); if(isancestor(a, B)) puts("yes"); else puts("no"); 3
5 혜아 인 어비스 이 문제는 running median이라고도 알려진 유명한 문제입니다. 이 문제를 풀 때 Balanced Binary Search Tree등을 이용하는 법도 있지만, Heap (Priority Queue)를 이용한 풀이가 간단하기 때문에 설명하겠습니다. 숫자들이 N 개가 있으면, 큰 숫자로 부터 세어 (N + 1)/2개를 min-heap에, 하위 (N 1)/2개를 max-heap에 담아 줍시다. 그러면 중간값은 min-heap의 최솟값이라는 것을 알 수 있습니다. 숫자 2개가 들어오면, 숫자가 중간값보다 큰지 작은지에 따라 힙에 넣어줍니다. 그리고 숫자 갯수가 맞지 않으면, max-heap 또는 min-heap 중에 크기가 큰 쪽에서 최댓값 또는 최솟값을 빼서 반대쪽에 넣어줍니다. 이 과정을 통하면, min-heap과 max-heap의 크기를 (N + 1)/2와 (N 1)/2로 계속 유지하는 것이 가능합니다. 시간복잡도는 쿼리당 O(log N )이고 상수가 크지도 않습니다. #include<queue> #include<vector> #include<functional> #include<cstdio> priority_queue<int> lessq; priority_queue<int, vector<int>, greater<int> > greaterq; void init(int X) lessq.push(x); int recruit(int X, int Y) if(x > lessq.top()) greaterq.push(x); else lessq.push(x); if(y > lessq.top()) greaterq.push(y); else lessq.push(y); if(lessq.size() == greaterq.size() + 3) greaterq.push(lessq.top()); lessq.pop(); if(lessq.size() + 1 == greaterq.size()) lessq.push(greaterq.top()); greaterq.pop(); return lessq.top(); int X; scanf("%d", &X); init(x); int T; scanf("%d", &T); for(int i=0; i<t; ++i) int A, B; scanf("%d%d", &A, &B); printf("%d\n", recruit(a, B)); 4
6 도시 연결 이 문제는 Minimum Spanning Tree로 잘 알려진 문제입니다. Minimum Spanning Tree란, 그래프의 부분 그래프 중에서 최소 가중치의 연결 그래프를 의미합니다. Kruskal, Prim, Boru vka등의 알고리즘이 있지만, 여기서는 제일 구현하기 간편한 Kruskal Algorithm을 설명합시다. Kruskal 알고리즘은, 간선을 가중치 순서대로 정렬합니다. 그 다음에 작은 것 부터 시작해서, 사이클이 없을 경우에 그 간선을 선택해 줍니다. 그래서 N 1개의 간선이 선택되어 스패닝 트리를 만들 때 까지 반복 해 줍니다. 이러면 답을 얻을 수 있습니다. 이 알고리즘이 올바르다는 것을 증명하기 위해서는 두 가지를 보여야 합니다. 1. 이 알고리즘은 언제나 Spanning Tree를 만든다.: 일단 이 그래프에서는 사이클이 생길 수 없습니다. 항상 다른 두 트리간에 연결을 한다는 점에서 알 수 있습니다. 그리고 그래프는 연결그래프 입니다. 왜냐하면 그래프가 두 부분 이상으로 나눠져 있다면, 알고리즘은 그 엣지를 처음 봤을 때 이어야 합니다. 2. 이 알고리즘은 최소 Spanning Tree를 찾는다.: 스패닝 트리를 만드는 과정 중에 항상 그 스패닝 트리를 포함하는 최소 스패닝 트리가 있음을 보이면 됩니다. 수학적 귀납법을 사용하여, T 에서 e 라는 엣지를 추가하려고 합니다. T 를 포함하는 최소 스패닝 트리인 M 이 존재하고, M + e에는 사이클이 존재합니다. 이 사이클에서 T 에 포함되지 않는 최소 원소인 f 가 존재 합니다. M 이 최소 스패닝 트리라서, f 의 가중치는 e의 가중치 보다 크지 못하기 때문에, M + e f 도 또 다른 최소 스패닝 트리이고, 수학적 귀납법에 의해서 계속 최소 스패닝 트리가 만들어 진다는 것을 알 수 있습니다. 증명과정이 어렵지만, Minimum Spanning Tree의 성질이 굉장히 좋다고 생각하시면 될 것 같습니다. #include <vector> #include <algorithm> #include <cstdio> struct ED int a, b, c; ED(int aa, int bb, int cc) : a(aa), b(bb), c(cc) bool operator<(const ED &o) return c < o.c; ; struct UF vector<int> UNF; UF(int N) : UNF(vector<int>(N+10, 0)) for(int i=0; i<n+10; i++) UNF[i] = i; int Find(int v) return UNF[v] == v? v : UNF[v] = Find(UNF[v]); bool Union(int a, int b) UNF[a = Find(a)] = (b = Find(b)); return a!= b; ; vector<ed> Ed; int mincost(int N, int M, int A[], int B[], int C[]) for(int i=0; i<m; i++) Ed.emplace_back(A[i], B[i], C[i]); sort(ed.begin(), Ed.end()); UF uf = UF(N); int ans = 0, cnt = 0; for(ed &e : Ed) if(uf.union(e.a, e.b)) ans += e.c, cnt++; 5
return (cnt == N-1? ans : -1); int N, M; scanf("%d%d", &N, &M); int *A = new int[m], *B = new int[m], *C = new int[m]; for(int i=0; i<m; ++i) scanf("%d%d%d", A+i, B+i, C+i); printf("%d\n", mincost(n, M, A, B, C)); 7 헤아의 타이핑 혜아의 타이핑 문제에서 답은 s의 길이가 같으면, 어떤 것이든 상관이 없다는 것을 알 수 있습니다. 그래서 우리는 s의 길이가 되게 타이핑 하는 방법의 수를 센 후에, 2 s 로 답을 나눠 줄 것입니다. ( mod M 에서 M +1 2로 나누는 법은 를 곱하시면 됩니다.) 2 그래서 이 문제는 동적계획법 테이블 Di,j 를, 키를 i번 쳤을 때, j개의 글자가 써져 있는 경우의 수를 O(N 2 )에 구하고, DN, s 의 값을 2 s 로 나눈 값을 출력해 주면 됩니다. #include<bits/stdc++.h> long long dp[5050][5050]; //i keystroke, j remain int N; const int MOD = 1e9+7; const int MODINV = (MOD+1)/2; char s[10101]; scanf("%d%s", &N, s); int K = strlen(s); dp[0][0] = 1; for(int i=0; i<=n; ++i) for(int j=0; j<=i; ++j) dp[i][j] %= MOD; dp[i+1][max(j-1, 0)] += dp[i][j]; dp[i+1][j+1] += 2*dp[i][j]; long long ans = dp[n][k]; for(int i=0; i<k; ++i) ans = (ans*modinv)%mod; printf("%lld\n", ans); 8 돌 돌 문제의 제한은 Backtracking이나 Branch and Bound같은 알고리즘을 떠올리게 합니다. 하지만 이 문제에는 다항시간 풀이법이 존재합니다. 6
우리는 이 문제를 다음과 같은 방법으로 min-cut으로 바꿀 것 입니다.: S를 부숴진 돌의 집합, T 를 부숴지지 않은 돌의 집합이라고 합시다. 우리는 모든 음수인 돌을 전부 부수는게 (가능하다면) 최적이라는 것을 알고 있습니다. 그래서 S에 부수려는 돌을, T 에 부수지 않았으면 하는 돌을 배치 합니다. 그리고 i가 S에 속하면, i의 배수는 T 에 속하지 못한다는 것을 알 수 있습니다. (이렇지 않은 경우에는 전부 가능합니다.) 그래서 우리는 다음과 같이 모델링을 할 수 있습니다. j가 i의 배수인데, j가 T 에, i가 S에 들어가 있으면, ai 0이고, i가 T 에 들어가 있으면, ai, ai > 0이고, i가 S에 들어가 있으면, ai 의 패널티를 받는다고 생각할 수 있습니다. 그래서 이 패널티를 기준으로 다음과 같은 그래프를 만듭니다. ai 0 이면 S i로 가중치 ai 의 간선 ai > 0 이면 i T 로 가중치 ai 의 간선 j = ni (n > 2)에 대해, i j로 가중치 의 간선 Flow-cut duality에 의해, S에서 T 까지 flow를 흘려주면 최소 패널티를 구할 수 있고, 정점 O(N ), 간선 O(N logn )개가 나오기 때문에, 흔한 플로우 알고리즘인 BFS Ford-Fulkerson Algorithm 같은 알고리즘으로도 O(N 3 log 2 N )으로 시간 안에 돌게 됩니다. #include<bits/stdc++.h> const int MAXN = 505; struct edgint pos; long long cap; int rev;; vector<edg> gph[maxn]; void clear()for(int i=0; i<maxn; i++) gph[i].clear(); void add_edge(int s, int e, long long x) gph[s].push_back(e, x, (int)gph[e].size()); gph[e].push_back(s, 0, (int)gph[s].size()-1); int dis[maxn], pnt[maxn]; bool bfs(int src, int sink) memset(dis, 0, sizeof(dis)); memset(pnt, 0, sizeof(pnt)); queue<int> que; que.push(src); dis[src] = 1; while(!que.empty()) int x = que.front(); que.pop(); for(auto &e : gph[x]) if(e.cap > 0 &&!dis[e.pos]) dis[e.pos] = dis[x] + 1; que.push(e.pos); return dis[sink] > 0; long long dfs(int x, int sink, long long f) 7
if(x == sink) return f; for(; pnt[x] < gph[x].size(); pnt[x]++) edg e = gph[x][pnt[x]]; if(e.cap > 0 && dis[e.pos] == dis[x] + 1) long long w = dfs(e.pos, sink, min(f, e.cap)); if(w) gph[x][pnt[x]].cap -= w; gph[e.pos][e.rev].cap += w; return w; long long match(int src, int sink) long long ret = 0; while(bfs(src, sink)) long long r; while((r = dfs(src, sink, (long long)2e9))) ret += r; return ret; int a[maxn]; int N; scanf("%d", &N); long long ans = 0; for(int i=1; i<=n; ++i) scanf("%d", a+i); if(a[i]>0) ans += a[i]; int S = N+1; int T = N+2; for(int i=1; i<=n; ++i) if(a[i] <= 0) add_edge(s, i, -a[i]); else add_edge(i, T, a[i]); for(int i=1; i<=n; ++i) for(int j=2*i; j<=n; j += i) add_edge(i, j, (long long)(1e18)); printf("%lld\n", ans - match(s, T)); 8