Level 2를 통과한 사람이 생각보다 많지 않아서, Level 1 점수 + 챌린지 점수로 등수가 많이 좌우된 대회였습니다.

Easy (250 pts.)

• 문제 설명 N명의 사람들이 있다. 각각의 사람들은 "현재 모인 사람들 중에서 정확히 k 명이 참말을 하고 있다"고 주장한다. 현재 모인 사람들 중에서 최대 몇 명이 참말을 하고 있는지를 계산하는 프로그램을 작성하시오. [spoiler="더 보기..."]* 해결 방법 r명의 사람이 참말을 하고 있다고 가정할 경우, "r명의 사람이 참말을 한다!"라고 주장하는 사람이 정확히 r명이어야 합니다. r명 보다 많거나 r명 보다 적은 경우에는, 모순이 되어버리기 때문입니다. 문제 해법이 간단해서인지 fastest score가 249.50이 되어버렸군요. :-) ~~~ cpp

struct TrueStatements {
int numberTrue(vector statements) {
int N = sz(statements);
vector a(52, 0);
for (int i = 0; i < N; i++) a[statements[i]]++;
for (int i = N; i >= 0; i--)
if (a[i] == i) return i;
return -1;
}
};

[/spoiler]

Medium (500 pts.)

* 문제 설명
  a0 + a1x1 + a2x2 + ... + anxn 꼴의 정수 다항식이 있을 때, 이 다항식을 만족시키는 정수 해를 찾고 싶다. 정수 해란 주어진 다항식에서 x 대신 그 수를 대입했을 때, 주어진 정수 다항식의 값 = 0을 만족시키는 수를 말한다.
  아래의 pseudo-code를 사용하여 a[0] 부터 a[n]까지 구한다.
[spoiler="더 보기..."]lX = length(X)
lY = length(Y)
for i = 0, 1, ..., n:
  p = i mod lX
  q = (i + Y[i mod lY]) mod lX
  a[i] = X[p]
  X[p] = X[q]
  X[q] = a[i]
[/spoiler]
[spoiler="더 보기..."]
* 해결 방법
  사람들이 이 문제에서 챌린지/시스템 페일 을 많이 당한 이유는 크게 두 가지가 있습니다. 첫 번째 경우는 답에 0이 포함된 경우를 체크하지 않아서이고, 두 번째 경우는 계산 과정 도중 integer 범위를 넘어가버리는 경우입니다.
  제가 접근했던 방법은 "조립제법"을 거꾸로 계산해 나가는 방법을 사용하였습니다. (주어진 다항식) = (x + v) * (.... ) 꼴이라고 가정했을 때, (....) 에서의 상수항은 바로 계산할 수 있습니다. 주어진 다항식의 상수항에서 v로 나눈 값일 테니까요. 그러면 이제 (....)의 x의 계수를 구할 차례인데요, (주어진 다항식)의 x 계수를 A, (....)의 x의 계수를 B, (....)의 상수항을 C라고 할 때, 아래의 조건을 만족시켜야 합니다.
  A = Bv + C
[/spoiler]
  좌변의 x의 계수는 A가 되고, 우변의 x의 계수는 Bv + C가 되기 때문인데요. 그러면 우리는 A와 C를 알기 때문에 B를 거꾸로 계산할 수가 있게 됩니다. 이 문제에서의 다항식은 모두 "정수 다항식"이기 때문에, B 역시 정수가 되어야 합니다. 이제 이러한 계산을 반복해서 v가 해가 되는지 되지 않는지를 검사하면 됩니다. 아래의 소스코드에서 check() 함수가 조립제법을 사용한 부분입니다. :-)
  그리고 위의 식을 잘 살펴보면, 정수해는 항상 a[i] (i는 a[i] != 0을 만족하는 제일 작은 수) 의 약수여야 한다는 사실을 알 수 있습니다. (두 상수항의 곱이 a[i]를 만족시켜야 하기 때문이지요.) 약수의 개수는 그다지 많지 않기 때문에, 충분히 시간안에 계산할 수 있습니다.
~~~ cpp

vector <int> getA(vector <int> X, vector <int> Y, int n) {
    int lX = sz(X), lY = sz(Y);
    vector <int> a;
    for (int i = 0; i <= n; i++) {
        int p = i % lX;
        int q = (i + Y[i % lY]) % lX;
        a.pb(X[p]);
        X[p] = X[q];
        X[q] = a[i];
    }
    return a;
}
vector <int> a, ret;
void check(int v) {
    long long last = a[0], l2;
    for (int i = 1; i < sz(a); i++) {
        if (abs(last) % abs(v) != 0) return;
        l2 = last / v;
        last = a[i] - l2;
    }
    if (last == 0) ret.pb(-v);
}
struct SolvePolynomial {
    vector <int> integerRoots(vector <int> X, vector <int> Y, int n) {
        a = getA(X, Y, n);
        while (a.back() == 0) a.pop_back();
        int g = a[0];
        FOR(i, 1, sz(a)) {
            if (a[i] == 0 || g == 0) { g = 0; break; }
            g = __gcd(g, a[i]);
        }
        if (g > 1) REP(i, sz(a)) a[i] /= g;
        if (a.back() < 0) REP(i, sz(a)) a[i] *= -1;
        if (a[0] == 0) {
            ret.pb(0);
            while (a[0] == 0) {
                FOR(i, 1, sz(a))
                    a[i - 1] = a[i];
                a.pop_back();
            }
        }
        int G = abs(a[0]);
        for (int i = 1; i * i <= G; i++) {
            if (G % i != 0) continue;
            check(i);
            check(-i);
            if (i * i == G) break;
            check(G / i);
            check(-G / i);
        }
        sort(all(ret));
        return ret;
    }
};

Hard (1000 pts.)

• 문제 설명
  • JM님과 상의하세요.
• 해결 방법
  • JM님은 알고 계심.
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]