[editorial] TCO09 Round 1

  • 일루
    일루

    tco09r1.png
    이번에는 Round 1 에디토리얼입니다. 그래프가 없으면 나름 경쟁력이 있는 나나 되겠습니다...
    1650명 중에서 750명을 추리는 대회였습니다.
    Easy(250pt, SequenceSums)
    R1다운 상큼한 문제입니다; 길이 L 이상 100 이하의, 1씩만 증가하는 0 이상의 정수들의 수열의 합이 N이 되도록 하는 최소의 길이의 수열을 찾는 문제입니다.
    그냥 길이 L부터 100까지 돌면서, 각 길이마다 이 조건을 만족하는 수열이 있나 체크하면 됩니다. 시작 수를 a라고 하면, (a + (a+L-1)) * L / 2 = N이 되어야 하니, 2a+L-1 = 2N / L 이 되어야 하고, 2a = (2N/L+1-L)이 되어야겠죠. 2N이 L로 나누어 떨어져야 하고, 이 결과로 나온 2a가 0 이상의 짝수여야 하겠습니다. 그대로 구현하면 됩니다.

    #include <vector>
#include <string>
#include <queue>
#include <map>
#include <math.h>
#include <cmath>
#include <algorithm>
using namespace std;
class SequenceSums
{
  public:
  vector <int> sequence(int N, int L)
  {
    vector<int> res;
    for (int sz=L; sz<=100; sz++) {
      if ((2*N)%sz) continue;
      int a = (2*N)/sz+1-sz;
      if (a<0 || a%2) continue;
      a /= 2;
      for (int i=0; i<sz; i++)
        res.push_back(a+i);
      return res;
    }
    return res;
  };
};

    Medium(500pt, KthProbableElement)
    문제가 간단하니 같이 번역을 해봅시다.
    M integers are randomly independently chosen from the interval lowerBound...upperBound, inclusive. Return the probability that the K-th smallest element of the generated set is equal to N. K=1 refers to the smallest element, K=2 refers to the second smallest element, and so on.
    M개의 정수를 lowerBound 이상 upperBound 이하의 정수들 중에서 랜덤하게 독립적으로 고르자. 이 수들 중 K번째로 작은 수가 N이 될 확률을 리턴해라. K=1이면 가장 작은 원소, K=2면 두번째로 작은 원소, 등등을 뜻한다.
    제 경우에는 처음에는 조합론적으로 시도했는데, 생각보다 수식을 만들기가 쉽지 않았습니다. 결국 Dynamic Programming 방법으로 전환했습니다.
    아래 코드에서 prob1[a][b] = a개를 골랐을 때, N 이하의 수가 정확히 b개 골라질 확률입니다.
    prob2[a][b] = a개를 골랐을 때, N-1 이하의 수가 정확히 b개 골라질 확률입니다.
    prob1[a][b~a] 를 모두 합하면, a개를 골랐을 때, N 이하의 수가 b개 이상 골라질 확률이 됩니다. 다시 말하면, b번째로 작은 수가 N 이하인 확률이 됩니다.
    prob2[a][b~a] 를 모두 합하면, a개를 골랐을 때, N-1 이하의 수가 b개 이상 골라질 확률이 됩니다. 다시 말하면, b번째로 작은 수가 N-1 이하인 확률이 됩니다.
    결국 prob1[a][b~a] 에서 prob[a][b~a]를 빼면, b번째로 작은 수가 N인 확률이 나옵니다.

    #include <vector>
#include <string>
#include <queue>
#include <map>
#include <math.h>
#include <cmath>
#include <algorithm>
using namespace std;
double prob1[1001][1001] = {0};
double prob2[1001][1001] = {0};
class KthProbableElement
{
  public:
  double probability(int M, int lowerBound, int upperBound, int N, int K)
  {
    int p = upperBound-lowerBound+1;
    N = N - lowerBound + 1;
    prob1[0][0] = 1.0;
    for (int i=1; i<=M; i++)
      for (int j=0; j<=i-1; j++) {
        prob1[i][j+1] += prob1[i-1][j]*N/(double)p;
        prob1[i][j] += prob1[i-1][j]*(p-N)/(double)p;
      }
    prob2[0][0] = 1.0;
    for (int i=1; i<=M; i++)
      for (int j=0; j<=i-1; j++) {
        prob2[i][j+1] += prob2[i-1][j]*(N-1)/(double)p;
        prob2[i][j] += prob2[i-1][j]*(p-(N-1))/(double)p;
      }
    double res = 0.0;
    for (int i=K; i<=M; i++)
      res += prob1[M][i]-prob2[M][i];
    return res;
  };
};

    Hard(900pt, Unicorn)
    이 문제는 경우의 수를 세는 아주 전형적인 문제로, DP로 해결할 수 있습니다. 즉 cnt[a][b][c] = 단어의 a번째 글자까지 체크했고, 마지막 글자의 위치가 (b, c)일 때의 경우의 수 라고 하고요, cnt[a-1][...][...]에서 적절히 cnt[a][...][...] 를 구하는 식으로 해서 마지막에 cnt[단어사이즈-1][b][c] 를 모두 더한 수가 답이 됩니다.
    한 가지 문제는, cnt[a][b][c]를 구할 때, cnt[a-1][...][...]들을 더해야 하는데, 유니콘이 한 스텝에 움직일 수 있는 (2+, 3+), (3+, 2+)의 좌표들을 모두 고려하면, 판의 대부분의 칸들에 대해서 저 값을 더해야 한다는 것입니다. 그림을 그려보면, 다음 위치에서만 유니콘이 올 수가 없습니다 - x 좌표 차이가 1 이하이거나, y 좌표 차이가 1 이하이거나, x 좌표 차이와 y 좌표 차이가 모두 2인 경우.
    즉 (모든 위치에 대해서 합을 더한 값) - (x좌표 차이가 -1~1인 위치에 대해서 합을 더한 값) - (y좌표 차이가 -1~1인 위치에 대해서 합을 더한 값) + (x좌표 차이가 -1~1이고 y좌표 차이가 -1~1인 위치에 대해서 합을 더한 값) - (x좌표 차이가 2이고 y좌표 차이가 2인 위치에 대해서 합을 더한 값) 이 cnt[a][b][c] 가 됩니다. 여기서 '모든 위치에 대해서 합을 더한 값', 'x좌표가 i인 모든 위치에 대해서 합을 더한 값', 'y좌표가 j인 모든 위치에 대해서 합을 더한 값' 을 각 a에 대해서 한번만 계산하면, 이후의 계산을 O(1)로 할 수 있음을 알 수 있습니다.
    실제 코드 구현도 이렇게 되어 있으니 보시면 쉽게 이해가 되실 것이라 생각합니다.

    #include <vector>
#include <string>
#include <queue>
#include <map>
#include <math.h>
#include <cmath>
#include <algorithm>
using namespace std;
const int mmod = 1000000007;
long long cnt[300][300] = {0};
long long next[300][300] = {0};
char chessboard[300][300] = {0};
class Unicorn
{
  public:
  int countWays(int R, int C, int L, int seed, string word)
  {
    int px[13] = {-2, 2, -2, 2, -1, 0, 1, -1, 0, 1, -1, 0, 1};
    int py[13] = {-2, -2, 2, 2, -1, -1, -1, 0, 0, 0, 1, 1, 1};
    int mult[13] = {-1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
    {
      int x = seed;
      int d = (65535 / L)+1;
      for (int r=0; r<R; r++)
        for (int c=0; c<C; c++) {
          x = (x * 25173 + 13849) % 65536;
          chessboard[r][c] = 65+x/d;
        }
    }
    for (int i=0; i<R; i++)
      for (int j=0; j<C; j++)
        if (chessboard[i][j]==word[0]) cnt[i][j] = 1;
    for (int i=1; i<word.size(); i++) {
      char target = word[i];
      long long row_sum[300] = {0};
      long long column_sum[300] = {0};
      long long total = 0;
/*      for (int i=0; i<R; i++)
        for (int j=0; j<C; j++)
          printf("%lld ", cnt[i][j]); printf("n");*/
      for (int i=0; i<R; i++)
        for (int j=0; j<C; j++) {
          row_sum[i] = (row_sum[i] + cnt[i][j]) % mmod;
          column_sum[j] = (column_sum[j] + cnt[i][j]) % mmod;
          total = (total + cnt[i][j]) % mmod;
        }
      for (int i=0; i<R; i++)
        for (int j=0; j<C; j++) {
          next[i][j] = 0;
          if (target == chessboard[i][j]) {
            next[i][j] = total;
            if (i>0) next[i][j] -= row_sum[i-1];
            next[i][j] -= row_sum[i];
            if (i<R-1) next[i][j] -= row_sum[i+1];
            if (j>0) next[i][j] -= column_sum[j-1];
            next[i][j] -= column_sum[j];
            if (j<C-1) next[i][j] -= column_sum[j+1];
            for (int k=0; k<13; k++)
              if (i+py[k]>=0 && i+py[k]<R && j+px[k]>=0 && j+px[k]<C)
                next[i][j] += mult[k]*cnt[i+py[k]][j+px[k]];
            while (next[i][j]<0) next[i][j] += mmod;
            next[i][j] %= mmod;
          }
        }
      for (int i=0; i<R; i++)
        for (int j=0; j<C; j++)
          cnt[i][j] = next[i][j];
    }
    /*  for (int i=0; i<R; i++)
        for (int j=0; j<C; j++)
          printf("%lld ", cnt[i][j]); printf("n");*/
    long long res = 0;
    for (int i=0; i<R; i++)
      for (int j=0; j<C; j++)
        res = (res + cnt[i][j]) % mmod;
    return res;
  };
};

    <img src="http://www.topcoder.com/i/clear.gif" alt="" border="0" height="5" width="1">
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

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

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