반응이 안 좋지만 또 써봅니다.

쉬운 easy에 재미있는(?) medium으로 구성된 셋이었습니다. 두 문제를 풀면 100등 이내에 들 수 있었네요.
Hard는 외계인과 지구인을 구분하는 문제였다고나 할까요. 페선생님과 로선생님만 풀었네요.

Easy (250 pts.)

• 문제 설명 자연수 n의 binary weight는 n을 2진수로 표현했을 때 1의 개수로 정의됩니다. (예를 들어 n=1717이면 1717=11010110101, binary weight는 7입니다.) n이 주어지면 n보다 크면서 n과 같은 binary weight를 가지는 수 중 가장 작은 수를 출력하세요. [spoiler="더 보기..."] * 풀이 2진수가 11010110101 이라면 답은 당연히 11010110110 이 되겠죠. 다시 말해서, 제일 오른쪽에 있는 1을 왼쪽으로 한칸 옮겨주면 됩니다. 그런데 만약 2진수가 ...011100 이런 형태라면 어떻게 될까요? 그럼 답은 ...100011 이 됩니다. 1이 k개가 모여 있으면, 그중에서 가장 왼쪽 1을 왼쪽으로 한칸 옮겨주고, 나머지 k-1개의 1을 제일 오른쪽에 채워주면 됩니다. 아래는 대회때 작성한, 제 코드입니다. [code] #define FOR(i,a,b) for( int i=(a); i<(b); ++i) #define FORD(i,a,b) for( int i=(a); i>(b); --i) #define REP(i,n) for(int i=0; i<(n); ++i) #define ALL(X) (X).begin(),(X).end() #define SZ(X) (int)(X).size() class NextNumber { public: int getNextNumber(int); }; int dt[50]; int NextNumber::getNextNumber(int N) { memset(dt,0,sizeof(dt)); int len=0; while (N) { dt[len++]=N%2; N/=2; } int j=0; REP(i,len) if (dt[i]==1 && dt[i+1]==0) { dt[i]=0; dt[i+1]=1; if (i+1==len) len++; j=i; break; } int cnt=count(dt,dt+j,1); REP(i,j) { if (i a(32, 0); for (int i = 0; i <= 31; ++i) { if (N & (1 << (31 - i))) a[i] = 1; printf("%d", a[i]); } printf("\n"); next_permutation(a.begin(), a.end()); int ret = 0; for (int i = 0; i <= 31; ++i) { ret += a[i] * (1 << (31 - i)); printf("%d", a[i]); } printf("\n"); return ret; } }; [/code]

[/spoiler]

Medium (500 pts.)

• 문제 설명 새로운 주사위를 만들려고 합니다. 주사위에는 자연수를 쓰며, 같은 숫자를 2번 이상 쓰지 않습니다. 그리고 주사위에 써진 수의 평균값은 M을 넘으면 안 됩니다. 만들 수 있는 주사위의 개수를 출력하세요. 답이 크므로 1000000007로 나눈 나머지를 출력합니다. [spoiler="더 보기..."] * 풀이 이리저리 변수를 굴려보다가 우연히(?) 생각이 나서 후다닥 푼 기억이 나네요. 6개의 변수를 각각 a1 ... a6 라고 하면, a1 + a2 + a3 + a4 + a5 + a6 <= 6*M 이면서 1 <= a1 < a2 ... < a5 < a6 인 모든 경우를 세면 됩니다. 변수를 이대로 두고 풀기는 만만치가 않으니 변수를 a1 ... a6 에서 d1 ... d6로 바꿔 봅시다. a1 = d1 a2 = d1 + d2 a3 = d1 + d2 + d3 . . a6 = d1 + d2 + d3 + d4 + d5 + d6 d1, d2, d3, d4, d5, d6 >= 1 6*d1 + 5*d2 + 4*d3 + 3*d4 + 2*d5 + d6 <= 6*M 이렇게 쓰면 문제 풀기가 한결 수월해집니다. DP로 풀 수 있습니다. dy[i][j] = 마지막 i개의 변수의 합이 j 이하여야 할 때, 가능한 경우의 수 점화식을 말로 풀어쓰니 조금 어렵네요. 예를 들어 dy[1][5]는 d6 <= 5 일때, 가능한 경우의 수이고, dy[3][10]은 3*d4 + 2*d5 + d6 <= 10 일때, 가능한 경우의 수입니다. 우선 dy[1][k] = k 인게 당연하고, dy[2][k]를 봅시다. 2*d5 + d6 <= k 인 경우겠죠. 2*d5를 k이하가 되도록 d5를 1부터 다 정해보면 dy[2][k] = dy[1][k-2] + dy[1][k-4] + dy[1][k-6] + ... // 이런 식이 됩니다. 간단한 점화식 테크닉을 이용해서 식을 바꿔보면 dy[2][k-2] = dy[1][k-4] + dy[1][k-6] + dy[1][k-8] + ... dy[2][k] = dy[1][k-2] + dy[2][k-2] 이렇게 됩니다. dy[3][k]인 경우도 비슷하게 구하면 되겠죠? 아래는 제가 대회 때 작성했던 코드입니다. [code] #define FOR(i,a,b) for( int i=(a); i<(b); ++i) #define REP(i,n) for(int i=0; i<(n); ++i) class CustomDice { public: int countDice(int); }; #define T 1000000007 int dy[6000005]; int res[6000005]; int CustomDice::countDice(int M) { int m=6*M+1; REP(i,m) dy[i]=i; FOR(i,2,7) { memset(res,0,sizeof(res)); FOR(j,i+1,m) { res[j]=res[j-i]+dy[j-i]; res[j]%=T; } memcpy(dy,res,sizeof(dy)); } LL tmp=res[m-1]; tmp*=30; tmp%=T; return tmp; } [/code] 처음에 코드를 작성했을 때는 long long dy[6000005], res[6000005] 이렇게 선언했었는데요. (혹시나 overflow날까봐..) 그리고 제 컴퓨터에서 돌려보고 답이 잘 나오길래 바로 제출해버렸는데, 제출하고 답이 잘 나오나 확인해보니 "caught signal SIGKILL" 라는 runtime-error가 나는 겁니다. 나중에 알고보니 메모리를 너무 많이 잡은 거더군요. long long을 int로 바꾸니까 답이 잘 나오더라구요. =_= [/spoiler]

Hard (1000 pts.)

• 문제 설명 죄송합니다. 아직 못 풀었습니다.
  [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]