TCO11 R1 - 탈락
Problem Solving/TopCoder logs 2011. 6. 23. 00:08
지난 주말 새벽에 열린 매치..
역시.. 이번에도 변함없이 확률문제에서 말렸다..
문제 출제자 확률문제 무지 좋아하는듯.. ㅠ_ㅠ;;
250도 늦게 풀어서 850등 안에 절대 못들거같아서.. 그냥 무작정 블챌을 시도했는데..
다 실패했다.... 쩝.. -125 점 .. ㅠ_ㅠ;;;;
결국 TCO 탈락.. rating 도 blue 로 떨어지고.. 기분 안좋음..
Level1 - TripleStrings
init -> goal 로 만드는 최소 operation 개수 구하기.. operation 종류에는 다음과 같이 있다..
If A is not an empty string, remove the leftmost character from A, and add it to the end of B.
If A is not an empty string, remove the leftmost character from A, and add it to the end of C.
If B is not an empty string, remove the leftmost character from B, and add it to the end of A.
If C is not an empty string, remove the leftmost character from C, and add it to the end of A.
이 문제는 init 의 suffix 와 goal 가 같은 최대 길이를 구하면 된다..
B 에는 'o' 만 담고 C 에는 'x' 만 담는다고 생각하면 greedy 로 최적이 가능하다는 것을 알 수 있다..~
역시.. 이번에도 변함없이 확률문제에서 말렸다..
문제 출제자 확률문제 무지 좋아하는듯.. ㅠ_ㅠ;;
250도 늦게 풀어서 850등 안에 절대 못들거같아서.. 그냥 무작정 블챌을 시도했는데..
다 실패했다.... 쩝.. -125 점 .. ㅠ_ㅠ;;;;
결국 TCO 탈락.. rating 도 blue 로 떨어지고.. 기분 안좋음..
Level1 - TripleStrings
init -> goal 로 만드는 최소 operation 개수 구하기.. operation 종류에는 다음과 같이 있다..
If A is not an empty string, remove the leftmost character from A, and add it to the end of B.
If A is not an empty string, remove the leftmost character from A, and add it to the end of C.
If B is not an empty string, remove the leftmost character from B, and add it to the end of A.
If C is not an empty string, remove the leftmost character from C, and add it to the end of A.
이 문제는 init 의 suffix 와 goal 가 같은 최대 길이를 구하면 된다..
B 에는 'o' 만 담고 C 에는 'x' 만 담는다고 생각하면 greedy 로 최적이 가능하다는 것을 알 수 있다..~
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7 //#define min(x, y) ((x) > (y) ? (y) : (x))
8 //#define max(x, y) ((x) > (y) ? (x) : (y))
9 //#define INF 999999999
10 //#define EPS 1e-14
11
12 class TripleStrings {
13 public:
14
15 int getMinimumOperations(string init, string goal)
16 {
17 int len;
18 int i, j;
19 len = init.size();
20 for (i = 0; i < len; i++) {
21 for (j = 0; i+j < len; j++) {
22 if (init[i+j] != goal[j]) {
23 break;
24 }
25 }
26 if (i+j == len)
27 return i * 2;
28 }
29 return len * 2;
30 }
31
32 };
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7 //#define min(x, y) ((x) > (y) ? (y) : (x))
8 //#define max(x, y) ((x) > (y) ? (x) : (y))
9 //#define INF 999999999
10 //#define EPS 1e-14
11
12 class TripleStrings {
13 public:
14
15 int getMinimumOperations(string init, string goal)
16 {
17 int len;
18 int i, j;
19 len = init.size();
20 for (i = 0; i < len; i++) {
21 for (j = 0; i+j < len; j++) {
22 if (init[i+j] != goal[j]) {
23 break;
24 }
25 }
26 if (i+j == len)
27 return i * 2;
28 }
29 return len * 2;
30 }
31
32 };
'Problem Solving > TopCoder logs' 카테고리의 다른 글
| TCO13 Round 1C 생명연장 매치 (0) | 2013.03.10 |
|---|---|
| TCO12 R1A - 606등 -_-;; (0) | 2012.04.01 |
| SRM 529 (0) | 2012.01.15 |
| SRM 521 (0) | 2011.10.24 |
| SRM 511 (0) | 2011.07.04 |
| SRM 509 !! (0) | 2011.06.09 |
| SRM 507 - 나이스! (0) | 2011.05.30 |
| TCO11 Qual2 (0) | 2011.05.20 |
| TCO11 Qual1 (2) | 2011.05.15 |
| SRM 504 - unrated event (0) | 2011.04.27 |