## TopCoder SRM 414 Div 1

Problem Solving/TopCoder logs 2008. 8. 17. 20:22

일요일 새벽 1시에 열렸던 매치.. 왠지 예감이 안좋았는데.. 역시나..;; 이번에도 최악의 퍼포먼스를 보이면서.. 좌절했다.. 두번연속 방 최하위.. ㅠ_ㅠ 덕분에 14번의 매치만에 결국 Div2로 추락했다.. 요즘 컨디션이 안좋은건가.. 실력이 줄고있는건가..;; 젠장.. 앞으로 3주동안 참여할수 있는 SRM도 없는데.. 당분간 좀 휴식을 취해야겠다..

rating을 힘들게 조금씩 올려놓았건만.. 떨어지는건 순식간이군.. 마지막 3번 매치만에 무려 375점을 까먹었다..

Level1 - Embassy

input으로 여러개의 form을 작성하는데 걸리는 시간과 하루의 길이(?)와 하루에 대사관이 열려있는 시간이 주어진다.. visa를 받기위해 여러 form을 작성해야하는데 form을 순서대로 하나씩 제출해야 다음 form을 받을 수 있다.. visa를 받으려면 최소 몇시간을 기다려야하는지 구하기..

단순 simulation 이지만 구현이 상당히 까다로운 문제이다..

Level2 - StringInterspersal

문자열이 여러개 주어지고.. 각 문자열을 모두 mix해서 lexy smallest한 문자열 하나를 만들기.. 이때 원래 문자열들은 문자의 순서가 뒤바뀌면 안된다..

to be updated..

Level3 - KPlanetaryAlignment

to be updated..

rating을 힘들게 조금씩 올려놓았건만.. 떨어지는건 순식간이군.. 마지막 3번 매치만에 무려 375점을 까먹었다..

Level1 - Embassy

input으로 여러개의 form을 작성하는데 걸리는 시간과 하루의 길이(?)와 하루에 대사관이 열려있는 시간이 주어진다.. visa를 받기위해 여러 form을 작성해야하는데 form을 순서대로 하나씩 제출해야 다음 form을 받을 수 있다.. visa를 받으려면 최소 몇시간을 기다려야하는지 구하기..

단순 simulation 이지만 구현이 상당히 까다로운 문제이다..

그러나 modular 연산을 사용하면 구현을 상당히 간단하게 할 수 있다..

그러기 위해서 지금까지 진행된 시간 합과는 별로로 현재가 하루중 몇시인지를 따로 관리한다..

그래서 현재시간이 openTime 안에 들지못하면.. 다음날 시작시간까지 기다려야한다는 의미이다..

그리고 또하나.. 처음에 무조건 0시부터 시작하면 최적이 아닌경우도 있다..

처음에 일부러 몇시간 기다리고 시작하는 경우가 나중에 더 효율적으로 끝나는 경우가 있는데..

바로 샘플 2번 케이스가 그렇다..

아.. 정말 어려운 문제..

아.. 정말 어려운 문제..

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

11 class Embassy {

12 public:

13

14

15 int visaApplication(vector <int> forms, int dayLength, int openTime)

16 {

17 int res, cur;

18 int i, j;

19 int min1;

20 min1 = INF;

21 for (j= 0; j <= openTime; j++) {

22 res = forms[0];

23 cur = j;

24 for (i = 1; i < forms.size(); i++) {

25 res += forms[i];

26 cur += forms[i];

27

28 cur = cur % dayLength;

29 if (cur > openTime) {

30 res += dayLength - cur;

31 cur = 0;

32 }

33 }

34 min1 = min(min1, res);

35 }

36 return min1;

37 }

38

39 };

Level2 - StringInterspersal

문자열이 여러개 주어지고.. 각 문자열을 모두 mix해서 lexy smallest한 문자열 하나를 만들기.. 이때 원래 문자열들은 문자의 순서가 뒤바뀌면 안된다..

to be updated..

Level3 - KPlanetaryAlignment

to be updated..

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

TopCoder SRM 421 Div 1 (0) | 2008.10.12 |
---|---|

TopCoder SRM 420 Div 2 (0) | 2008.10.03 |

TopCoder SRM 418 Div 2 (0) | 2008.09.21 |

TopCoder SRM 417 Div 2 (0) | 2008.09.13 |

TopCoder SRM 416 Div2 (0) | 2008.09.07 |

TopCoder SRM 413 Div 1 (0) | 2008.08.08 |

TopCoder SRM 412 Div 1 (0) | 2008.08.01 |

TopCoder SRM 410 Div 1 (2) | 2008.07.20 |

TopCoder SRM 409 Div 1 (완료) (0) | 2008.07.11 |

TopCoder SRM 408 Div 1 (0) | 2008.07.03 |