TopCoder SRM 372 Div 2

요즘 계속 DIV2에서 놀고있다.. 한번 떨어지고나니 계속 못올라가고있다..
문제를 천천히푸는 나는 최소한 두문제는 풀어야하는데.. 열라 구린문제들만 나온다..
이번에도 쉬운문제인데도 불구하고 이해를 못해서 결국 못풀었다.. 젠장..!
SRM 끝나고나서 다시보니 이해가 됐다.. ㅠ_ㅠ
DIV2의 경우 통상 두문제정도는 쉬운데 항상 말리면서 제대로 못풀고있다.. 운도 안따르는것같다..
이번에는 두문제를 푼사람이 1명밖에없었고.. easy를 얼마나 빨리 풀었느냐에따라 등수가 갈렸다..
나도 남들처럼 코딩이 빨라야되는데.. ㅠ_ㅠ

방 10등 전체 304등..

[250] DietPlan

Problem Statement
    
The doctor has given you your diet, in which each character corresponds to some food that you should eat. You also know what you have eaten for breakfast and lunch, in which each character corresponds to a type of food that you have already eaten that day. You have decided that you will eat all of the remaining food in your diet during dinner, and you want to return that as a string (sorted in alphabetical order). If you have cheated in anyway (either by eating too much of one type of food, or by eating some food that is not in the dietPlan), you should return the string "CHEATER" (quotes for clarity).
Definition
   
Class:
DietPlan
Method:
chooseDinner
Parameters:
string, string, string
Returns:
string
Method signature:
string chooseDinner(string diet, string breakfast, string lunch)
(be sure your method is public)
   
 
Constraints
-
diet will contain between 0 and 26 characters, inclusive.
-
Each character in diet will be an uppercase letter ('A'-'Z').
-
There will be no duplicate characters in diet.
-
breakfast will contain between 0 and 26 characters, inclusive.
-
Each character in breakfast will be an uppercase letter ('A'-'Z').
-
lunch will contain between 0 and 26 characters, inclusive.
-
Each character in lunch will be an uppercase letter ('A'-'Z').
-
There will be no duplicate characters in breakfast.
-
There will be no duplicate characters in lunch.
-
No character will appear in both breakfast and lunch.
Examples
0)
 
   
"ABCD"
"AB"
"C"
Returns: "D"
Here, you have eaten most of your food for the day. So, you can only eat a single 'D' for dinner.
1)
 
   
"ABEDCS"
""
""
Returns: "ABCDES"
Here you've saved all of your food for dinner.
2)
 
   
"EDSMB"
"MSD"
"A"
Returns: "CHEATER"
You cheated at lunch time by eating an 'A'!
3)
 
   
""
""
""
Returns: ""
 
4)
 
   
"IWANTSODER"
"SOW"
"RAT"
Returns: "DEIN"
 
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.

주어진 음식에대해서 아침에 먹고 점심에 먹고 남은것을 저녁에 다 먹어야한다.. 저녁에 먹어야하는 음식들을 sort해서 출력하기.. 단 diet list에 없는 음식을 먹은경우 CHEATER를 출력..

쉬운문제였다.. 'A'부터 'Z'까지 커버하는 배열을 잡아놓고 먹은것에대해 marking하는 방법으로 풀었다..
남들보다 한참 늦게 풀었는데.. 이제 코딩 속도도 높이도록 노력해야겠다..

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 class DietPlan {
      9 public:
     10
     11 string chooseDinner(string diet, string breakfast, string lunch)
     12 {
     13     char check[128];
     14     char buf[128];
     15     int i, j;
     16     string ret;
     17
     18     memset(check, 0, sizeof(check));
     19     strcpy(buf, diet.c_str());
     20     for (i = 0; i < strlen(buf); i++) {
     21         check[(int)buf[i]]++;
     22     }
     23     strcpy(buf, breakfast.c_str());
     24     for (i = 0; i < strlen(buf); i++) {
     25         if (check[buf[i]] == 0) {
     26             return "CHEATER";
     27         }
     28         check[buf[i]]--;
     29     }
     30     strcpy(buf, lunch.c_str());
     31     for (i = 0; i < strlen(buf); i++) {
     32         if (check[buf[i]] == 0) {
     33             return "CHEATER";
     34         }
     35         check[buf[i]]--;
     36     }
     37     j = 0;
     38     for (i = 'A'; i <= 'Z'; i++) {
     39         if (check[i] == 1) {
     40             buf[j] = i;
     41             j++;
     42         }
     43     }
     44     buf[j] = 0;
     45     ret = buf;
     46     return ret;
     47 }
     48
     49 };

[500] RoadConstruction

Problem Statement
    
During today's meeting of the Council of Rainban, your advisors warned you about the growing traffic problems in your fair country. It seems that the Daring Ostrich Society has shut down the Rainban Access Motorway due to the annual migration of ostriches across the highway. This is rather unfortunate, as many cars are now trapped on the highway. Construction crews have begun to build an emergency exit so that the trapped cars can exit, but there will be chaos without rules on when cars can exit. To promote friendly driving, you decide to enforce the following rules:
A car may not exit if there is a car in front of it in its lane.
A car may not exit if a car in a lower numbered lane is about to exit.
Once a car has reached the front of its lane, it must (if possible) yield exactly once to a car from a higher numbered lane. This means that the car will allow a car from a higher numbered lane to exit (if one exists).
If a car has fulfilled all of the above requirements, it may exit the highway. The next car in that lane (if there is one) then moves to the front of the lane.
As an example, suppose that there are five cars in the highway, as pictured below (with the front of the lane located on the left):
0 A B
1 C D
2 E
Car A has not yet yielded, so it must yield. The same happens for car C. Car E cannot yield (as there are no cars in higher lanes), and so it exits. Now car A fulfills the exiting rules (having yielded to car E), and it can exit. Car B moves up to the front, but has not yet yielded, and thus must yield to car C. Car B then can exit, followed by car D.
You will be given currentLanes. The i-th element of currentLanes corresponds to the cars currently located in lane i. The 0-th character in each element corresponds to the car at the front of the lane. No car in currentLanes has yielded yet. The car represented by the character 'D' is a diplomat from a far-off country. You want to know how many cars exit in front of this diplomat (so that you know whether you have time to take a bath before his arrival), and return this number.
Definition
   
Class:
RoadConstruction
Method:
getExitTime
Parameters:
vector <string>
Returns:
int
Method signature:
int getExitTime(vector <string> currentLanes)
(be sure your method is public)
   
 
Constraints
-
currentLanes will contain between 1 and 50 elements, inclusive.
-
Each element of currentLanes will contain between 1 and 50 characters, inclusive.
-
Each character of currentLanes will be an uppercase letter ('A'-'Z').
-
There will be exactly one 'D' in currentLanes.
Examples
0)
 
   
{"AB",
 "CD",
 "E"}
Returns: 4
The example from the problem statement.
1)
 
   
{"AH",
 "D",
 "BCG",
 "E",
 "F"}
Returns: 2
Car F goes first. Having yielded right of way, car A moves next, followed by car D (which already yielded to car F).
2)
 
   
{"AAA",
 "A",
 "AAA",
 "A",
 "AAD",
 "A",
 "AAB"}
Returns: 13
Multiple cars can be represented by the same letter, but there will be exactly one diplomat.
3)
 
   
{"DEFGHIJK"}
Returns: 0
 
4)
 
   
{"I",
 "WANT",
 "TO",
 "DRINK",
 "SOME",
 "COFFEE"}
Returns: 5
 
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.

1. 같은 차선에서는 앞에있는 차가 먼저 나간다..
2. 위에있는 차선의 차가 먼저 나간다..
3. 위에있는 차선의 차는 반드시 한번 밑에있는 차에게 양보해야한다.

이런 조건을 만족할 때 'D' 번 차 이전에 몇개의 차가 빠져나가는지 구하는 문제..

그냥 simulation 하면 된다.. 컨테스트 도중 마지막 케이스가 이해가 안되서 30분동안 이해해보려고 삽질했었다..
컨테스트 끝나고 알아냈는데.. C -> I -> W -> T -> A -> D 순이다..

그냥 simulation 했다.. 문제 이해만 하면 쉬운문제.. -_-

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class RoadConstruction {
  9 public:
 10
 11 int getExitTime(vector<string> currentLanes)
 12 {
 13     int n;
 14     int i, last, cnt;
 15     int pos[100], len[100];
 16     char lane[100][100];
 17     char check[100][100];
 18     n = currentLanes.size();
 19     for (i = 0; i < n; i++) {
 20         strcpy(lane[i], currentLanes[i].c_str());
 21     }
 22     for (i = 0; i < n; i++) {
 23         pos[i] = 0;
 24         len[i] = strlen(lane[i]);
 25     }
 26     memset(check, 0, sizeof(check));
 27     cnt = 0;
 28     while (1) {
 29         last = -1;
 30         for (i = 0; i < n; i++) {
 31             if (pos[i] >= len[i])
 32                 continue;
 33             if (check[i][pos[i]] == 1) {
 34                 break;
 35             }
 36             check[i][pos[i]] = 1;
 37             last = i;
 38         }
 39         if (i < n) {
 40             printf("%c exit\n", lane[i][pos[i]]);
 41             if (lane[i][pos[i]] == 'D')
 42                 break;
 43             cnt++;
 44             pos[i]++;
 45         }
 46         else if (i == n) {
 47             printf("%c exit\n", lane[last][pos[last]]);
 48             if (lane[last][pos[last]] == 'D')
 49                 break;
 50             cnt++;
 51             pos[last]++;
 52         }
 53     }
 54     return cnt;
 55 }
 56
 57 };

[1000] RainyDay

Problem Statement
    
As the ruler of Rainban, you are well aware of the fact that your country often has violent rainstorms. Thus, you usually remember to ride the Rainban Official Motorcade to your destination. Today, however, you looked outside and, eschewing common sense, decided to walk to the store. Now, a very bad storm is coming, and your Giant Hole (TM) umbrella has a large hole in it!
You know the path that you need to travel to return to your home. You are currently standing where the 'Y' is and are trying to reach home (the 'H'). The rest of the path consists of either 'C' or '.', corresponding to whether that section of the path is covered (and thus rain-proof) or uncovered, respectively. Both your current location and home are rain-proof. You also know the forecast, in which the i-th character is 'R' if it is currently raining at the i-th section of the path, or '.' if it is not.
During each minute, the following events happen:
You choose whether or not to move. If you choose to move, you immediately move one step to an adjacent section of the path. If you choose not to move, you remain in your current section.
If you are now standing in an uncovered section and it is raining there, you get wet.
The forecast circularly shifts one section to the left. For example, "R..R" would become "..RR" (quotes for clarity).
If you are standing in an uncovered section and it is now raining there, you get wet.
So if the path is "Y..H" and the forecast is "R.RR", then choosing to move right every minute would result in the following:
Forecast: R.RR       R.RR       .RRR       .RRR       RRR.       RRR.
Path:     Y..H  -->  CY.H  -->  CY.H  -->  C.YH  -->  C.YH  -->  C..Y
               You        Rain   Get  You   Get  Rain  Get You    Get
               move       moves  wet  move  wet  moves wet move   home
Thus, in the above case, you would get wet 3 times on your way home.
Return the minimum number of times that you will get wet before returning home, if you time your journey properly. You don't care how long it takes, as long as you eventually get home while as dry as possible.
Definition
   
Class:
RainyDay
Method:
minimumRainTime
Parameters:
string, string
Returns:
int
Method signature:
int minimumRainTime(string path, string forecast)
(be sure your method is public)
   
 
Constraints
-
path will be between 2 and 50 characters, inclusive.
-
Each character in path will be 'Y', 'C', '.', or 'H'.
-
There will be exactly one 'Y' and exactly one 'H' in path.
-
forecast will contain the same number of characters as path.
-
Each character in forecast will be either 'R' or '.'.
Examples
0)
 
   
"Y..H"
"R.RR"
Returns: 3
The example from the statement.
1)
 
   
"Y.C.H"
"RRRR."
Returns: 2
Here, you wait 2 minutes, then move right twice (getting wet once). You can then wait 1 minute and move right twice again, getting wet once more.
2)
 
   
"Y..C.H"
"RRR.R."
Returns: 3
 
3)
 
   
"CCH..Y"
"RRRR.R"
Returns: 2
 
4)
 
   
"CCH.........Y"
"............."
Returns: 0
No rain at all in the forecast!
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.

Y 가 현재 있는 위치이고 H까지 이동해야 한다.. C는 covered되서 비에 맞지 않는지역이다..
비를 최소한 안맞고 가는 방법을 찾는다.. 단 중간에 멈춰서 임의의 시간을 쉴 수 있다..
'R'은 비오는 지역, '.' 은 비가 안오는 지역이고.. 이 정보는 1분마다 옆으로 한칸씩 shift한다..

이 문제는 DP로 풀 수 있을듯 하다..  dp[i][j] = 'i 칸에서 j번째 쉬프트에서 이동할때 비에맞는 최소값' 을 저장하면서 풀면 되려나..? -_-?? 음.. 코딩해봐야되는데 귀찮다.. ㅠ_ㅠ 이러니 실력이 안늘지.. ㅠ_ㅠ;;
소스를 보니 BFS로 푼 사람도 있다..