밀린 에디토리얼 시리즈 2 입니다.
(felix-halim이 접속이 안되는 관계로 그림은 생략 - ainu7 25등 JongMan 26등 araste 72등 Toivoa 79등 Astein 149등)
Easy(250pt, Library)
주어진 권한과 소속된 그룹으로 접근할 수 있는 문서의 수를 구해라! 그냥 다 돌리면 되는 문제입니다. 다만 겹치는 문서는 하나로 처리해야겠지요...
[spoiler="코드 보기!"]~~~ cpp

#include
#include
#include
#include
#include
#include
using namespace std;
class Library
{
public:
int documentAccess(vector records, vector userGroups, vector roomRights)
{
vector books;
for (int i=0; i<records.size(); i++)
{
char t1[100], t2[100], t3[100];
sscanf(records[i].c_str(), "%s %s %s", t1, t2, t3);
string book_name = t1;
string room_name = t2;
string group_name = t3;
int ok = 0;
for (int j=0; j<userGroups.size(); j++) if (userGroups[j]==t3) {ok++; break;}
for (int j=0; j<roomRights.size(); j++) if (roomRights[j]==t2) {ok++; break;}
if (ok==2) books.push_back(t1);
}
sort(books.begin(), books.end());
int cnt = 0;
for (int i=0; i<books.size(); i++)
if (i==0 || books[i]!=books[i-1]) cnt++;
return cnt;
};
};

# 지정된 언어 [/spoiler]를 찾을 수 없습니다.
Medium(500pt, SchoolTrip)
  n명의 학생이 둥그렇게 모여서 공을 던지고 있다. 0번 학생부터 돌아가면서 마지막 한 명이 남을 때까지 공을 던지는데, 각 학생은 다른 학생을 맞춰서 나가게 할 수 있다. 각 학생의 던지기 성공률이 주어졌을 때, 학생들이 최선의 전략을 사용한다고 했을 때 게임이 끝날 때의 공을 던질 평균 횟수를 구해라.
  DP 점화식은 금방 나오죠 - q[a][b] = a번 학생의 턴에서 b에 속한 학생들이 남아있는 상황일때(b가 21=10101(2) 라면 0, 2, 4번 학생이 남아있는 상황이겠죠) 필요한 예상 횟수 라고 할 때, a가 노리는 각 사람 c에 대해서, (a가 c를 맞출 확률) * q[c가 빠진 상황에서 a 다음사람][b에서 c를 뺀 학생들] + (a가 c를 못맞출 확률) * q[a 다음사람][b] 가 됩니다.
  다만 여기서 q 배열은 결정되어 있는 상황이 아닙니다. 따라서 이 DP 과정을 여러번 돌려서 수렴할 때까지 구하게 됩니다. 수렴에 대한 증명은 못했지만 최대의 n과 최소의 확률에서 수렴을 하기에 제출!
[spoiler="코드 보기!"]~~~ cpp

#include <math.h> 
#include <string.h> 
#include <vector> 
#include <string> 
#include <queue> 
#include <algorithm> 
using namespace std; 
class SchoolTrip 
{ 
  public: 
  double duration(vector <int> prob) 
  { 
    int n = prob.size(); 
    double q[10][100] = {0}; 
    for (int iteration=0;; iteration++) 
    { 
      double diff = 0.0; 
      for (int i=0; i<(1<<n); i++) 
      { 
        for (int j=0; j<n; j++) 
          if (((1<<j)&i) && (1<<j)!=i) 
          { 
            double expected_min = -1; 
            for (int k=0; k<n; k++) 
              if (j!=k && ((1<<k)&i)) 
              { 
                double expected = 1.0; 
                int next_with_k = (j+1)%n; 
                while (!((1<<next_with_k)&i)) next_with_k = (next_with_k+1)%n; 
                int next_without_k = (j+1)%n; 
                while (next_without_k==k || !((1<<next_without_k)&i)) next_without_k = (next_without_k+1)%n; 
                expected += prob[j]/100.0*q[next_without_k][i-(1<<k)]; 
                expected += (100-prob[j])/100.0*q[next_with_k][i]; 
                if (expected_min<-0.5 || expected<expected_min) expected_min = expected; 
              } 
            if (expected_min>-0.5) 
            { 
              if (j==0 && i==((1<<n)-1)) diff = fabs(q[j][i]-expected_min); 
              q[j][i] = expected_min; 
            } 
  //          printf("%d/ q[%d][%d] = %f\n", iteration, j, i, q[j][i]); 
          } 
      } 
      if (diff < 1e-11) break; 
    } 
    return q[0][(1<<n)-1]; 
  }; 
};

~~~[/spoiler]
Hard(1000pt, ChessTraining)
  두 사람이 턴을 돌아가면서 게임을 하고 있다. 이 게임에서는 체스판에 체스말이 (x, y) 자리에 있는데, 이 말을 (x-k, y), (x, y-k), (x-k, y-k)의 위치로 옮길 수 있다. (k는 1 이상이고 좌표를 0 미만으로 만들면 안됨) 체스말이 여러 개가 있을 때(50개 이하),  (0,0)에 체스말을 하나라도 가져다주는 사람이 이기게 된다. 어떤 사람이 이길지 결정해라.
  각 체스말이 독립적으로 움직일 수 있고, 어떤 거라도 움직을 수 있다는 것이 이 문제를 복잡하게 합니다. 하지만, Grundy number를 사용하면 이러한 종류의 문제를 쉽게 해결할 수 있는데요, 3개의 stack을 사용하는 nim 게임 같은 것이 대표적인 예가 되겠습니다. 즉 각 체스말의 초기위치에 대해서 Grundy number를 구하고, 이 값들을 모두 xor 시킨 것이 0이면 두번째 사람이 이기고, 아니면 첫번째 사람이 이깁니다. 각 체스말의 위치에 대한 Grundy number는 그 위치에서 바로 갈 수 있는 다른 위치들에 대한 Grundy number를 모두 구한 뒤에, 0부터 시작해서 중간에 빠져있는 첫 번째 숫자가 Grundy number가 됩니다. (증명은 생략, 더 궁금하면 검색찬스 사용 ㄱㄱ)
  SRM 388 Hard도 같은 방법으로 해결할 수 있습니다.
[spoiler="코드 보기!"]~~~ cpp

연습방에서 짤 때까지 코드는 생략!

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