## TopCoder SRM 412 Div 1

Problem Solving/TopCoder logs 2008. 8. 1. 23:58

어제 저녁 8시에 열린 매치.. 아.. 정말 짜증나는 매치였다.. 250점 짜리는 나름 괜찮은 DP 문제가 나왔는데.. 500은 정말 무슨말인지 도저히 이해가 안되는 문제가 나와서 짜증 팍팍 났던 매치였다.. 문제 해석만 난해햇지 실제 난이도는 쉬운문제라서 더더욱 열받았다.. 결국 챌도 하나 실패하고.. 완전 망쳤다.. 결국 rating은 3연속 상승에서 마감.. ㅠ_ㅠ 무려 71점이나 대폭락했다.. rating이 올라갈수록.. 역시 잘하는 사람과 경쟁하게되어서.. 매치가 상당히 빡세다.. 휴.. 빨리 실력을 키워야하는데..;;

방에 있는 사람들도 짜증내고 있다.. ㅎㅎ

Level1 - ForbiddenStrings

A, B, C로만 이루어진 임의의 string을 만들때 세개의 연속된 letter가 A, B, C가 각각 하나씩 있는 string은 허용이 안된다.. 이때 길이가 n인 string을 몇가지 만들수 있는지 구하는 문제..

전형적인 DP 문제이다..

dp[n][i] = "길이 n의 string에서 마지막이 i 상태로 끝날때의 경우의 수" 라고 정의하고 풀면 된다..

여기서 i 의 상태는 다음의 총 9가지가 있다..

0 - AA로 끝나는 경우

1 - AB로 끝나는 경우

2 - AC로 끝나는 경우

3 - BA로 끝나는 경우

...

...

8 - CC로 끝나는 경우

이렇게 하여 dp[n][i] 의 상태는 dp[n-1][j]의 상태를 이용해서 채워나갈 수 있다..

1 #include <iostream>

2 #include <cstdio>

3 #include <algorithm>

4 #include <vector>

5 #include <string>

6 using namespace std;

7

8 long long dp[40][10];

9

10 class ForbiddenStrings {

11 public:

12

13 long long countNotForbidden(int n)

14 {

15 int i;

16 long long sum;

17 if (n == 1)

18 return 3;

19 if (n == 2)

20 return 9;

21 if (n == 3)

22 return 21;

23

24 memset(dp, 0, sizeof(dp));

25 dp[3][0] = 3;

26 dp[3][1] = 2;

27 dp[3][2] = 2;

28 dp[3][3] = 2;

29 dp[3][4] = 3;

30 dp[3][5] = 2;

31 dp[3][6] = 2;

32 dp[3][7] = 2;

33 dp[3][8] = 3;

34 for (i = 4; i <= n; i++) {

35 dp[i][0] = dp[i-1][0] * 1 + dp[i-1][3] * 1 + dp[i-1][6] * 1;

36 dp[i][1] = dp[i-1][0] * 1 + dp[i-1][3] * 1 + dp[i-1][6] * 0;

37 dp[i][2] = dp[i-1][0] * 1 + dp[i-1][3] * 0 + dp[i-1][6] * 1;

38

39 dp[i][3] = dp[i-1][1] * 1 + dp[i-1][4] * 1 + dp[i-1][7] * 0;

40 dp[i][4] = dp[i-1][1] * 1 + dp[i-1][4] * 1 + dp[i-1][7] * 1;

41 dp[i][5] = dp[i-1][1] * 0 + dp[i-1][4] * 1 + dp[i-1][7] * 1;

42

43 dp[i][6] = dp[i-1][2] * 1 + dp[i-1][5] * 0 + dp[i-1][8] * 1;

44 dp[i][7] = dp[i-1][2] * 0 + dp[i-1][5] * 1 + dp[i-1][8] * 1;

45 dp[i][8] = dp[i-1][2] * 1 + dp[i-1][5] * 1 + dp[i-1][8] * 1;

46 }

47 sum = 0;

48 for (i = 0; i < 9; i++) {

49 sum += dp[n][i];

50 }

51 printf("sum = %lld\n", sum);

52 return sum;

53 }

54

55 };

2 #include <cstdio>

3 #include <algorithm>

4 #include <vector>

5 #include <string>

6 using namespace std;

7

8 long long dp[40][10];

9

10 class ForbiddenStrings {

11 public:

12

13 long long countNotForbidden(int n)

14 {

15 int i;

16 long long sum;

17 if (n == 1)

18 return 3;

19 if (n == 2)

20 return 9;

21 if (n == 3)

22 return 21;

23

24 memset(dp, 0, sizeof(dp));

25 dp[3][0] = 3;

26 dp[3][1] = 2;

27 dp[3][2] = 2;

28 dp[3][3] = 2;

29 dp[3][4] = 3;

30 dp[3][5] = 2;

31 dp[3][6] = 2;

32 dp[3][7] = 2;

33 dp[3][8] = 3;

34 for (i = 4; i <= n; i++) {

35 dp[i][0] = dp[i-1][0] * 1 + dp[i-1][3] * 1 + dp[i-1][6] * 1;

36 dp[i][1] = dp[i-1][0] * 1 + dp[i-1][3] * 1 + dp[i-1][6] * 0;

37 dp[i][2] = dp[i-1][0] * 1 + dp[i-1][3] * 0 + dp[i-1][6] * 1;

38

39 dp[i][3] = dp[i-1][1] * 1 + dp[i-1][4] * 1 + dp[i-1][7] * 0;

40 dp[i][4] = dp[i-1][1] * 1 + dp[i-1][4] * 1 + dp[i-1][7] * 1;

41 dp[i][5] = dp[i-1][1] * 0 + dp[i-1][4] * 1 + dp[i-1][7] * 1;

42

43 dp[i][6] = dp[i-1][2] * 1 + dp[i-1][5] * 0 + dp[i-1][8] * 1;

44 dp[i][7] = dp[i-1][2] * 0 + dp[i-1][5] * 1 + dp[i-1][8] * 1;

45 dp[i][8] = dp[i-1][2] * 1 + dp[i-1][5] * 1 + dp[i-1][8] * 1;

46 }

47 sum = 0;

48 for (i = 0; i < 9; i++) {

49 sum += dp[n][i];

50 }

51 printf("sum = %lld\n", sum);

52 return sum;

53 }

54

55 };

Level2 - StringsAndTabs

to be updated..

Level3 - ErrantKnight

to be updated..

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

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 414 Div 1 (0) | 2008.08.17 |

TopCoder SRM 413 Div 1 (0) | 2008.08.08 |

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 |

TopCoder SRM 407 Div 1 (2) | 2008.06.28 |

TopCoder SRM 405 Div 1 (2) | 2008.06.15 |