TopCoder SRM382 DIV2

탑코더 후기 올리는것도 은근히 귀찮다.. 더군다나 최근에 몇차례 연빵으로 있어서.. 아직 밀린 문제들이 많은데.. 흠.. ;; 부지런히 해야겠다.. 더군다나 나의 블로그의 글들이 거의 탑코더 후기로 채워지고 있다.. 흠.. 이러면 안되는데.. 포스팅도 자주자주 해야겠다..

SRM 382는 수요일 아침 11시에 있었던 매치..;; 역시.. 아침 11시는 정말 컨디션 최악이라는것을 다시한번 느꼈다.. 왜 아침만되면 코딩이안되는지.. -_- 단순코딩문제를 계속 헤매다가 정말 간신히 풀었다.. 훔

1) 매번 할때마다 단순 코딩문제만 풀고.. 정작 풀고싶은 DP라든지 알고리즘 쓰는 문제는 죄다 놓치는것 같다.. 흠.. 이러면 안되는데..;; ㅠ_ㅠ

2) 최근에 한국 유저가 많이 등록함에따라서.. (왠만한 매치에는 거의 항상 30명이 넘는다..) 종종 같은 방에서 만난다.. 좋은 현상인것같다.. 다같이 선전해서 한국이 위대하다는것을 보여줬으면 좋겠다..

3) 우리나라가 네덜란드를 제치고 세계 10위 마크~!!! 내가 탑코더에 열심히 참여한 덕분에 10위 탈환이 좀 늦어지지않았나 생각해본다 (응? 응?)

방 10등 전체 228등..

[250] ContiguousSubsequences

Problem Statement
     
Given an integer sequence a[0], a[1], ..., a[N-1], find a contiguous subsequnce a[i], a[i+1], ..., a[j] such that:
The length of the subsequence (j-i+1) is at least K.
The average value in the subsequence (a[i] + a[i+1] + ... + a[j])/(j-i+1) is maximized.
You are given a vector <int> a containing the original sequence, and an int K. Return a vector <int> containing exactly two elements. The first element is the first index of the contiguous subsequence described above, and the second element is the last index. Both indices are 0-based. If there are multiple subsequences that satisfy the conditions above, return the longest one among them. If there are still multiple subsequences, return the one among them with the smallest first index.
Definition
   
Class:
ContiguousSubsequences
Method:
findMaxAverage
Parameters:
vector <int>, int
Returns:
vector <int>
Method signature:
vector <int> findMaxAverage(vector <int> a, int K)
(be sure your method is public)
   
 
Constraints
-
a will contain between 1 and 50 elements, inclusive.
-
Each element of a will be between 0 and 1000000, inclusive.
-
K will be between 1 and number of elements in a, inclusive.
Examples
0)
 
   
{1,3,7}
2
Returns: {1, 2 }
There are 3 possible contiguous subsequences:
{1,3}, average = 2.
{1,3,7}, average = 11/3.
{3,7}, average = 5.
So {3,7} is the best case.
1)
 
   
{5,1,3,4}
2
Returns: {2, 3 }
 
2)
 
   
{10}
1
Returns: {0, 0 }
There is only one possible subsequence - the whole sequence.
3)
 
   
{381,921,513,492,135,802,91,519}
1
Returns: {1, 1 }
When K = 1, we can select the subsequence containing only the maximal elements.
4)
 
   
{381,921,513,492,135,802,91,519}
4
Returns: {0, 3 }
 
5)
 
   
{3,5,7,7,2,5,4,7,7,2,4}
1
Returns: {2, 3 }
 
6)
 
   
{3, 1, 3, 3, 3, 1, 3, 3, 3}
1
Returns: {2, 4 }
 
7)
 
   
{1, 3, 2, 1, 1, 2, 2, 2, 2}
3
Returns: {5, 8 }
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

숫자 배열이 들어오고.. 길이가 K이상인 연속된 subsequence중에서 평균이 가장 큰 sequence의 앞과 맨 끝 index를 구하기.. 답이 여러개일 경우 가장 긴 sequence 그중에서도 index가 젤 빠른걸 골라야한다.. 그걸 모르고 왜 sample이 안나오는지 한참 고민했다..

음.. 단순 구현문제인데 코딩에서 말리는바람에 한참 늦게풀었다.. 나같은경우 처음 시작부터 cumulative sum을 구해놓고 n^2으로 구했다..

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 class ContiguousSubsequences {
      9 public:
     10
     11 vector <int> findMaxAverage(vector <int> a, int K)
     12 {
     13     int n, sum;
     14     int i, j;
     15     int x, y;
     16     double max1, avg;
     17     int arr[100];
     18     vector<int> res;
     19     n = a.size();
     20     max1 = -1.0;
     21     memset(arr, 0, sizeof(arr));
     22     arr[0] = a[0];
     23     for (i = 1; i < n; i++) {
     24         arr[i] += arr[i-1] + a[i];
     25     }
     26     for (i = n; i >= K; i--) {
     27         for (j = 0; j+i-1 < n; j++) {
     28             if (j == 0)
     29                 sum = arr[j+i-1];
     30             else
     31                 sum = arr[j+i-1] - arr[j-1];
     32             avg = (double)sum / (double)i;
     33             if (avg > max1) {
     34                 max1 = avg;
     35                 x = j;
     36                 y = j+i-1;
     37             }
     38         }
     39     }
     40     res.push_back(x);
     41     res.push_back(y);
     42 printf("x, = %d, y = %d\n", x, y);
     43     return res;
     44 }
     45
     46
     47 };

[500] CollectingRiders

Problem Statement
     
A rider is a fantasy chess piece that can jump like a knight several times in a single move. (See notes for a description of how a knight jumps.) A rider that can perform a maximum of K jumps during a single move is denoted as a K-rider. For example, a 2-rider can jump once or twice during a single move, and a 1-rider is a traditional knight.
 
There are some riders of different types on a chessboard. You are given a vector <string> board representing the layout of the pieces. The j-th character of the i-th element of board is the content of the square at row i, column j. If the character is a digit K between '1' and '9', the square contains a K-rider. Otherwise, if the character is a '.', the square is empty. Return the minimal total number of moves necessary to move all the riders to the same square. Only one piece can move during each move. Multiple riders can share the same squares at all times during the process. Return -1 if it is impossible.
Definition
   
Class:
CollectingRiders
Method:
minimalMoves
Parameters:
vector <string>
Returns:
int
Method signature:
int minimalMoves(vector <string> board)
(be sure your method is public)
   
 
Notes
-
A traditional knight has up to 8 moves from a square with coordinates (x,y) to squares (x+1,y+2), (x+1,y-2), (x+2,y+1), (x+2,y-1), (x-1,y+2), (x-1,y-2), (x-2,y+1), (x-2,y-1), and can not move outside the chessboard.
Constraints
-
board will contain between 1 and 10 elements, inclusive.
-
Each element of board will contain between 1 and 10 characters, inclusive.
-
All elements of board will have the same length.
-
board will contain only positive digits ('1'-'9') and '.' characters.
-
board will contain at least one digit.
Examples
0)
 
   
{"...1",
 "....",
 "2..."}
Returns: 2
The 2-rider can jump from (2,0) to (0,1) in the first move, and then from (0,1) to (2,2) to (0,3) in the second.
1)
 
   
{"........",
 ".1......",
 "........",
 "....3...",
 "........",
 "........",
 ".7......",
 "........"}
Returns: 2
In 2 moves, we can move all the pieces to the cell initially occupied by the 1-rider.
2)
 
   
{"..",
 "2.",
 ".."}
Returns: 0
No moves are necessary.
3)
 
   
{".1....1."}
Returns: -1
 
4)
 
   
{"9133632343",
 "5286698232",
 "8329333369",
 "5425579782",
 "4465864375",
 "8192124686",
 "3191624314",
 "5198496853",
 "1638163997",
 "6457337215"}
Returns: 121
Kind of maximal test.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

k-rider는 체스판에서 knight와 같이 움직이는데 한번에 k번 이하의 knight move를 움직일 수 있다.. 체스판에있는 모든 k-rider를 한곳으로 모으는데드는 최소비용 구하기..

솔루션은 에디토리얼을 참고했다.. 우선 모든 rider는 1-rider라고 생각하고 모든 지점에대한 all-pair shortest path를 구한다.. 그리고 k-rider에 대해서 적용하면 A 지점에서 B 지점으로 이동시 드는 비용은 ceil(dist(A, B) / k)이 된다.. (dist(A,B) = 1-rider가 A에서 B로 이동시 드는 비용)

all-pair shortest path는 모든 쌍에 대해서 bfs로 다 돌렸다.. 그리고나서 모든 지점에 대해서 모든 rider를 위치했을때 드는 비용을 다 구해보고 그중 최소값을 취한다..

아.. 코딩하는데 드럽게 오래걸렸다.. 이런문제 나오면 도대체 어케풀어.. ㅠ_ㅠ;;;;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <queue>
  7 using namespace std;
  8
  9 typedef struct _p {
 10     int x, y;
 11 } POINT;
 12
 13 int n, m;
 14 int map[11][11][11][11];
 15 char b[100][100];
 16
 17 int bfs(POINT s, POINT t)
 18 {
 19     int check[11][11];
 20     int x, y, cnt;
 21     POINT p1, p2;
 22
 23     memset(check, -1, sizeof(check));
 24
 25     queue<POINT> q;
 26     q.push(s);
 27     check[s.x][s.y] = 0;
 28
 29     while (!q.empty() && check[t.x][t.y] == -1) {
 30         p1 = q.front();
 31         q.pop();
 32         cnt = check[p1.x][p1.y];
 33         x = p1.x;
 34         y = p1.y;
 35
 36         if (x+1 < n && y+2 < m && check[x+1][y+2] == -1) {
 37             check[x+1][y+2] = cnt+1;
 38             p2.x = x+1;
 39             p2.y = y+2;
 40             q.push(p2);
 41         }
 42         if (x+2 < n && y+1 < m && check[x+2][y+1] == -1) {
 43             check[x+2][y+1] = cnt+1;
 44             p2.x = x+2;
 45             p2.y = y+1;
 46             q.push(p2);
 47         }
 48         if (x-1 >= 0 && y+2 < m && check[x-1][y+2] == -1) {
 49             check[x-1][y+2] = cnt+1;
 50             p2.x = x-1;
 51             p2.y = y+2;
 52             q.push(p2);
 53         }
 54         if (x-2 >= 0 && y+1 < m && check[x-2][y+1] == -1) {
 55             check[x-2][y+1] = cnt+1;
 56             p2.x = x-2;
 57             p2.y = y+1;
 58             q.push(p2);
 59         }
 60         if (x+1 < n && y-2 >= 0 && check[x+1][y-2] == -1) {
 61             check[x+1][y-2] = cnt+1;
 62             p2.x = x+1;
 63             p2.y = y-2;
 64             q.push(p2);
 65         }
 66         if (x+2 < n && y-1 >= 0 && check[x+2][y-1] == -1) {
 67             check[x+2][y-1] = cnt+1;
 68             p2.x = x+2;
 69             p2.y = y-1;
 70             q.push(p2);
 71         }
 72         if (x-1 >= 0 && y-2 >= 0 && check[x-1][y-2] == -1) {
 73             check[x-1][y-2] = cnt+1;
 74             p2.x = x-1;
 75             p2.y = y-2;
 76             q.push(p2);
 77         }
 78         if (x-2 >= 0 && y-1 >= 0 && check[x-2][y-1] == -1) {
 79             check[x-2][y-1] = cnt+1;
 80             p2.x = x-2;
 81             p2.y = y-1;
 82             q.push(p2);
 83         }
 84     }
 85     return check[t.x][t.y];
 86 }
 87
 88 class CollectingRiders {
 89 public:
 90
 91 int minimalMoves(vector <string> board)
 92 {
 93     int i, j, k, l;
 94     int cnt, r, min1, fl;
 95     POINT p1, p2;
 96
 97     n = board.size();
 98     m = board[0].size();
 99     for (i = 0; i < n ;i++) {
100         strcpy(b[i], board[i].c_str());
101     }
102
103     for (i = 0; i < n; i++) {
104         for (j = 0; j < m; j++) {
105             for (k = 0; k < n; k++) {
106                 for (l = 0; l < m; l++) {
107                     p1.x = i;
108                     p1.y = j;
109                     p2.x = k;
110                     p2.y = l;
111
112                     cnt = bfs(p1, p2);
113                     map[i][j][k][l] = cnt;
114 //printf("map[%d][%d][%d][%d] = %d\n", i, j, k, l, cnt);
115                 }
116             }
117         }
118     }
119
120     // (k, l)의 rider를 (i, j)로 이동..
121     min1 = 999999999;
122     for (i = 0; i < n; i++) {
123         for (j = 0; j < m; j++) {
124             fl = 1;
125             cnt = 0;
126             for (k = 0; k < n; k++) {
127                 for (l = 0; l < m; l++) {
128                     if (b[k][l] != '.') {
129                         r = b[k][l] - '0';
130                         if (map[i][j][k][l] == -1) {
131                             fl = 0;
132                             break;
133                         }
134                         if (map[i][j][k][l] % r == 0)
135                             cnt += (map[i][j][k][l] / r);
136                         else
137                             cnt += (map[i][j][k][l] / r) + 1;
138                     }
139                 }
140                 if (fl == 0)
141                     break;
142             }
143
144             if (fl && cnt < min1)
145                 min1 = cnt;
146         }
147     }
148 printf("min1 = %d..\n", min1);
149     if (min1 == 999999999)
150         return -1;
151     return min1;
152 }
153
154 };

[1000] CharmingTicketsEasy

Problem Statement
     
A ticket number that contains exactly 2*K digits is called charming if and only if at least one of the following conditions is satisfied:
The sum of the first K digits is equal to the sum of the last K digits.
The sum of all the digits at positions with odd indices is equal to the sum of all the digits at positions with even indices.
Also, you think that some digits are better than others, so a charming number must contain only digits that you consider to be good. These digits are given in the string good. Determine the number of different charming numbers containing exactly 2*K digits. Return this number modulo 999983. Remember that ticket numbers may contain leading zeroes.
Definition
   
Class:
CharmingTicketsEasy
Method:
count
Parameters:
int, string
Returns:
int
Method signature:
int count(int K, string good)
(be sure your method is public)
   
 
Constraints
-
K will be between 1 and 50, inclusive.
-
good will contain between 1 and 10 characters, inclusive.
-
good will contain only digits ('0' - '9').
-
All characters in good will be distinct.
Examples
0)
 
   
1
"0123456789"
Returns: 10
Only "XX" numbers are charming.
1)
 
   
2
"21"
Returns: 8
Only 1111, 1122, 1212, 1221, 2112, 2121, 2211, 2222 are charming numbers.
2)
 
   
2
"0123456789"
Returns: 1240
 
3)
 
   
10
"731"
Returns: 207444
 
4)
 
   
50
"0123456789"
Returns: 367584
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

to be updated..