아무도 관심없는 editorial을 쓰고 있는 astein입니다 ㄱㅡ...

A. Text Messaging Outrage

[문제 설명]

영어문자 서비스를 생각해 보자. 어떤 전화의 keypad는 아래와 같이 구성되어 있다.
[spoiler="더 보기..."] key 2: abc
key 3: def
key 4: ghi
key 5: jkl
key 6: mno
key 7: pqrs
key 8: tuv
key 9: wxyz
[/spoiler]
처음 누르는 키는 첫번째 문자를 나타내며, 여러번 누르면 그 다음 문자를 표현할 수 있다. 예를 들어 "snow"를 쓰기 위해서는 7을 네번, 6을 두번, 6을 세번, 9를 한번 눌러야 하므로 총 10번의 키 입력을 필요로 한다.
당신을 키 배치를 바꾸어, 키 입력을 최소화 하기 위려고 한다. 전화기에 K개의 키가 있고, 각각의 키는 최대 P개의 문자까지 표현할 수 있다. L개의 서로 다른 알파벳(영어가 아니기 때문에 26보다 클 수 있다.)의 사용빈도가 주어질 때, 이 스트링을 표현하기 위해서 필요한 키 입력의 최소 수를 구하시오.
[spoiler="풀이 보러가기..."] [문제 풀이]
직관적으로 생각해 봅시다. 빈도가 높은 알파벳이 있을 때, 이 알파벳을 조금 눌러서 표현할 수 있도록 배치하는 것이 효율적이 되겠지요? 왜냐하면 빈도가 높다는 것은 그만큼 자주 눌러야 할 테니까요. 이러한 생각을 일반화하여 한번 눌러서 표현할 수 있는 키는 빈도가 높은 K개의 알파벳이 될 것입니다. :)
각 키를 한번 눌러서 표현할 수 있는 알파벳을 정했다면 이제 두번 눌러서 표현할 수 있는 알파벳을 정할 차례입니다. 이것도 앞에서 했던 것과 같은 방법으로 많이 누르는 키들을 차례대로 배치하는게 효율적이라고 볼 수 있지요. 이러한 과정을 반복하면 원하는 답을 구할 수 있게 됩니다.
[/spoiler]
[spoiler="네타 주의(GCJ Round 1A를 푼 사람만)"] 사실 이 문제는 GCJ Round 1A의 A번 문제와 공통점이 많습니다. 그 문제에서는 음수가 나올 수 있다는 조건이 있지만, 나머지 조건을 거의 일치하거든요. 이 문제를 약간 수정하면 Round 1A - A번 문제로 바꿀 수 있습니다. 예를 들면 아래와 같이 바꿀 수 있지요.
v1 = (1, 1, .., 2, 2, .., 3, 3, .., P, P, ... ) : 1 ~ P 까지의 수가 K 개씩 있는 벡터
v2 = (키의 빈도 리스트, 나머지 빈 부분은 0으로 채워서 v1과 원소 수를 맞춘다)
이렇게 바꾸면 동일한 문제가 되지요. 이렇게 변환한 문제를 푸는 방법은 해당 글을 참조하세요 :)[/spoiler]
[spoiler="소스코드 보러가기..."]~~~ cpp

#include
#include
#include
#include
using namespace std;
int main() {
int T;
int P, K, L;
scanf("%d", &T);
for (int cn = 1; cn <= T; ++cn) {
printf("Case #%d: ", cn);
scanf("%d%d%d", &P, &K, &L);
vector a(L);
for (int i = 0; i < L; ++i)
scanf("%Ld", &a[i]);
sort(a.begin(), a.end());
reverse(a.begin(), a.end()); // decreasing order로 정렬해서
long long press = 0, ret = 0;
for (int i = 0; i < L; ++i) {
if (i % K == 0) press++;
ret += press * a[i]; // 1부터 차례대로 배치합니다.
}
cout << ret << endl;
}
}

# 지정된 언어 [/spoiler]를 찾을 수 없습니다.
B. Ugly Numbers 

    [문제 설명]
  어떤 숫자가 (2, 3, 5, 7) 중의 하나로 나누어 떨어지면 그 수를 "Ugly Numbers" 라고 부른다. 따라서 14는 Ugly하지만 13은 그렇지 않다. 또한 39는 Ugly이고 121는 Ugly하지 않다. 다만 0은 Ugly한 수라고 부른다. 물론 이는 음수에 대해서도 성립한다. -14와 -39는 Ugly Number라고 부른다. 
  당신은 모처럼 한가한 시간을 보내고 있었다. 그러던 중 "123456"이 씌어진 종이를 발견하고, 이 숫자들 사이에 +나 - 부호를 넣어서 얼마나 많은 Ugly Number가 나오는지 궁금했다. 예를 들어 1 + 234 - 5 + 6 = 236 이 되어 이 수는 Ugly Number이다. 하지만 123 + 4 - 56 = 71 과 같이 수정하면 Ugly하지 않은 수가 나온다.
  얼마나 다양한 경우가 나오는지 계산을 해 보았다. 이 경우 각 숫자들 사이에 +, -를 넣거나, 아무것도 넣지 않는 경우가 있으므로, D자리의 숫자가 있으면 3^(D-1) 가지의 경우가 생긴다. 이 숫자는 앞에 나오는 0을 무시하지 않는다. 즉 "01023"이 입력으로 들어오면 "01023", "0+1-02+3", "01-023" 모두 올바른 수식이다.
  당신이 해야 할 일은 간단하다. 3^(D-1)가지의 경우 중에서 ugly number가 나오는 경우가 얼마나 되는지 구하여라.
[spoiler="풀이 보러가기..."]    [문제 풀이]
  Small Dataset은 D가 13 이하입니다. 따라서 작은 데이터의 경우에는 모든 경우를 다 구해도 최대 531441가지의 경우밖에 나오지 않습니다. 즉 모든 경우를 다 구해도 시간 안에 답을 얻을 수 있게 되지요. 하지만 Large Dataset은 D는 40 이하로, 최대 405,2555,1530,1897,6267번의 연산을 필요로 하지요. 컴퓨터가 아주 좋지 않은 이상 8분 안에 답을 구할 수는 없습니다 :<
  그럼 Large Dataset을 푸는 방법을 생각해 봅시다. 우선 Ugly Number의 조건을 다시 한번 생각해 보도록 하지요. 2, 3, 5, 7중의 하나로 나누어 떨어지면 Ugly Number가 됩니다. 그러면 각각의 숫자로 나누었을 때 나머지를 가지고 튜플(tuple)을 생성해 보도록 합시다. 예를 들어 26은 (0, 2, 1, 5) 가 되고, 39는 (1, 0, 4, 4)가 되겠지요. 이러한 튜플의 원소 중에서 0이 있다면 Ugly Number, 없다면 Ugly가 아니라고 볼 수 있겠지요.
  튜플이 전체 몇 가지나 있을지 계산을 해 봅시다. 첫번째 위치에는 0이나 1, 두번째 위치에는 0, 1, 2, 세번째는 0 ~ 4, 네번째는 0 ~ 6이 올 수 있지요. 이 경우의 수는 2 * 3 * 5 * 7 = 210가지 입니다. 즉 20으로 만들어진 튜플과 230으로 만들어진 튜플은 같지요. 즉 어떤 숫자를 총 210가지의 상태중 하나로 표현이 가능합니다.
  이제 튜플얘기는 여기까지로 하고, 원래 문제의 풀이로 돌아가 봅시다. 이 문제는 동적계획법(Dynamic Programming)이라는 방법으로 접근하면 쉽게 해결할 수 있습니다. 큰 문제를 답을 작은 문제의 해를 이용하여 구한다는 컨셉이지요. 이차원 배열 Table을 잡아서 아래와 같이 정의합니다.
      Table i, j = i개의 문자열을 사용하여 (210으로 나눈 나머지가 j)를 만들 수 있는 경우의 수.

  예제에 있는 "011"를 가지고 진행을 해 봅시다. 일단 1개의 문자열 "0"을 가지고 만들 수 있는 경우는 "0" 밖에 없지요. 즉 Table 1, 0 = 1이 됩니다.
  "01"을 가지고 만들 수 있는 경우를 생각해 봅시다. 우선 이 사이에 +를 넣는 경우는 "0"으로 만들어진 모든 경우에 1을 더한 값이 됩니다. 즉 Table 2, 1 += Table 1, 0이 되고, Table 2, 2 += Table 1, 1이 되지요. 왼쪽의 식을 말로 표현하면 {"01"을 사용했을 때 210으로 나눈 나머지가 1이 되는 경우의 수}는 {"0"을 사용하여 210으로 나눈 나머지가 0이 되는 경우의 수}만큼이 추가됩니다. "+1"을 뒤에 붙이면 되니까요. 이제 0과 1 사이에 -를 넣는 경우를 봅시다. 이 경우는 Table 2, 1 += Table 1, 2가, Table 2, 2 += Table 1, 3이 됩니다. "0"으로 나머지 2를 만들고 뒤에 "-1"을 붙이면 되니까요. 마지막으로 아무것도 붙이지 않는 경우는 "01"이 되지요. 즉 이 값은 나머지가 1이므로 Table 2, 1에 1을 더해주면 됩니다.
  위의 점화식을 일반적으로 표현하면 Table i, j = Sum(Table k, p) : { 단, k는 0 ~ i-1 이며 (p + STRING[k,i]를 210으로 나눈 나머지) = j를 만족하는 p에 대하여 } 가 됩니다. 소스코드는 아래와 같이 되고요.
  위의 방법과는 비슷하지만 포함-배제의 원리를 사용해도 풀 수 있습니다. Go(N)이라는 함수를 "N으로 나누었을 때 나누어 떨어지는 모든 경우의 수"를 구하는 함수라고 가정하면, 우리가 구하고자 하는 Ugly Number의 수는 Go(2) + Go(3) + Go(5) + Go(7) - Go(2*3) - Go(2*5) - Go(2*7) - Go(3*5) - Go(3*7) - Go(5*7) + go(2*3*5) + Go(2*3*7) + Go(2*5*7) + Go(3*5*7) - go(2*3*5*7) 이 되지요. 포함 배제의 원리는 인터넷에 많이 있습니다 ! (고등학교 수학에서 배우는 것으로 알고 있습니다.) Go함수도 위에서 헀던 것처럼 Dynamic Programming을 사용하면 작성할 수 있지요 :)[/spoiler]
[spoiler="소스코드 보러가기(Small Dataset)"]~~~ cpp

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
string S;
long long ret;
void go(int last, long long num, long long sum, bool sign) {
    int iSign;
    if (sign) iSign = 1; else iSign = -1;
    if (last == S.size()) {
        sum += iSign * num;
        if (sum % 2 == 0 ||
            sum % 3 == 0 ||
            sum % 5 == 0 ||
            sum % 7 == 0) {
            ret++;
        }
        return;
    }
    int d = S[last] - '0';
    go(last + 1, num * 10 + d, sum, sign); // no sign
    go(last + 1, d, sum + iSign * num, true); // plus
    go(last + 1, d, sum + iSign * num, false); // minus
}
int main() {
    int T;
    scanf("%d", &T);
    for (int cn = 1; cn <= T; ++cn) {
        ret = 0;
        cin >> S;
        go(1, S[0] - '0', 0, true);
        printf("Case #%d: %Ld\n", cn, ret);
    }
}

[/spoiler]
[spoiler="소스코드 보러가기(Large Dataset)"]~~~ cpp

#include
#include
#include
using namespace std;
string S;
int modular(string s) { // 숫자가 매우 클 수 있으므로, 한 자리씩 끊어서 계산합니다.
int ret = 0;
for (int i = 0; i < s.size(); ++i) {
ret = (ret * 10 + (s[i] - '0')) % 210;
}
return ret;
}
long long table[45][211];
int main() {
int T;
scanf("%d", &T);
for (int cn = 1; cn <= T; ++cn) {
cin >> S;
memset(table, 0, sizeof(table));
for (int i = 0; i < S.size(); ++i) {
for (int j = 0; j <= i; ++j) {
int last = modular(S.substr(j, i - j + 1)); // last = j번째 ~ i번째 자리의 수를 210으로 나눈 나머지 값
if (j == 0) {
table[i][last]++; // 사이에 아무 부호도 없는 경우
} else {
for (int k = 0; k < 210; ++k) {
table[i][k] += table[j - 1][(k + last) % 210]; // 두 수 사이에 (-) 부호를 넣는 경우
table[i][k] += table[j - 1][(k + 210 - last) % 210]; // 두 수 사이에 (+) 부호를 넣는 경우
}
}
}
}
long long ret = 0;
for (int i = 0; i < 210; ++i) {
if (i % 2 == 0 || i % 3 == 0 || i % 5 == 0 || i % 7 == 0) ret += table[S.size() - 1][i];
}
printf("Case #%d: %I64d\n", cn, ret); // mingw C++로 컴파일을 하여 I64d를 사용하였습니다.
}
}

[/spoiler]


C. Increasing Speed Limits 
    [문제 설명]
  당신은 고속도로에서 과속을 하다가 경찰에게 붙잡혔다. 당신은 경찰에게 붙잡히기 전까지 브레이크를 한번도 사용하지 않았다는 것이 밝혀졌다. 그래서 당신은 "여기까지 오는 동안 내가 봤던 속도 제한 표지판은 점점 올라갔기 때문에 한번도 브레이크를 밟지 않았다" 라고 주장하였다.
  이제 당신은 계속 증가하는 표지판을 볼 수 있는 경우의 수를 구하여 당신의 무죄[?]를 입증하려고 한다. 단, 표지판을 하나도 보지 않는 경우는 제외한다. 
  예를 들어 (1, 2, 5)는 (1, 4, 2, 3, 5, 5)의 순서대로 표지판이 있을 때, 볼 수 있는 표지판의 순서 중 하나이다. 또한 위의 데이터에서는 (1, 2, 5)를 볼 수 있는 경우가 두 가지가 있다고 카운트한다. 입력 데이터는 아래의 소스코드를 실행하여 나오는 결과를 가지고 사용한다.
[spoiler="더 보기..."]for i = 0 to n-1
  print A[i mod m]
  A[i mod m] = (X * A[i mod m] + Y * (i + 1)) mod Z
[/spoiler]
[spoiler="풀이 보러가기..."]
    [문제 풀이]
 이 문제도 Small Dataset은 동적계획법으로 해결할 수 있습니다. i번째 표지판을 마지막으로 봤을때의 경우의 수를 T[i]라고  가정하면, T[i] = 1 + sum(T[j]) { when j < i and speed[j] < speed[i] } 라고 할 수 있겠지요. 말로 표현하자면 i번째 표지판을 마지막으로 본 경우의 수는 (1) i번째 표지판만 본 경우 + (2) j번째 표지판을 보고 다른 표지판은 모두 지나치다가 i번째 표지판을 보는 두 가지 경우로 나눌 수 있으니까요. 
 위의 식을 가지고 풀면 O(n^2)의 시간복잡도로 이 문제를 해결할 수 있습니다. 하지만 이 경우 Large Dataset은 풀 수 없게 되지요.
 위에서 정의한 테이블을 살짝 다르게 표현해 봅시다. 위에서는 T[i]를 i번째 표지판을 마지막으로 봤다고 가정하였다면, S[i] = "i라고 씌어 있는 표지판을 마지막으로 봤을때의 경우의 수"로 가정해 보는 겁니다. 이 경우에도 동적 계획법으로 풀 수 있겠지요. (물론 스피드 제한이 작은 경우에 대해서지만요.)  S[i]를 사용하여 점화식을 세워 보면 S[i] = 1 + sum(S[j]) { when j < i } 가 됩니다. 제한속도 i인 표지판을 보기 전엔 제한속도가 i보다 작은 표지판을 봤을테니까요. (앞에 1을 더한 이유는, i를 처음 본 경우입니다)
 어째서 비슷하게 보이지만 T[i]가 아니라 S[i]를 정의했을까요? 그 이유는 {when j < i and speed[j] < speed[i]} 보다 {when j < i } 로 줄어들었기 때문입니다. 즉 S[i]를 구하기 위해서는 S[0] + S[1] + ... + S[i -1]을 구하면 되었으니까요. T[i]의 경우에는 speed값도 동시에 고려해 주어야 했지만 S[i]는 그럴 필요가 없기 때문이지요.
 물론 순차적인 방법으로 접근하면 S[0]부터 S[i-1]까지의 합을 구하기 위해서는 O(n)의 시간복잡도가 필요합니다. 이래서는 T[i]를 사용하여 구한것과 다를바가 없지요. 시간 복잡도를 줄이기 위해 효율적인 자료구조를 사용해서 접근해야 합니다. 여기에서는 Binary Indexed Tree (명칭이 맞는지는...)를 사용해서 풀어보도록 하겠습니다 :)
 <IMG alt=tree_001.JPG src="/files/attach/images/53443/163/048/tree_001.JPG" editor_component="image_link">
 위와 같은 트리를 구성했다고 가정합시다. 사각형은 Leaf Node로 위에서 나타낸 S[i]를 나타냅니다. 8번 노드가 S[0], 9번 노드는 S[1], ..., 15번 노드는 S[7]이라고 이해하시면 됩니다. i를 0~7로 가정했을 때의 그림이라고 보시면 되겠습니다. 원으로 나타낸 노드의 값은 현재 노드를 기준으로 하위 Leaf Node의 합을 가지고 있습니다. 2번 노드는 8~11번 노드의 합을, 6번 노드는 12~13번 노드의 합을 가지고 있다고 볼 수 있겠지요.
 위와 같이 트리를 구성한 후, S[5] = S[0] + S[1] + ... + S[4] 를 구하는 알고리즘을 살펴 보겠습니다. 일단 우리가 구해야 하는 값은 S[0] ~ S[4] 까지의 합이므로, 8번부터 12번 노드까지의 합이 됩니다. 일일이 다섯번의 덧셈 연산으로 구할 수 있겠지만, 8번노드와 9번노드의 합은 4번노드에, 10번노드와 11번노드의 합은 5번 노드에 저장되어 있다는 것을 이용하면 세 번의 덧셈 연산만으로도 구할 수 있지요. 또한 4번노드와 5번노드의 합은 2번 노드에 저장되어 있으므로 S[5] = 2번 노드 + 12번 노드 로 구할 수 있습니다. 처음에 다섯번의 덧셈이 필요했던 과정이 단 두번의 덧셈으로 해결할 수 있게 된 셈이지요.
  이 트리를 이용하면 N번의 덧셈이 필요했던 것을 lg N 번의 덧셈을 사용하여 구할 수 있게 됩니다. 즉 원래의 알고리즘이 O(N^2)이었다면 O(N lg N)의 복잡도로 감소된 셈이지요. 따라서 이 문제를 해결할 수 있게 되는 것입니다 :)
  S[i]값을 구했다면, 트리에 갱신하는 과정도 포함되어야 겠지요. 이번에 S[5]번 노드가 새로 갱신되었다고 합시다. 그러면 S[5] = 13번 노드의 합을 가지고 있는 부모 노드들의 값이 변경되어야 합니다. 즉 13번 -> 6번 -> 3번 -> 1번 노드의 값이 변경되겠네요. 이는 부모노드를 trace 하면서 변경시켜주면 되기 때문에 트리의 높이만큼의 연산을 필요로 하겠지요. 결국 이 연산도 O(lg N)이 됩니다.
  이 문제를 보면 S[i]에서 i의 범위가 0 ~ 10억-1 입니다. 따라서 실제로 이렇게 구현하면 메모리때문에 고생하게 될 것입니다. 이를 어떻게 해결해야 할지는 각자 생각해 보세요! [아래의 소스코드에 정답이 있습니다.]
[/spoiler]
[spoiler="소스코드 보러가기(Small Dataset)"]~~~ cpp

#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
const int MOD = 1000000007;
vector <int> make_sequence(vector <int> init, int n, int m, long long X, long long Y, long long Z) {
    vector <int> a;
    for (long long i = 0; i < n; ++i) {
        a.push_back(init[i % m]);
        init[i % m] = (X * init[i % m] + Y * (i + 1)) % Z;
    }
    return a;
}
int table[5001];
int main() {
    int T;
    scanf("%d", &T);
    int n, m;
    long long X, Y, Z;
    for (int cn = 1; cn <= T; ++cn){
        scanf("Case #%d: ", cn);
        cin >> n >> m >> X >> Y >> Z;
        vector <int> init(m);
        for (int i = 0; i < m; ++i)
            cin >> init[i];
        vector <int> a = make_sequence(init, n, m, X, Y, Z);
        int ret = 0;
        for (int i = 0; i < n; ++i) {
            table[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (a[j] < a[i]) {
                    table[i] = (table[i] + table[j]) % MOD;
                }
            }
            ret = (ret + table[i]) % MOD;
        }
        printf("Case #%d: %d\n", cn, ret);
    }
}

~~~[/spoiler]
[spoiler="소스코드 보러가기(Large Dataset)"]~~~ cpp

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
const int MOD = 1000000007;
int tree[1 << 20];
vector <int> make_sequence(vector <int> init, int n, int m, long long X, long long Y, long long Z) {
    vector <int> a;
    for (long long i = 0; i < n; ++i) {
        a.push_back(init[i % m]);
        init[i % m] = (X * init[i % m] + Y * (i + 1)) % Z;
    }
    return a;
}
void add(int pos, int value) {
    int num = (1 << 19) + pos;
    while (num != 0) {
        tree[num] = (tree[num] + value) % MOD;
        num >>= 1;
    }
}
int getsum(int pos) {
    int num = (1 << 19) + pos;
    int ret = 0;
    while (num != 0) {
        if (num % 2 == 0) {
            ret = (ret + tree[num]) % MOD;
            num--;
        } 
        num >>= 1;
    }
    return ret;
}
int main() {
    int T;
    scanf("%d", &T);
    int n, m, X, Y, Z;
    for (int cn = 1; cn <= T; ++cn){
        scanf("Case #%d: ", cn);
        scanf("%d%d%d%d%d", &n, &m, &X, &Y, &Z);
        vector <int> init(m);
        for (int i = 0; i < m; ++i)
            scanf("%d", &init[i]);
        vector <int> b = make_sequence(init, n, m, X, Y, Z);
        vector <int> a = b; /* vector <int> a 가 위의 설명에 있는 S 배열 입니다. */
        /* make_sequence로 만들어진 수가 10억(1억인가요? 문제가 기억이...) 이하의 수이기 때문에,  *
         * 50만 이하로 맞추기 위해 map을 이용하였습니다.            *
         * 일종의 count sort라고 볼 수 있겠지요.                      */
        sort(b.begin(), b.end());
        map<int, int> mtable;
        for (int i = 0; i < n; ++i) mtable[b[i]] = i;
        for (int i = 0; i < n; ++i) a[i] = mtable[a[i]];
        memset(tree, 0, sizeof(tree));
        int ret = 0;
        for (int i = 0; i < n; ++i) {
            a[i]++;
            int tmpsum = getsum(a[i] - 1);
            add(a[i], 1 + tmpsum); // 트리에 경우의 수만큼 추가
            ret = (ret + (1 + tmpsum)) % MOD; // 답을 갱신. 우리는 MOD로 나눈 나머지를 구하면 됩니다.
        }
        printf("Case #%d: %d\n", cn, ret);
    }
}

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