TopCoder SRM 371 Div2 (완료)

음.. 처음해본 상금매치였는데.. 결과가 안좋았다..
두문제 풀고도 둘다 sysfail이라니.. ㅠ_ㅠ 그나마 챌 3개를 성공해서 중간은 유지했다..
세문제 다 쉬웠는데 매우 아쉽다.. 이러다가 계속 DIV2에 머무는거 아닌지. ㅠ_ㅠ
그래도 rating 소폭 상승.. green으로 돌아왔다..

방 8등 전체 307등

[250] CondorcetVoting

Problem Statement
   
One approach to voting is to have voters assign a rank to each candidate. Candidate A is preferred to candidate B if there are more voters who rank A ahead of B than there are voters who rank B ahead of A. A Condorcet winner is a candidate which is preferred to all other candidates. There can be at most one Cordorcet winner in an election, but there might also be none.
You will be given a vector <string> votes. The jth character of the ith element of votes is a lowercase letter, indicating the ranking that voter i assigned to candidate j. Letters closer to 'a' indicate higher-ranked (preferred) candidates, while those closer to 'z' are lower-ranked (less preferred). Return the 0-based index of the Cordorcet winner, or -1 if there isn't one.
Definition
   
Class:
CondorcetVoting
Method:
winner
Parameters:
vector <string>
Returns:
int
Method signature:
int winner(vector <string> votes)
(be sure your method is public)
   
 
Constraints
-
votes will contain between 1 and 50 elements, inclusive.
-
Each element of votes will contain between 1 and 50 characters, inclusive.
-
Each element of votes will contain the same number of characters.
-
Each element of votes will contain only lowercase letters ('a' - 'z').
Examples
0)
 
    
{"acbd",
 "bacd",
 "bdca"}
Returns: 0
Voters 0 and 2 ranked candidate 0 higher than candidate 1, while voter 1 ranked candidate 1 higher than candidate 0. Therefore, candidate 0 is preferred to candidate 1.
All three voters ranked candidate 0 higher than candidate 2, so candidate 0 is preferred to candidate 2.
Finally, voters 0 and 1 ranked candidate 0 higher than candidate 3, while only voter 2 ranked candidate 3 higher than candidate 0. Therefore, candidate 0 is preferred to candidate 3 as well.
1)
 
   
{"abc",
 "bca",
 "cab"}
Returns: -1
This is a classic example of a cyclic preference. Two voters prefer 0 to 1, two prefer 1 to 2, and two prefer 2 to 0. There is no Condorcet winner.
2)
 
   
{"cezdqcw"}
Returns: -1
Even with only one voter, there may be no Condorcet winner because of a simple tie.
3)
 
   
{"abcd", "abcd", "abcd", "abcd", "abcd", "abcd",
 "cbad", "cbad", "cbad", "cbad", "cbad",
 "dbca", "cbda", "cbda"}
Returns: 1
Candidate 1 is nobody's first choice, but still wins.
4)
 
   
{"abbcbbbaaccaaccbbacbbbaacbccbccacaaacaacaaacbccaac",
 "accbabcaacacbcccbbccbbcaccccccbbcbbcbaccbcbcacbcbc",
 "acacaaabccaaaccabbaaaacabaaabacacbaacbcccbccbcbacb",
 "acbcbabaabbcaababaacbabcacbaccabbaaacccbcabbbcacba",
 "cbbbacbbacccbbabbbcbaabaaaacaacbcbccbaaccbcaaccbcb",
 "cbacbbcbbcbcaaabccabcabbcbacaaabccabbcbacbbacbbaca",
 "cacaabccbbbaaacccacbbcacababbcaaabccbbacbbbccacbaa",
 "bccbbabaaaababcbabbbbcbcacbcbcbacccacacacacacacaab",
 "bccabcaabcabbccaaccbcabaaabbbcaabaaabbbbabbbaabaac",
 "accccbabaaaabcbacabbcbbacaacaaaacccbbbcacaccccaaac",
 "cccbcaababbaacaaabbbaabbccccacaacbacaacbbbaacccbbb",
 "bccccaccbcbbaaaaaaaaccbababcabaaccacbbabbbcabbaaca",
 "cbacacaabbccacaabbbbbbccabcbbaccacbcacacacbccbcbcc",
 "baabcabccaaaaccbaacaaccacccbcbbaaacacaccbcaacbbbba",
 "bccaaaabcbbcbbbbbcaabaacccbccbbcbabacaaccbccaababb",
 "cacbbbbcabbcbaabbccbaccbaacbbcbbbbcabababccabbbcab",
 "bccbcacbccaacacccccaacabacbacbbbcaabacacccbbbccaac",
 "aaaccbbbacacbaaaacacaabbaacccbcccbcabbccbcacabbacb",
 "bcabcbbacbacacbbaaccabcabcbbaabacacccbbbcabbbcaacb",
 "bacbbbbaccbaabbbbbcaccbbcbcabbbccbcacccbabbbcaaacc",
 "bababcacbacacacccccbbcacccbbcbccaccaacbbcacabcabba",
 "aaabaccbbcacaacbabccccabbbcbcccccccbaacbccbaacbbbc",
 "abacbaaaaaccacbbbaccbbbabaacbcbccacccabaaaacbaabbb",
 "cbbcacbaccabbbcaacbcbabbcabcbaccabcbbbcabcbcbaacca",
 "babbacaaacbbcbbbabbaabcbabcbbaacaacbbbaaaabbcabcca",
 "cbabaacabcccaabbbacccaccbacabbaacaaabcbcccbcbcccaa",
 "aabbbcbacabbcabcbcccbccaccbcacbaacabbbccaabaabcbba",
 "caccabcccabbaacbabbaaaccccccccaaccbcaccacaabacccba",
 "bbbcabcababaabacaccacabcbccacccbbbbcbbbaccabcabaab",
 "bbbcaababbbbababababcbbbbaaabbacaabcacbbccbcaaaaaa",
 "bcbacccaaaabbcbcabbbcababbcacaabbbbcbbacbaabcbaccb",
 "bbcaccaaccacbbaaccaaaabccbbacbcbacaacbacbccaaccbba",
 "abaaacbccbbabbcaccbaccccbaaacaccccababcbccccbabcca",
 "acccaccababababacbbaccbcabcaccbabaabacbaacaaacabca",
 "aaabababccabccbcbabcabcacbbcacbcbbbabcabacbcaacacb",
 "ccacbaabbcbaccaccbbabbabbabaacccabcaaccacacccbbcab",
 "bbaabcbabbbaacacabaabcbaaabacbccccaccaaaacbacabbbc",
 "abaaaccaacbbcacacbcbccbaaacbbcbacabbbccabbbccaaaac",
 "bbacbabbcacbbacccaccbcbcabbcbaacabbbbabbaaabaacacb",
 "cacbacbccbcbabacccacabcacacabbcabbccaacacbaaacaacb",
 "bacbbacbccccabcbabcbbcbacacaaabcbaccccaabaabbacbcb",
 "abcaaccccabccaaaaccbabccacbcaaaacaccaccccccaaaabaa",
 "bacabcbccbacccbaaaabcbbaabbabaabcabacccbcabacccbcc",
 "babaccbbcbcbacccabccbcccbaaaaacccabcbccbbbbcbabcbc",
 "cccbbaccbabbbbcbcbcbaaacbbcacbcaacacacccbcabccbcaa",
 "caacbcacbccaaaaacaaababbcccacbabaaabcaacaaababacba",
 "cccccaccabcaacababbacbcbabbcaacbacbabbbccbabcbabbb",
 "ccbcababcabcbcccaccccacabcbaaacaabccbbaabaccbaccab",
 "abbbcacaccabcbccbacabbbccaccaaaacccabbcbacbbccabcb",
 "bacabccabcbbcaacbcacabcbccacbcccbcbcaaaabbaabccabb"}
Returns: 12
 
5)
 
   
{"h", "e", "l", "l", "o"}
Returns: 0
 
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.

voting 결과에 대해서 누가 winner인지 구하는 문제.. winner를 한명 뽑을수 없을때 -1을 return한다..

문제를 잘못이해한것인가.. sys fail이다..

흠.. 다른사람 소스를 봐도 여전히 아리송이다..;; 문제해석이 난해한덕분에 챌을 3개나 성공했지만.. 나도 완벽하게 이해못해서 sys fail을 당했다.. 불행중 다행인가 다행중 불행인가..

이제야 제대로 이해..;;
i 후보에게 j 후보보다 좋은 점수를 준 사람이 많으면 i > j 라고 하자..
모든 임의의 j (j != i) 에 대해 i > j 이면 i가 winner이다.. winner가 없을수도있다..

쉬운문제인데.. 문제해석이 어려운문제.. 이런문제 왜 만드는지 모르겠다..

모든 i, j 쌍에 대해서 cnt[i][j] (j보다 i에게 좋은 점수를 준 사람 수)를 기록 한 후.. i 가 모든 다른 j 에 대해서 (i > j) 인지 구했다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 #define max(x, y) ((x) > (y) ? (x) : (y))
  8
  9 class CondorcetVoting {
 10 public:
 11
 12 int winner(vector <string> votes)
 13 {
 14     int size, n;
 15     int i, j, k, res, fl;
 16     int cnt[100][100];
 17     char map[100][100];
 18
 19     size = votes.size();
 20     n = votes[0].size();
 21     for (i = 0; i < size; i++) {
 22         strcpy(map[i], votes[i].c_str());
 23     }
 24     memset(cnt, 0, sizeof(cnt));
 25     for (i = 0; i < n; i++) {
 26         for (j = 0; j < n; j++) {
 27             if (i == j)
 28                 continue;
 29             // i > j 인 사람이 몇명..?
 30             for (k = 0; k < size; k++) {
 31                 if (map[k][i] < map[k][j])
 32                     cnt[i][j]++;
 33             }
 34         }
 35     }
 36     fl = 0;
 37     for (i = 0; i < n; i++) {
 38         for (j = 0; j < n; j++) {
 39             if (i == j)
 40                 continue;
 41             if (cnt[i][j] <= cnt[j][i])
 42                 break;
 43         }
 44         if (j == n) {
 45             fl++;
 46             res = i;
 47         }
 48     }
 49     if (fl == 1)
 50         return res;
 51     return -1;
 52 }
 53
 54 };

[500] SpiralRoute

Problem Statement
   
The King of Elbonia lives in a palace that is width meters by length meters. Since he makes his subjects live in mud, he is not very popular. He wants the palace partitioned so that visitors have to walk a long way to reach him. His security advisors have settled on a spiral. A visitor enters the palace at the South-West corner and starts walking East. Every time the visitor reaches an outer wall or his own path, he turns left. The corridors in the spiral are 1 meter wide. The diagram below shows an example of a spiral path: the visitor moves from a (the South-West corner) through the alphabet to x, the throne.
nmlkji
oxwvuh
pqrstg
abcdef
The King wants to have his throne correctly placed before all the partitioning is done, so he needs to know where the spiral will end. Write a class SpiralRoute with a method thronePosition that returns two integers, indicating the coordinates of the throne. The South-West corner is (0, 0), the South-East corner is (width - 1, 0) and the North-East corner is (width - 1, length - 1).
Definition
   
Class:
SpiralRoute
Method:
thronePosition
Parameters:
int, int
Returns:
vector <int>
Method signature:
vector <int> thronePosition(int width, int length)
(be sure your method is public)
   
 
Constraints
-
width and length will both be between 1 and 5000, inclusive.
Examples
0)
 
   
6
4
Returns: {1, 2 }
This is the example above.
1)
 
   
6
5
Returns: {3, 2 }
 
2)
 
   
1
11
Returns: {0, 10 }
 
3)
 
   
12
50
Returns: {5, 6 }
 
4)
 
   
5000
5000
Returns: {2499, 2500 }
 
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.

n by m의 직사각형 통로를 spiral형태로 밖에서 시작해서 않으로 이동할때 마지막에 끝나는 위치를 찾는 문제..

다 풀어놓고 critical input하나를 생각을 못했다.. 그러고보니 이런류의 문제는 항상 그부분에서 틀리는거같다..
쉬운문제였는데 아쉽다..


헐.. 문제는 초기화였다.. ㅠ_ㅠ 젠장!! 초기화때문에 틀린게 벌써 몇번째야..!! 초기화는 항상 체크해야겠다..
그냥 simulation을 했다.. 갈수있는데까지 계속 가다가 못가면 stop..

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 class SpiralRoute {
      9 public:
     10
     11 vector <int> thronePosition(int width, int length)
     12 {
     13     int x1, y1, x2, y2;
     14     int turn, lastx, lasty;
     15     vector<int> res;
     16     x1 = 0;
     17     x2 = width-1;
     18     y1 = 0;
     19     y2 = length-1;
     20     turn = 0;
     21
     22     lastx = lasty = 0;
     23     while (1) {
     24         if (turn == 0) {
     25             lastx = x2;
     26             y1++;
     27         }
     28         else if (turn == 1) {
     29             lasty = y2;
     30             x2--;
     31         }
     32         else if (turn == 2) {
     33             lastx = x1;
     34             y2--;
     35         }
     36         else if (turn == 3) {
     37             lasty = y1;
     38             x1++;
     39         }
     40 printf("x1 = %d, x2 = %d, y1 = %d, y2 = %d\n", x1, x2, y1, y2);
     41         if (x1 > x2 || y1 > y2)
     42             break;
     43         turn++;
     44         turn %= 4;
     45     }
     46     res.push_back(lastx);
     47     res.push_back(lasty);
     48     return res;
     49 }
     50
     51 };

[1000] FloodRelief

Problem Statement
    
Global warming has caused your home town to receive far more rain than usual, and it is in danger of becoming flooded. You have been put in charge of buying and installing pumps that will carry away the water. There is no limit on how much water a pump can handle, but they must be placed correctly so that all the water will flow into a pump, with no lakes or even puddles left over. The pumps are also expensive, so you must determine the minimum number that need to be bought.
You are given a vector <string> heights. This is a rectangular grid representing the height of each square meter of your town. It contains only lowercase letters ('a' - 'z'), with 'a' meaning low ground and 'z' meaning high ground. Water flows from a cell to every cell that shares an edge and is of equal or lower height. The town is surrounded by high mountains on all sides, so water cannot flow off the map. You must return the minimum number of pumps that can be placed to ensure that all rain will eventually flow to some pump.
Definition
   
Class:
FloodRelief
Method:
minimumPumps
Parameters:
vector <string>
Returns:
int
Method signature:
int minimumPumps(vector <string> heights)
(be sure your method is public)
   
 
Constraints
-
heights will contain between 1 and 50 elements, inclusive.
-
Each element of heights will contain between 1 and 50 characters, inclusive.
-
Each element of heights will contain the same number of characters.
-
Each element of heights will contain only lowercase letters ('a' - 'z').
Examples
0)
 
   
{"ccccc",
 "cbbbc",
 "cbabc",
 "cbbbc",
 "ccccc"}
Returns: 1
A bowl-shaped area. A single pump in the center is sufficient.
1)
 
   
{"cbabcbabc",
 "cbabcbabc",
 "cbabcbabc",
 "cbabcbabc"}
Returns: 2
Two valleys separated by a ridge. Each valley needs a pump.
2)
 
   
{"ccccccccccc",
 "caaaaaaaaac",
 "caaaaaaaaac",
 "caazpppzaac",
 "caapdddpaac",
 "caapdddpaac",
 "caapdddpaac",
 "caazpppzaac",
 "caaaaaaaaac",
 "caaaaaaaaac",
 "ccccccccccc"}
Returns: 2
A castle with a central courtyard and a moat. One pump is needed for each.
3)
 
   
{"ab",
 "ba"}
Returns: 2
Water cannot flow diagonally.
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.

z가 높은 위치이고 a가 낮은 위치이다.. 물이 고이는곳이 얼마나 있는지 구하는 문제..

시간이 없어서 시도하지 못했다..


그냥 간단히 낮은곳부터 물로 채웠다.. flood fill 문제.. 근데 높은곳부터 흘리면 안된다.. 왜그럴까..?
참 좋은문제인거 같다..

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 int n, m;
      9 char map[100][100];
     10 char check[100][100];
     11
     12 void dfs(int u, int v, char ch)
     13 {
     14     if (u-1 >= 0 && map[u-1][v] >= ch && check[u-1][v] == 0) {
     15         check[u-1][v] = 1;
     16         dfs(u-1, v, map[u-1][v]);
     17     }
     18     if (v-1 >= 0 && map[u][v-1] >= ch && check[u][v-1] == 0) {
     19         check[u][v-1] = 1;
     20         dfs(u, v-1, map[u][v-1]);
     21     }
     22     if (u+1 < n && map[u+1][v] >= ch && check[u+1][v] == 0) {
     23         check[u+1][v] = 1;
     24         dfs(u+1, v, map[u+1][v]);
     25     }
     26     if (v+1 < m && map[u][v+1] >= ch && check[u][v+1] == 0) {
     27         check[u][v+1] = 1;
     28         dfs(u, v+1, map[u][v+1]);
     29     }
     30 }
     31
     32 class FloodRelief {
     33 public:
     34
     35 int minimumPumps(vector <string> heights)
     36 {
     37     int i, j, k;
     38     int cnt;
     39
     40     n = heights.size();
     41     m = heights[0].size();
     42     for (i = 0; i < n; i++) {
     43         strcpy(map[i], heights[i].c_str());
     44     }
     45
     46     cnt = 0;
     47     memset(check, 0, sizeof(check));
     48     for (i = 'a'; i <= 'z'; i++) {
     49         for (j = 0; j < n; j++) {
     50             for (k = 0; k < m; k++) {
     51                 if (map[j][k] == i && check[j][k] == 0) {
     52                     check[j][k] = 1;
     53                     cnt++;
     54                     dfs(j, k, i);
     55                 }
     56             }
     57         }
     58     }
     59     return cnt;
     60 }
     61
     62 };