[editorial] SRM 383 DIV 2

  • Rada
    Rada

    안녕하세요
    2부리거 Rada입니다.
    1월 1일 2008년도를 맞이해서 여전히 할 것도 없고, 여자친구마저 없어서 이렇게 문제를 풀어봤습니다.
    SRM 383 이구요. 지금 제 컴퓨터가 망가진건지 TC가 이상한건지 Arena가 실행도지 않아서 점수 Point를 정확히 모른채 풀게되서 죄송합니다.
    Easy - FloorLayout
    한개의 방이 몇개의 파티션으로 나뉘어져 있는 지를 찾아내는 문제입니다.
    입력으로는 가로로 나뉘어진 파티션을 의미하는 "-"과
    세로로 나뉘어진 파티션을 의미하는 "|"이 들어옵니다.
    연속된 -과 |는 하나의 방으로 계산을 하는 문제지요.
    [spoiler="풀이보기"]넵. 다들 예상하셨다 싶이 DFS를 묻는 문제입니다.
    DFS를 이해하고 있는 분이라면 누구든지 쉽게 풀이하실 수 있지요.
    같은 방향으로 이루어진 원소가 더이상 나오지 않을때까지 "-"는 오른쪽 왼쪽으로, "|"는 위쪽, 아래쪽으로 검색해주시고, 방향이 바뀔때마다 카운트를 올려주시면 되겠지요?[/spoiler]
    Medium - Pranks
    Div1의 Easy와 동일한 문제입니다.
    아래 Being님꼐서 설명해주신 http://algospot.com/zbxe/tc/44375 을 참고하세요-*
    Hard - HillWalker
    "존"이라는 친구가 등산을 하려고 한다네요. 높은 곳을 좋아하는 시간제한(timeToDark)내에 최대한 높은 곳에 갔다가 숙소(0, 0)으로 돌아오고 싶다고 합니다. 근데 이 친구가 은근 약골인지 높이차이(threshold)가 많으면 올라가지 못한다는 군요. 그래서 이 친구를 위해서 프로그램을 작성해주어야 한답니다.
    입력으로는 1~26, 27~52까지의 높이를 의미하는 A-Z, a-z로 이루어진 배열과, 높이 차이인 threshold, 제한 시간인 timeToDark가 들어옵니다.
    [spoiler="풀이보기"]DIV2지만 그래도 한번쯤 생각해봐야 하는 문제입니다.
    저는 Floyd 전쌍최단경로를 이용하였습니다.
    landspace를 인접배열방식으로 확장시켜서 한 지점에서 다른 점까지 갈 수 있는지 판단하면서 그래프를 만들어줍니다.
    이렇게 생성된 그래프에 Floyd 알고리즘을 적용하면 모든 쌍에 해당하는 최단 거리를 구하실 수 있습니다.
    그 후에 모든 쌍에 대해서 Graph[0][n] + Graph[n]0의 값이 timeToDark 이하인 것들 중에서 최고 높이를 찾아주시면 문제가 해결됩니다.
    처음에 그래프를 만드실 때 조금만 주의하시면 쉽게 해결하실 수 있을 거라 생각합니다.
    소스코드를 첨부하면 아래와 같은데

    int moveX[] = {1, -1, 0, 0 };
int moveY[] = {0, 0, 1, -1 };
class HillWalker { 
public: 
 int getHeight(char c)
 {
  if ( c >= 'A' && c <= 'Z' ) return (int)(c - 'A');
  else return (int)(c - 'a') + 26;
 }
  int highestPoint(vector <string> landscape, int threshold, int timeToDark) {  
  int y = landscape.size();
  int x = landscape[0].size();
  vector< vector<int> > map( x * y , vector<int> ( x * y , timeToDark) );
  int toX, toY;
  int range = 0;
  // make graph
  for(int i = 0 ; i < y ; i++)
  {
   for(int j = 0 ; j < x ; j++)
   {
    for(int k = 0 ; k < 4 ; k++)
    {
     toX = j + moveX[k];  toY = i + moveY[k];
     if( toX < 0 || toY < 0) continue;
     if( toX >= x || toY >= y) continue;      
     range = getHeight(landscape[i][j]) - getHeight(landscape[toY][toX]);
     if(abs(range) <= threshold)
     {
      if(range < 0) map[i*x+j][toY*x+toX] = range*range;
      else map[i*x+j][toY*x+toX] = 1;      
     }     
    }
   }
  }
  // process Floyd
  for(int i = 0 ; i < x*y ; i++)  map[i][i] = 0;
  for(int i = 0 ; i < x*y ; i++)
  {   
   for(int j = 0 ; j < x*y ; j++)
   {
    for(int k = 0 ; k < x*y ; k++)
    {
     map[j][k] = min(map[j][k], map[j][i] + map[i][k]);
    }
   }
  }
  //find max_height
  int max_height = -1;
  for (int i = 0; i < y; i++) {
   for (int j = 0; j < x; j++) {     
    if (map[0][i * x + j] + map[i * x + j][0] <= timeToDark)
    {     
     max_height = max(max_height, getHeight(landscape[i][j]));
    }
   }
  }
  return max_height;
 } 
}

    make graph 부분에서 floyd 알고리즘을 적용하기 위한 인접배열을 구현하는 방법과
    Floyd 알고리즘을 적용하는 부분을 중점적으로 보시면 되실 거라 생각합니다 ^^
    [/spoiler]
    그럼 새해 복 많이 받으세요~!~!!!!

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    16년 전
6개의 댓글이 있습니다.
  • helloneo
    helloneo

    음.. x, y가 각각 최대 25인데.. floyd로 구현했다면.. (25*25)^3 이 pass하네요.. -_-;;
    매치때 time limit 날까봐.. 생각도 못한 방법인데.. ㅠ_ㅠ


    16년 전 link
  • nocut98
    nocut98

    좀 빠르게 풀어볼려고 recursive하게 풀어봤는데, 최고 430ms 정도가 나오더군요... TLE나도 할말없는 시간... 후덜덜;;;
    25*25 배열이 꽤나 크네요;;; 코딩도 알고 짯는데도 500점 정도... 첨본 상태에서 짯으면 당연히 fail ...
    언제 1부리그로 올라갈지... @_@


    16년 전 link
  • 김우현
    김우현

    우왕 ㅋ 굿이에요!


    16년 전 link
  • JongMan
    JongMan

    TLE 는 2초인데요? ^^;; 최고 430ms 정도면 충분히 안전하다고 생각하는데..


    16년 전 link
  • Rada
    Rada

    이런 경우엔 구현하는 시간이 얼마 되지 않으니까 일단 코딩먼저 해보시는게 좋지 않을까 합니다.
    TLE가 나와도 몇몇 부분에서 최적화가 가능할지도 모르고, 그래프가 만들어져 있으니까 다른 알고리즘을 적용하기도 비교적 쉽지 않을까요?


    16년 전 link
  • nocut98
    nocut98

    그러게요. 이러면서 하나씩 배우네요 ^^


    16년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.