けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ ???? Increasing Sequence (AUPC 2020 day1-D)

in-place な DP にもっと慣れていきたい

問題へのリンク

問題概要

 N 個の数列がある。 i 個目の数列は  M_{i} 個の要素からなる。 i 個目の数列の  j 番目の要素は  A_{ij} と表す。

  •  i 個目の数列から 1 個以下の要素を選び、選んだ要素を元の数列の順番通りに並べた数列を  X とする。

数列  X が狭義単調増加となるように選ぶ方法は何通りあるか、1000000007 で割ったあまりを求めよ (数列が等しくても選び方が異なれば異なるものとする)。

制約

  •  1 \le N \le 10^{5}
  •  1 \le \sum_{j} M_{j} \le 10^{5}

考えたこと

とりあえず、登場する数値は高々  10^{5} 種類しかないようなので、座圧する。そのときの登場しうる数値の種類数を  S と表すことにする。

さて、この問題を見たとき、次のような DP をしたくなる

  • dp[ i ][ j ] := 最初の i 個の数列についての処理を確定したとき、数列の最後の値が j であるようにする操作の個数

このとき、DP は次のような式になる。

  • 各 j に対して dp[ i + 1 ][ j ] += dp[ i ][ j ] (なにも選ばない)
  • i 番目の数列中の値 k に対して、dp[ i + 1 ][ k ] += sum(dp[ i ][ j ], j = 0, 1, ..., k - 1)

このままでは  O(NS) の計算量となって間に合わない。しかしよく見ると、DP の更新を in-place にすれば 1 個目は無視できる。2 個目の更新については、BIT 上で DP すればそれぞれの値 k に対して  O(\log S) の計算量で更新できる。

全体の計算量は  O(S \log S) となる。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s << endl; }




// modint
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() const { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr istream& operator >> (istream &is, Fp<MOD>& x) noexcept {
        is >> x.val;
        x.val %= MOD;
        if (x.val < 0) x.val += MOD;
        return is;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

template <class Abel> struct BIT {
    Abel UNITY_SUM = 0;
    vector<Abel> dat;
    
    // [0, n)
    BIT(int n, Abel unity = 0) : UNITY_SUM(unity), dat(n, unity) { }
    void init(int n) {
        dat.assign(n, UNITY_SUM);
    }
    
    // a is 0-indexed
    inline void add(int a, Abel x) {
        for (int i = a; i < (int)dat.size(); i |= i + 1)
            dat[i] = dat[i] + x;
    }
    
    // [0, a), a is 0-indexed
    inline Abel sum(int a) {
        Abel res = UNITY_SUM;
        for (int i = a - 1; i >= 0; i = (i & (i + 1)) - 1)
            res = res + dat[i];
        return res;
    }
    
    // [a, b), a and b are 0-indexed
    inline Abel sum(int a, int b) {
        return sum(b) - sum(a);
    }
    
    // debug
    void print() {
        for (int i = 0; i < (int)dat.size(); ++i)
            cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

const int MOD = 1000000007;
using mint = Fp<MOD>;

int N;
vector<vector<int>> A;
vector<int> all;

mint solve() {
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());
    int S = all.size();
    BIT<mint> bit(S + 10);
    bit.add(0, 1);
    for (int i = 0; i < N; ++i) {
        vector<pair<int,mint>> chs;
        for (int j = 0; j < A[i].size(); ++j) {
            int k = lower_bound(all.begin(), all.end(), A[i][j]) - all.begin() + 1;
            mint add = bit.sum(0, k);
            chs.emplace_back(k, add);
        }
        for (auto p : chs) bit.add(p.first, p.second);
    }
    return bit.sum(0, S+2);
}

int main() {
    while (cin >> N) {
        A.assign(N, vector<int>());
        all.clear();
        for (int i = 0; i < N; ++i) {
            int M;
            cin >> M;
            A[i].resize(M);
            for (int j = 0; j < M; ++j) cin >> A[i][j], all.push_back(A[i][j]);
        }
        cout << solve() << endl;
    }
}

AOJ ???? Umg Kart (HUPC 2020 day3-K)

確かに、えでゅふぉのラス問にありそう!

問題へのリンク

問題概要

 N 人の選手が距離  L のレースを走る。 i (= 1, 2, \dots, N) 人目はデフォルトでは距離 1 走るのに  t_{i} 秒かかる。

スタートから距離が  0 \le X_{1} \lt X_{2} \lt \dots \lt X_{M} \lt L のところにアイテムがある。各アイテムは各選手に対して独立に、確率  \frac{p_{i}}{100} で減速 (距離 1 走るのにかかる時間が  t_{i} + D 秒になる) し、確率  \frac{100 - p_{i}}{100} で加速 (距離 1 走るのにかかる時間が  t_{i} - D 秒になる) する。

1 番目の選手の順位の期待値を求めよ。ただし、選手  i, j が同着のとき、 i \lt j ならば選手  i の方が順位が上とする。

制約

  •  2 \le N, L, t_{i} \le 10^{5}
  •  1 \le M \le L - 1

考えたこと

すべて 0-indexed で考えることにする。選手  0 の順位が  a であるとは、選手  1, 2, \dots, N-1 のうち選手  0 に勝った人が  a - 1 人であることを意味する。よって求める期待値は、期待値の線形性から、

  •  1 + \sum_{i = 2}^{N} (選手 i が選手 1 に勝つ確率)

ということになる。選手  i が選手  0 に勝つ確率を求めるためには、次のものを求める必要がある。

  • 選手  0 がゴールするまでの時間の確率分布を求める
  • 選手  i がゴールするまでの時間の確率分布を求める

これらは自体は独立に計算できる。

距離 1 あたり t 秒で走る選手のゴール時間の確率分布

選手の速度を  t [ 秒/m] とする。選手が何秒でゴールするかについては  2^{M} 通りのパターンがある。しかしながら、減速する分の距離  l (このとき、加速する距離は  L - X_{0} - l になる) としてありうるパターンは  O(L) 通りになるので、それほど多くはない。加速する分の距離が  l であるとき、選手のゴール時間は

 Lt + lD - (L - X_{0} - l)D

となる。というわけで、選手が減速分距離が  l となる確率を計算しよう。普通に考えれば

  •  {\rm dp} \lbrack i \rbrack \lbrack l \rbrack := 最初の  i 個のチェックポイントを使った時点で、減速距離が  l になる確率

として、部分和 DP をすればよい。でもこれでは  O(ML) の計算量を要するので間に合わない。こういうのを FFT で高速化するのは典型ではある。

部分和 DP を求める問題を FFT

結局、各チェックポイントごとに加速または減速する距離を  l_{0}, l_{1}, \dots, l_{M} として、次の多項式を考えたとき、 x^{l} 次の項が求める確率となる!!!

 (p_{0}x^{l_{0}} + (1 - p_{0}))(p_{1}x^{l_{1}} + (1 - p_{1})) \dots (p_{M-1}x^{l_{M-1}} + (1 - p_{M-1}))

これも単純に FFT すると、 O(L^{2} \log L) となってしまう。しかし順番を工夫すると  O(L (\log L)^{2}) になるのだ。具体的には次のようにすればよい。

  •  M 個ある多項式のうち次数の小さい 2 個を選んで計算し、その積で置き換えることを繰り返す

このように順序を工夫する発想で計算量を下げる考え方は、次の問題でも出ていた模様。

codeforces.com

確率分布から答えへ

各選手の減速距離に関する確率分布が求められたら、選手  i が選手  0 に勝つ確率は、次のように計算できる。

  • 選手  0 の減速距離が  l_{0} であるとき
  • 選手  i の減速距離を  l_{i} として

 Lt_{0} + l_{0}D - (L - X_{0} - l_{0})D \gt Lt_{i} + l_{i}D - (L - X_{0} - l_{i})D
 l_{i} - l_{0} \lt \frac{L(t_{0} - t_{i})}{2D}

となる。つまり、 l_{i} - l_{0} の確率分布がわかれば、次のようにして答えが求められる。

  •  l_{i} - l_{0} の確率分布の累積和をとる
  • それを用いて  \frac{L(t_{0} - t_{i})}{2D} 未満となる確率を求める

 l_{i} - l_{0} の確率分布は、ふたたび FFT を用いて計算できる。計算量は  O(L (\log L)^{2} + N)

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

// modint
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() const { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    constexpr bool operator < (const Fp& r) const noexcept {
        return this->val < r.val;
    }
    friend constexpr istream& operator >> (istream &is, Fp<MOD>& x) noexcept {
        is >> x.val;
        x.val %= MOD;
        if (x.val < 0) x.val += MOD;
        return is;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

namespace NTT {
    long long modpow(long long a, long long n, int mod) {
        long long res = 1;
        while (n > 0) {
            if (n & 1) res = res * a % mod;
            a = a * a % mod;
            n >>= 1;
        }
        return res;
    }

    long long modinv(long long a, int mod) {
        long long b = mod, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        u %= mod;
        if (u < 0) u += mod;
        return u;
    }

    int calc_primitive_root(int mod) {
        if (mod == 2) return 1;
        if (mod == 167772161) return 3;
        if (mod == 469762049) return 3;
        if (mod == 754974721) return 11;
        if (mod == 998244353) return 3;
        int divs[20] = {};
        divs[0] = 2;
        int cnt = 1;
        long long x = (mod - 1) / 2;
        while (x % 2 == 0) x /= 2;
        for (long long i = 3; i * i <= x; i += 2) {
            if (x % i == 0) {
                divs[cnt++] = i;
                while (x % i == 0) x /= i;
            }
        }
        if (x > 1) divs[cnt++] = x;
        for (int g = 2;; g++) {
            bool ok = true;
            for (int i = 0; i < cnt; i++) {
                if (modpow(g, (mod - 1) / divs[i], mod) == 1) {
                    ok = false;
                    break;
                }
            }
            if (ok) return g;
        }
    }

    int get_fft_size(int N, int M) {
        int size_a = 1, size_b = 1;
        while (size_a < N) size_a <<= 1;
        while (size_b < M) size_b <<= 1;
        return max(size_a, size_b) << 1;
    }

    // number-theoretic transform
    template<class mint> void trans(vector<mint> &v, bool inv = false) {
        if (v.empty()) return;
        int N = (int)v.size();
        int MOD = v[0].getmod();
        int PR = calc_primitive_root(MOD);
        static bool first = true;
        static vector<long long> vbw(30), vibw(30);
        if (first) {
            first = false;
            for (int k = 0; k < 30; ++k) {
                vbw[k] = modpow(PR, (MOD - 1) >> (k + 1), MOD);
                vibw[k] = modinv(vbw[k], MOD);
            }
        }
        for (int i = 0, j = 1; j < N - 1; j++) {
            for (int k = N >> 1; k > (i ^= k); k >>= 1);
            if (i > j) swap(v[i], v[j]);
        }
        for (int k = 0, t = 2; t <= N; ++k, t <<= 1) {
            long long bw = vbw[k];
            if (inv) bw = vibw[k];
            for (int i = 0; i < N; i += t) {
                mint w = 1;
                for (int j = 0; j < t/2; ++j) {
                    int j1 = i + j, j2 = i + j + t/2;
                    mint c1 = v[j1], c2 = v[j2] * w;
                    v[j1] = c1 + c2;
                    v[j2] = c1 - c2;
                    w *= bw;
                }
            }
        }
        if (inv) {
            long long invN = modinv(N, MOD);
            for (int i = 0; i < N; ++i) v[i] = v[i] * invN;
        }
    }

    // small case (T = mint, long long)
    template<class T> vector<T> naive_mul 
    (const vector<T> &A, const vector<T> &B) {
        if (A.empty() || B.empty()) return {};
        int N = (int)A.size(), M = (int)B.size();
        vector<T> res(N + M - 1);
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < M; ++j)
                res[i + j] += A[i] * B[j];
        return res;
    }

    // mint
    template<class mint> vector<mint> operator * 
    (const vector<mint> &A, const vector<mint> &B) {
        if (A.empty() || B.empty()) return {};
        int N = (int)A.size(), M = (int)B.size();
        if (min(N, M) < 30) return naive_mul(A, B);
        int MOD = A[0].getmod();
        int size_fft = get_fft_size(N, M);
        vector<mint> a(size_fft), b(size_fft), c(size_fft);
        for (int i = 0; i < N; ++i) a[i] = A[i];
        for (int i = 0; i < M; ++i) b[i] = B[i];
        trans(a), trans(b);
        vector<mint> res(size_fft);
        for (int i = 0; i < size_fft; ++i) res[i] = a[i] * b[i];
        trans(res, true);
        res.resize(N + M - 1);
        return res;
    }
};

const int MOD = 998244353;
using mint = Fp<MOD>;
using namespace NTT;

int main() {
    long long N, L, M, D;
    cin >> N >> L;
    vector<long long> t(N);
    for (int i = 0; i < N; ++i) cin >> t[i];
    cin >> M >> D;
    vector<long long> x(M + 1, L);
    vector<mint> p(M);
    for (int i = 0; i < M; ++i) cin >> x[i] >> p[i], p[i] /= 100;

    priority_queue<pair<int,vector<mint>>, vector<pair<int,vector<mint>>>, greater<pair<int,vector<mint>>>> que;
    for (int i = 0; i < M; ++i) {
        long long l = x[i+1] - x[i];
        vector<mint> v(l+1, 0);
        v[0] = mint(1) - p[i];
        v[l] = p[i];
        que.push({l+1, v});
    }
    while (que.size() >= 2) {
        auto left = que.top(); que.pop();
        auto right = que.top(); que.pop();
        auto mul = left.second * right.second;
        que.push({mul.size(), mul});
    }
    auto f = que.top().second;
    long long deg = f.size() - 1;
    auto g = f;
    reverse(g.begin(), g.end());
    auto fg = f * g;
    vector<mint> sum(fg.size()+1, 0);
    for (int i = 0; i < fg.size(); ++i) sum[i+1] = sum[i] + fg[i];

    mint res = 1;
    for (int i = 1; i < N; ++i) {
        long long lim = deg + (L * (t[0] - t[i]) + D * 20000000 + D * 2 - 1) / (D * 2) - 10000000;
        chmax(lim, 0LL);
        chmin(lim, (long long)sum.size() - 1);
        res += sum[lim];
    }
    cout << res << endl;
}

AOJ ???? Hokkaido High School (HUPC 2020 day3-M)

比較的簡単枠だとは思っていたけど、B よりも解かれたのはびっくり!

問題へのリンク

問題概要

北海道高校には  M 個の科目があり、それぞれ 1, 2, 3 の 3 段階で成績がつけられる。 各生徒の成績は長さ  M の文字列で表される

生徒  X が生徒  Y の「上位互換」であるとは

  • すべての科目  i について ( X の科目  i の成績) ≥ ( Y の科目  i の成績)
  • ある科目  i が存在して、( X の科目  i の成績) > ( Y の科目  i の成績) の両方がみたされることをいいます。

今、教室には誰もいない。これから  Q 人の生徒が順に教室に入っていく。 i 番目の生徒の成績は文字列  S_{i} で表される。各生徒は、自分が教室に入ったときに教室に自分の上位互換が存在していると悲しくなる。

 Q人それぞれの生徒について、悲しくなるかどうかを判定せよ。

制約

  •  1 \le Q \le 5 \times 10^{5}
  •  1 \le M \le 15

考えたこと

上位互換の条件に含まれる「1 科目だけ完全に上でなければならない」という部分が扱いづらい。ここでは、A が B 以上であるとは、すべての成績が A >= B であることと定義する。このとき、(a, b, c, ...) の上位互換の人は

  • (a+1, b, c, ...) 以上
  • (a, b+1, c, ...) 以上
  • (a, b, c+1, ...) 以上
  • ...

のいずれかの条件を満たすことになる。

DP へ

以上の考察を基にして、こんな DP を前処理で求めておこう。

  • dp[ S ] := 成績 S 以上をおさめる人の index の最小値

これは先ほどの考察から、

dp[ S ] = min_{T: S を 1 教科だけ点数を上げたもの} dp[ T ]

という漸化式で更新できる。この計算量は  O(M 3^{M})。これはまさに  M 次元累積 min そのもの。高速ゼータ変換の一種ともみなせる。

このテーブルがあれば、各クエリには簡単に答えられる。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

inline int conv(const string &s) {
    int res = 0;
    for (int i = s.size()-1; i >= 0; --i) res *= 3, res += (int)(s[i] - '1');
    return res;
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<string> S(N);
    vector<int> bitS(N);
    for (int q = 0; q < N; ++q) cin >> S[q], bitS[q] = conv(S[q]);

    vector<int> three(M+1, 1);
    for (int i = 0; i < M; ++i) three[i+1] = three[i] * 3;
    vector<int> dp(three[M], N);
    for (int q = 0; q < N; ++q) chmin(dp[bitS[q]], q);
    for (int bit = three[M]-1; bit >= 0; --bit) {
        for (int i = 0; i < M; ++i) {
            if (bit / three[i] % 3 == 2) continue;
            chmin(dp[bit], dp[bit + three[i]]);
        }
    }
    for (int q = 0; q < N; ++q) {
        int res = N;
        for (int i = 0; i < M; ++i) {
            if (S[q][i] == '3') continue;
            chmin(res, dp[bitS[q] + three[i]]);
        }
        cout << (res < q ? 1 : 0);
    }
    cout << endl;
}

コード

AOJ ???? Proper Instructions (HUPC 2020 day3-J)

比較的素直な考察で解ける問題

問題へのリンク

問題概要

umgくんは 1 次元上の座標 0 にいます。今は時刻 0 です。時刻が 1 進むごとに、今いる座標より 1 大きい座標に移動するか、 1 小さい座標に移動するか、その座標にとどまるかという行動ができます。

 N 個の指示が与えられます。  i 個目の指示は、「時刻  T_i には  L_{i} \le x \le R_{i} を満たす座標  x にいなければならない」という指示です。

 N 個の指示の空でない部分集合  S が「適切」であるとは、umgくんが上手く動くことで、 S に含まれるすべての指示に従うことができることをいいます。適切である指示の集合としてあり得るものの個数を 998244353 で割った余りを求めてください。

制約

  •  1 \le N \le 300
  •  1 \le T_{1} \lt \dots \lt T_{N} \le 10^{9}
  •  -10^{9} \le L_{i} \le R_{i} \le 10^{9}

考えたこと

数え上げ問題では、まず判定問題を解くのが定石ではある!

時刻順にソートして、存在可能区間を遷移していけば OK。i 番目の区間で [l, r) の範囲にいることが可能であった場合、j 番目の区間では dt = tj - ti として、[max(l - dt, Lj), min(r + dt, Rj)] の範囲内にいることができる (これが空だったら両立不可)。

DP へ

以上の考察から、とりあえずこんな DP が考えられる

  • dp[ i ][ l ][ r ] := i 番目の区間を考えている段階で移動可能区間が [l, r] であるような状態にするための、区間の選び方の場合の数

このままでは状態量が多すぎる。しかし、この値が正になるような (l, r) の組合せはとても少ない。具体的には、次のようになる。

  • l としてとりうる値は、右へと進みながら時刻を遡ったときに、ある区間の左端になるような点 ( O(N) 個しかない)
  • r としてとりうる値は、左へと進みながら時刻を遡ったときに、ある区間の右端になるような点 ( O(N) 個しかない)

よって状態を圧縮して  O(N^{3}) で解ける。

コード

あんまりきれいじゃないかも...

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};
using mint = Fp<998244353>;

int main() {
    int N;
    cin >> N;
    vector<long long> T(N), L(N), R(N);
    for (int i = 0; i < N; ++i) cin >> T[i] >> L[i] >> R[i];

    int M = N*2 + 10;
    vector<vector<mint>> dp(M, vector<mint>(M, 0));
    auto ndp = dp;
    dp[0][0] = 1;
    vector<long long> left({0}), right({0}), nleft, nright;
    long long curT = 0;
    for (int i = 0; i < N; ++i) {
        ndp.assign(M, vector<mint>(M, 0));
        nleft = vector<long long>({-T[i], L[i]});
        nright = vector<long long>({T[i], R[i]});
        for (int j = 0; j < i; ++j) {
            nleft.push_back(L[j] - T[i] + T[j]);
            nright.push_back(R[j] + T[i] - T[j]);
        }
        sort(nleft.begin(), nleft.end());
        sort(nright.begin(), nright.end());
        nleft.erase(unique(nleft.begin(), nleft.end()), nleft.end());
        nright.erase(unique(nright.begin(), nright.end()), nright.end());
        for (int l = 0; l < left.size(); ++l) {
            for (int r = 0; r < right.size(); ++r) {
                if (dp[l][r] == 0) continue;

                // 区間 i を選ばない場合
                int nl = lower_bound(nleft.begin(), nleft.end(), left[l] - T[i] + curT) - nleft.begin();
                int nr = lower_bound(nright.begin(), nright.end(), right[r] + T[i] - curT) - nright.begin();
                ndp[nl][nr] += dp[l][r];

                // 区間 i を選ぶ場合
                long long nL = max(L[i], left[l] - T[i] + curT);
                long long nR = min(R[i], right[r] + T[i] - curT);
                if (nL <= nR) {
                    nl = lower_bound(nleft.begin(), nleft.end(), nL) - nleft.begin();
                    nr = lower_bound(nright.begin(), nright.end(), nR) - nright.begin();
                    ndp[nl][nr] += dp[l][r];
                }
            }
        }
        swap(ndp, dp);
        swap(nleft, left);
        swap(nright, right);
        curT = T[i];
    }
    mint res = 0;
    for (int l = 0; l < left.size(); ++l) {
        for (int r = 0; r < right.size(); ++r) {
            res += dp[l][r];
        }
    }
    cout << res - 1 << endl;
}

AOJ ???? Plane Graph (HUPC 2020 day3-E)

原案でした!僕は比較的アドホック寄りの問題を作る傾向があったかもだけど、これは典型な感じ。

問題へのリンク

問題概要

頂点数  N、辺数  M の連結な平面グラフが与えられます。ここで、各頂点の座標  (x_{i}, y_{i}) も入力として与えられます。

どの 3 点も一直線上にはありません。また、橋も関節点もありません。したがって、平面グラフは多角形を敷き詰めたものとみなすことができます。これらの多角形のうち、内部に頂点や辺を含まないものの面積の最大値を 2 倍した値を求めてください。

制約

  •  3 \le N \le 300
  •  3 \le M \le \min(1000, \frac{N(N+1)}{2})

考えたこと

多角形をすべて抽出しよう!!!
各頂点 v ごとに、あらかじめ、v に接続する辺を偏角でソートしておくことにする。 そして、平面グラフの各辺に対応して、双方向の向きの辺をつけた有向グラフとして考えることにする。

f:id:drken1215:20200916195821p:plain

そして目的はこういう風にすること。

f:id:drken1215:20200916195857p:plain

以下を貪欲に繰り返すことで、面をすべて抽出できる。

  • 有向辺 (u, v) が残っているならば、それを一つ選ぶ
  • v に接続している有向辺 (残っているもの) のうち、u の方向から時計回りに回して最初に出てくるものを選んで進む
  • 以後、終点が u になるまでこれを繰り返す
  • そうすると、出来上がるものは以下のいずれかになるので、それを構成する有向辺をすべて削除する
    • 内部に点を一つも含まない多角形 (それを構成する有向辺は反時計回り)
    • 平面グラフの外側 (これだけそれを構成する有向辺が時計回り)

こうしてできた多角形の符号付き面積を求めていけば OK。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using DD = double;
const DD INF = 1LL<<60;      // to be set appropriately
const DD EPS = 1e-10;        // to be set appropriately
const DD PI = acosl(-1.0);
DD torad(int deg) {return (DD)(deg) * PI / 180;}
DD todeg(DD ang) {return ang * 180 / PI;}

/* Point */
struct Point {
    DD x, y;
    Point(DD x = 0.0, DD y = 0.0) : x(x), y(y) {}
    friend ostream& operator << (ostream &s, const Point &p) {return s << '(' << p.x << ", " << p.y << ')';}
};
inline Point operator + (const Point &p, const Point &q) {return Point(p.x + q.x, p.y + q.y);}
inline Point operator - (const Point &p, const Point &q) {return Point(p.x - q.x, p.y - q.y);}
inline Point operator * (const Point &p, DD a) {return Point(p.x * a, p.y * a);}
inline Point operator * (DD a, const Point &p) {return Point(a * p.x, a * p.y);}
inline Point operator * (const Point &p, const Point &q) {return Point(p.x * q.x - p.y * q.y, p.x * q.y + p.y * q.x);}
inline Point operator / (const Point &p, DD a) {return Point(p.x / a, p.y / a);}
inline Point conj(const Point &p) {return Point(p.x, -p.y);}
inline Point rot(const Point &p, DD ang) {return Point(cos(ang) * p.x - sin(ang) * p.y, sin(ang) * p.x + cos(ang) * p.y);}
inline Point rot90(const Point &p) {return Point(-p.y, p.x);}
inline DD cross(const Point &p, const Point &q) {return p.x * q.y - p.y * q.x;}
inline DD dot(const Point &p, const Point &q) {return p.x * q.x + p.y * q.y;}
inline DD norm(const Point &p) {return dot(p, p);}
inline DD abs(const Point &p) {return sqrt(dot(p, p));}
inline DD amp(const Point &p) {DD res = atan2(p.y, p.x); if (res < 0) res += PI*2; return res;}
inline bool eq(const Point &p, const Point &q) {return abs(p - q) < EPS;}
inline bool operator < (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x < q.x : p.y < q.y);}
inline bool operator > (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x > q.x : p.y > q.y);}
inline Point operator / (const Point &p, const Point &q) {return p * conj(q) / norm(q);}

/* Line */
struct Line : vector<Point> {
    Line(Point a = Point(0.0, 0.0), Point b = Point(0.0, 0.0)) {
        this->push_back(a);
        this->push_back(b);
    }
    friend ostream& operator << (ostream &s, const Line &l) {return s << '{' << l[0] << ", " << l[1] << '}';}
};

DD CalcArea(const vector<Point> &pol) {
    DD res = 0.0;
    for (int i = 0; i < pol.size(); ++i) {
        res += cross(pol[i], pol[(i+1)%pol.size()]);
    }
    return res/2.0L;
}

int N, M;
vector<Point> allp;
vector<vector<int>> G;

DD ang(int from, int to) {
    Point p = allp[to] - allp[from];
    return amp(p);
}

long long solve() {
    long long res = 0;
    vector<map<int,int>> next(N);
    vector<map<int,bool>> used(N);
    for (int v = 0; v < N; ++v) {
        vector<int> edges = G[v];
        sort(edges.begin(), edges.end(), [&](int a, int b) {
            return ang(v, a) < ang(v, b);
        });
        for (int j = 0; j < edges.size(); ++j) {
            next[v][edges[j]] = edges[(j+1)%edges.size()];
            used[v][edges[j]] = false;
        }
    }
    for (int v = 0; v < N; ++v) {
        for (int i = 0; i < G[v].size(); ++i) {
            int to = G[v][i];
            if (used[v][to]) continue;
  
            vector<Point> vp;
            int cur = v;
            do {
                vp.push_back(allp[cur]);
                used[cur][to] = true;
                int nto = next[to][cur];
                cur = to;
                to = nto;
            } while (cur != v);
            DD area = CalcArea(vp);
            if (area < 0) {
                area = -area * 2;
                long long tmp = (long long)(area + 0.1);
                chmax(res, tmp);
            }
        }
    }
    return res;
}

int main() {
    cin >> N >> M;
    allp.resize(N);
    for (int i = 0; i < N; ++i) cin >> allp[i].x >> allp[i].y;
    G.assign(N, vector<int>());
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    cout << solve() << endl;
}