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

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

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

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] 경기를 제외하고 모두 보려고 합니다. 이를 만족하면서 경기의 입장권을 사려고 할 때 필요한 최소의 비용은 얼마인지 구해야 합니다.
<img src="http://code.google.com/codejam/contest/images/?image=wc2010.png&amp;p=698485&amp;c=635102" width="0" height="0" link_url="http://code.google.com/codejam/contest/images/?image=wc2010.png&amp;p=698485&amp;c=635102" editor_component="image_link" />
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]);
 }