algospot.com :: 과거 게시판: [editorial] [밀린 에디토리얼 시리즈 3] SRM 388 Div 1

[editorial] [밀린 에디토리얼 시리즈 3] SRM 388 Div 1

밀린 에디토리얼 시리즈 3 입니다.
이 SRM은 저에게는 아주 뜻깊은 SRM입니다! 어거지로 짠 Fastest Hard와 함께 1년 2개월간 지속된 2350-2660 박스권을 뚫어낸 SRM이거든요. (참조: http://www.topcoder.com/tc?module=MemberProfile&cr=22653720)
(ainu7 4등, Jongman 40등, Astein 113등, zizavino 142등)
Easy(250pt, SmoothNumbers)
문제는 1~N까지 중에서 소인수가 k 이하로만 이루어져있는 수들의 갯수를 구해라(1 포함) 입니다. N과 k가 큰 Div 2 Hard와는 달리 그냥 다 돌려서 풀 수 있습니다...
[spoiler="코드 보기!"]~~~ cpp

#include
#include
#include
#include
#include
#include
#include
using namespace std;
class SmoothNumbers
{
public:
int countSmoothNumbers(int N, int k)
{
int cnt = 0;
for (int i=1; i<=N; i++)
{
int p = i;
for (int j=2; j<=k; j++)
if (p%j==0) {p/=j; j--;}
if (p==1) cnt++;
}
return cnt;
};
};

Medium(500pt, InformFriends)
  주인공이 a에게 어떤 정보를 전해주면, G[a][b] = 1인 b에게 이 정보를 전해줄 수 있습니다. 주인공이 모든 사람에게 정보를 한 가지 정보만 전해준다고 할 때, 모든 사람이 공통적으로 알 수 있는 정보의 수는 최대 몇 가지일까요? (사람수 15 이하)
  실전에는 백트래킹으로 짰으나 TLE... 만약 입력된 vector<string>을 2차원 배열로 바꾸기만 했더라도 통과할 수 있었습니다만 당시에 과도한 자신감으로 그냥 submit하는 만행을 보였다죠 -_- 만약 통과했다면 SRM Win이 가능했던 상황이었습니다.
  아무튼 연습방에서 새로 짠 것은 DP(를 가장한 Brute force)입니다. 한 가지 정보를 모든 사람들이 알기 위해서 주인공이 알려주어야 하는 사람들의 집합의 모든 경우를 구해놓고(아래 소스의 D 배열), 이것들을 조합해서 최대한 많은 정보를 전달하도록 합니다. (아래 소스의 E 배열)
[spoiler="코드 보기!"]~~~ cpp

#include <math.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
class InformFriends
{
 public:
 int maximumGroups(vector <string> friends)
 {
  int C[15] = {0};
  int D[32768] = {0};
  int num = 0;
  int F[32768] = {0};
  int E[32768] = {0};
  int n = friends.size();
  for (int i=0; i<n; i++)
  {
   C[i] = 1<<i;
   for (int j=0; j<n; j++)
    if (friends[i][j]=='Y') C[i]|=1<<j;
  }
  for (int i=0; i<(1<<n); i++)
  {
   int t = 0;
   int candidate = 0;
   for (int j=0; j<n; j++)
    if (i&(1<<j))
    {
     t |= C[j];
     candidate |= 1<<j;
     if (t==(1<<n)-1)
     {
      if (!D[candidate])
      {
       F[num] = candidate;
       num ++;
      }
      D[candidate] = 1;
      break;
     }
    }
  }
  F[num] = 1<<n;
  int answer = 0;
  int cnt = 0;
  for (int i=0; i<(1<<n); i++)
  {
   if (F[cnt]==i) cnt ++;
   for (int j=0; j<cnt; j++)
    if ((i&F[j])==F[j])
     E[i] >?= E[i-F[j]]+1;
   answer >?= E[i];
  }
  return answer;
 };
};

~~~[/spoiler]
Hard(1000pt, TelephoneNumbers)
  7자리 16진수의 전화번호가 있다. 사람들이 헷갈리지 않기 위해서, 모든 전화번호가 seperation개의 숫자 이상 다르게 하려고 한다. 0000000부터 오름차순으로 찾으면서, 그 동안 배당된 전화번호들과 충돌하지 않는 것들을 순서대로 배당한다. 1<=seperation<=3, 1<=k<=300000일 때, k번째로 배당될 전화번호를 출력하라.
  '그 동안의 모든 전화번호들'과 충돌하지 않아야 한다는 조건이 이 문제를 어렵게 만들죠. 실전에서는 seperation=1인 경우를 먼저 처리하고(그냥 k-1을 16진수로 출력하면 되죠), seperation=2, 3인 경우를 처리하려고 했습니다. 하다보니 그냥 짜도 배열 크기와 수행 시간의 경계 안쪽으로 들어오더군요. 공식 에디토리얼에도 모범답안으로 올라오기는 했지만 이 문제를 어렵게 짜다가 포기하고 해법을 본 사람들이 모두 다 허탈해했다죠~~~~
  제가 사용한 방법은 와일드카드를 사용한 방법입니다.
  sepeartion=2인 경우: k<=300000이면 첫 자리는 무조건 0입니다. 따라서 전체를 6자리로 하고 나서...
    pp[0][a][b][c][d][e] : *abcde 는 안된다고 체크해놓음
    pp[1][a][b][c][d][e] : a*bcde 는 안된다고 체크해놓음
    ...
    pp[5][a][b][c][d][e] : abcde* 는 안된다고 체크해놓음
  sepeartion=3인 경우:
    pp[0][a][b][c][d][e] : **abcde 는 안된다고 체크해놓음
    pp[1][a][b][c][d][e] : *a*bcde 는 안된다고 체크해놓음
    ...
    pp[20][a][b][c][d][e] : abcde** 는 안된다고 체크해놓음
[spoiler="코드 보기!"]~~~ cpp

#include <vector> 
#include <string> 
#include <queue> 
#include <algorithm> 
#include <map> 
#include <math.h> 
#include <string.h> 
using namespace std; 
bool pp[21][16][16][16][16][16]; 
class TelephoneNumbers 
{ 
  public: 
  string kthNumber(int separation, int k) 
  { 
    string res; 
    if (separation==1) 
    { 
      char temp[30] = ""; 
      sprintf(temp, "%07x", k-1); 
      res = temp; 
    } 
    else if (separation==2) 
    { 
      int cnt = 0; 
      for (int a2=0; a2<16; a2++) 
      for (int a3=0; a3<16; a3++) 
      for (int a4=0; a4<16; a4++) 
      for (int a5=0; a5<16; a5++) 
      for (int a6=0; a6<16; a6++) 
      for (int a7=0; a7<16; a7++) 
      if (!pp[0][a3][a4][a5][a6][a7] && 
          !pp[1][a2][a4][a5][a6][a7] && 
          !pp[2][a2][a3][a5][a6][a7] && 
        !pp[3][a2][a3][a4][a6][a7] && 
        !pp[4][a2][a3][a4][a5][a7] &&  
        !pp[5][a2][a3][a4][a5][a6]) 
      { 
        pp[0][a3][a4][a5][a6][a7] = 1; 
        pp[1][a2][a4][a5][a6][a7] = 1; 
        pp[2][a2][a3][a5][a6][a7] = 1; 
        pp[3][a2][a3][a4][a6][a7] = 1; 
        pp[4][a2][a3][a4][a5][a7] = 1; 
        pp[5][a2][a3][a4][a5][a6] = 1; 
        cnt ++; 
        if (cnt == k) 
        { 
          char temp[30] = ""; 
          sprintf(temp, "%x%x%x%x%x%x%x", 0, a2, a3, a4, a5, a6, a7); 
          return temp; 
        } 
      } 
    } 
    else if (separation==3) 
    { 
      int cnt = 0; 
      for (int a1=0; a1<16; a1++) 
      for (int a2=0; a2<16; a2++) 
      for (int a3=0; a3<16; a3++) 
      for (int a4=0; a4<16; a4++) 
      for (int a5=0; a5<16; a5++) 
      for (int a6=0; a6<16; a6++) 
      for (int a7=0; a7<16; a7++) 
      if (!pp[0][a3][a4][a5][a6][a7] && 
        !pp[1][a2][a4][a5][a6][a7] && 
        !pp[2][a2][a3][a5][a6][a7] && 
        !pp[3][a2][a3][a4][a6][a7] && 
        !pp[4][a2][a3][a4][a5][a7] && 
        !pp[5][a2][a3][a4][a5][a6] && 
        !pp[6][a1][a4][a5][a6][a7] && 
        !pp[7][a1][a3][a5][a6][a7] && 
        !pp[8][a1][a3][a4][a6][a7] && 
        !pp[9][a1][a3][a4][a5][a7] && 
        !pp[10][a1][a3][a4][a5][a6] && 
        !pp[11][a1][a2][a5][a6][a7] && 
        !pp[12][a1][a2][a4][a6][a7] && 
        !pp[13][a1][a2][a4][a5][a7] && 
        !pp[14][a1][a2][a4][a5][a6] && 
        !pp[15][a1][a2][a3][a6][a7] && 
        !pp[16][a1][a2][a3][a5][a7] && 
        !pp[17][a1][a2][a3][a5][a6] && 
        !pp[18][a1][a2][a3][a4][a7] && 
        !pp[19][a1][a2][a3][a4][a6] && 
        !pp[20][a1][a2][a3][a4][a5]) 
      { 
        pp[0][a3][a4][a5][a6][a7] = 1; 
        pp[1][a2][a4][a5][a6][a7] = 1; 
        pp[2][a2][a3][a5][a6][a7] = 1; 
        pp[3][a2][a3][a4][a6][a7] = 1; 
        pp[4][a2][a3][a4][a5][a7] = 1; 
        pp[5][a2][a3][a4][a5][a6] = 1; 
        pp[6][a1][a4][a5][a6][a7] = 1; 
        pp[7][a1][a3][a5][a6][a7] = 1; 
        pp[8][a1][a3][a4][a6][a7] = 1; 
        pp[9][a1][a3][a4][a5][a7] = 1; 
        pp[10][a1][a3][a4][a5][a6] = 1; 
        pp[11][a1][a2][a5][a6][a7] = 1; 
        pp[12][a1][a2][a4][a6][a7] = 1; 
        pp[13][a1][a2][a4][a5][a7] = 1; 
        pp[14][a1][a2][a4][a5][a6] = 1; 
        pp[15][a1][a2][a3][a6][a7] = 1; 
        pp[16][a1][a2][a3][a5][a7] = 1; 
        pp[17][a1][a2][a3][a5][a6] = 1; 
        pp[18][a1][a2][a3][a4][a7] = 1; 
        pp[19][a1][a2][a3][a4][a6] = 1; 
        pp[20][a1][a2][a3][a4][a5] = 1; 
        cnt ++; 
        if (cnt == k) 
        { 
          char temp[30] = ""; 
          sprintf(temp, "%x%x%x%x%x%x%x", a1, a2, a3, a4, a5, a6, a7); 
          return temp; 
        } 
      } 
    } 
    return res; 
  }; 
};

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

18년 전

0개의 댓글이 있습니다.

정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

SINCE 2007

다가오는 이벤트들

[editorial] [밀린 에디토리얼 시리즈 3] SRM 388 Div 1

0개의 댓글이 있습니다.