밀린 에디토리얼 시리즈 4 입니다. JM이 지난 번에 제가 SRM 384 Hard를 못 풀었을 때 해법에 대해 공부하라고 링크를 줘서 미리 공부해둔(x) SRM하다가 링크를 기억해낸(o) 것이 큰 도움이 되었습니다.
(ainu7 8등, lewha0 92등, zivavino 101등, ipkn 106등, ltdtl 113등)
Easy(250pt, ApproximateDivision)
a/b를 무한급수 1/b=1/(t-c)=c^0/t^1 + c^1/t^2 + c^2/t^3 + ... 을 이용해서 근사해라. 최초 terms 항만 계산하면 된다.
여기서 t는 b 이하의 가장 큰 2^k꼴의 수이다.
-> 그냥 주어진 대로 계산하면 되죠 ^^ 다만 int 범위에서 c^terms/t^terms 를 하다가 오버플로우가 나는 수가 있습니다. (i번째 항) = (i-1번째 항) * c/t의 식을 이용해서 풀면 쉽게 계산하실 수 있겠습니다.
[spoiler="코드 보기!"]~~~ cpp

#include
#include
#include
#include
#include
#include
using namespace std;
class ApproximateDivision
{
public:
double quotient(int a, int b, int terms)
{
int t = 1;
while (t<b) t*=2;
int c = t-b;
double res = 0.0;
double now = 1.0/t;
for (int i=0; i<terms; i++)
{
res += now;
now *= c;
now /= t;
}
return res*a;
};
};

# 지정된 언어 [/spoiler]를 찾을 수 없습니다.
Medium(500pt, GuitarChords)
  vector<string> strings로 각 기타 스트링의 베이스 음이 주어지고, vector<string> chords로 어떤 음을 연주해야 할 것인가가 주어집니다. 모든 스트링이 음을 연주해야 한다고 하고, 모든 음은 최소한 하나 이상의 스트링에 의해서 연주되어야 한다고 할 때, 짚어야 하는 줄의 위치 간격을. 손이 짚어야 하는 위치 범위의 최소치를 리턴해라.
  -> 제 경우는 모든 경우를 찾아봅니다. 즉, 각 스트링이 어떤 음을 연주할 것인가를 모든 경우를 찾아보면서, 하나의 음이라도 배제된 경우는 제거합니다. 또한 각 스트링이 어떤 음을 연주할 것인가에서, 0옥타브와 1옥타브로 나누어서 생각했습니다. 즉 최대 (6*2)^6 가지의 경우를 찾아보겠죠.
  이 때 옥타브를 미리 나누지 않고, 어떤 스트링이 가장 왼쪽에서 짚어질 것인가에 따라서 결정해서 계산할 수도 있습니다. 이렇게 하면 경우의 수가 (6^6)*6으로, 꽤 줄어듭니다.
[spoiler="코드 보기!"]~~~ cpp

#include <math.h> 
#include <string.h> 
#include <vector> 
#include <string> 
#include <queue> 
#include <algorithm> 
using namespace std; 
const string absolute[12] = {"A", "A#", "B", "C", "C#", "D", "D#", "E", "F", "F#", "G", "G#"}; 
class GuitarChords 
{ 
  public: 
  int stretch(vector <string> strings, vector <string> chord) 
  { 
    int n = strings.size(); 
    int m = chord.size(); 
    vector<int> S; 
    vector<int> C; 
    for (int i=0; i<n; i++) 
      for (int j=0; j<12; j++) 
        if (strings[i]==absolute[j]) 
          S.push_back(j); 
    for (int i=0; i<m; i++) 
      for (int j=0; j<12; j++) 
        if (chord[i]==absolute[j]) 
          C.push_back(j); 
    vector<int> combi(n); 
    int mmin = 999999; 
    while (1) 
    { 
      int test[10] = {0}; 
      for (int i=0; i<n; i++) test[combi[i]/2] = 1; 
      int ok = 1; 
      for (int i=0; i<m; i++) if ( test[i]==0 ) ok = 0; 
      if (ok) 
      { 
        int min_fret = -1; 
        int max_fret = -1; 
        for (int i=0; i<n; i++) 
        { 
          int now_fret = C[combi[i]/2]-S[i]; 
          if (now_fret<0) now_fret += 12; 
          if ( combi[i]%2 ) now_fret += 12; 
          if ( now_fret>0) 
          { 
            if ( min_fret == -1 || min_fret>now_fret ) min_fret = now_fret; 
            if ( max_fret == -1 || max_fret<now_fret ) max_fret = now_fret; 
          } 
        } 
        int now_score = 0; 
        if ( min_fret != -1 ) 
          now_score = max_fret-min_fret+1; 
    //    for (int i=0; i<n; i++) printf("%d ", combi[i]); printf("=> %d %d %d\n", min_fret, max_fret, now_score); 
        if ( now_score < mmin ) mmin = now_score; 
      } 
      // make next combination 
      combi[n-1] ++; 
      int k = n-1; 
      while (k>0 && combi[k]==m*2) 
      { 
        combi[k] = 0; 
        combi[k-1] ++; 
        k --; 
      } 
      if ( combi[0]==m*2) break; 
    } 
    return mmin; 
  }; 
};

~~~[/spoiler]
Hard(1000pt, LittleSquares)
  두 사람이 게임을 하면서 판을 채운다. 판은 세로줄이 2의 배수 크기로, 10x10 크기를 넘지 않는다. 판을 채울때 1x1 square 하나로 채울 수도 있고, 2x2 square 하나로 채울 수도 있는데, 기존에 채웠던 것과 겹치면 안되며, 2x2 square의 경우에는 홀수번째 줄에서만 시작할 수 있다. 마지막에 채우는 사람이 이긴다고 할 때, 주어진 판의 상태에서 마지막에 이길 사람을 알아내라.
  -> 2x2 square가 놓아지는 위치에 따라서 판을 위에서부터 두 줄씩 나누어야 합니다. 이러면 (세로줄/2) 개의 독립된 판이 나오고, 어떤 판이나 골라서 1x1이나 2x2의 square를 자유롭게 배치하는 문제로 바꿀 수 있겠죠.
  푸는 방법은 384 Hard와 같습니다. 즉 Grundy number를 이용하는 건데요, 2줄짜리 판(최대 2x10=20칸)의 가능한 모든 configuration에 대해서 Grundy number를 구하고, 독립된 각각의 판마다의 Grundy number를 xor해서 0이면 두번째 사람이 이기고, 1이면 첫번째 사람이 이기게 됩니다.
[spoiler="코드 보기!"]~~~ cpp

#include <math.h> 
#include <string.h> 
#include <vector> 
#include <string> 
#include <queue> 
#include <algorithm> 
using namespace std; 
int grundy[1<<20]; 
class LittleSquares 
{ 
  public: 
  void preprocess(int m) 
  { 
    int p[30]; 
    for (int i=0; i<2*m; i++) 
      p[i] = 1<<(2*m-1-i); 
    for (int i=0; i<m-1; i++) 
      p[2*m+i] = p[i]+p[i+1]+p[i+m]+p[i+m+1]; 
    int cnt = m*3-1; 
    for (int i=0; i<cnt; i++) printf("%d ", p[i]); printf("\n"); 
    for (int i=(1<<(2*m))-1; i>=0; i--) 
    { 
      int q[31] = {0}; 
      for (int j=cnt-1; j>=0; j--) 
        if ( !(i&p[j]) ) q[grundy[i+p[j]]] = 1; 
      int j=0; 
      for (j=0; j<=30; j++) 
        if ( !q[j] ) 
        { 
          grundy[i] = j; 
          break; 
        } 
      if ( j==31 ) printf("!!!!\n"); 
    } 
  } 
  string winner(vector <string> state) 
  { 
    int n = state.size(); 
    int m = state[0].size(); 
    preprocess(m); 
    int total = 0; 
    for (int i=0; i<n; i+=2) 
    { 
      int number = 0; 
      if (i==n-1) 
      { 
        for (int j=0; j<n; j++) 
          if (state[i][j]=='.') number = 1 - number; 
      } 
      else 
      { 
        int ppp = 0; 
        for (int j=0; j<2; j++) 
          for (int k=0; k<m; k++) 
          { 
            ppp *= 2; 
            if ( state[i+j][k] == '#' ) ppp ++; 
          } 
        number = grundy[ppp]; 
      } 
      printf("this number : %d\n", number); 
      total = total ^ number; 
    } 
    printf("total = %d\n", total); 
    string first = "first"; 
    string second = "second"; 
    if ( total == 0 ) return second; 
    return first; 
  }; 
};

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