## TCO10 Qaul2

Problem Solving/TopCoder logs 2010.05.13 14:55

어제 열렸던 TCO10 Q2

600등까지가 다음 라운드로 진출하는데 어처구니없게도 613 등으로 실격됐다.. ㅠ_ㅠ

25일 아침에 마지막 패자부활전이 남아있지만.. 그걸 참가하려면 휴가를 써야한다..

나이를 먹다보니 점점 순발력이 떨어지는것 같다..

250 을 조금만 더 빨리풀었으면 됐는데.. 흑흑.. ㅠ_ㅠ;

Level1 - JingleRingle

사고자 하는 가격, 팔고자 하는 가격이 주어질때.. 이를 이용해서 최대 차익을 얼마나 낼 수 있는지..

greedy 로 풀리는 문제이다..

buy 는 역순으로.. sell 은 정방향으로 매치시켜나가다가 더이상 수익을 낼 수 없으면 break

greedy 로 하면 안되는 경우가 있는지 한참 생각하다가 시간을 허비했다..

Level2 - FuzzyLife

0 과 1 로 되어있는 grid 가 매 단계마다 변하는데..

neighbor 중에 1이 3 개면 1로 되고 2 이면 상태 유지 그 이외의 경우면 0 이 된다..

? 를 적절히 바꿔서 1단계 이후에 최대 1의 개수 구하기

to be updated..

Level3 - HandlesSpelling

주어진 단어들만 이용해서 문장을 최대한 많이 커버해야하는데.. (단어는 중복사용 가능, overlap 불가능)

score 는 (covered 된 가장 긴 substring)^2 - (# of uncovered letters) 가 된다.. score 를 최대화 하기..

to be updated..

600등까지가 다음 라운드로 진출하는데 어처구니없게도 613 등으로 실격됐다.. ㅠ_ㅠ

25일 아침에 마지막 패자부활전이 남아있지만.. 그걸 참가하려면 휴가를 써야한다..

나이를 먹다보니 점점 순발력이 떨어지는것 같다..

250 을 조금만 더 빨리풀었으면 됐는데.. 흑흑.. ㅠ_ㅠ;

Level1 - JingleRingle

사고자 하는 가격, 팔고자 하는 가격이 주어질때.. 이를 이용해서 최대 차익을 얼마나 낼 수 있는지..

greedy 로 풀리는 문제이다..

buy 는 역순으로.. sell 은 정방향으로 매치시켜나가다가 더이상 수익을 낼 수 없으면 break

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 int comp(const int& a, const int& b)

13 {

14 return b < a;

15 }

16

17 class JingleRingle {

18 public:

19

20 int profit(vector <int> buy, vector <int> sell, int tax)

21 {

22 int n, m;

23 int dif, t;

24 int i;

25 int sum;

26 n = buy.size();

27 m = sell.size();

28

29 if (n == 0 || m == 0)

30 return 0;

31

32 sort(buy.begin(), buy.end(), comp);

33 sort(sell.begin(), sell.end());

34

35 sum = 0;

36

37 for (i = 0; i < min(n, m); i++) {

38 dif = buy[i] - sell[i];

39 t = (int)(((double)buy[i] * tax) / 100.0 + EPS);

40 if (dif - t <= 0)

41 break;

42 sum += dif - t;

43 }

44

45 return sum;

46 }

47

48 };

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 int comp(const int& a, const int& b)

13 {

14 return b < a;

15 }

16

17 class JingleRingle {

18 public:

19

20 int profit(vector <int> buy, vector <int> sell, int tax)

21 {

22 int n, m;

23 int dif, t;

24 int i;

25 int sum;

26 n = buy.size();

27 m = sell.size();

28

29 if (n == 0 || m == 0)

30 return 0;

31

32 sort(buy.begin(), buy.end(), comp);

33 sort(sell.begin(), sell.end());

34

35 sum = 0;

36

37 for (i = 0; i < min(n, m); i++) {

38 dif = buy[i] - sell[i];

39 t = (int)(((double)buy[i] * tax) / 100.0 + EPS);

40 if (dif - t <= 0)

41 break;

42 sum += dif - t;

43 }

44

45 return sum;

46 }

47

48 };

Level2 - FuzzyLife

0 과 1 로 되어있는 grid 가 매 단계마다 변하는데..

neighbor 중에 1이 3 개면 1로 되고 2 이면 상태 유지 그 이외의 경우면 0 이 된다..

? 를 적절히 바꿔서 1단계 이후에 최대 1의 개수 구하기

to be updated..

Level3 - HandlesSpelling

주어진 단어들만 이용해서 문장을 최대한 많이 커버해야하는데.. (단어는 중복사용 가능, overlap 불가능)

score 는 (covered 된 가장 긴 substring)^2 - (# of uncovered letters) 가 된다.. score 를 최대화 하기..

to be updated..

#### 'Problem Solving > TopCoder logs' 카테고리의 다른 글

SRM 477 (0) | 2010.07.29 |
---|---|

SRM 476 - GOOD (0) | 2010.07.20 |

SRM 472 - 현충일 새벽에 삽질.. (0) | 2010.06.07 |

SRM 470 (0) | 2010.05.28 |

TCO10 Qual3 - 이런 젠장 (0) | 2010.05.25 |

TCO10 Qaul2 (2) | 2010.05.13 |

SRM 469 (0) | 2010.05.05 |

[SRM 468] 보람이 없구만.. (0) | 2010.04.21 |

SRM 466 (0) | 2010.04.05 |

TopCoder Open 2010 일정.. (0) | 2010.03.31 |

SRM 464 (0) | 2010.03.18 |

## Comments

규욱이가 휴가쓰고 Qual3 참가한다는 것에 1000 원 건다~ ㅋㅋ

ㅋㅋㅋ 당연히 참가해야죠..~