질문 사항이 있으시면 댓글로 달아주시거나 hanirc에 있는 #icpc 채널로 오셔서 astein을 찾아주세요.
(댓글로 달면 답변이 늦어질 수 있으므로 irc로 오시는 것을 추천합니다 :)

A. Crop Triangles
[문제 설명]
격자 좌표에 많은 나무들이 심어져 있다. 당신은 이 나무들을 연결하여 삼각형을 만들고 싶다. 특히 삼각형의 중심이 "정수 좌표"가 되는 경우를 원한다. 참고로 (x1, y1), (x2, y2), (x3, y3)로 이루어진 삼각형의 중심 좌표는 ( (x1 + x2 + x3) / 3, (y1 + y2 + y3) / 3 ) 이다.
입력은 아래의 pseudo-code를 사용하여 generate 한다.
[spoiler="더 보기..."] X = x0, Y = y0
print X, Y
for i = 1 to n - 1
X = (A * X + B) MOD M
Y = (C * Y + D) MOD M
[/spoiler]
만약 넓이가 0인 삼각형이라고 하더라도, 이 문제에서는 valid한 삼각형이라고 본다.
[spoiler="풀이 보러가기..."] [문제 풀이]
삼각형을 만들 수 있는 경우를 세어 봅시다. n개의 좌표가 입력으로 주어지는 경우, 이 중에서 3개를 순서없이 고르는 경우가 되니, nC₃이 되겠지요. Small Dataset의 경우에는 n이 겨우 100밖에 되지 않으므로 모든 경우를 고려해서 풀어도 답을 구할 수 있습니다. 이 경우는 어렵지 않으니 소스코드는 생략하도록 할게요 :)
그러면 이제 Large Dataset을 풀어봅시다. Large Dataset은 n이 10만이기 때문에 위의 방법으로는 구할수가 없지요.
(1, 2), (3, 5)를 두 점으로 잡고 나머지 한 점의 좌표를 (x, y)라고 가정할 때 이 세 점으로 중심이 "정수 좌표"가 되는 조건을 찾아보도록 합시다. 우선 x좌표가 정수가 되어야 하므로, (1 + 3 + x) / 3 = k (k는 임의의 정수) -> 1 + 3 + x = 3k -> x = 3k - 4 꼴이 됩니다. 마찬가지로 y좌표의 조건을 구햅보면 y = 3m - 7꼴이 되지요. 즉, x와 y 모두 3으로 나누었을 때 나머지가 2인 모든 점에 대하여 중심이 정수좌표인 삼각형을 만족시키게 됩니다. 좀 더 확장해서 생각하면 어차피 우리가 만들고자 하는 것은 3으로 나누었을때의 나머지만 가지고 계산해도 상관이 없으므로, 모든 좌표를 3으로 나눈 나머지로 표현해도 답이 같게 나옴을 알 수 있습니다.

그러면 총 9가지의 상태가 나오게 됩니다. 이제 이 점들을 가지고 만들 수 있는 모든 삼각형의 갯수를 세어주면 Large Dataset도 풀 수 있게 되는 것이지요. 자세한 것은 아래의 소스코드를 참조해주세요. 생각보다 어렵지 않으니까요 :)[/spoiler]
[spoiler="소스코드 보러가기..."]~~~ cpp

#include
#include
#include
#include
using namespace std;
long long N, a, b, c, d, x0, y0, M;
long long ret;
vector X, Y;
long long t[3][3];
void generate_triangle() {
X.clear(), Y.clear();
X.push_back(x0), Y.push_back(y0);
for (int i = 0; i < N - 1; ++i) {
X.push_back((a * X.back() + b) % M);
Y.push_back((c * Y.back() + d) % M);
}
}
int main() {
int T;
scanf("%d", &T);
for (int cn = 1; cn <= T; ++cn) {
cin >> N >> a >> b >> c >> d >> x0 >> y0 >> M;
generate_triangle();
memset(t, 0, sizeof(t));
for (int i = 0; i < N; ++i)
t[X[i] % 3][Y[i] % 3]++;
ret = 0;
for (int i = 0; i < 9; ++i) {
for (int j = i; j < 9; ++j) {
for (int k = j; k < 9; ++k) {
int xmod = (i / 3 + j / 3 + k / 3) % 3;
int ymod = (i % 3 + j % 3 + k % 3) % 3;
if (xmod == 0 && ymod == 0) {
long long n1 = t[i / 3][i % 3];
long long n2 = t[j / 3][j % 3];
long long n3 = t[k / 3][k % 3];
if (i == j && j == k) { // all points are same.
ret += n1 * (n2 - 1) * (n3 - 2) / 6;
continue;
} else if (i == j || j == k || k == i) { // two of three are same.
if (i == j) {
ret += n1 * (n2 - 1) * n3 / 2;
} else if (j == k) {
ret += n1 * n2 * (n3 - 1) / 2;
} else if (k == i) {
ret += (n1 - 1) * n2 * n3 / 2;
}
continue;
} else {
ret += n1 * n2 * n3; // all points are different.
}
}
}
}
}
cout << "Case #" << cn << ": " << ret << endl;
}
}

[/spoiler]

B. Number Sets 
    [문제 설명]
  연속된 숫자들이 있을 때, 당신은 이 숫자들을 그룹으로 묶어서 관리하고 싶어한다.
  어떤 정수 구간 [A, B]와 자연수 P가 주어진다. 초기 상태는 각각의 숫자들은 하나씩으로 이루어진 그룹을 형성하고 있다.
  이 구간에서 임의의 두 숫자를 선택했을 때, 둘 모두 P 이상의 소수로 나누어 떨어진다면, 이 두 숫자들이 이루어진 그룹을 하나로 합칠 수 있다. 이 과정을 반복하면 최종 상태에는 몇 개의 그룹이 남겠는가?
  A = 10, B = 20, C = 3 이라면 아래와 같이 7개의 그룹이 만들어진다.
  {10, 12, 15, 18, 20}, {11}, {13}, {14}, {16}, {17}, {19}
[spoiler="풀이 보러가기..."]    [문제 풀이]
  이 문제를 그래프로 변환해서 생각해 보도록 하겠습니다. 각각의 수를 Vertex로 두고, 임의의 두 수가 동시에 P 이상의 소수로 나누어 떨어진다면, 두 Vertex 사이를 잇는 Edge를 생성해 줍시다.
  그러면 이 문제는 몇개의 Disjoint Graph인지 구하는 문제로 변환이 가능합니다. Small Dataset은 n이 작기 때문에 adjacent matrix로 그래프를 표현해도 풀리지만, Large Dataset의 경우는 n이 꽤 크기 때문에 adjacent list로 그래프를 나타내야 하지요. :) 또한 3, 6, 9, 12의 경우에는 모두 3으로 나누어 떨어지기 때문에 3-6, 3-9, 3-12, 6-9, 6-12, 9-12 이렇게 여섯개의 Edge가 생성될 수 있지만, Disjoint Graph의 여부인지 구하는 것이 우리의 목표이기 때문에, 3-6, 3-9, 3-12의 정보만 가지고 있다고 하더라도 정해를 구할 수 있게 됩니다.
  아래의 제 소스 코드는 adjajcent list로 graph를 구성하여 graph의 수를 count하는 방식으로 구현되어 있습니다. 이 방법을 사용하지 않고,  Disjoint Set을 쓰는것도 하나의 솔루션이 될 수 있겠지요. :) Disjoint Set으로 짠 소스는 다른 분이 올려주실거라 믿고 B번의 풀이는 여기서 마치겠습니다. :-P
[/spoiler]
[spoiler="소스코드 보러가기..."]
~~~ cpp

#include <vector>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
int prime[1000001]; // 0 -> prime
vector <vector <int> > graph;
vector <int> check;
void bfs(int num) {
    queue<int> Q;
    Q.push(num);
    check[num] = 1;
    while (!Q.empty()) {
        int v = Q.front(); Q.pop();
        for (int i = 0; i < graph[v].size(); ++i) {
            if (check[graph[v][i]] == 0) {
                check[graph[v][i]] = 1;
                Q.push(graph[v][i]);
            }
        }
    }
}
int main() {
    int T;
    long long A, B, P;
    scanf("%d", &T);
    // 소수는 에라토스테네스의 체를 사용하여 구합니다.
    for (long long i = 2; i <= 1000000; ++i) {
        if (prime[i] == 0) {
            for (long long j = i * i; j <= 1000000; j += i)
                prime[j] = 1;
        }
    }
    for (int cn = 1; cn <= T; ++cn) {
        cin >> A >> B >> P;
        graph.assign(B - A + 1, vector <int> ());
        check.assign(B - A + 1, 0);
        for (long long i = P; i <= B - A; ++i) {
            if (prime[i - A]) continue;
            int start = ((A + (i - 1)) / i) * i;
            for (long long j = start + i; j <= B; j += i) {
                graph[start - A].push_back(j - A);
                graph[j - A].push_back(start - A);
            }
        }
        int ret = 0;
        for (long long i = A; i <= B; ++i) {
            if (check[i - A] == 0) {
                ret++;
                bfs(i - A);
            }
        }
        cout << "Case #" << cn << ": " << ret << endl;
    }
}

[/spoiler]

C. Mousetrap
[문제 설명]
Mousetrap은 혼자서 할 수 있는 간단한 카드게임이다. 이 게임은 1부터 N으로 이루어진 N장의 카드를 사용한다. 게임의 규칙은 아래와 같다.

1. 게임은 제일 윗 장의 카드를 확인한다.
2. 1부터 시작해서 하나씩 카운트 해 나간다. 카운트한 숫자와 카드에 쓰여져 있는 숫자가 같다면 카드를 덱에서 제거하고 (1)을 반복한다. 카드를 덱에서 제거한 경우 다시 1부터 카운트한다. 만약 두 수가 같지 않다면 현재 카드를 덱 아래로 넣고 (1)을 반복한다.
3. 만약 당신의 카운트가 N+1이 된다면 당신은 지게 된다. 그 전에 모든 카드를 덱에서 제거했다면 당신은 이긴다. 카드 덱에 2, 5, 3, 1, 4 순서로 카드가 쌓여있다고 하자. 그러면 첫 턴에 2를 오픈하고, 카운트는 1이므로 패스한다. 그 다음 5를 오픈하고, 카운트는 2이므로 패스한다. 세 번째로 3이 오픈되고, 카운트가 3이 되므로 우리는 이 덱에서 3을 제거할 수 있다. [그러면 현재 상태는 1, 4, 2, 5가 된다. 카드는 항상 덱 아래에 넣는다는 것을 참고한다.] 두 번째 턴에는 1을 오픈하고, 카운트가 1이므로 바로 제거할 수 있다. 같은 방법으로 반복하면 2, 4, 5의 순서로 제거할 수 있고, 당신은 이 게임을 이길 수 있게 되는 것이다. 카드를 잘 배열하면 덱에서 제거하는 순서를 1에서부터 차례대로 없앨 수 있다. 이러한 경우를 "Perfect" 한 경우라고 부른다. 예를 들어 4장의 카드를 사용한 게임에서 1, 4, 2, 3으로 카드가 배치되어 있다면 "Perfect"한 경우가 되는 것이다. 당신은 N장의 카드를 가지고 게임을 할 때 "Perfect" 한 게임을 할 수 있는 초기상태에서, k번째 위치에 있는 카드를 구하는 프로그램을 작성하여야 한다. (input/output은 원래 문제를 참조하세요) [spoiler="풀이 보러가기..."] [문제 풀이] Small DataSet부터 풀어 봅시다. 항상 첫번째 위치에는 1이 들어가 있겠지요. 그리고 한칸 건너뛰어 2가 들어가 있고, 두칸 건너뛰어 3이... 이런 식으로 채워져 있게 됩니다. 만약 세는 도중에 다른 숫자가 채워져 있다면 skip하고 count하는 방식으로 채워 나갈 수 있습니다. Small DataSet의 K가 5000이라고 하더라도, 단순히 채워나간다면 시간안에 답을 구하기 힘들 것입니다. 따라서 간단한 처리를 해 주어야 겠지요. 만약 현재 전체 카드가 200장, 남은 카드가 3장이고, 197칸 건너뛰어야 한다고 가정해 봅시다. 200장을 한 번 훑어 볼 때 마다 우리는 겨우 3칸 건너뛰는 연산을 할 것이며, 197번이나 무의미한 skip연산을 하게 되지요. 이러한 필요없는 연산을 줄이기 위해 "나머지 연산"을 사용합니다. 197번 건너뛰나 194번 건너뛰나 ... 2번 건너뛰나 결과는 같게 될 테니까요. 이 방법만 사용해 주더라도 시간 안에 원하는 답을 구할 수 있게 됩니다. 하지만 Large DataSet은 위의 방법을 사용하더라도 한계에 부딪치게 됩니다. K가 너무 크거든요. Large DataSet을 풀기 위해 다른 방법으로 접근해 보도록 하지요. :0 N = 5일때의 경우를 예로 들어 설명하도록 하겠습니다. 배열을 하나 잡고 이 배열을 unused라고 부르도록 하지요. 즉 아직 채워져 있지 않은 칸을 나타냅니다. unused : 1 1 1 1 1 --> 초기 상태입니다. 우선 우리는 첫번째 칸에 항상 1이 들어가는 것을 알지요. 이제 첫번째 칸의 값을 0으로 바꾸겠습니다. unused : 0 1 1 1 1 --> 첫번째 칸의 값이 0이 되었습니다. 그러면 이제 우리는 현재 위치에서 한칸 점프하고, 그 다음칸을 선택해야 겠지요. 현재 위치는 첫번째이므로 한칸 (두번째 위치)을 점프하고 다음 1이 있는 위치는 세번째 위치가 됩니다. 여기에 2가 들어가겠네요. unused : 0 1 0 1 1 --> 세번째 칸의 값도 0이 되었습니다. 이번엔 두 칸 점프합니다. 네 번째, 다섯 번째 위치를 점프하고 다음에 나오는 1은 두 번째 위치네요. 이제 여기에는 3이 들어갈 것입니다. unused : 0 0 0 1 1 --> 두 번째 위치에서 세 칸 점프할 차례입니다. 그러면 네번째, 다섯번째, 네번째를 점프하고 다섯번째 칸에 4가 들어갑니다. 반복하면 네 번째 위치에 5가 들어가죠. 즉 "1 3 2 5 4"라는 값이 완성됩니다. 위에서 사용한 연산을 정리하면 크게 두 가지 연산이 있습니다. 1) 1 지우기 ... ① 2) 현재 위치에서 k번 점프한 위치 구하기 하지만 현재 위치에서 k번 점프한 위치 구하기는 "현재 위치보다 앞에 몇개의 1이 있는지 구하기.. ②" 연산과 "i번째 1찾기.. ③" 연산으로 구할 수 있습니다. 현재 위치를 알고 i번째 위치를 찾을 수 있다면 (2)를 구할 수 있으니까요. Binary Indexed Tree (정식 명칭인지는 가물가물) 를 사용하여 풀어보도록 하겠습니다. 아래쪽의 사각형은 Leaf Node를 의미하고, 가운데에 있는 원은 Non-Leaf Node로, 각 값은 자기 하위 노드들의 합으로 구성되어 있습니다. 원과 사각형 밖에 있는 값은 Tree Index입니다. (편의상 1-based Tree로 두었습니다.) N = 5일때의 트리를 나타내면 아래와 같습니다. Leaf Node는 위에서 설명했던 unused Array로 생각하시면 이해하기 쉬울 겁니다. 여기에서 이제 ①을 적용해 봅시다. 1은 항상 첫번째 unused array를 0으로 만들게 되지요. 이러면 8번 index를 0으로 바꿔줍니다. 이 때 8번 node의 ancestor node인 4, 2, 1번의 값은 모두 1씩 감소하게 되지요. 이 다음 상태는 아래의 트리와 같이 됩니다. 이제 현재 위치 (8번 노드, unused의 첫번째 위치) 앞에 몇 개의 1이 있는지 찾아보는 ③번 과정을 수행해 봅시다. 사실 이건 별로 의미가 없지요 (0개니까요.) 그럼 다른 예를 들어 세번째 위치 (10번 노드) 앞에 몇 개의 1이 있는지 찾아봅시다. 우리는 8,9,10번 노드의 합을 구하고 싶습니다. 하지만 이 것들을 일일이 더해준다면 O(N)만큼의 시간이 걸리게 되지요. 따라서 이렇게 트리로 나타낸 이유는 이 연산을 좀 더 빠르게 하고 싶기 때문입니다. 위의 경우만 보더라도, 8과 9의 합은 4번 노드에 저장이 되어 있지요. 즉 8,9,10번 노드의 합 = 4,10번 노드의 합이 되므로 좀 더 빠르게 계산할 수 있게 됩니다. 현재 위치를 k라고 하면 처음부터 k-1번째까지 몇 개의 1이 있는지 찾아보면 되는 것이지요. 마지막으로 ②번 과정입니다. 두번째 트리에서 앞에서 세 번째 1을 찾는다는 요청이 들어왔을때의 처리 과정을 예를 들어 살펴보겠습니다. 이 과정은 루트에서부터 출발하는데요. 루트의 값이 4이므로, 루트 밑에 4개의 1이 존재한다는 뜻이 되겠습니다. 여기서 왼쪽 child의 값은 3, 오른쪽 child의 값은 1이지요. 우리가 찾고자 하는 3번째 값은 루트보다 왼쪽 노드에 있다는 것을 알 수 있습니다. 왼쪽 child의 값이 3이라는 것은 왼쪽에 1이 3개가 있다는 뜻이니까요. 그럼 왼쪽으로 가서 (2번 인덱스) 살펴보면 왼쪽 child (4번) 값은 1, 오른쪽 child(5번) 값은 2임을 알 수 있습니다. 이번엔 오른쪽으로 가야겠지요. 오른쪽으로 이동하는 경우는 왼쪽에 있는 1을 빼 줍니다. 2번 인덱스를 기준으로 왼쪽 child 부분에 1이 1개 있으므로, 오른쪽 child에서 두번째 1을 찾으면 되기 때문이지요. 이 과정을 recursive하게 반복하면 11번 Node에 이르게 됩니다. 위의 ①, ②, ③ 연산 모두 O(lg N)의 연산만에 해결할 수 있습니다. 이러한 과정을 N번 반복하면 모든 인덱스를 채울 수 있으므로 케이스마다 O(N lg N) 번의 연산을 통하여 답을 구할수가 있는 것이지요. 아래의 소스코드에 주석은 없지만 설명과 매치시켜가면서 읽으신다면 이해하는 데 도움이 될 것입니다 :) 좋은 하루 되세요. [/spoiler] [spoiler="소스코드 보러가기..."]~~~ cpp

#include
#include
#include
using namespace std;
int tree[1 << 21];
int table[1000001];
void add(int pos, int value) {
int now = pos + (1 << 20);
while (now != 0) {
tree[now] += value;
now >>= 1;
}
}
int findpos(int pos) {
int now = 1;
while (now < (1 << 20)) {
if (tree[now * 2] >= pos) {
now = now * 2;
} else {
pos -= tree[now * 2];
now = now * 2 + 1;
}
}
return now - (1 << 20);
}
int sum(int pos) { // get [1..pos]
int ret = 0;
int now = pos + (1 << 20);
while (now != 0) {
if (now % 2 == 0) {
ret += tree[now];
now--;
}
now /= 2;
}
return ret;
}
int main() {
int T;
int K, N;
scanf("%d", &T);
for (int cn = 1; cn <= T; ++cn) {
printf("Case #%d:", cn);
memset(tree, 0, sizeof(tree)); // 트리 초기화
memset(table, -1, sizeof(table));
scanf("%d", &K);
for (int i = 0; i < K; ++i)
add(i, 1);
int last = 0, target;
for (int i = 1; i <= K; ++i) {
add(last, -1); // 트리에서 1을 빼줍니다.
table[last] = i; // 1을 빼준 위치에 i를 사용한다는 뜻이지요.
if (i == K) break;
int s = sum(last); // 현재 위치보다 앞쪽에 1이 몇개인지 셉니다.
int step = (i + 1) % (K - i); // (i+1)번만큼 Jump합니다. (K-i)보다 큰 경우에는 사이클을 돌게 되므로 나머지 연산을 취할 수 있지요.
if (s + step > (K - i)) {
target = s + step - (K - i);
} else {
target = s + step;
if (target == 0) target = K - i;
}
// 우리가 다음 숫자를 채울 위치가 몇번째 1인지를 정합니다. 그 값이 target입니다.
last = findpos(target); // last에는 target번째 1이 몇번 노드에 있는지를 저장합니다.
}
scanf("%d", &N);
vector a(N);
for (int i = 0; i < N; ++i) {
scanf("%d", &a[i]);
printf(" %d", table[a[i] - 1]);
}
printf("\n");
}
}

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