안녕하세요, JM 입니다.
SRM428 은 무지 쉬운 easy 와 꽤나 어려웠던 medium, 그리고 코딩은 어렵지 않지만 precalc 를 제대로 해야 했던 안드로 hard 덕분에 안드로로 달려간 매치였습니다. 덕분에 한국인 전원은 모두 이지만 풀고 집단 사망... 250에 챌린지 하나로 96위에 올라간 helloneo 님, 250 레코드 하나만으로 -_-; 102위에 올라간 JongMan, 107위의 KooKyungryeol 이 한국 top3 이었습니다.
1등한 건 아니긴 한데, 너무 말린 관계로 가슴이 아파 반성하는 의미로 장문의 에디토리얼을 써 봅니다. 음훗
250 - TheLuckyString

문제 설명
문자열에서 같은 문자가 두 번 반복되는 일이 없을 때, 이 문자열을 Lucky String 이라고 합니다. 길이가 10 이하인 문자열 s 가 주어질 때, 이 문자열의 문자의 순서를 바꿔서 만들 수 있는 Lucky String 의 수는?
Key Insight
s의 문자열을 재배열할 수 있는 수 = 10! = 360만
해법
이런 문제를 보면 제일 먼저 10! 을 윈도우 계산기에서 계산해 봅시다. :) 3백만은 충분히 시간 안에 모든 문자열을 계산해 볼 수 있는 방법이죠. 재귀호출을 이용해 모든 문자열을 만들어 보면서 Lucky String 의 수를 셀 수 있습니다. 그게 아니라면, C++ STL 에 있는 next_permutation 을 쓸 수 있는데요, 이를 이용해 모든 문자열을 간단하게 만들 수 있습니다. 아래 코드처럼요.

struct TheLuckyString 
{
  int count(string s) 
  {
    int ret = 0;
    sort(s.begin(), s.end());
    do
    {
      bool ok = true;
      for(size_t i = 0; i < s.size(); ++i)
        if(s[i] == s[i+1])
        {
          ok = false; break;
        }
      if(ok) ++ret;
    } while(next_permutation(s.begin(), s.end()));
    return ret;
  }
};

500 - TheLongPalindrome

문제 설명

소문자 알파벳으로 구성된 palindrome 중, 길이가 n 이하이고, 사용된 알파벳의 개수가 k 이하인 것의 총 수는?
Key Insight

• 길이가 n 인 palindome 의 수 = 길이가 (n+1)/2 인 문자열의 수
• Matrix exponentation 해법

일단 가장 먼저 떠올려야 할 것은, 모든 palindrome 은 가운데를 반으로 쪼개서 길이가 (n+1)/2 인 문자열로 만들 수 있다는 거죠. 예를 들면 abcba => abc, abba => ab 이런 식으로 일대일 대응이 됩니다.
따라서, 길이가 (n+1)/2 인 문자열의 수 = 길이가 n 인 palindome 의 수가 됩니다.
오, 그러면 길이가 n 인 palindrome 의 수 C[n] 에 대한 closed formula 를 구할 수 있는 것 같아 보입니다.

let m = (n+1)/2, then C[n] = min(m, k)^m * P(26, min(m, k))

이 때 P(a, b) 는 a 개의 알파벳 중 b 개를 순서 고려해서 골라내는 경우의 수이죠. 이렇게 되면 좋겠다! 라고 생각해서 제가 대회때 삽질했습... orz 이렇게 세면, 중복이 생기게 되죠. 예를 들어, m = 2 이고 k = 2 이면, aa 라는 스트링은 P(26, 2) 번만큼 등장하게 됩니다.
이것을 저는 대회때 inclusion-exclusion 으로 극복해 보려 했지만, 흐흑... 쉽지 않더군요. :-p 따라서, 결론은 동적 계획법. n 이 작다고 가정하고 점화식을 만들어 봅니다.

C[a,b] = 길이가 a 이고, 모두 b 종류의 알파벳을 사용하는 palindrome 의 수

이 때, a-2 인 palindrome 의 가운데를 자르고 그 사이에 새 글자를 끼워넣는다고 생각하면

C[a,b] = C[a-2,b] * (26-b+1) + C[a-2,b-1] * (b-1)

임을 알 수 있습니다. (요거 유도하는 과정이 동적 계획법의 핵심이니, 직접 해보세용) 그런데, n 이 1백만도 아니고 10억이니 이대로 답을 구하긴 힘들겠죠. 따라서, 이 점화식의 값을 matrix exponentation 을 이용해 구해야 합니다.

matrix exponentation 을 이용한 동적 계획법을 모르시는 분을 위해 간략 설명 피보나치 수열을 생각해 봅시다. f[n] = f[n-1] + f[n-2]. f[102471423] 의 마지막 세 자리는 얼마일까요? 가장 straightforward 한 방법은 f[1] 부터 쭉 구해가는 것이겠습니다만.. 아무래도 너무 느리죠. 그런데, f[n] 을 이전 항들에 대해 선형 결합(linear combination) 으로 표현할 수 있다는 점에 착안하면 위의 관계식을 행렬로 나타낼 수 있습니다. 다음과 같이요. [ 0 1 ] [ f[a] ] [ f[a+1] ] [ 1 1 ] [ f[a+1] ] = [ f[a+2] ] 왼쪽은 2x2 의 행렬이고, 나머지는 2x1 의 열벡터라고 보죠. 그러면 위와 같은 식이 성립한다는 것을 알 수 있습니다. 왼쪽 행렬을 A 라고 두고, [ f[1] ] [ f[2] ] A [ f[2] ] = [ f[3] ] 이것을 일반화 해 보면 [ f[1] ] [ f[1+n] ] A^n [ f[2] ] = [ f[2+n] ] 가 됩니다. 행렬은 계산 순서를 달리 해도 결과는 항상 같죠. 따라서, 오른쪽부터 계산하는 대신 A^n 을 fast exponentation 을 이용해 O(logn) 번의 행렬 곱셈으로 구하면, O(2*2*2 * logn) 의 시간에 f[n] 을 구할 수 있게 됩니다.

이 점화식에서 n-2 가 등장하는 게 맘에 들지 않으니, 짝수와 홀수를 따로 계산한다고 생각해서 점화식을 다음과 같이 바꿉시다.

C[a,b] = C[a-1,b] * (26-b+1) + C[a-1,b-1] * (b-1)

그러면 이것은 C[a] 가 C[a-1] 의 선형 변환 (linear transformation) 으로 표현되므로, 역시 행렬로 표현해서 다음과 같이 쓸 수 있습니다: C[a] = T * C[a-1]
이 행렬 T 는 다음과 같은 원소를 가져야 합니다.
C[b,b] = (26-b+1)
C[b,b-1] = (b-1)
나머지는 모두 0
왜 이런지는 위 점화식에서 쉽게 알 수 있죠. ^^; 그러면
[1 ]
[0 ]
T^((n+1)/2) * [..]
[..]
[..]
[..]
를 계산하면 이 벡터의 k번째 원소 = 길이가 n 이고 k 개의 알파벳을 사용하는 palindrome 의 수 가 됩니다. 여기까지 왔으면 거의 다 왔구나! 하겠지만 여전히 관문이 하나 남아 있습니다. (이 문제 캐 어렵네효...) 길이가 n 인 palindrome 의 수를 구하는 게 아니라, n 이하인 palindrome 의 수를 모두 구해야 하니까요. 따라서
T * v + T * v +
T^2 * v + T^2 * v +
T^3 * v + T^3 * v +
..
T^n * v
를 구해야 하죠. 그런데, 다행히도 T + T^2 + T^3 + .. + T^n 은 분할 정복으로 쉽게 구할 수 있습니다. T 가 짝수라면,
T + T^2 + T^3 + .. T^n
= (T + T^2 + .. + T^(n/2)) + (T^(n/2)+1 + .. + T^n)
= (T + T^2 + .. + T^(n/2))
+ (T + T^2 + .. + T^(n/2)) * T^(n/2)
이니까요. 따라서, 다음과 같은 코드로 이를 구현할 수 있습니다.

// returns a+a^2+a^3+..+a^b
matrix matexpsum(const matrix& a, int b)
{  
  // b = 0 이라면 텅 빈 행렬
  if(b == 0) return matrix(a.size(), a.size());
  // 홀수라면 별도처리
  if(b % 2) return a * (identity(a.size()) + matexpsum(a, b-1));
  int half = b/2;
  // a+a^2+..+a^half
  matrix first = matexpsum(a, half);
  // 뒷쪽 절반
  matrix second = first * matexp(a, half);
  return first + second;
}

따라서, 위와 같은 행렬 T 를 만들어 준 뒤, matexpsum 으로 T + T^2 + T^3 + .. + T^(n+1)/2 를 구한 뒤, 이것을 [1 0 0 .. 0] 에 곱해 준 다음, 벡터의 모든 원소를 더하면 답을 구할 수 있습니다.... orz
너무 긴 설명에 비해, 짧은 소스 코드 나갑니다.

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const ll M = 1234567891;
typedef vector > matrix;
matrix operator * (const matrix& a, const matrix& b)
{  
  // 생략
}
matrix operator + (const matrix& a, const matrix& b)
{
  // 생략
}
// returns an identity matrix of given size
matrix identity(int size)
{
  matrix ret(size, size);
  for(int i = 0; i < size; ++i)
    ret[i][i] = 1;
  return ret;
}
// returns a^b
matrix matexp(const matrix& a, int b)
{
  matrix ret = identity(a.size());
  matrix unit = a;
  while(b > 0)
  {
    if(b % 2) ret = ret * unit;
    b /= 2;
    unit = unit * unit;
  }
  return ret;
}
// returns a+a^2+a^3+..+a^b
matrix matexpsum(const matrix& a, int b)
{
  if(b == 0) return matrix(a.size(), a.size());
  // 홀수라면 별도처리
  if(b % 2) return a * (identity(a.size()) + matexpsum(a, b-1));
  int half = b/2;
  // a+a^2+..+a^half
  matrix first = matexpsum(a, half);
  // 뒷쪽 절반
  matrix second = first * matexp(a, half);
  return first + second;
}
struct TheLongPalindrome 
{
  int count(int n, int k) 
  {
    k = min(k, (n+1)/2);
    matrix T(k+1, k+1);
    for(int i = 1; i <= k; ++i)
    {
      T[i][i] = i;
      T[i][i-1] = (26 - i + 1);
    }
    matrix even = matexpsum(T, n/2);
    matrix odd = matexpsum(T, (n+1)/2);
    ll ret = 0;
    for(int c = 1; c <= k; ++c)
    {
      ret = (ret + even[c][0]) % M;
      ret = (ret + odd[c][0]) % M;
    }
    return ret;
  }
};

1000 - TheStringGame

문제 설명
X, O, L 로 구성된 16글자 이하의 문자열로 게임을 합니다. 두명이 번갈아가며, 게임판에 남아 있는 X 를 하나 선택해 O 나 L 중 하나로 바꿉니다. 이 때, 게임판에 연속되어 LOL 이 등장하게 되면 마지막 차례였던 사람이 게임에 승리합니다. 둘 중 어느 쪽이 게임에 이길까요? 각 사람은 이기면 이길 수 있는 턴 수를 최소로, 지면 지는 턴 수를 최대로 늘리려고 노력한다고 합시다.
Key Insight
3^16 = 43,046,721. 그러나, 단 한 개의 초기상태를 뺀 나머지 경우 X의 수는 모두 15 이하.
해법
일단 문제만 보면 이 문제는 전형적인 계산 게임, 그 중에서도 impartial 게임 문제입니다. 계산 게임은 게임판의 상태들이 DAG 를 그리는 경우에는 쉽게 DP 로 해결할 수 있지요. 하지만 이 문제는 상태의 개수가 너무 큽니다. X 16개로 게임이 시작하는 경우, 3^16 개의 상태가 존재할 수 있으니까요.
예제 입력의 마지막 예를 보면 힌트가 떠오릅니다. 가장 오래 걸리는 경우 X 16개 에 대해서 답이 나와 있으니까요. 여기서 떠올라야 할 것은 무얼까요? 예 바로 솔루션 하드코딩입니다!! XD
마지막 예제의 경우만을 빼면, 모든 게임판에서 X 는 15개 이하만 존재합니다. 이 경우, 3^15 개의 상태는 4백만 정도이므로 우리가 적절히 탐색할 수 있는 수준이죠. 따라서, 마지막 예제의 경우를 하드코딩하고, 나머지를 DP 로 해결하면 됩니다.
실제로 구현했을 경우, X가 15개 존재하는 경우에도 소스 코드가 좀 느릴 수 있습니다. 그런데, X가 15개 존재하는 게임판은 모두 33개밖에 없습니다. (X 15개인 판, X 16개인 판에 하나가 L 이나 O 로 바뀐 판) 따라서, 외부 컴파일러를 사용하는 참가자들은 이 33개에 대해 모두 답을 생성해 소스 코드에 붙여넣을 수 있습니다. (실제 대회에서 이 문제를 맞은 사람들은 다 이렇게 하곤 했구요. 외부 컴파일러 없는 사람은 어쩌란 말이냐! 라면.. 아래의 최적화 섹션을 참조하세요.)
DP 는 비교적 평이하지만, 몇 가지 까다로운 점이 있습니다.
1. 상태가 길이가 n 인 3진수로 표현되기 때문에 게임의 승패 판정을 하려면 나눗셈을 하는 등의 삽질을 해야 합니다. 반면, 현재 게임판의 string 표현을 memoization 함수에 같이 넣어 주면 판단이 훨씬 쉬워지므로 좋습니다.
2. 이기면 턴 수를 최소로, 지면 턴 수를 최대로 한다는 것이 좀 까다롭습니다. 수많은 if 문이 들어가기 십상인데, 제가 보기에 가장 깔끔하게 구현하는 방법은 아래 예제 소스 코드와 같은 것 같습니다.
이상이고요. 다음은 소스 코드입니다. 이 소스 코드는 메모리 사용량을 줄이기 위해, 배열을 3^15 크기만을 잡고, 상태를 표현할 때 처음부터 L 이나 O 로 고정되어 있는 칸은 여기에 넣지 않았습니다.
최적화
실제로는, 우리가 찾아야 하는 문자열이 LOL (palindrome) 인 것을 이용해, 서로 대칭인 게임판들을 하나로 보면 모든 결과를 시간 안에 구할 수 있다고 합니다. 'ㅅ'/

char cache[14348907];
const char LOSE = 0;
const char DRAW = 50;
const char WIN = 100;
const char* move = "LO";
struct TheStringGame 
{
  int P[16];
  int xs;
  vector index;
  bool LOL(string& state, int index)
  {
    if(index < 0 || index+2 >= state.sz) return false;
    return state[index] == 'L' && state[index+1] == 'O' && state[index+2] == 'L';
  }
  // returns DRAW if draws
  // returns WIN + turns if will win
  // returns LOSE - turns if will lose
  char go(int id, string& state)
  {
    char& ret = cache[id];
    if(ret != -1) return ret;
    char worst = WIN+1;
    REP(i,index.sz) 
    {
      int idx = index[i];
      if(state[idx] != 'X') continue;
      REP(j,2)
      {
        state[idx] = move[j];
        if(LOL(state, idx) || LOL(state, idx-1) || LOL(state, idx-2))
        {
          ret = WIN - 1;
          state[idx] = 'X';
          return ret;
        }
        worst = min(worst, go(id + (j+1) * P[i], state));
      }
      state[idx] = 'X';
    }
    if(worst < DRAW)
      ret = WIN - (worst - LOSE) - 1;
    else if(worst == DRAW || worst > WIN)
      ret = DRAW;
    else 
      ret = LOSE + (WIN - worst) + 1;
    return ret;
  }
  string winner(string s)
  {
    index.clear();
    P[0] = 1;
    FOR(i,1,16) P[i] = P[i-1] * 3;
    CLEAR(cache,-1);
    REP(i,s.sz) if(s[i] == 'X') index.pb(i);
    if(index.sz == 16) return "Brus 16";
    if(index.sz == 15)
    {
      if(s.sz == 15) return "John 15";
      if(count(all(s), 'L'))
      {
        string sol[] = { "John 13","John 15","John 15","John 13","John 13","John 13","John 13","John 13","John 13","John 13","John 13","John 13","John 13","John 15","John 15","John 13"};
        return sol[s.find('L')];
      }
      else
      {
        string sol[] = { "John 15","John 15","John 15","John 15","John 15","John 15","John 15","John 15","John 15","John 15","John 15","John 15","John 15","John 15","John 15","John 15" };
        return sol[s.find('O')];
      }
    }
    CLEAR(cache,-1);
    char verdict = go(0, s);
    if(verdict == DRAW) return "Draw";
    char buf[1024];
    if(verdict > DRAW)
      sprintf(buf, "John %d", int(WIN - verdict));
    else
      sprintf(buf, "Brus %d", int(verdict - LOSE));
    return buf;
  }
};