지난 주말 새벽에 열린 매치..
역시.. 이번에도 변함없이 확률문제에서 말렸다..
문제 출제자 확률문제 무지 좋아하는듯.. ㅠ_ㅠ;;

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 };



'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
TCO11 R1 - 탈락  (0) 2011.06.23
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

Leave a Comment


to Top