Google Code Jam 2019 Round2 : New Elements: Part 1

問題. New Elements: Part 1

2種類の原子からなる $N$ 個の分子が与えられる． $i$ 番目の分子を1種類目と2種類目の原子の個数の対 $(C_i, J_i)$ で表す．このとき，分子量が狭義単調増加するような $N$ 個の分子の並べ方が何通りあるか求めよ．ただし，分子量とは分子に含まれる原子の原子量の総和である．
$i_1, i_2, \ldots, i_N$ が条件を満たす分子の並べ方であるとは，1種類目と2種類目のある原子量 $x, y$ （正整数）が存在して，任意の $1 \le j < N$ に対して， $C_{i_j} x + J_{i_j} y < C_{i_{j + 1}} x + J_{i_{j + 1}} y$ を満たすことである．

制約： $1 \le C_i, J_i \le 10^9$ ，　 $i \neq j$ ならば $(C_i, J_i) \neq (C_j, J_j)$
Small 制約： $2 \le N \le 6$
Large 制約： $2 \le N \le 300$

解法1. 全探索

解法は Editorial を参考にしている．

$a$ 番目と $b$ 番目の分子について考える． $a$ の右隣に $b$ があるとき，1種類目と2種類目の原子のある原子量 $x, y$ が存在して， $C_a x + J_a y < C_b x + J_b y$ となる． $x, y$ は正整数なので式変形を行うと，
　 $J_a - J_b < (C_b - C_a) \frac{x}{y}$
となる．このとき， $\frac{x}{y}$ の範囲は $C_b - C_a$ の値によって次の3つの場合に分けられる．
　1. $C_a = C_b$ のとき， $J_a < J_b$
　2. $C_a < C_b$ のとき， $\frac{J_a - J_b}{C_b - C_a} < \frac{x}{y}$
　3. $C_a > C_b$ のとき， $\frac{J_a - J_b}{C_b - C_a} > \frac{x}{y}$
すべての分子の並べ方に対して，その並べ方が条件を満たすかどうかを $\frac{x}{y}$ が存在する範囲が空でないかどうかで判定する．ただし， $C_a = C_b$ かつ $J_a > J_b$ となる要素対が存在する場合は条件を満たさない． $(0, \infty)$ を $\frac{x}{y}$ の存在する区間の初期値として，上の条件 2, 3 によって範囲を更新する．区間の端点を double 型で計算すると精度が足りないかもしれないので有理数型で計算する（分子と分母からなる整数型の対）．

計算時間： $O(N!)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

template<typename T>
struct Rational {
    using Int = T;
    Int p, q; // p / q

    Rational(Int p, Int q = 1) : p(p), q(q) { normalize(); }

    Int gcd(Int a, Int b) { return b ? gcd(b, a % b) : a; }

    void normalize() { // keep q positive
        if (q < 0) p *= -1, q *= -1;

        const Int d = gcd(p < 0 ? -p : p, q);
        if (d == 0) p = 0, q = 1;
        else p /= d, q /= d;
    }

    bool operator<(const Rational &rhs) const {
        return this->p * rhs.q < this->q * rhs.p;
    }
    bool operator<=(const Rational &rhs) const {
        return !(rhs < *this);
    }
    bool operator>(const Rational &rhs) const {
        return rhs < *this;
    }
    bool operator>=(const Rational &rhs) const {
        return !(*this < rhs);
    }
    bool operator==(const Rational &rhs) const {
        return !(*this < rhs) && !(rhs < *this);
    }
    bool operator!=(const Rational &rhs) const {
        return (*this < rhs) || (rhs < *this);
    }
};

/********************************************************************/
class Solver {
public:
    Solver(int _n) : num_case(_n) {}

    void input() {
        cin >> N;
        C.resize(N); J.resize(N);
        for (int i = 0; i < N; ++i) cin >> C[i] >> J[i];
    }
    void print() {
        cout << "Case #" << num_case << ": " << num_order << '\n';
    }
    void solve();

private:
    // define variable
    const int num_case;
    int N;
    vector<ll> C, J;

    const ll INF = 2 * 1e9;
    int num_order = 0;

};

void Solver::solve() {
    if (6 < N) return ; // large case

    vector<int> idx(N);
    iota(idx.begin(), idx.end(), 0);

    do {
        Rational<ll> lb(0), ub(INF);
        bool exit_mole = true;

        for (int i = 0; i + 1 < N; ++i) {
            const int a = idx[i], b = idx[i + 1];

            if (C[a] == C[b]) {
                if (J[a] > J[b]) {
                    exit_mole = false;
                    break;
                }
                else continue;
            }

            Rational<ll> k(J[a] - J[b], C[b] - C[a]);

            if (C[a] < C[b] && lb < k) lb = k;
            else if (C[a] > C[b] && k < ub) ub = k;

            if (ub <= lb) {
                exit_mole = false;
                break;
            }
        }

        if (exit_mole) ++num_order;

    } while (next_permutation(idx.begin(), idx.end()));
}
/********************************************************************/

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(4) << setiosflags(ios::fixed);

    int T; cin >> T;
    for (int i_case = 1; i_case <= T; ++i_case) {
        Solver s(i_case);
        s.input();
        s.solve();
        s.print();
    }

    return 0;
}

解法2.

解法1の並べ方を全探索する部分を高速化する．
$k_{a, b} = \frac{J_a - J_b}{C_b - C_a}$ とする． $C_b - C_a$ の符号によって， $\frac{x}{y}$ の範囲と， $a$ 番目と $b$ 番目の分子の位置関係が変化する．
　・ $C_a < C_b$ の場合
　　　□ $a < b$ のとき， $k_{a, b} < \frac{x}{y}$
　　　□ $a > b$ のとき， $k_{a, b} > \frac{x}{y}$
　・ $C_a > C_b$ の場合
　　　□ $a < b$ のとき， $k_{a, b} > \frac{x}{y}$
　　　□ $a > b$ のとき， $k_{a, b} < \frac{x}{y}$

$C_a = C_b$ のときは， $J_a < J_b$ ならば $a < b$ ， $J_a > J_b$ ならば $a > b$ となり，2分子間の位置関係は固定される．条件を満たす並べ方は分子量に関して狭義単調増加しており推移性を満たすので，上の条件は隣り合う2分子間のみだけではなく，2分子間の相対的な位置関係も決定する．すなわち， $C_b - C_a$ の符号は入力時に固定されるので， $a$ 番目と $b$ 番目の分子の相対的な位置関係によって $\frac{x}{y}$ が $k_{a, b}$ の左右どちらにあるかが決定される．
$K = \{k_{a, b} \mid 1 \le a < b \le N, C_a \neq C_b \}$ とする． $K \cup \{0\} \cup \{\infty\}$ の要素を昇順に一列に並べたものを $(k_1, k_2, \ldots, k_l)$ とする．このとき，区間 $(k_i, k_{i + 1})$ ( $1 \le i < N$ ) の全体と，条件を満たす並べ方に対応する $\frac{x}{y}$ の存在する最小区間全体との間に一対一対応が存在する．したがって，答えは， $|K| + 1$ となる．

計算時間： $O(N^2 \log N)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

template<typename T>
struct Rational {
    using Int = T;
    Int p, q; // p / q

    Rational(Int p, Int q = 1) : p(p), q(q) { normalize(); }

    Int gcd(Int a, Int b) { return b ? gcd(b, a % b) : a; }

    void normalize() { // keep q positive
        if (q < 0) p *= -1, q *= -1;

        const Int d = gcd(p < 0 ? -p : p, q);
        if (d == 0) p = 0, q = 1;
        else p /= d, q /= d;
    }

    bool operator<(const Rational &rhs) const {
        return this->p * rhs.q < this->q * rhs.p;
    }
    bool operator<=(const Rational &rhs) const {
        return !(rhs < *this);
    }
    bool operator>(const Rational &rhs) const {
        return rhs < *this;
    }
    bool operator>=(const Rational &rhs) const {
        return !(*this < rhs);
    }
    bool operator==(const Rational &rhs) const {
        return !(*this < rhs) && !(rhs < *this);
    }
    bool operator!=(const Rational &rhs) const {
        return (*this < rhs) || (rhs < *this);
    }
};

class Solver {
public:
    Solver(int _n) : num_case(_n) {}

    void input() {
        cin >> N;
        C.resize(N);
        J.resize(N);
        for (int i = 0; i < N; ++i) {
            cin >> C[i] >> J[i];
        }
    }
    void print() {
        cout << "Case #" << num_case << ": " << num_order << '\n';
    }

    void solve();

private:
    // define variable
    const int num_case;
    int num_order = 0;

    int N;
    vector<ll> C, J;
};

void Solver::solve() {
    set<Rational<ll>> num_variety;

    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            if ((C[i] <= C[j] && J[i] <= J[j]) ||
                (C[j] <= C[i] && J[j] <= J[i])) continue;

            if (C[i] != C[j]) {
                Rational<ll> r(J[i] - J[j], C[j] - C[i]);
                num_variety.insert(r);
            }
        }
    }

    num_order = num_variety.size() + 1;
}
/********************************************************************/

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(4) << setiosflags(ios::fixed);

    int T; cin >> T;
    for (int i_case = 1; i_case <= T; ++i_case) {
        Solver s(i_case);
        s.input();
        s.solve();
        s.print();
    }

    return 0;
}

ただ座る人と化していたのでツラかった．