챌이 꽤나 많았던 대회였는데.. 밥먹고 온다고 챌을 못한게 아쉬웠습니다 -.-
ainu7님이 저보다 랭킹이 높으심에도 불구하고 300점짜리를 틀렸다는 이유로 저한테 에디토리얼을 떠넘기셨습니다.
하지만 ainu7님의 382, 384 Div 1 에디토리얼을 기대합니다.

Easy (300 pts.)

• 문제 설명 N개의 상자가 있습니다. 각각의 상자에는 구슬들이 적당히 들어 있습니다. 우리는 아래의 조건을 만족하는 상태를 만들고 싶습니다. 1) N개의 상자 중 (최대) 하나를 joker box로 정할 수 있습니다. 이 joker box에는 어떤 색깔의 구슬이 들어있어도 됩니다. 물론 joker box는 우리가 선택할 수 있습니다. 2) joker box를 제외한 모든 상자는 비어있거나 한가지 색깔의 구슬만 있어야 합니다. 3) joker box에 있는 구슬을 제외하고는 임의의 한 색깔의 구슬은 둘 이상의 상자에 존재해서는 안됩니다. (즉, 빨간색의 구슬은 joker box에 있거나 하나의 상자에 담겨져 있거나, joker box와 하나의 상자에 담겨져 있어야겠지요.) 상자의 구슬은 "이동"할 수 있습니다. (상자 A에서 상자 B로 구슬들을 옮기는 연산입니다. 한번에 옮길 수 있는 구슬의 수는 제한이 없습니다.) 초기 상태에서 위의 조건을 만족하는 상태로 만드는 데 최소 몇번의 이동연산이 필요할까요? [spoiler="더 보기..."]* 해결 방법 임의의 joker box를 잡는다고 가정합시다. joker box가 아닌 상자는 아래와 같은 세 가지의 경우가 존재하겠지요? 1) 구슬이 하나도 없다 -> 이 경우는 이동연산이 필요 없습니다. 2) 2가지 이상의 색깔의 구슬이 존재한다 -> 그냥 joker box에 전부 쏟아버리면 해결됩니다. 어차피 한번 이상의 연산이 필요하니, joker box에 몰아넣는 쪽이 이동연산이 최소가 됩니다. 3) 1가지 색깔의 구슬만 있다 -> joker box가 아닌 상자에서 모읍니다. A 색깔만 있는 상자가 k개 있다면 k-1번의 연산이 필요하겠죠? N개의 상자를 한 번 씩 joker box로 설정하면서 1~3의 규칙으로 몇 번의 이동이 필요한지 simulation하면 됩니다. ~~~ cpp

struct MarblesRegroupingEasy {

int minMoves(vector boxes) {

int N = sz(boxes), M = sz(boxes[0]);

int ret = 987654;

REP(joker, N) {

vector numOfBox(M, 0);

int tmp = 0;

REP(i, N) {

if (i == joker) continue;

int ct = 0;

REP(j, M)

if (boxes[i][j] != '0') ct++;

if (ct > 1) {

tmp++;

} else {

REP(j, M)

if (boxes[i][j] != '0') numOfBox[j]++;

}

}

sort(all(numOfBox));

reverse(all(numOfBox));

REP(i, min(N - 1, M))

if (numOfBox[i] > 0) numOfBox[i]--;

REP(i, M) tmp += numOfBox[i];

ret <?= tmp;

}

return ret;

}

};

[/spoiler]



Medium (500 pts.)

* 문제 설명
  N개의 interval(구간)이 있습니다. i번째 interval은 [si, fi]꼴로 표현할 수 있지요. (si와 fi를 포함합니다.)
  주어진 set의 subset은 아래의 두 가지 조건을 모두 만족시킬때 valid합니다.
  조건 1) subset의 임의의 두 interval을 선택했을 때, 교집합이 없어야 합니다. 
  조건 2) 현재의 subset에 "포함되지 않은 interval"을 추가할 수 없습니다. (즉, 현재의 subset과 교집합이 없는 '포함되지 않는 interval'은 존재하지 않아야 합니다.)
  N개의 interval이 주어졌을 때, distinct하고 valid한 subset의 수를 구하는 프로그램을 작성하시오, distinct한 subset이란 서로 다른 인덱스의 set을 의미합니다.... (예제로 파악하시는게 ㅠㅠ) 

[spoiler="더 보기..."]* 해결 방법
1차원 다이나믹으로 해결 가능합니다. 테이블 Ti는 아래와 같이 정의합니다.
Ti : i번째 interval을 right-most element로 포함하는 subset의 수
위의 규칙대로 하기 위해서는 finish[i]로 sort하는 연산이 필요하겠지요. (없어도 상관은 없지만.. 귀찮아지죠)
i번째 interval 앞에 j번째 interval이 오는 조건은 finish[j] < start[i]입니다. 또한 "조건 2"를 만족하기 위해서는, i와 j를 제외한 임의의 k번째 interval을 설정하더라도 finish[j] < start[k] && finish[k] < start[i]를 만족하는 경우가 없어야 합니다. 앞에 쓴 내용을 모두 만족하는 j번째 interval이 있다면 Ti에 Tj를 더할 수 있겠지요. 'ㅁ'
자세한 것은 소스코드를 참고하세용 'ㅁ'
~~~ cpp

int table[105]; 
int isPre[105]; 
int isNext[105]; 
int bet[105][105]; 
struct IntervalSubsets { 
    int numberOfSubsets(vector <int> start, vector <int> finish) { 
        int N = sz(start); 
        for (int i = 0; i < N; ++i) { 
            for (int j = i + 1; j < N; ++j) { 
                if (start[i] > start[j]) { 
                    swap(start[i], start[j]); 
                    swap(finish[i], finish[j]); 
                } 
            } 
        } 
        for (int i = 0; i < N; ++i) { 
            for (int j = 0; j < N; ++j) { 
                if (finish[i] < start[j]) { 
                    isPre[j] = 1; 
                    isNext[i] = 1; 
                } 
            } 
        } 
        for (int i = 0; i < N; ++i) 
            for (int j = 0; j < N; ++j) { 
                if (finish[i] < start[j]) { 
                    for (int k = 0; k < N; ++k) 
                        if (finish[i] < start[k] && finish[k] < start[j]) bet[i][j] = 1; 
                } 
            } 
        for (int i = N - 1; i >= 0; --i) { 
            if (isNext[i] == 0) { 
                table[i] = 1; 
            } else { 
                for (int j = i + 1; j < N; ++j) { 
                    if (finish[i] < start[j] && !bet[i][j]) table[i] += table[j]; 
                } 
            } 
        } 
        int ret = 0; 
        for (int i = 0; i < N; ++i) 
            if (isPre[i] == 0) ret += table[i]; 
        return ret; 
    } 
};

[/spoiler]

Hard (950 pts.)

• 문제 설명 무한 순열 P가 있다. 이 수열의 i번째 값은 아래와 같이 정의된다.

  P[i] = (A[i % A.size] ^ (B[i % B.size] + i / B.size)) % 1000000007

  ( %는 나머지, ^는 거듭제곱, /는 나누기를, X.size는 X의 원소 수를 의미합니다. :9 ) vector 꼴로 이루어진 A와 B, 그리고 interget N (10^18 이하의) 이 있을 때 P[0] + P[1] + ... + P[N-1]을 1000000007로 나눈 나머지를 구하시오. [spoiler="더 보기..."]* 해결 방법 뭔가 많이 복잡해보이지만, LCM(A.size, B.size) 개의 구간으로 분리해서 생각하면 "sum of 등비수열의 합" 을 구하는 문제가 됩니다. a + ar + ar^2 + ... + ar^(n-1)을 구하고 싶습니다. 이를 인수분해하면 a * { 1 + r + ... + r^(n-1) }이 됩니다. 그런데 n이 너무너무 커서 쉽게 구할 수가 없지요. 아래와 같이 recursion을 생각해봅시다. Let S(n) = 1 + r + ... + r^(n-1) -> n이 짝수일 때 (항의 개수가 짝수일 때) S(n) = S(n / 2) * {1 + r^(n/2) } -> n이 홀수일 때 (항의 개수가 홀수일 때) S(n) = S(n - 1) + r^(n-1) 이게 S(n)은 recursive하게 구했습니다. S(0) = 1이라는 초기상태를 알고 있으니 이제 남은 것은 r^n꼴을 구하는 거네요. r^n은 위에서와 비슷한 방식으로 구합니다. n이 홀수일 때와 짝수일 때로 나눠서 recursive하게 구하는 것이죠. 어차피 나머지를 구하면 되는 문제이므로, 각각의 스텝마다 (% MOD)를 해 준다면 long long 범위 안에서 해결 가능합니다. 참고) 저는 예전에 이 문제와 비슷한 문제를 가지고 고민해 본 적이 있어서 생각보다 쉽게 [?] 접근할 수 있었습니다. SRM377-HARD 에디토리얼을 참고하세요. http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm377 ~~~ cpp

const int MOD = 1000000007;
int pow(int a, long long b) {
if (b == 0) return 1;
if (b == 1) return a;
long long ret = 0;
ret = pow(a, b / 2);
ret = ret * ret;
ret %= MOD;
if (b % 2 == 1) {
ret = ret * a;
ret %= MOD;
}
return ret;
}
int get(long long a, long long r, long long k) {
if (k == 0) return 1;
if (k == 1) return (1 + r) % MOD;
long long L, R, ret = 0;
if (k % 2 == 0) {
L = get(a, r, k / 2 - 1);
R = (1 + pow(r, k / 2)) % MOD;
} else {
L = get(a, r, k / 2);
R = (1 + pow(r, (k + 1) / 2)) % MOD;
}
ret = ((L * R) % MOD);
if (k % 2 == 0) ret += pow(r, k);
ret %= MOD;
return ret;
}
struct StrangeArray {
int calculateSum(vector A, vector B, string _N) {
long long N;
int M = sz(A) * sz(B) / __gcd(sz(A), sz(B));
sscanf(_N.c_str(), "%Ld", &N);
long long ret = 0;
for (int i = 0; i < M; ++i) {
long long a = pow(A[i % sz(A)], B[i % sz(B)] + i / sz(B));
long long r = pow(A[i % sz(A)], M / sz(B));
long long K = (N / M) + (N % M > i) - 1;
if (K == -1) break;
ret += ((long long)a * (long long)get(a, r, K)) % MOD;
ret %= MOD;
}
return (int)ret;
}
};

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