## SRM 469

Problem Solving/TopCoder logs 2010.05.05 22:35

어제 저녁8시에 열린 매치..~

처음으로 회사에서 한번 해봤다.. 코딩환경이 집이랑 다르다보니.. 좀 부자연스럽긴 했다..~

250점 문제는 결정적으로 input 범위를 착각하는 바람에 어처구니없게 틀렸다.. -_-

뭔가.. 문제풀때 집중이 안돼..;;

Level1 - TheMoviesLevelOneDivOne

n by m 형태의 seat 가 있다.. 두명이 같은 row 에 이웃해서 앉을 수 있는 경우의 수 구하기

각 row 에 대해서 연속된 seat 를 계속 찾았다..

row 가 최대 10억 이므로 1...n 까지 모두 loop 를 도는 것은 불가능하지만

input 이 최대 50 이므로 input 에 들어온 수를 renumbering 하는 방법으로 풀었다..~

매치중에 뭔 생각을 했는지.. row 가 최대 50 인줄 알았다.. -_-;;

Level2 - TheMoviesLevelTwoDivOne

to be updated..

Level3 - TheMoviesLevelThreeDivOne

to be updated

처음으로 회사에서 한번 해봤다.. 코딩환경이 집이랑 다르다보니.. 좀 부자연스럽긴 했다..~

250점 문제는 결정적으로 input 범위를 착각하는 바람에 어처구니없게 틀렸다.. -_-

뭔가.. 문제풀때 집중이 안돼..;;

Level1 - TheMoviesLevelOneDivOne

n by m 형태의 seat 가 있다.. 두명이 같은 row 에 이웃해서 앉을 수 있는 경우의 수 구하기

각 row 에 대해서 연속된 seat 를 계속 찾았다..

row 가 최대 10억 이므로 1...n 까지 모두 loop 를 도는 것은 불가능하지만

input 이 최대 50 이므로 input 에 들어온 수를 renumbering 하는 방법으로 풀었다..~

매치중에 뭔 생각을 했는지.. row 가 최대 50 인줄 알았다.. -_-;;

1 #include <iostream>

2 #include <cstdio>

3 #include <algorithm>

4 #include <vector>

5 #include <string>

6 #include <map>

7 using namespace std;

8 //#define min(x, y) ((x) > (y) ? (y) : (x))

9 //#define max(x, y) ((x) > (y) ? (x) : (y))

10 //#define INF 999999999

11 //#define EPS 1e-14

12

13 class TheMoviesLevelOneDivOne {

14 public:

15

16 long long find(int n, int m, vector <int> row, vector <int> seat)

17 {

18 int size;

19 int cnt;

20 int i, j;

21 int cur, prev;

22 long long sum, dif;

23 vector<long long> num[100];

24 map<int, int> mm;

25

26 cnt = 0;

27 size = row.size();

28 for (i = 0; i < size; i++) {

29 if (mm.find(row[i]) == mm.end()) {

30 mm[row[i]] = cnt;

31 cnt++;

32 }

33 cur = mm[row[i]];

34 num[cur].push_back(seat[i]);

35 }

36 for (i = 0; i < cnt; i++) {

37 sort(num[i].begin(), num[i].end());

38 }

39

40 sum = 0;

41 for (i = 0; i < cnt; i++) {

42 cur = prev = 0;

43 for (j = 0; j < num[i].size(); j++) {

44 cur = num[i][j];

45 if (cur - prev - 1 >= 2) {

46 dif = cur - prev - 1;

47 sum += dif - 1;

48 }

49 prev = cur;

50 }

51 if (m - prev >= 2) {

52 dif = m - prev;

53 sum += dif - 1;

54 }

55 }

56 sum += (long long)(n-cnt) * (m-1);

57 return sum;

58 }

59

60 };

2 #include <cstdio>

3 #include <algorithm>

4 #include <vector>

5 #include <string>

6 #include <map>

7 using namespace std;

8 //#define min(x, y) ((x) > (y) ? (y) : (x))

9 //#define max(x, y) ((x) > (y) ? (x) : (y))

10 //#define INF 999999999

11 //#define EPS 1e-14

12

13 class TheMoviesLevelOneDivOne {

14 public:

15

16 long long find(int n, int m, vector <int> row, vector <int> seat)

17 {

18 int size;

19 int cnt;

20 int i, j;

21 int cur, prev;

22 long long sum, dif;

23 vector<long long> num[100];

24 map<int, int> mm;

25

26 cnt = 0;

27 size = row.size();

28 for (i = 0; i < size; i++) {

29 if (mm.find(row[i]) == mm.end()) {

30 mm[row[i]] = cnt;

31 cnt++;

32 }

33 cur = mm[row[i]];

34 num[cur].push_back(seat[i]);

35 }

36 for (i = 0; i < cnt; i++) {

37 sort(num[i].begin(), num[i].end());

38 }

39

40 sum = 0;

41 for (i = 0; i < cnt; i++) {

42 cur = prev = 0;

43 for (j = 0; j < num[i].size(); j++) {

44 cur = num[i][j];

45 if (cur - prev - 1 >= 2) {

46 dif = cur - prev - 1;

47 sum += dif - 1;

48 }

49 prev = cur;

50 }

51 if (m - prev >= 2) {

52 dif = m - prev;

53 sum += dif - 1;

54 }

55 }

56 sum += (long long)(n-cnt) * (m-1);

57 return sum;

58 }

59

60 };

Level2 - TheMoviesLevelTwoDivOne

to be updated..

Level3 - TheMoviesLevelThreeDivOne

to be updated

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

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 |

TopCoder SRM 463 (2) | 2010.03.06 |