R3 전에 쓰는 거니 안밀린 에디토리얼이라 할 수 있겠군요 후후후... 과연 레이팅 2927이 Career high가 될 것인지!!!
(전 9등인데 랭킹 찾아보기 귀찮아졌다능...)
Easy(250pt, IsomorphicWords)
주어진 단어집에서, Isomorphic한 두 단어의 pair 수를 계산하라. 한 단어의 모든 글자들이 다른 단어로 remapping될 수 있다면 그것을 Isomorphic하다고 한다.
-> 모든 두 단어의 조합에 대해서, 한 단어의 글자가 어떻게 다른 단어의 글자로 mapping되는지를 일단 테이블로 만들어서 저장합니다. 일치하지 않는 mapping이 있거나, 두 개 이상의 글자가 한 글자로 mapping되는 경우가 없는지도 체크합니다.
[spoiler="코드 보기!"]~~~ cpp

#include
#include
#include
#include
#include
#include
using namespace std;
class IsomorphicWords
{
public:
int countPairs(vector words)
{
int n = words.size();
int cnt = 0;
for (int ii=0; ii<n; ii++)
for (int jj=ii+1; jj<n; jj++)
{
string str1 = words[ii];
string str2 = words[jj];
if (str1.size()!=str2.size()) continue;
int mmap[26] = {0};
for (int i=0; i<26; i++) mmap[i] = -1;
for (int i=0; i<str1.size(); i++)
mmap[str1[i]-'a'] = str2[i]-'a';
int ok = 1;
for (int i=0; i<str1.size(); i++)
if (mmap[str1[i]-'a'] != str2[i]-'a') { ok = 0; break; }
if (!ok) continue;
for (int i=0; i<26; i++)
for (int j=i+1; j<26; j++)
if (mmap[i]==mmap[j] && mmap[i]!=-1) { ok = 0; break; }
if (!ok) continue;
cnt ++;
}
return cnt;
};
};

# 지정된 언어 [/spoiler]를 찾을 수 없습니다.
비효율적이지만 알기 쉽게 이렇게 짜도 됩니다.
[spoiler="코드 보기!"]~~~ cpp

  int countPairs(vector <string> words) 
  { 
    int n = words.size(); 
    int cnt = 0; 
    for (int ii=0; ii<n; ii++) 
      for (int jj=ii+1; jj<n; jj++) 
      { 
        string str1 = words[ii]; 
        string str2 = words[jj]; 
        if (str1.size()!=str2.size()) continue;
        int ok = 1;
        for (int i=0; i<str1.size(); i++) 
          for (int j=i+1; j<str1.size(); j++)
            if ((str1[i]==str1[j]) ^ (str2[i]==str2[j])) { ok = 0; break; } 
        cnt += ok;
      } 
    return cnt; 
  }; 

~~~[/spoiler]
Medium(500pt, KeysinBoxes)
  N개의 박스가 있고, 박스마다 그 박스를 열 수 있는 열쇠가 있는데, 그것들을 무작위로 섞어서 각 박스 안에 하나씩 놔두고 박스를 밖에서 잠가버린다. 이제 폭탄을 써서 박스를 열고, 이 박스에 담긴 열쇠들을 이용해서 다른 박스들을 열어나갈 수 있다. 폭탄이 M개 있다고 할 때, 박스를 모두 열 수 있는 확률을 계산해라.
  -> N개의 박스가 있고 M개의 폭탄이 남아있는 경우에, 폭탄을 써서 박스를 하나 열면, 여러가지 경우가 있습니다.
  (1) 그 박스에 그 박스를 여는 열쇠가 있는 경우 : 확률 1/N, 박스와 폭탄이 하나 줄어듭니다.
  (2) 그 박스에 다른 박스를 여는 열쇠가 있었고, 그 다른 박스를 열어보니 원래 박스를 여는 열쇠가 있는 경우
  확률 = (N-1)/N * 1/(N-1) = 1/N, 박스가 2개 폭탄이 1개 줄어듭니다.
  (3) 그 박스에 다른 박스를 여는 열쇠가 있었고, 그 다른 박스를 열어보니 또 다른 박스를 여는 열쇠가 있었고, 그 다른 박스를 열어보니 원래 박스를 여는 열쇠가 있는 경우
  확률 = (N-1)/N * (N-2)/(N-1) * 1/(N-2) = 1/N, 박스가 3개, 폭탄이 1개 줄어듭니다.
  (4) (5) 계속~~~
  따라서 (박스N, 폭탄M에서 가능한 확률) = 1/N * ((박스N-1, 폭탄M-1에서 가능한 확률) + (박스N-2, 폭탄M-1에서 가능한 확률) + ... + (박스1, 폭탄M-1에서 가능한 확률) + (박스0, 폭탄M-1에서 가능한 확률)) 이 되겠죠.
  확률을 기약분수형태로 계산해야하므로, 각 단계에서의 확률을 up[i][j]/down[i][j] 꼴로 유지하면서 계속 확률을 계산해나갑니다. 분모가 20!이 넘는 경우는 없으므로, 64bit 안에서 해를 구할 수 있습니다.
[spoiler="코드 보기!"]~~~ cpp

#include <math.h> 
#include <string.h> 
#include <vector> 
#include <string> 
#include <queue> 
#include <algorithm> 
using namespace std; 
int covered[30][30] = {0}; 
long long up[30][30] = {0}; 
long long down[30][30] = {0}; 
class KeysInBoxes 
{ 
  public: 
  long long gcd(long long a, long long b) 
  { 
    if (b==0) return a; 
    return gcd(b, a%b); 
  } 
  void calc(int N, int M) 
  { 
    if (covered[N][M]) return; 
    covered[N][M] = 1; 
    if (N==0) 
    { 
      up[N][M] = 1; 
      down[N][M] = 1; 
      return; 
    } 
    if (M==0) 
    { 
      up[N][M] = 0; 
      down[N][M] = 1; 
      return; 
    } 
    long long a = 0; 
    long long b = 1; 
    for (int i=0; i<N; i++) 
    { 
      calc(N-1-i, M-1); 
      long long c = up[N-1-i][M-1]; 
      long long d = down[N-1-i][M-1]; 
      long long e = gcd(b, d); 
      long long f = d/e*a+b/e*c; 
      long long g = b/e*d; 
      long long h = gcd(f, g); 
      a = f/h; 
      b = g/h; 
    } 
    b *= N; 
    long long c = gcd(a, b); 
    up[N][M] = a/c; 
    down[N][M] = b/c; 
  } 
  string getAllKeys(int N, int M) 
  { 
    calc(N, M); 
    char temp[100]; 
    sprintf(temp, "%lld/%lld", up[N][M], down[N][M]); 
    return temp; 
  }; 
};

~~~[/spoiler]
Hard(1000pt, Transformation)
  10^18 미만의 positive integer들 A1, A2, ... An을 준다. 이것을 B1, B2, ... Bn으로 바꾸는데, Bi|Ai여야 하며 LCM(A1, ... An) = LCM(B1, ... Bn)이면서 이러한 조건을 만족하는 B1~n중에서 사전순으로 제일 먼저 나오는 것을 찾아라!
  -> Bi|Ai여야 한다므로 우선 각 수를 소인수분해를 합니다. 그러면 소인수들이 나오겠고, 이 중에서 일부분만 선택하는 형식이 되겠죠. 이제 LCM이 같다는 조건을 해결하기 위해서 각 factor별로 어떤 것을 선택해야 하는지를 결정합니다. 각 factor별로 가장 많이 나오면서 제일 먼저 나오는 것을 선택하면 되겠죠 
  예를 들어서 1500과 1575가 입력으로 들어왔다고 합시다.
   1500 = 2*2*3    *5*5*5
   1575 =         3*3*5*5    *7
  여기서 2*2는 위에것밖에 안나오므로 선택해야 하고, 3의 경우는 위의 3을 없앨 수 있으며, 5*5*5가 있으므로 아래쪽 5*5를 없앨 수 있고(위에 것을 조금이라도 건드렸다가는 LCM이 달라집니다.), 7은 선택해야 합니다.
  이렇게 하면 되는데, 문제는 소인수분해를 하기에 수가 너무 크다는 것입니다. 따라서 두 가지 경우로 나누어서 생각합니다.
  (1) 100만 이하의 소인수 -> 위와 같이 해결합니다.
  (2) 100만 초과의 소인수 -> 10^18 미만의 수는 10^6이 넘는 소인수를 최대 두 개 가질 수 있습니다. 100만 이하로 나누어지지 않는 부분만 남아있다고 할 때, 남은 각각의 수들에 대해서 gcd를 구하면, 겹치는 소인수를 찾을 수 있습니다. 이렇게 찾은 소인수에 대해서, (1)과 같이 해결합니다.
  좀 더 간단하게 해결할 수도 있는 모양인데, 저는 잘 모르겠습니다 ^^
[spoiler="코드 보기!"]~~~ cpp

#include <math.h> 
#include <string.h> 
#include <vector> 
#include <string> 
#include <queue> 
#include <algorithm> 
using namespace std; 
class Transformation 
{ 
  public: 
  long long gcd(long long a, long long b) 
  { 
    if (b==0) return a; 
    return gcd(b, a%b); 
  } 
  vector <string> transform(vector <string> A) 
  { 
    int n = A.size(); 
    long long B[50] = {0}; 
    for (int i=0; i<n; i++) 
      sscanf(A[i].c_str(), "%lld", &B[i]); 
    for (int i=0; i<n; i++) 
      for (int j=i+1; j<n; j++) 
        if (B[j]%B[i]==0) B[i] = 1; 
    long long C[50] = {0}; 
    for (int i=0; i<n; i++) 
      C[i] = 1; 
    for (int i=2; i<1000000; i++) 
    { 
      if (i>2 && i%2==0) continue; 
      int cnt[50] = {0}; 
      for (int j=0; j<n; j++) 
        while (B[j]%i==0) { cnt[j] ++; B[j]/=i; } 
      int mmax = 0; int index = -1; 
      for (int j=n-1; j>=0; j--) 
        if (cnt[j]>mmax) { mmax = cnt[j]; index = j; } 
      if (mmax) 
        for (int j=0; j<mmax; j++) 
          C[index] *= i; 
    } 
    for (int i=0; i<n; i++) printf("%lld %lld\n", B[i], C[i]); printf("\n"); 
    for (int p1=0; p1<n; p1++) for (int p2=p1+1; p2<n; p2++) 
    { 
      long long i = gcd(B[p1], B[p2]); 
      if (i==B[p1]) { B[p1] = 1; continue; } 
      if (i==1) continue; 
      int cnt[50] = {0}; 
      for (int j=0; j<n; j++) 
        while (B[j]%i==0) { cnt[j] ++; B[j]/=i; } 
      int mmax = 0; int index = -1; 
      for (int j=n-1; j>=0; j--) 
        if (cnt[j]>mmax) { mmax = cnt[j]; index = j; } 
      if (mmax) 
        for (int j=0; j<mmax; j++) 
          C[index] *= i; 
    } 
    for (int i=0; i<n; i++) printf("%lld %lld\n", B[i], C[i]); printf("\n"); 
    vector<string> res; 
    for (int i=0; i<n; i++) 
    { 
      char temp[50]; 
      sprintf(temp, "%lld", B[i]*C[i]); 
      res.push_back(temp); 
    } 
    return res; 
  }; 
};

~~~[/spoiler]
<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/45316">원문보기</a>]</div>