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

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

AtCoder ABC 133 E - Virus Tree 2 (500 点)

木の走査って

  • 根の方から情報を配っていく
  • 子ノードたちの情報を引っ張ってくる (いわゆる木 DP)

という二つの方向性があって、状況に応じてうまいこと使い分けるとよいイメージがある。

問題へのリンク

問題概要

 N 頂点の木があたえられる。木の各頂点を  K 色に塗り分ける方法のうち、どの距離が 2 以下の二頂点も異なる色になるようにする方法が何通りあるか、1000000007 で割ったあまりを求めよ。

制約

  •  1 \le N, K \le 10^{5}

考えたこと

こういうの一目、木 DP なのだけど、ちょっと手を動かしてみると


なんか頂点を見ていくごとに、各頂点について「自由度」が決まって、その積が答えになる


みたいな雰囲気をかすかに感じた。なのでその直感を信じると、子ノードから頑張って情報を引っ張って木 DP する、というよりは単純に各ノードを見ていくだけで答えが求まりそう。

詰めてみる

根をとりあえず決める。

  • 根はどう塗ってもいいので  K 通り
  • 根の子頂点たちは、根と同じ色ではダメで、さらに互いにどの頂点も色が異なっていなければならないので、その個数を  c とすると、 {}_{K-1}{\rm P}_{c} 通りになる
  • それより深いところにある頂点 v についてその子頂点たちは、v とその親とは色が異なっていなければならず、さらに互いにどの頂点も色が異なっていなければならないので、その個数を  c とすると、 {}_{K-2}{\rm P}_{c} 通りになる

という感じで、根から下へ下がっていって掛け算していけば答えになる。

modint

以下の実装では、

を用いている。

#include <iostream>
#include <vector>
using namespace std;

// modint (1000000007 で割ったあまりを扱う構造体)
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) v += 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 istream& operator >> (istream &is, Fp<MOD>& x) noexcept {
        return is >> 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 T> struct BiCoef {
    vector<T> fact_, inv_, finv_;
    constexpr BiCoef() {}
    constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
        init(n);
    }
    constexpr void init(int n) noexcept {
        fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
        int MOD = fact_[0].getmod();
        for(int i = 2; i < n; i++){
            fact_[i] = fact_[i-1] * i;
            inv_[i] = -inv_[MOD%i] * (MOD/i);
            finv_[i] = finv_[i-1] * inv_[i];
        }
    }
    constexpr T com(int n, int k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        return fact_[n] * finv_[k] * finv_[n-k];
    }
    constexpr T fact(int n) const noexcept {
        if (n < 0) return 0;
        return fact_[n];
    }
    constexpr T inv(int n) const noexcept {
        if (n < 0) return 0;
        return inv_[n];
    }
    constexpr T finv(int n) const noexcept {
        if (n < 0) return 0;
        return finv_[n];
    }
};

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

int N, K;
vector<vector<int>> G;

void rec(int v, int p, mint &res, int depth) {
    int chs = 0;
    for (auto ch : G[v]) {
        if (ch == p) continue;
        ++chs;
        rec(ch, v, res, depth+1);
    }
    if (depth == 0) res *= bc.com(K-1, chs) * bc.fact(chs);
    else res *= bc.com(K-2, chs) * bc.fact(chs);
}

int main() {
    bc.init(110000);
    cin >> N >> K;
    G.assign(N, vector<int>());
    for (int i = 0; i < N-1; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    mint res = 1;
    rec(0, -1, res, 0);
}

AtCoder ABC 133 D - Rain Flows into Dams (400 点)

時々こういうの見る気がする。とりあえず求めたい値を  x と置いてみる感じ。

問題概要

 N を奇数とする。整数  A_{0}, A_{1}, \dots, A_{N-1} が与えられるので

  •  x_{0} + x_{1} = 2A_{0}
  •  x_{1} + x_{2} = 2A_{1}
  •  x_{2} + x_{3} = 2A_{2}
  • ...
  •  x_{N-1} + x_{0} = 2A_{N-1}

を満たすような  x_{0}, x_{1}, \dots, x_{N-1} を求めよ。

制約

  •  3 \le N \le 10^{5}-1
  •  N は奇数

考えたこと

問題の構造として

 x_{0} を決めると、残りが芋づる式にすべて決まってしまう」

というのがある。例えば

  •  2A = 6, 16, 14, 10, 10

に対して  x_{0} = 0 とすると

  •  x = 0, 6, 10, 4, 6 (6 - 0 = 6、16 - 6 = 10、14 - 10 = 4、10 - 4 = 6)

と決まるのだけど、最後  6 + 0 = 10 とはなっていないので辻褄が合わない。これが辻褄が合うような  x を見つけたい。 x_{0} = x とすると

  •  x_{0} = x
  •  x_{1} = 6-x
  •  x_{2} = 10+x
  •  x_{3} = 4-x
  •  x_{4} = 6+x

という風になる。

  •  x + (6 + x) = 10

を解いて  x = 2 になる。なお  x_{0} = x とおいたときの  x_{N-1} の式は、  N が奇数だと、「 x_{0} = 0 としたときの  x_{N-1} の値」に  x を足したものになる。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N; cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i], A[i] *= 2;

    // x0 = 0 のとき
    long long offset = 0;
    for (int i = 0; i < N; ++i) offset = A[i] - offset;
    long long x = offset / 2;

    // 復元
    long long cur = x;
    for (int i = 0; i < N; ++i) {
        cout << cur << " ";
        cur = A[i] - cur;
    }
    cout << endl;
}

AtCoder ABC 133 C - Remainder Minimization 2019 (300 点)

高校数学で

 n を整数として  n(n+1)(n+2) は 3 の倍数であることを示せ」

という問題はよくあったと思う。これは「連続する 3 整数には 3 の倍数が含まれる」というのが理由になっている。今回こんな感じのことを考える。

問題へのリンク

問題概要

2 つの整数  L, R があたえられる。 L \le x \lt y \le R を満たす  x y に対する  xy を 2019 で割ったあまりの最小値を求めよ。

制約

  •  0 \le L \lt R \le 2 \times 10^{9}

考えたこと

整数問題っぽいけど、こういうのはまずは「単純な全探索できないか...」と考えるのがよさそう。今回でいえば単純な全探索は二重ループでできそう。

しかし今回は  L, R \le 2 \times 10^{9} とかなので、このままだとダメ。そこで工夫を考えることになる。

工夫

例えば  L = 10,  R = 3000 とかだったら、 x = 2019 とかにすれば、 xy は 2019 で割り切れるのであまりを 0 にできる!!!!!

あまりは 0 よりは小さくならない。で、よく考えると「2019 個以上の整数が連続すると、その中に必ず 2019 の倍数がある」というのが言える。よって

  •  R - L \ge 2019 のときは答えが 0
  • それ以外のときは、全探索できる!!!候補数は多く見積もっても  (R - L)^{2} くらいなので。

となる。下の実装上は安全のため、「R - L > 3000 なら 0」としている。

#include <iostream>
using namespace std;

int main() {
    long long L, R; cin >> L >> R;
    if (R - L > 3000) cout << 0 << endl;
    else {
        long long res = 2018;
        for (long long i = L; i < R; ++i)
            for (long long j = i+1; j <= R; ++j)
                res = min(res, (i * j) % 2019);
        cout << res << endl;
    }
}

AtCoder ABC 051 B - Sum of Three Integers (200 点)

AtCoder 過去問精選10問記事だと「計算量意識するのは 300 点から」って書いてしまっているのだけど、この問題の存在がちょっと心苦しいかも ^^;

問題へのリンク

問題概要

2 つの整数  K, S が与えられます。
3 つの  0 以上  K 以下の整数  (x, y, z) の組であって、 x + y + z = S を満たすものが何通りあるか求めよ。

制約

  •  1 \le K \le 2500
  •  1 \le S \le 3K

全探索

一目見てすごく数学色強そうで怖そうなのだけど、とりあえず答えを出すコードを求めるだけなら、すべての場合を調べてしまえばよい!!!

具体的には

  •  0 以上  K 以下の整数  x
  •  0 以上  K 以下の整数  y
  •  0 以上  K 以下の整数  z

の組合せを全パターンを試して、そのうち  x + y + z = S を満たすものをカウントします。

    int count = 0;
    for (int x = 0; x <= K; ++x) {
        for (int y = 0; y <= K; ++y) {
            for (int z = 0; z <= K; ++z) {
                if (x + y + z == S) {
                    ++count;
                }
            }
        }
    }

しかし...

B 問題, 200 点問題だったら、これで通って欲しい。。。でもこれだと TLE (実行時間超過, Time Limit Exceeded) してしまう。

理由は以下の記事の 8 問目 - Otoshidama の解説に書いたのと同じなのだけど、for 文を三重にしているので、計算量は  O(K^{3}) になっている。ここで最大ケースの  K = 2500 を代入してみると  2500^{3} が大体  10^{10} くらいになる。しかし実行時間制限は  10^{9} くらいが限界なのだ。

qiita.com

改良

実は for 文を三重から二重に減らすことができます。例えば

  •  S = 10
  •  x = 2,  y = 3 の場合を考えると
  •  z 10 - 2 - 3 = 5 になるしかない

ということが見て取れます。つまり  x, y の値が決まった時点で、 z のとるべき値は決まってしまうのです。そしてそれが実際に  0 以上  K 以下になっているかどうかを確かめてあげて、それを満たしていたらカウントするようにすればよいです。

これによって、z のループが消えて、for 文が二重になりました。計算量は  O(K^{2}) に下がります!!!!!
今度こそ通ります!!!

#include <iostream>
using namespace std;

int main() {
    int K, S; cin >> K >> S;
    int count = 0;
    for (int x = 0; x <= K; ++x) {
        for (int y = 0; y <= K; ++y) {
            int z = S - x - y;
            if (z >= 0 && z <= K) {
                ++count;
            }
        }
    }
    cout << count << endl;
}

AtCoder AGC 015 A - A+...+B Problem (200 点)

確かに 200 点かもしれないけど、AGC-A は時々こういう注意力系が出るね。

問題へのリンク

問題概要

 N 個の整数であって、最小が  A、最大が  B であるようなものについて、その総和として考えられる値が何通りあるかを求めよ。

制約

  •  1 \le N, A, B \le 10^{9}

考えたこと

この手の問題で重要なこととして、とりうる値は  x 以上  y 以下の整数という具合に、区間になっていることがあげられる。つまり、 6 が作れて  8 も作れるなら  7 も作れるのだ。

こういう風に、取りうる値が区間になることを見越した考察は、より高難易度な問題であっても、すごくたくさん出てくる。で今回は  A \le B とは言っていないことに注意。

  •  A \gt B のとき解なしなので 0
  •  A \le B のとき、最小が  (N-1)A + B で最大が  A + (N-1)B なので答えは、 (A + (N-1)B) - ((N-1)A - B) + 1 = (N-2)(B - A) + 1 になる...のだが、 N = 1 の場合に注意!!!!!!!
  •  N = 1 のときは例外処理を行う。 A = B なら 1 で、それ以外だと 0
#include <iostream>
using namespace std;

int main() {
    long long N, A, B; cin >> N >> A >> B;
    if (A > B) cout << 0 << endl;
    else if (N == 1) cout << (A == B ? 1 : 0) << endl;
    else cout << (N-2) * (B-A) + 1 << endl;
}