Codeforces Round #459 (Div. 2)

A. Eleven

  주어진 길이에 대해 피보나치 수가 넘어가지 않을 때까지 'O'로 바꿔주기만 하면 된다.

?

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

#include <cstdio> #include <cstring> int main() {     int N,a=1,b=1,t;     char name[1001] = {};     scanf("%d", &N);     memset(name, 'o', N);     name[0] = 'O';     while (a + b <= N) {         name[a + b - 1] = 'O';         t = b;         b = a + b;         a = t;     }     printf("%s", name);     return 0; }

B. Radio Station

  map 등의 hashing 자료구조를 활용하여 해결할 수 있다. 문자열 통째로 key로 두던가 아니면 필자처럼 숫자로 변경해서 해싱을 진행해도 좋다.

?

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

#include <cstdio> #include <map> using namespace std; using ll = long long; int main() {     map<ll, char*> pool;     ll ip;     int n, m, a, b, c, d;     char *tmp,name[11];     scanf("%d%d\n", &n, &m);     while (n--) {         ip = 0;         tmp = new char[11]{};         scanf("%s %d.%d.%d.%d\n", tmp, &a, &b, &c, &d);         ip |= a; ip <<= 8;         ip |= b; ip <<= 8;         ip |= c; ip <<= 8;         ip |= d;         pool[ip] = tmp;     }     while (m--) {         scanf("%s %d.%d.%d.%d;\n", name, &a, &b, &c, &d);         ip = 0;         ip |= a; ip <<= 8;         ip |= b; ip <<= 8;         ip |= c; ip <<= 8;         ip |= d;         printf("%s %d.%d.%d.%d; #%s\n", name, a, b, c, d, pool[ip]);     }     return 0; }

C. The Monster

  두 가지 포인트에 집중한다.

1. 구간 (l,r)은 최대 길이 5000에 대해서 5000*(5001)/2 개의 조합이 나올 수 있다.

2. 구간 (l,r)에 대해 l을 고정한 것에 대해 l<r<L(문자열 s의 길이) 에 대해 (l,r)을 계산할 때 (l,r-1)을 이용할 수 있다(optimal substructure)

  1.에 의해 O(N^2) 솔루션이 가능하고, 2.에 의해 이중 for문 안에서 이전에 있던 위치값을 이용할 수 있음을 알 수 있다.

  +) 대부분 이런식으로 푼 것 같다. 구간에 대해 올바른 순서가 존재할 수 있는지만을 판단한다.

  1. left, right 구간을 줄 변수를 둔다. 구간 (i,j)에 대해 가상 left, right를 각각 l,r로 둔다. i부터 j까지 correct bracket sequence를 만족하면 l = 0이 된다. 반면 r이 음수일 경우 ')'로 시작하는 것이기에 이 때는 i로 시작하는 올바른 순서가 존재할 수 없다. r의 역할은 ?의 개수 및 (의 개수를 말한다. l의 역할은 현재 (인지와 ?가 (인지를 말한다.

  2. 가상 구간에 대해 문자에 따라 처리해준다.

2-1. (일 경우 : l++, r++

2-2. )일 경우 : l--, r--

2-3. ?일 경우 : l--, r++

자세한 내용은 에디토리얼에 나와 있다.

  

?

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

#include <cstdio> #include <cstring> int main() {     char board[5001];     int i, j,L,ans = 0,l,r;     scanf("%s", board);     L = strlen(board);     for (i = 0; i < L; i++) {         l = r = 0;         for (j = i; j < L; j++) {             if (board[j] == '(') l++, r++;             else if (board[j] == ')') l--, r--;             else l--, r++;             if (r < 0) break;             if (l < 0) l = 1;             if (l == 0) ans++;         }     }     printf("%d", ans);     return 0; }

D. MADMAX

  제목처럼 서로 각 턴에 대해 많은 정점을 방문하면 이길 수 있게 되어 있다.

  또한 각 턴마다 상대방이 지난 간선 보다 ASCII Code 상 크거나 같은 값을 지닌 간선만 지나갈 수 있다. 본문에 쓰여있듯 경우의 수가 매우 많기 때문에 브루트 포스로 처리하기엔 너무 오래 걸린다. 또한 A(Max)와 B(Lucas)의 상태도를 나타면 100x100의 경우가 있으며 이전상태에 대해 소문자 알파벳의 총 수 26 가지가 존재하게 된다. 추가적으로 처음 게임을 시작할 때는 어떤 간선을 갈 수 있도록 설정해야하므로 1을 추가해준다. 따라서 명백하게 부분문제가 겹치는 것을 알 수 있으므로 dynamic programming을 진행한다.

cache[이전 알파벳][현재 A의 정점 위치][현재 B의 정점 위치]

시간 복잡도 : O(N^2)

?

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

#include <cstdio> #include <vector> #include <cstring> using namespace std; vector<vector<int>> adj; int cache[27][100][100], board[100][100]; // NONE : 0, 'a' : 1 bool dfs(int bef, int vn, int rn) {     int& ret = cache[bef][vn][rn];     if (ret == -1) {         ret = 0;         for (int v : adj[rn])             if (bef <= board[rn][v])                 if(!dfs(board[rn][v], v, vn)) ret = 1;     }     return ret; } int main() {     memset(cache, -1, sizeof(cache));     char ch;     int n, m,u,v,A,B,i,j;     scanf("%d%d", &n, &m);     adj.resize(n);     while (m--) {         scanf("%d%d %c\n", &u, &v, &ch);         u--, v--;         adj[u].push_back(v);         board[u][v] = ch - 'a' + 1;     }     for (i = 0; i < n; i++) {         for (j = 0; j < n; j++)             printf("%c", dfs(0, j, i) ? 'A' : 'B');         puts("");     }     return 0; }

E. Pollywog