어제 저녁8시에 열린 매치..~
처음으로 회사에서 한번 해봤다.. 코딩환경이 집이랑 다르다보니.. 좀 부자연스럽긴 했다..~
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 };



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

to Top