일단 레이팅 변화만 올려둡니다. 언제나처럼 Top 9 [?] 과 상위 150등 안에 든 한국인들만 잘랐습니다.
(그림판이 맛이 가서 우울하네요)

P.S) lewha0님이 Red가 되셨습니다 축하해여 +_+

Easy (250 pts.)

• 문제 설명 어떤 자연수 n이 주어졌다. n을 prefix로 하는 "0이 아닌 n의 각 자리수"로 나누었을 때의 나머지가 모두 0인 자연수 중 최소값을 구하여라. [spoiler="더 보기..."]* 풀이 우선 이 문제는 1 ~ 9 까지 모든 숫자의 LCM이 2520이기 때문에, 최대 4자리만 추가하면 항상 그 안에 답이 존재한다는 것을 "비둘기 집의 원리"에 의해 증명할 수 있습니다. 1번 풀이] D자리 추가한다고 가정했을 때, 0 ~ 10^D - 1을 뒤에 붙인 수가 각 자리수를 나누어 떨어지는지를 검사한다. 2번 풀이] 우선 LCM을 구한 다음, D자리 추가한다고 가정했을 때 범위 안에 LCM으로 나누어 떨어지는 수가 있는지를 modular를 이용하여 O(1)에 구한다. 그런데 처음에 증명했던 것과 같이 LCM이 매우 작기 때문에 1번 풀이를 사용해도 얼마든지 간단하게 구할 수 있습니다. 만약에 LCM이 매우 큰 수였다면 2번 풀이를 이용해야했겠지요. 아래에 1번 풀이를 사용해서 작성한 제 소스코드를 첨부합니다. ~~~ cpp

int flag[10];
bool go(string s) {
long long now;
sscanf(s.c_str(), "%Ld", &now);
for (int i = 1; i <= 9; i++)
if (flag[i] && now % i != 0) return false;
return true;
}
struct DivisibleByDigits {
long long getContinuation(int n) {
string s = toString(n);
REP(i, sz(s)) flag[s[i] - '0'] = 1;
long long ret, P = 1;
for (int digit = 0; ; digit++) {
for (int i = 0; i < P; i++) {
string tmp = toString(i);
tmp = string(digit - sz(tmp), '0') + tmp;
if (go(s + tmp)) {
sscanf((s + tmp).c_str(), "%Ld", &ret);
return ret;
}
}
P = P * 10;
}
return ret;
}
};

# 지정된 언어 [/spoiler]를 찾을 수 없습니다.
Medium (500 pts.)

* 문제 설명
  당신은 날짜를 입력하는 작업을 하고 있다. 하지만 어제 밤에 술을 너무 많이 마셨기 때문인지 오타가 종종 발생하기도 한다. 그래도 그나마 다행인 사실은, 아무리 술에 취해 있다고는 하지만, 키보드를 누른 횟수는 절대로 틀리지 않는다. 아래에 키보드 그림을 보자.
<IMG height=300 src="http://www.topcoder.com/contest/problem/DateFieldCorrection/keyboard.gif" width=643 border=0 editor_component="image_link">
  위의 그림에서 빨간색 Edge는 1만큼 떨어져 있음을 의미하고, 녹색 Edge는 3만큼 떨어져 있음을 의미한다.
  우리는 이제 penalty를 정의할 수 있다. 만약 올바른 키를 입력하였다면 penalty가 0이다. 하지만 오타가 발생하였을 경우에는 "두 key 사이의 거리" 만큼의 penalty를 받게 된다.
  input string과 correct date가 같은 길이라면, 두 string사이의 penalty의 합을 구할 수 있다. 이를 Distance 라고 하자.
  input string이 주어졌을 때, Distance를 최소로 하는 correct date를 구하시오. 만약 답이 여러 개 있을 경우, 제일 이른 날짜를 출력한다. 그리고 이 문제의 달력은 윤년을 기준으로 하기 때문에 2월 29일도 valid date로 본다.
[spoiler="더 보기..."]* 풀이
  우선 두 key 사이의 거리를 구해야 합니다. 제일 단순무식한 방법으로 짠다면 모든 Edge를 직접 typing하는 방법이 있지만, 그렇게 하면 실수를 할 수도 있기 때문에 별로 추천하지는 않습니다. 저는 키보드를 string 배열에 그려넣고, 이 배열을 이용하여 Edge를 만들었습니다. (자세한 내용은 소스 코드를 참조하시면 됩니다.) 그래프를 만들 때 주의하실 점이 두 가지 있는데, "녹색 Edge의 거리는 3" 이라는 사실과, "Z와 space bar는 연결되어 있지 않다" 입니다.
  일단 그래프를 만들었으면 각 key 사이의 최단거리를 구합니다. N이 작기 때문에 Floyd-Warshall 알고리즘을 사용하면 간단하게 코딩할 수 있지요. :-)  이제 남은 일은 1월 1일부터 12월 31일까지 모든 경우에 대해 Distance를 구하고, Distance를 최소로 하는 correct date를 구하면 됩니다.
~~~ cpp

string M[12] = {"January", "February", "March", "April", "May", "June", 
"July", "August", "September", "October", "November", "December"}; 
int month[12] = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; 
string keyb[4] = {"  1 2 3 4 5 6 7 8 9 0   ",  
                  "   Q W E R T Y U I O P  ", 
                  "    A S D F G H J K L   ", 
                  "     Z X C V B N M      "}; 
int graph[128][128]; 
int go(string a, string b) { 
  int ret = 0; 
  REP(i, sz(a)) { 
    ret += graph[a[i]][b[i]]; 
  } 
  return ret; 
} 
string toUpper(string s) { 
  REP(i, sz(s)) 
    if (s[i] >= 'a' && s[i] <= 'z') s[i] -= 32; 
  return s; 
} 
struct DateFieldCorrection { 
  string correctDate(string input) { 
    string ret; 
    int mini = 987654; 
    memset(graph, -1, sizeof(graph)); 
    char c1, c2; 
    /* construct graph */ 
    for (int i = 0; i < 3; i++) { 
      for (int j = 0; j < sz(keyb[i]); j++) { 
        if (keyb[i][j] != ' ') { 
          c1 = keyb[i][j]; 
          c2 = keyb[i + 1][j - 1]; 
          if (c2 != ' ') graph[c1][c2] = graph[c2][c1] = 1; 
          c2 = keyb[i + 1][j + 1]; 
          if (c2 != ' ') graph[c1][c2] = graph[c2][c1] = 1; 
        } 
      } 
    } 
    for (int i = 0; i < 4; i++) { 
      for (int j = 0; j < sz(keyb[i]) - 2; j++) { 
        if (keyb[i][j] != ' ') { 
          c1 = keyb[i][j]; 
          c2 = keyb[i][j + 2]; 
          if (c2 != ' ') graph[c1][c2] = graph[c2][c1] = 1; 
        } 
      } 
    } 
    string tmp = "XCVBNM"; 
    for (int i = 0; i < 6; i++)  
      graph[tmp[i]][' '] = graph[' '][tmp[i]] = 3; 
    /* floyd-warshall algorithm, don't forget sequence of I, J, K */ 
    for (int i = 0; i < 128; i++) 
      for (int j = 0; j < 128; j++) { 
        if (graph[j][i] == -1) continue; 
        for (int k = 0; k < 128; k++) { 
          if (graph[i][k] == -1) continue; 
          if (graph[j][k] == -1 || graph[j][k] > graph[j][i] + graph[i][k]) graph[j][k] = graph[j][i] + graph[i][k]; 
        } 
      } 
    for (int i = 0; i < 128; i++) 
      graph[i][i] = 0; 
    for (int i = 0; i < 12; i++) { 
      for (int j = 1; j <= month[i]; j++) { 
        tmp = M[i] + " " + toString(j); 
        if (sz(input) == sz(tmp)) { 
          int dist = go(toUpper(input), toUpper(tmp)); 
          if (mini > dist) { 
            mini = dist; 
            ret = tmp; 
          } 
        } 
      } 
    } 
    return ret; 
  } 
}; 

~~~[/spoiler]


Hard (1000 pts.)
* 문제 설명
  1000000x1000000크기의 체스판에 Duke가 한 마리 있다. duke는 위, 아래, 왼쪽, 오른쪽으로 한 칸 씩만 움직일 수 있다.
  각 좌표는 "(<Column number>, <Row number>)" 꼴로 표현한다. <Column number>, <Row number>는 6자리 숫자로, 예를 들어 (499999, 000000)과 (500000, 000000)은 제일 아래 라인의 가운데에 있는 두 cell의 좌표를 의미한다.
  duke의 path는 duke가 방문했던 cell 좌표들의 space로 구분 된 list로 표현할 수 있다. 예를 들어 "(444444, 600000) (444445, 600000) (444445, 599999)"  같은 경우에는 (444444, 600000)에 있던 duke가 오른쪽으로 한 번, 아래 쪽으로 한 번 이동했을 때의 path이다. path중 에서  같은 좌표를 두 번 이상 지나지 않는 path를 simple하다고 정의한다. 
  duke가 처음에 initPosition 에 있다고 가정했을 때, lexicographically greatest simple path를 구할 수 있다. 이 path에서 제일 마지막 cell의 좌표를 return하는 프로그램을 작성하시오. duke는 더 이상 움직일 수 없을때까지 이동한다.

[spoiler="더 보기..."]
* 풀이
  일단 풀어서 passed하긴 했는데, topcoder 홈페이지에 editorial이 나오면 그걸 이해하는 것이 더 나을지도 모르겠다는 생각이 듭니다. -_-; 
  제가 푼 알고리즘은, N이 짝수이고, 작은 경우에 대해 back-tracking으로 답을 구합니다. 그런 다음 테이블을 text 파일로 만들어서, 규칙을 찾은 다음에 각각의 규칙을 몇 가지 경우로 나누어서 경우에 대해 if ~ printf 를 사용하였습니다. 생각보다 경우가 많지 않기 때문에 소스코드도 아주 길지는 않네요 [........]
~~~ cpp

const int N = 1000000;
string GET(int X, int Y) {
 char tmp[20];
 sprintf(tmp, "(%06d, %06d)", X, Y);
 return tmp;
}
struct DukeOnLargeChessBoard {
 string lastCell(string initPosition) {
  int X = atoi(initPosition.substr(1, 6).c_str());
  int Y = atoi(initPosition.substr(9, 6).c_str());
  if (Y == N - 1) {
   if (X % 2 == 1) 
    return GET(0, N - 1); 
   else 
    return GET(0, N - 2 - X);
  }
  if (X == 0) return GET(0, Y + 1);
  if (X == N - 1) {
   if (Y % 2 == 0) 
    return GET(0, 0);
   else 
    return GET(N - Y, 0); 
  }
  if (Y == 0) {
   if (X % 2 == 0) 
    return GET(X - 1, 0);
   else
    return GET(0, 0);
  }
  if (Y == 1) return GET(N - 1, 0);
  if (X % 2 == 0 && Y == N - 2) return GET(0, N - 1);
  if (X > Y && (X + Y) % 2 == 1) return GET(0, 0);
  if (X + 1 == Y && X % 2 == 1) return GET(0, 0);
  if (X % 2 == 1 && X < Y) return GET(0, Y - X - 1);
  if (X % 2 == 0 && X <= Y) return GET(0, Y - X + 1);
  if (Y % 2 == 0) return GET(X - Y - 1, 0);
  if (Y % 2 == 1) return GET(X - Y + 1, 0);
  return "-1";
 }
};

[/spoiler]