[editorial] SRM 436 DIV 1

  • Toivoa
    Toivoa

    SRM 392에서 0점맞고 에디토리얼 쓰고 1년만에 SRM 에디토리얼 쓰는 Toivoa 입니다.
    개인적으로는 TopCoder 시작한지 5년만에 레드를 찍은 SRM이었습니다.
    srm436.png
    결과는 위와 같았습니다. 한국인 중에 Hard를 푼 사람이 아무도 없었습니다.
    [Easy - BestView]
    직선 위에 건물들이 있습니다. 건물의 높이가 주어지고, 어떤 건물의 옥상에서 다른 건물들의 옥상이 몇개나 보이는지 알아내는 문제입니다.
    [spoiler="해설"]저는 어떤 건물의 옥상에서 다른 건물의 옥상이 몇개나 보이는지는 해당 건물을 중심으로 앞/뒤로 보면서 tangent 값 - (높이 차이) / (거리) - 이 줄어드는 건물이 몇개 있는지 세어보면서 풀었습니다.
    이 외에도 ccw를 이용해서 세어보는 등의 방법이 존재합니다.

    #include <vector> 
#include <algorithm> 
using namespace std; 
class BestView 
{ 
public: 
int numberOfBuildings(vector<int> heights) 
{ 
  int ret = 0; 
  int n = heights.size(); 
  for (int i = 0; i < n; ++i) 
  { 
    int t = 0; 
    double x = 1e+100; 
    for (int j = i - 1; j >= 0; --j) 
    { 
      double k = double(heights[i] - heights[j]) / double(i - j); 
      if (x > k) 
      { 
        t++; 
        x = k; 
      } 
    } 
    x = 1e+100; 
    for (int j = i + 1; j < n; ++j) 
    { 
      double k = double(heights[i] - heights[j]) / double(j - i); 
      if (x > k) 
      { 
        t++; 
        x = k; 
      } 
    } 
    ret >?= t; 
  } 
  return ret; 
} 
};

    [/spoiler]
    [Med - DoNotTurn]
    N*N의 정사각형으로 구성된 미로가 있습니다. (0, 0)에서 시작해서 (N - 1, N -1)의 위치로 가야 하는데, 최소한의 turn을 하는 것이 목표입니다.
    [spoiler="해설"]문제에서는 pseudo-random으로 미로를 구성하도록 되어 있습니다. 문제를 제대로 읽지 않고, 미로를 구성하는 단계를 잘못 구현해서 삽질을 많이 했습니다.
    미로를 구성한 후에는 전형적인 BFS 문제가 됩니다.
    저는 위치와 방향을 queue에 넣고, 해당 방향으로 쭉 가보면서 turn을 하는 경우를 queue에 넣는 식으로 구현하였습니다. 만약 deque를 이용한다면 진행은 deque의 앞에 넣고, 방향 전환은 deque의 뒤에 넣는 식으로 구현할 수도 있습니다. (이 방법은 Astein님의 소스코드를 참조하세요)

    #include <algorithm> 
#include <queue> 
using namespace std; 
typedef long long ll; 
int table[500][500]; 
int tx[500][500][4]; 
int visit[500][500][4]; 
int arr[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; 
struct in_que 
{ 
  int x, y, z; 
}; 
class DoNotTurn 
{ 
public: 
int go(int n) 
{ 
  queue<in_que> q; 
  in_que c, d; 
  visit[0][0][1] = visit[0][0][2] = 1; 
  c.x = 0; c.y = 0; c.z = 1; 
  q.push(c); 
  c.z = 2; 
  q.push(c); 
  while(!q.empty()) 
  { 
    c = q.front(); 
    q.pop(); 
    d.x = c.x; d.y = c.y; d.z = c.z; 
    while (1) 
    { 
      d.x += arr[c.z][0]; 
      d.y += arr[c.z][1]; 
      if (d.x < 0 || d.x >= n || d.y < 0 || d.y >= n || table[d.x][d.y]) break; 
      if (visit[d.x][d.y][c.z]) continue; 
      visit[d.x][d.y][c.z] = 1; 
      tx[d.x][d.y][d.z] = tx[c.x][c.y][c.z]; 
      if (d.x == n - 1 && d.y == n - 1) return tx[c.x][c.y][c.z]; 
      for (int i = 0; i < 4; ++i) 
      { 
        d.z = i; 
        if (visit[d.x][d.y][d.z]) continue; 
        visit[d.x][d.y][d.z] = 1; 
        tx[d.x][d.y][d.z] = tx[c.x][c.y][c.z] + 1; 
        q.push(d); 
      } 
    } 
  } 
  return -1; 
} 
int minimumTurns(int N, int X0, int A, int B, int Y0, int C, int D, int P, int M) 
{ 
  ll x0 = X0, y0 = Y0; 
  ll a = A, b = B, c = C, d = D, p = P; 
  if (M > 0) 
  { 
    x0 %= p; y0 %= p; 
    table[x0 % N][y0 % N] = 1; 
    for (int i = 1; i < M; ++i) 
    { 
      x0 = (x0 * a + b) % p; 
      y0 = (y0 * c + d) % p; 
      table[x0 % N][y0 % N] = 1; 
    } 
  } 
  table[0][0] = table[N - 1][N - 1] = 0; 
  return go(N); 
} 
};

    [/spoiler]
    [Hard - CircularShifts]
    같은 길이를 가지는 두 수열 x, y가 있습니다. 두 수열을 임의로 circular shift 하여 x[0] * y[0] + x[1] * y[1] + ... + x[n - 1] * y[n - 1] 의 최대 값을 구해야 합니다.
    수열을 circular shift한다는 것은 x'[0] = x[1], x'[1] = x[2], ... x'[n - 1] = x[0] 입니다.
    이 문제의 풀이는 JongMan님이 알고계십니다.

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

    15년 전
2개의 댓글이 있습니다.