안녕하세요 Toivoa 입니다.
개인적으로는 Submit도 못해보고 0점맞은 뜻깊은 SRM이었습니다. ㅠㅠ (지못미 rating)
다음번에는 한국인 중 1등으로 editorial 쓸 수 있기를 바라면서 써봅니다. :D

Easy (250 pts.)

• 문제 설명 wildcard ('*')가 하나 포함된 string이 두 개 주어질 때, 두 문자열을 모두 만족하는 가장 짧은 문자열을 찾는 것입니다. wildcard는 null로 치환할 수 있습니다. 예를 들어 TO*CODER와 TOPCOD*ER가 주어진다면 TOPCODER가 됩니다. [spoiler="더 보기..."]
• 문제 해법 문제에서 wildcard가 하나라고 되어 있으니 다른 많은 방법이 있겠지만, wildcard의 개수에 구애받지 않는 DP로도 풀 수 있습니다. 여기에서는 DP로 설명하겠습니다. 먼저 첫 번째 string을 s1, 두 번째 string을 s2라 할 때, table[x][y] : s1에서 처음부터 x개, s2에서 처음부터 y개의 문자열을 이용해서 만들어지는 가장 짧은 string의 길이 로 정의합니다. 이렇게 정의한 table에서 table[0][0] = 0 이 되며, table[0][k], table[k][0] = inf 가 되는 것은 쉽게 알 수 있습니다. 이 table을 채워나갈 수 있는 방법은 다음 6가지 경우가 있습니다.
• s1[x]와 s2[y]가 모두 wild card인 경우, table[x + 1][y + 1] = table[x][y] 가 됩니다. (여기에서 s1[x], s2[y]는 0-based입니다.) -> 양쪽 다 wildcard이니 글자를 더 추가하지 않아도 됩니다.
• s1[x] == s2[y]인 경우, 혹은 s1[x]가 wildcard인 경우, 또는 s2[y]가 wildcard인 경우. table[x + 1][y + 1] = table[x][y] + 1 이 됩니다. -> 둘 다 같은 글자이니 대각선 위에서 뒤에 한 글자 추가해서 내려올 수 있습니다. -> 둘 중 하나가 wildcard이니 대각선 위에서 wildcard가 아닌 쪽의 한 글자를 추가해서 내려올 수 있습니다.
• s1[x]가 wildcard인 경우 table[x + 1][y + 1] = table[x][y + 1] 이 됩니다. -> 이 경우는 s1[x]의 wildcard를 null로 치환하는 형태입니다.
• s1[x]가 wildcard인 경우 table[x + 1][y + 1] = table[x + 1][y] + 1 이 됩니다. -> wildcard에 s2[y]를 추가하는 형태입니다.
• s2[y]가 wildcard인 경우 table[x + 1][y + 1] = table[x][y + 1] + 1 이 됩니다.
• s2[y]가 wildcard인 경우 table[x + 1][y + 1] = table[x + 1][y] 이 됩니다. -> 5, 6은 3, 4와 같은 형태입니다. 위 경우에서 table[x + 1][y + 1]이 가장 작은 수가 되는 경우를 취하면 되고, 리턴 문자열은 경로를 기억해 두었다가 역추적하면 됩니다. 그런데 이렇게만 하면 맨 앞에 wildcard가 있는 경우는 제대로 처리하지 못합니다. 이 때는 table[1][0] = 0 과 같은 형태로 초기값을 넣어주면 됩니다. 여기까지 이해하셨다면 이유는 쉽게 아실 수 있으리라 믿습니다. ^^ ~~~ cpp

int table[100][100];
int from[100][100];
const int INTMAX = 1000000000;
class TwoStringMasks
{
public:
string shortestCommon(string s1, string s2)
{
int l1 = s1.length(), l2 = s2.length();
int i, j;
for (i = 0; i <= l1; i++) for (j = 0; j <= l2; j++) table[i][j] = INTMAX;
table[0][0] = 0;
if (s1[0] == '*') table[1][0] = 0;
if (s2[0] == '*') table[0][1] = 0;
for (i = 0; i < l1; i++)
{
for (j = 0; j < l2; j++)
{
if (s1[i] == '*' && s2[j] == '*')
{
table[i + 1][j + 1] = table[i][j];
from[i + 1][j + 1] = 0;
}
if (s1[i] == s2[j] || s1[i] == '*' || s2[j] == '*')
{
if (table[i + 1][j + 1] > table[i][j])
{
table[i + 1][j + 1] = table[i][j] + 1;
from[i + 1][j + 1] = 1;
}
}
if (s1[i] == '*')
{
if (table[i + 1][j + 1] > table[i][j + 1])
{
table[i + 1][j + 1] = table[i][j + 1];
from[i + 1][j + 1] = 2;
}
if (table[i + 1][j + 1] > table[i + 1][j] + 1)
{
table[i + 1][j + 1] = table[i + 1][j] + 1;
from[i + 1][j + 1] = 3;
}
}
if (s2[j] == '*')
{
if (table[i + 1][j + 1] > table[i][j + 1] + 1)
{
table[i + 1][j + 1] = table[i][j + 1] + 1;
from[i + 1][j + 1] = 4;
}
if (table[i + 1][j + 1] > table[i + 1][j])
{
table[i + 1][j + 1] = table[i + 1][j];
from[i + 1][j + 1] = 5;
}
}
}
}
if (table[l1][l2] >= INTMAX) return "impossible";
int x = l1, y = l2;
char cc[1000];
int pos = 0;
while (x >= 0 && y >= 0)
{
char c = '*';
if (from[x][y] == 0)
{
x--; y--;
continue;
}
else if (from[x][y] == 1)
{
c = s1[x - 1];
if (c == '*') c = s2[y - 1];
x--; y--;
}
else if (from[x][y] == 2)
{
x--;
}
else if (from[x][y] == 3)
{
c = s2[y - 1];
y--;
}
else if (from[x][y] == 4)
{
c = s1[x - 1];
x--;

}
else if (from[x][y] == 5)
{
y--;
}
if (c != '*') cc[pos++] = c;
}
cc[pos] = 0;
reverse(cc, cc + pos);
return cc;
}
};
[/Code]
[/spoiler]

Medium (500 pts.)

• 문제 설명 1 부터 N까지의 번호를 가진 N개의 cell이 원형(시계방향)으로 배열되어 있으며, cell 위에는 token들이 있습니다. 당신은 이 cell들 중 하나를 선택해서 얻을 수 있는 token의 개수를 최대로 하려 합니다. 현재 어떤 cell이 선택되어 있을 때, 현재 cell의 번호를 이루는 숫자들의 합 만큼 시계방향으로 이동한 cell이 다음으로 선택됩니다. 예를 들어 cell의 개수가 4인 경우 1번 cell에서는 2번, 2번에서는 4번, 3번에서는 2번, 4번에서는 4번 cell이 다음으로 선택되는 cell이 됩니다. [spoiler="더 보기..."]
• 문제 해법 선택되는 cell들을 따라가다 보면 cycle이 생기게 됩니다. 이 때 cycle 위에 있는 cell들을 맨 처음에 선택한다면 cycle의 길이만큼의 token을 얻게 됩니다. 만약 cycle을 이루지 않는 cell을 처음 선택한다면 다음 선택되는 cell에서 얻을 수 있는 token의 개수 + 1개를 얻게 됩니다. 따라서 cell들을 따라가다가 cycle을 찾으면 계산해서 돌아오는 식으로 쉽게 풀 수 있습니다. 아래 코드는 이를 비재귀로 구현한 코드입니다. [code cpp] int sz[200000]; int vec[200000]; int lv[200000]; int used[200000]; class RoundAboutCircle { public: int getMovnum(int t) { int ret = 0; while (t != 0) { ret += t % 10; t /= 10; } return ret; } void calc(int t, int N) { int p = 0, rz = 2147483647; vec[p] = t; used[t] = 1; lv[t] = p + 1; while (1) { t += getMovnum(t + 1); t %= N; vec[++p] = t; if (used[t]) { if (lv[t] != 0) { // cycle int ln = p - lv[t] + 1; for (int i = 0; i < ln; i++) { sz[vec[p--]] = ln; lv[vec[p]] = 0; } } break; } lv[t] = p + 1; used[t] = 1; } while (p > 0) { int nex = vec[p]; int now = vec[p - 1]; sz[now] = sz[nex] + 1; lv[now] = 0; --p; } } int maxScore(int N) { int ret = 0, i; fill(used, used + N, 0); for (i = 0; i < N; i++) { if (used[i] == 0) calc(i, N); ret >?= sz[i]; } return ret; } };

[/spoiler]




Hard (1000 pts.)

* 문제 설명
어떤 수 x가 equidigit라는 것은 x를 이루는 숫자들의 개수의 합이 모두 같은 것을 의미합니다. (물론 leading zero는 없습니다.)
예를 들어 5, 239, 333888, 566353이 equidigit가 됩니다.
어떤 수 n이 주어졌을 때 n 이상인 가장 작은 equidigit를 찾는 것이 문제입니다.
[spoiler="더 보기..."]
* 문제 해법
1. 이 문제에서 답은 주어진 n의 자리수를 증가시키지 않습니다. (같은 자리수로 모두 9로만 채우면 equidigit가 됩니다.)
2. 이 성질을 이용해서 사용할 수 있는 숫자의 가지수를 찾을 수 있습니다. (자리수 % 가지수 == 0인 경우)
3. 자리수와 숫자의 가지수가 결정되면 답이 될 수 있는 후보는 백트래킹으로 간단히 찾을 수 있습니다.
4. 후보들 중에서 가장 작은 수가 답이 됩니다.
~~~ cpp

typedef long long ll;
int ln;
const ll MAXDIGIT = 9223372036854775807LL;
int used[10];
int seld[10];
int uval[10];
class EquiDigitNumbers
{
public:
ll solve(ll now, int lv, const string& n, const int vals, const int uselimit)
{
 int i, j;
 if (lv == ln) return now;
 for (i = n[lv] - 48; i < 10; i++)
 {
  // can use
  if (i != n[lv] - 48)
  { // any numbers
   for (j = 0; j < vals; j++)
   {
    if (uval[j] == i) break;
    if (uval[j] == -1)
    {
     seld[i] = 1;
     uval[j] = i;
     break;
    }
   }
   if (j == vals) continue;
   if (used[i] == uselimit) continue;
   used[i]++;
   lv++;
   for (j = 0; j < vals; j++)
   {
    if (uval[j] == -1)
    {
     for (int k = 0; k < 10; k++)
     {
      if (seld[k] == 0)
      {
       seld[k] = 1;
       uval[j] = k;
       break;
      }
     }
    }
   }
   now = now * 10 + i;
   while (lv != ln)
   {
    for (j = 0; j < 10; j++)
    {
     if (seld[j] && used[j] < uselimit)
     {
      now = now * 10 + j;
      used[j]++;
      lv++;
      break;
     }
    }
   }
   return now;
  }
  else
  {
   for (j = 0; j < vals; j++)
   {
    if (uval[j] == i) break;
    if (uval[j] == -1)
    {
     seld[i] = 1;
     uval[j] = i;
     break;
    }
   }
   if (j == vals) continue;
   if (used[i] == uselimit) continue;
   used[i]++;
   ll t = solve(now * 10LL + i, lv + 1, n, vals, uselimit);
   if (t != MAXDIGIT) return t;
   used[i]--;
   if (used[i] == 0) 
   {
    seld[i] = 0;
    for (j = 0; j < vals; j++)
    {
     if (uval[j] == i) uval[j] = -1;
    }
   }
  }
 }
 return MAXDIGIT;
}
ll findNext(string n)
{
 int i;
 ll ret = MAXDIGIT;
 ln = n.length();
 for (i = 1; i <= 10; i++)
 {
  if (ln % i == 0)
  {
   fill(uval, uval + i, -1);
   fill(used, used + 10, 0);
   fill(seld, seld + 10, 0);
   ret <?= solve(0, 0, n, i, ln / i);
  }
 }
 return ret;
}
};

[/spoiler]