우선 Standing입니다.

챌린지 하나에 힘입어 5등까지 올라갔네요. 150등 안에 한국인은 총 6명 있었습니다.
Writer가 누구인지는 모르겠지만, 250점짜리 (DIv 2 기준 500점 짜리) 문제의 solution이 틀렸던 것 같습니다. 최종 결과가 12시가 넘어서야 결정되었으니까요.
다음부터는 진행이 매끄럽게 되길 기대해 봅시다.
P.S) ainu7님이 250점짜리 문제 fastest 를 찍으셨습니다 +_+ 앞으로 JongMan님 과의 fastest 대결도 볼만하겠네요.
Division Two에서도 domeng님이 fastest를 찍으셨네요. 얼씨구~

Easy (250 pts.)

• 문제설명 큰 상자 안에 여러 색깔의 marble이 들어 있고, 각각의 색깔의 marble이 몇 개 씩 들어 있는지가 주어졌다. 이 상자에서 n개의 marble을 임의로 꺼낼 때, 꺼낸 marble이 모두 같은 색깔일 확률을 구하여라. 최대 50가지 색깔의 marble이 존재하며, n은 1 이상 전체 marble의 수 이하이다. 한 색깔당 최대 marble의 수는 50이다.

[spoiler="풀이 보러가기"]

• 해결방법 고등학교 수학시간에 배웠을 법한 확률문제입니다. 상자 안에 들어있는 전체 marble의 수를 S라고 하고, i번 색깔의 marble이 Ai개 있을 때, i번 색깔의 marble이 n개 나올 확률은 Combi(Ai, n) / Combi(S, n) 이 됩니다. (단, Ai >= n를 만족할 때) 이제 이 식을 가지고 모든 경우에 대해 확률을 구해 합한 결과를 return하면 해결할 수 있습니다. 조금 덧붙이자면, Combi(Ai, n) / Combi(S, n) 를 구하는 코드는 아래와 같이 작성할 수 있습니다. double tmp = 1.0; for (int j = A[i]; j > A[i] - n; j--) { tmp *= (double)j / (double)(S - A[i] + j); } ret += tmp; [/spoiler]

Medium (500 pts.)

• 문제설명 도시 A와 B는 distance만큼 떨어져 있다. 둘 사이를 잇는 직선 도로 상에 여러개의 '발신기(transmitter)'가 위치해 있다. 발신기 사이의 거리가 '발신기의 범위(transmission range)'보다 크지 않다면, 두 발신기는 직접 통신할 수 있다. 또한 발신기는 도시들과도 같은 조건으로 통신 가능하다. 각각의 발신기의 범위는 어떤 양의 정수값으로 나타낼 수 있고, 각 발신기의 범위는 같은 값을 가진다. 이미 두 도시 사이에 발신기가 설치되어 있다. 당신은 이 발신기를 옮길 수 있는데, k 만큼을 옮기기 위해서는 k 달러가 필요하다. 하지만 당신은 funds 달러 만큼의 돈을 가지고 있고, 이를 초과해서 사용할 수 없다. 또한 발신기는 항상 정수 거리 만큼만 움직일 수 있다. 발신기의 초기 위치와 초기에 가지고 있는 돈, 그리고 A와 B 사이의 거리가 주어졌다. 당신은 A와 B 사이에 통신이 가능하면서, '발신기의 범위'를 가능한 작게 만들고 싶다. 발신기의 수는 50개 이하, distance는 100 이하. funds는 10만 이하이다.

[spoiler="풀이 보러가기"]

• 해결방법 (발신기의 위치가 초기에 sort되어 있지 않습니다. 그래서 입력받자마자 sort해 주는 routine이 필요합니다. sort를 해 주지 않으면 아래에 정의한 부분해의 정의가 제대로 적용되지 않기 때문에 올바른 해를 구할 수가 없게 됩니다.) 발신기의 범위를 R이라고 했을 때, 필요한 최소 비용을 구해봅시다. 필요한 최소 비용은 동적계획법 (Dynamic Programming)으로 구할 수 있습니다. table의 정의는 아래와 같이 할 수 있습니다. table[i][j] = i번째 transmitter를 j에 배치할 때 필요한 최소 비용 [/spoiler] 위와 같이 테이블을 정의하면 아래와 같이 테이블을 갱신할 수 있습니다. [spoiler="더 보기..."] table[i][j] = MAX(table[i - 1][j - k]) + abs(j - position[i]) [ 단, k = 0 ~ min(j, R)이고, position[i]는 i번째 발신기의 위치. ] [/spoiler] 위의 점화식을 사용하여 테이블을 갱신하고, 마지막 발신기(도시 B)가 distance에 위치할 때의 최소 비용과 funds를 비교합니다. 만약 funds가 최소 비용보다 적다면 발신기의 범위가 R인 경우를 만들 수 없다는 말이 됩니다. 따라서 R을 증가시킨 다음 위의 과정을 반복합니다. N = 발신기의 수, M = distance라고 할 때, 발신기의 범위 R은 1부터 M까지 가능하므로 O(N*M^3)의 시간복잡도가 나옵니다. 또한 통과한 많은 솔루션은 위의 알고리즘에 binary search를 이용하여 해결한 경우가 많았습니다. 즉, 발신기의 범위 R을 binary search를 사용하여 lg M 시간만에 구합니다. binary search를 추가하여 풀면 시간복잡도는 O(N*M^2lg M)가 됩니다.

Hard (950 pts.)

• 문제설명 k개의 약수를 가지는 제일 작은 양의 정수를 구하시오. 만약 답이 10^18보다 크다면 -1을 리턴하시오. ( k <= 50000 )

[spoiler="풀이 보러가기"]

• 해결방법
  문제가 짧고 간결하여 이해하기가 쉽네요. 개인적으로 이런 문제 스타일을 매우 좋아합니다 :-)
  우선 이 문제를 풀려면 고등학교 수학이 필요하네요. N = p1^a1 * p2^a2 * p3^a3 ... * pn^an일 때 (∀pi = prime number, ai = 정수) N의 약수의 갯수는 (a1 + 1) * (a2 + 1) * ... * (an + 1) 이라는 식을 알아야 접근할 수 있습니다. (자세한 증명은 생략합니다.)
  950점 짜리 문제는 위의 식을 안다면 할 수 있는 생각이, k를 소인수 분해 하여 decreasing order로 sort하고, 2^X * 3^Y * ... 로 return하는 greedy approach 입니다. 문제에서 주어진 test case도 모두 통과하는 나름대로 괜찮은 솔루션이기도 합니다. 하지만 k = 8인 경우는 greedy를 사용하면 k = 2 * 2 * 2이므로, 2^1*3^1*5^1 = 30이 됩니다. 하지만 2^3*3^1 = 24도 역시 소수를 8개 가질 수 있으므로, greedy 알고리즘만 사용하는 경우 올바른 해를 구할 수 없습니다.
  대회 당시에는 Back-Tracking을 사용하여 풀었지만, Editorial에는 동적 계획법으로 쓰겠습니다. 전체적인 알고리즘은 같으나 Back-Tracking을 사용하면 이미 구했던 해를 다시 구해야 하기 때문에 비효율적입니다. (다만 Memoization을 사용한다면 그 만큼의 메모리 낭비는 어쩔 수 없습니다.)
  이 문제의 테이블 a[i][j]는 아래와 같이 정의합니다.
  a[i][j] = prime[i] 이상의 소수들을 사용하여 약수를 j 개 가지는 최소 정수. (만약 10^18보다 크다면 10^18+1을 저장)
  [/spoiler]
  아래에 소스코드를 첨부합니다. 주석을 열심히 달았다고 생각하는데... 혹시나 이해가 되지 않는 부분이 있으시다면 댓글로 남겨주세요. :-)
  [spoiler="더 보기..."]
  long long INF = 1000000000000000001LL; /* 10^18 + 1. long long type이기 때문에 숫자 뒤에 LL을 붙여야합니다. /
  long long a[17][50001]; / 저장할 테이블 /
  int prime[17] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,57}; / 소수 17개. 17개인 이유는 2^17 > 50000이기 떄문입니다. /
  struct NumberOfDivisors {
  long long go(int p, int K) {
  if (K == 1) return 1; / K가 1인 경우의 최적해는 1입니다. /
  if (a[p][K] != -1) return a[p][K]; / a[p][K]의 값이 갱신되어 있다면, 이 전에 구한 최적해를 return합니다. */

  long long ret = INF; /* ret는 return할 값. 즉 a[p][K] */
  long long tmp = 1; /* tmp에는 prime[p] ^ (i - 1)을 저장합니다. */
  
  for (int i = 2; i <= K; i++) {
      if (ret / prime[p] < tmp) break; /* ret < prime[p] ^ i일때는 i를 더 이상 증가시킬 수 없으므로 빠져나갑니다. */
      tmp *= prime[p]; /* tmp 갱신 */
  
      if (K % i == 0) { /* i가 K의 약수일 때 */
          long long next = go(p + 1, K / i); /* next는 K / i개의 약수를 prime[p + 1]이상의 소수들을 사용하여 만들 때의 최소 정수입니다.*/
          if (ret / tmp < next) continue; /* ret < next * tmp일 때, 즉 현재까지 구한 답이 더 좋은 경우 갱신시키지 않습니다. */
          ret = tmp * next; /* 현재까지의 답보다 좋다면 갱신해야 겠지요? */
      }
  }
  return (a[p][K] = ret); /* a[p][K] 테이블에 ret를 쓰고, 그 값을 return 합니다. */

  }
  long long smallestNumber(int k) {
  memset(a, -1, sizeof(a)); /* 테이블 초기화 /
  long long ret = go(0, k); / prime0 이상의 소수를 사용하여 K개의 약수를 가지는 경우의 최소값을 구합니다. /
  if (ret == INF) ret = -1; / 만약 최소값이 10^18 보다 크다면 -1을 리턴. */
  return ret;
  }
  };
  [/spoiler]

  [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]