일단 순위표 만든걸 올려둡니다 :)
srm376.bmp
제 그림판 능력이 이렇게 딸린다니ㅠㅠ
그럼 문제 설명~
EASY(250)

• 문제 설명 지도가 있습니다. 직사각형 지도의 각 칸은 '+', '|', '-', 'S', '.'가 채워질 수 있는데 '+', 'S': 사방으로 움직일 수 있도록 길이 있다 '|': 위아래로만 움직일 수 있도록 길이 있다 '-': 얖옆으로만~ '.' 갈길이 없다 와 같은 의미입니다. 특히 유일하게 하나 존재하는 S는 님의 출발점입니다. 님은 최대 fuel번 움직일 수 있는데 최종적으로 몇 칸이나 도달할 수 있는지 세는 문제였습니다. ㅎㅎ 간단히 bfs로 풀 수 있는 문제였습니다. 어떤 인접한 두 칸이 서로 갈 수 있는지 확인할 수 있고, 어떤 칸을 최소 몇 fuel을 사용하여 갈 수 있는지 알아볼 수만 있으면, 풀 수 있죠 :) [code] #include #include #include using namespace std; int xmove[4] = {1, -1, 0, 0}; int ymove[4] = {0, 0, 1, -1}; struct Trainyard { int reachableSquares(vector layout, int fuel) { int n, m, sol(0); int i, j, x, y, tx, ty; queue > que; n = layout.size(); m = layout[0].size(); bool available[10][10][4]; int reached[10][10]; memset(available, 0, sizeof(available)); memset(reached, -1, sizeof(reached)); for(i = 0; i < n; ++ i) { for(j = 0; j < m; ++ j) { if(layout[i][j] == '|') { available[i][j][0] = available[i][j][1] = true; } else if(layout[i][j] == '-') { available[i][j][2] = available[i][j][3] = true; } else if(layout[i][j] == '+') { available[i][j][0] = available[i][j][1] = true; available[i][j][2] = available[i][j][3] = true; } else if(layout[i][j] == 'S') { available[i][j][0] = available[i][j][1] = true; available[i][j][2] = available[i][j][3] = true; que.push(make_pair(i, j)); reached[i][j] = 0; } } } while(!que.empty()) { x = que.front().first; y = que.front().second; que.pop(); ++ sol; if(reached[x][y] < fuel) { for(i = 0; i < 4; ++ i) { if(available[x][y][i]) { tx = x + xmove[i]; ty = y + ymove[i]; if(0 <= tx && tx < n && 0 <= ty && ty < m && available[tx][ty][i] && reached[tx][ty] == -1) { que.push(make_pair(tx, ty)); reached[tx][ty] = reached[x][y] + 1; } } } } } return sol; } }; [/code] MEDIUM(500)
• 문제 설명 직사각형 모양으로 기계들이 배치되어 있습니다-0- 이들은 상품에 대한 연산을 수행합니다. 기계는 1초에 한 연산씩 수행하게 되는데, 연산의 종류는 다음과 같습니다:
• 정해진 개수의 상품을 추가
• 정해진 방향(위, 아래, 왼쪽, 오른쪽 = N, S, W, E)으로 상품들을 보냄. 낭떠러지 떨어지면 없어진걸로 봄
• 상품을 없애버림 어떤 기계에 k개의 연산이 있다고 합시다. 그럼 t초에는 (t % k)번째의 연산을 하게 됩니다. 즉 "0DDSW" 이란 연산을 가지고 있다면 10초째에는 "0"이란 연산을 하게 됩니다. 기계들이 배치되어 있는 상태가 주어졌을 때, t초 후에 가장 많은 상품을 가지고 있는 기계가 몇개나 가지고 있는지 알아내는게 문제입니다. 기계는 최대 10종류이고, 한 기계는 6개 이하의 연산을 가지고 있으며, 기계의 배치는 8*8 이하입니다. 그리고 시간은 1억초-_-까지 입력으로 주어집니다. 이 문제 최악입니다 -_-;;;; 는 훼이크고 (t-1)초에 어떤 상태를 알고 있을 때, t초의 상태를 알아낼 수 있겠느냐? 는 것이 문제의 핵심입니다. 어떤 t초에는 모든 기계들의 상태를 알고 모든 연산은 옮기거나 없애거나 상수를 추가하거나 하는 등 단지 행렬의 곱으로만 나타낼 수 있습니다. 즉 S_t를 t초의 상태라고 할 때((가로 곱하기 세로, 즉 칸의 수) 차원의 vector입니다. 각 칸에 몇개가 있는지 저장하는.. 편의를 위해 상수를 위한 차원 1을 늘리는 것이 좋습니다:) S_t = A_(t-1) * S_(t-1) 인 A_(t-1)을 찾을 수 있습니다. 근데 놀랍게도 기계의 연산의 수는 6 이하인데, lcm(1 to 6) = 60이므로 A_t = A_(t - 60)임을 알 수 있습니다. 즉 60 주기를 가짐을 알 수 있습니다. (더 작은 주기를 가질수도 있지만 귀찮으므로..) 따라서 S_final = A_(t-1) * A_(t-2) * ... * A_0 * S_initial 인데, A_59 * ... * A_0 = W라 하면 S_final = A_(t-1) A_(t-2) ... A_(q) W^(t / 60) S_initial 입니다. (A는 60의 주기를 가지므로... 단 q는 t-1이하의 최초의 60의 배수) 이제 A들은 그냥 곱해주고 W는 효율적으로 곱해주면(n승을 n/2승의 제곱 혹은 (n-1)/2승의 제곱에 W를 곱한 것으로 바꾸어 나가는 식으로.. 혹은 W^1, W^2, W^4, ...를 구해나가는 식으로) 풀립니다 ㅠㅠ [code] #include #include using namespace std; struct States { long long table[65][65]; }; int n, m; vector actions; vector layout; States state[61]; long long pnum[100]; States powers[100]; struct MarbleMachine { void add(long long to, const long long *from) { for(int i = 0; i <= n * m; ++ i) { to[i] += from[i]; } } void apply(const States &from, States &to, int time) { int i, j, type, pt, pt2, wh; char what; memset(to.table, 0, sizeof(to.table)); to.table[n * m][n * m] = 1; for(i = 0; i < n; ++ i) { for(j = 0; j < m; ++ j) { pt = i * m + j; type = layout[i][j] - '0'; what = actions[type][time % actions[type].size()]; wh = 0; if(what == 'N') { pt2 = pt - m; } else if(what == 'S') { pt2 = pt + m; } else if(what == 'E') { if(j == m - 1) { pt2 = -1; } else { pt2 = pt + 1; } } else if(what == 'W') { if(j == 0) { pt2 = -1; } else { pt2 = pt - 1; } } else if(what == 'D') { wh = -1; } else { type = what - '0'; wh = -2; } if(wh == -2) { add(to.table[pt], from.table[pt]); to.table[pt][n * m] += type; } else if(wh != -1) { if(0 <= pt2 && pt2 < n * m) { add(to.table[pt2], from.table[pt]); } } } } } void apply(const States &a, const States &b, States &c) { memset(c.table, 0, sizeof(c.table)); int i, j, k; for(i = 0; i <= n * m; ++ i) { for(j = 0; j <= n * m; ++ j) { for(k = 0; k <= n * m; ++ k) { c.table[i][j] += a.table[i][k] * b.table[k][j]; } } } } long long maxMarbles(vector layout_, vector actions_, int t) { actions = actions_; layout = layout_; n = layout.size(); m = layout[0].size(); int i; for(i = 0; i <= n * m; ++ i) { state[0].table[i][i] = 1; } for(i = 0; i < 60; ++ i) { apply(state[i], state[i + 1], i); } powers[0] = state[60]; pnum[0] = 60; for(i = 0; true; ++ i) { if(pnum[i] >= t) break; apply(powers[i], powers[i], powers[i + 1]); pnum[i + 1] = pnum[i] + pnum[i]; } States a, b; memset(a.table, 0, sizeof(a.table)); a.table[n * m][n * m] = 1; for(; i > -1; -- i) { if(t >= pnum[i]) { t -= pnum[i]; apply(powers[i], a, b); a = b; } } apply(state[t], a, b); long long sol(0); for(i = 0; i < n * m; ++ i) { if(sol < b.table[i][n * m]) { sol = b.table[i][n * m]; } } return sol; } }; [/code] HARD(1000) 이 문제 꽤 재밌습니다. 일렬로 맵이 있고 폰이 있거나 말거나 합니다. *.. 이러면 폰이 1, 4의 위치에 있는겁니다.(1-index) 이 때 다음과 같은 세 가지 연산이 허용됩니다: (연산은 뒤집어도 허용되는 것이며 그 전후에 뭐가 있든 상관 없습니다...)
• **. -> ..*
• .. -> .*
• ??. -> .?? 예를 들면 처음부터 순서대로 ..
  ...* (2번) .*.* (2번) ...** (3번) 와 같이 바꿀 수 있습니다.. 이 때 시작점과 끝점이 주어지면 그 사이 길이 있는지 물어보는 문제입니다 :) 풀이는 다음과 같습니다. 먼저 시작과 끝 모두 맵이 비어있는지 확인합니다. empty->not empty, not empty->empty는 절대 안됩니다. empty->empty는 절대 됩니다. 이제 우리의 관심은 not empty->not empty.. 이제 3칸씩 띄어서 센 것들끼리 카운팅을 합니다. a0, a1, a2로.. (갑자기 0-index로 변신) 즉 a0 = sigma(ai for i = 3k), a1 = sigma(ai for i = 3k + 1), and so on.. 시작점을 a0, a1, a2라 하고, 끝점을 b0, b1, b2라 합시다. 1번 규칙을 적용하면,, 적당히 셋중 하나가 늘고 나머지 둘이 줍니다 2번 규칙을 적용하면 셋중 하나가 줄고 나머지 둘이 늡니다 3번 규칙을 적용하면 변경 없습니다. 이 때 적당히 저 멀리 안드로메다로 폰들을 옮겨서 1, 2를 연산하고 다시 지구로 돌아올 수도 있기 때문에 적당히 3번 규칙을 중간에 이용하면 언제 어디서나 1, 2번 규칙을 적용할 수 있습니다.(단 폰이 0개인데 줄게 하는 연산을 시키지만 않으면..) 또 살펴볼게, 1, -1, 1 1, 1, -1 과 같은 규칙을 적용하면 2, 0, 0을 만들 수 있고, 마찬가지로 -2, 0, 0을 만들 수 있으므로, 각 수를 2로 나눈 나머지가 중요합니다. 이 intuition을 이용하여 답을 생각해보면, ai, bi의 binary parity(홀짝성)이 같을 때 ci = 0, 다를때 ci=1이라 하면, sigma(ci) = 0 or 3이면 만들 수 있고, 아니면 만들 수 없습니다:) 이 부분은 한 번 생각해보셔요 ^&^ [code] class NoException extends Exception { } public class Unjumpers { int[] count(String x) throws NoException { int[] counted = new int[3]; counted[0] = counted[1] = counted[2] = 0; for(int i = 0; i < x.length(); ++ i) { if(x.charAt(i) == '*') { ++ counted[i % 3]; } } if(counted[0] == 0 && counted[1] == 0 && counted[2] == 0) { throw new NoException(); } for(int i = 0; i < 3; ++ i) { counted[i] %= 2; } return counted; } public int reachableTargets(String start, String[] targets) { boolean checked = false; int sol = 0; int[] counter, tcnt; counter = new int[3]; counter[0] = counter[1] = counter[2] = 0; try { counter = count(start); } catch(NoException e) { checked = true; } for(String str: targets) { boolean checked2 = false; tcnt = new int[3]; tcnt[0] = tcnt[1] = tcnt[2] = 0; try { tcnt = count(str); } catch(NoException e) { checked2 = true; } if(checked) { if(checked2) { ++ sol; } } else { if(!checked2) { int t = 0; for(int i = 0; i < 3; ++ i) { if(counter[i] != tcnt[i]) { ++ t; } } if(t == 0 || t == 3) { System.out.println(str); for(int i = 0; i < 3; ++ i) { System.out.println(counter[i] + ", " + tcnt[i]); } ++ sol; } } } } return sol; } } [/code] -- to be updated..
  [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]