A와 B번 문제에 대한 editorial입니다. C나 D는 다른 분이 써주실거라 기대합니다.
[A - Elegant Diamond]
어떤 다이아몬드가 우아하다(elegant)라고 하기 위해서는 다이아몬드의 특정 위치의 숫자(digit)가 다이아몬드의 중심선을 기준으로 수직으로 대칭인 부분의 숫자와 같아야 하며, 수평으로 대칭인 부분의 숫자와 같아야 합니다.
다이아몬드가 주어졌을 때 돈을 들여서 다이아몬드의 크기를 키울 수 있습니다. 다이아몬드를 키우는데 드는 비용은 (키우고 난 이후 다이아몬드를 이루는 숫자의 개수 - 기존 다이아몬드를 이루는 숫자의 개수) 입니다.

우아한 다이아몬드를 만들기 위한 최소의 비용을 구해야 합니다.

저는 배열 내에 다이아몬드 모양으로 입력받은 후에, 어떤 위치가 중점일 때 다이아몬드가 우아한지 체크해보는 방법을 이용하였습니다. 선택 가능한 중점은 입력받은 중점과 같은 중점을 기준으로 크기가 k * 2인 다이아몬드의 내부 전체입니다. 이렇게 체크해보면 모든 경우에 대해 체크할 수 있습니다. (다이아몬드의 크기가 k * 2가 되면 중점을 기준으로 한 사분면으로 모두 모을 수 있기 때문에 더 큰 범위에 대한 체크는 불필요합니다.)
아래는 소스코드입니다. 헤더 파일을 include 하는 부분은 생략했습니다.

int sz[500];
int table[500][500];
int k;
bool chk(int cx, int cy)
{
 int x = 240;
 for (int i = 1; i <= k; ++i)
 {
  int y = 240 - i;
  for (int j = 1; j <= i; ++j)
  {
   int px = x + 2 * (cx - x);
   int py = y + 2 * (cy - y);
   if (table[px][y] != -1 && table[px][y] != table[x][y])
    return false;
   if (table[x][py] != -1 && table[x][py] != table[x][y])
    return false;
   y += 2;
  }
  ++x;
 }
 for (int i = k - 1; i > 0; --i)
 {
  int y = 240 - i;
  for (int j = 1; j <= i; ++j)
  {
   int px = x + 2 * (cx - x);
   int py = y + 2 * (cy - y);
   if (table[px][y] != -1 && table[px][y] != table[x][y])
    return false;
   if (table[x][py] != -1 && table[x][py] != table[x][y])
    return false;
   y += 2;
  }
  ++x;
 }
 return true;
}
int main()
{
 int t, cases = 0;
 scanf("%d", &t);
 for (int i = 1; i < 500; ++i)
 {
  sz[i] = ((i * (i + 1)) + (i * (i - 1))) / 2;
 }
 while (t--)
 {
  fill(table[0], table[500], -1);
  scanf("%d", &k);
  int res = 10000000;
  int x = 240;
  for (int i = 1; i <= k; ++i)
  {
   int y = 240 - i;
   for (int j = 1; j <= i; ++j)
   {
    scanf("%d", &table[x][y]);
    y += 2;
   }
   ++x;
  }
  for (int i = k - 1; i > 0; --i)
  {
   int y = 240 - i;
   for (int j = 1; j <= i; ++j)
   {
    scanf("%d", &table[x][y]);
    y += 2;
   }
   ++x;
  }
  int cx = 240 + k - 1, cy = 239;
  x = 240 - k;
  for (int i = 1; i <= k * 2; ++i)
  {
   int y = 240 - i;
   int z = i * 2 - 1;
   for (int j = 1; j <= z; ++j)
   { // x, y is center
    int nk = abs(cx - x) + abs(cy - y) + k;
    if (chk(x, y))
    {
     res = min(res, sz[nk]);
    }
    ++y;   
   }
   ++x;
  }
  for (int i = k * 2 - 1; i > 0; --i)
  {
   int y = 240 - i;
   int z = i * 2 - 1;
   for (int j = 1; j <= z; ++j)
   { // x, y is center
    int nk = abs(cx - x) + abs(cy - y) + k;
    if (chk(x, y))
    {
     res = min(res, sz[nk]);
    }
    ++y;   
   }
   ++x;
  }
  printf("Case #%d: %d\n", ++cases, res - sz[k]);
 }
}

[B - World Cup 2010]
월드컵에 진출한 팀들의 경기 토너먼트가 있습니다. 각 경기의 입장권의 가격은 모두 다릅니다. (small input에서는 가격이 항상 1입니다.) Varva는 각 팀들에 대해 팀들이 치르게 되는 경기들 중 최대 M[i] 경기를 제외하고 모두 보려고 합니다. 이를 만족하면서 경기의 입장권을 사려고 할 때 필요한 최소의 비용은 얼마인지 구해야 합니다.

small input은 가격이 1이라는 것을 이용해서 결승전부터 아래로 보면서 greedy하게 선택하면 됩니다. 이것에 대해서는 자세한 설명과 소스 코드는 생략합니다.
저는 large input을 풀기 위해서 다음과 같은 점화식을 세워서 풀었습니다.
T[X, Y]: X번 경기까지 고려했을 떄 (X번 경기의 입장권을 사는지 여부는 중요하지 않습니다.) 이 경기와 관련된 팀들 중 반드시 보고 싶은 경기의 수가 최대 Y가 될 때의 최소 비용.
-> X번 경기를 고려했다는 것은 X번 경기 이하 라운드 (예를 들어 X번 경기가 결승전인 경우 모든 경기, 준결승전인 경우 해당 준결승전을 root로 하는 subtree)를 모두 고려했다는 것입니다.
-> 이렇게 할 때 결승전의 번호를 1번, 준결승을 2, 3번, 8강전을 4, 5, 6, 7번, ... 으로 하면 이진트리의 특성으로 바로 하위 경기의 번호를 쉽게 알 수 있습니다.
-> 각 팀에서 반드시 보고 싶은 경기의 수는 P - M[i]가 됩니다.
T를 위와 같이 정의하면서 가장 하위의 경기는 각 팀으로 합니다. 예를 들어서 문제의 그림에서 8번 경기는 아르헨티나, 9번 경기는 독일, ... 으로 힙니다.
그러면 초기화는 각 팀의 경기에서 반드시 보고 싶은 경기 수 (P - M[i]) 에 0을, 나머지는 INF로 채워주면 됩니다.
이후 T[X, Y]는 아래 값들의 최소값이 됩니다.

• min(T[X * 2, 0 ... Y] + T[X * 2 + 1, Y], T[X * 2, Y] + T[X * 2 + 1, 0 ... Y]) // X번 경기를 보지 않는 경우입니다.
• min(T[X * 2, 0 ... Y + 1] + T[X * 2 + 1, Y + 1], T[X * 2, Y + 1] + T[X * 2 + 1, 0 ... Y + 1]) + X번 경기의 가격 // X번 경기를 보는 경우입니다. 이 테이블을 다 채운 후 답은 T[1, 0]이 됩니다. ~~~ cpp

typedef long long ll;
#define INF 35184372088832LL
int s2[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192};
int vals[8192];
ll res[2048][12];
int cost[1024];
int main()
{
int t, cases = 0;
scanf("%d", &t);
while (t--)
{
int p;
scanf("%d", &p);
fill(teams[0], teams[1024], 0);
fill(res[0], res[2048], INF);
for (int i = 0; i < s2[p]; ++i)
{
scanf("%d", &vals[i]);
vals[i] = p - vals[i];
res[s2[p] + i][vals[i]] = 0;
}
for (int i = p - 1; i >= 0; --i)
{
for (int j = 0; j < s2[i]; ++j)
{
scanf("%d", &cost[s2[i] + j]);
}
}
for (int i = s2[p] - 1; i >= 1; --i)
{
for (int j = 0; j <= p; ++j)
{
const ll& js = res[i * 2][j];
if (js == INF) continue;
for (int k = 0; k <= p; ++k)
{
const ll& ks = res[i * 2 + 1][k];
if (ks == INF) continue;
int tx = max(j, k);
ll s = js + ks;
res[i][tx] = min(res[i][tx], s);
if (tx != 0)
res[i][tx - 1] = min(res[i][tx - 1], s + cost[i]);
}
}
}
printf("Case #%d: %I64d\n", ++cases, res[1][0]);
}

<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/65735">원문보기</a>]</div>