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

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

AtCoder ABC 206 E - Divide Both (青色, 500 点)

約数系包除原理の教育的問題

問題概要

整数  L, R が与えられるので、以下の条件を満たす整数  (x, y) の組の個数を求めてください。

  •  L \le x, y \le R
  •  g = {\rm GCD}(x, y) としたとき、 g \neq 1,  \frac{x}{g} \neq 1,  \frac{y}{g} \neq 1

制約

  •  1 \le L \le R \le 10^{6}

解法 (1):約数系包除

まさに約数系包除原理の教育的良問。この問題をきっかけとして、次の記事を書いてみました。この問題の解説も次の記事の最後で行ってみました。

qiita.com

流れのみを確認すると、この問題は結局は、各  k に対して


 {\rm GCD}(x, y) = k,  L \le x, y \le R となる  (x, y) の個数を求めよ


という問題に帰着される。なお、そうなる過程では、 \frac{x}{g} = 1 となるもの (簡単に数えられる) を最後に引くという方針をとることで、 \frac{x}{g} \neq 1 という条件を無効化する、みたいなことをやっている。

さて、このように「最大公約数がちょうど  k になるような場合を考える」という問題では、約数系包除が活躍することが多い。なぜなら、ちょうど  k になる場合を求めるのは難しくても

 {\rm GCD}(x, y) k の倍数になる場合の数 ( L \le x \lt y \le R) を求めることは簡単

だからだ。

 {\rm GCD}(x, y) k の倍数
 x, y k の倍数

が成立するので、条件がとても簡単になる。こういうときは、約数系包除原理が活躍する。計算量は  O(R \log \log R) になる。

解法 (2):調和級数的計算量

約数系包除原理の問題は、調和級数的計算量でも解けることが多い気がする。詳しくは、kyopro_friends さんの公式解説より。

atcoder.jp

ただし、約数系包除で解ける問題を、調和級数的計算量の理屈で解くと、計算量は  O(R \log R) になる。少し遅くなる。

メビウス関数を用いて約数系包除原理をするのは、調和級数的計算量の理屈で解くのを高速化したとみなすこともできる。

解法 (3):添字 GCD 畳み込み

添字 GCD 畳み込みで殴ることもできる。約数系包除原理の考察が面倒になったら、分かりやすく添字 GCD 畳み込みで殴ってしまうのはとてもいいかもしれない。詳しくは kuprin さんのユーザー解説より。

kanpurin.hatenablog.com

解法 (4): O(R^{0.75}) 解法

maspy さんの記事より。

maspypy.com

AtCoder ABC 206 F - Interval Game 2 (黄色, 600 点)

Grundy 数は Grundy 数でも、「山を分割していく」というタイプの Grundy 数ですね。

問題概要

 N 個の区間が与えられる。 i 個目の区間は  \lbrack L_{i}, R_{i}) となっている。

Alice と Bob は次のようなゲームを行う。

まだ残っている区間のうち、「今までに選ばれたどの区間とも共有点をもたない」ものを交互に選んでいく。先に区間を選べなくなった方が負けである。

双方最善を尽くしたとき、どちらが勝つか?

(マルチテストケース: T 回)

制約

  •  1 \le T \le 20
  •  1 \le N \le L_{i}, R_{i} \le 100

考えたこと

 L_{i}, R_{i} \le 100 という小さく見える制約に意味があるのかな...というのを最初思った。その後、 N \le 100 という制約もあるから座圧すれば実質意味ない制約なのかな... となった。でもコンテスト的には座圧しなくてもいいのは楽だね。

それはそうと、いわゆる区間スケジューリング問題のような設定でゲームをする!!!今までありそうでなかった面白い問題だね!!!

こういう「山とか盤面とかが分割されて行くようなゲーム」は、Grundy 数と相場は決まっている!!!

盤面が分割していくゲーム

初期状態だとゲームの盤面は、[0, 100) という状態になっている (区間の座標を 0-indexed にする)。

ここからたとえば  N 個の区間の中に [10, 20) があったと仮定して、これを選ぶと、盤面は

  • [0, 10)
  • [20, 100)

という具合に分割される。ここで、盤面を  \lbrack l, r) の範囲に制限したときの Grundy 数を G[l][r] と書くことにしよう。このとき、このように「盤面全体が 2 つに分割された状態の局面」の Grundy 数は

G[0][10] ^ G[20][100]

になることが知られている。よって、 N 個の区間  \lbrack l_{i}, r_{i}) それぞれに対して、

  • G[0][l[0]] ^ G[r[0]][100]
  • G[0][l[1]] ^ G[r[1]][100]
  • ...
  • G[0][l[N-1]] ^ G[r[N-1]][100]

の mex を求めれば OK。

メモ化再帰へ

以上のことを再帰的に行えば OK。区間  \lbrack a, b) に関する Grundy 数をメモ化しながら、G[0][100] を求めよう。

計算量は  A = 100 として、 O(A^{2}N) となる。

#include <bits/stdc++.h>
using namespace std;

int MAX = 110;
int N;
vector<int> L, R;
vector<vector<int>> dp;

int solve(int left = 0, int right = MAX) {
    if (right == left) return 0;
    if (dp[left][right] != -1) return dp[left][right];

    set<int> se;
    for (int i = 0; i < N; ++i) {
        if (left <= L[i] && R[i] <= right) {
            int tmp = solve(left, L[i]) ^ solve(R[i], right);
            se.insert(tmp);
        }
    }

    int grundy = 0;
    while (se.count(grundy)) ++grundy;
    return dp[left][right] = grundy;
}

int main() {
    int NUM_CASE;
    cin >> NUM_CASE;

    while (NUM_CASE--) {
        cin >> N;
        L.resize(N), R.resize(N);
        for (int i = 0; i < N; ++i) {
            cin >> L[i] >> R[i];
            --L[i], --R[i];
        }
        dp.assign(MAX, vector<int>(MAX+1, -1));
        cout << (solve() > 0 ? "Alice" : "Bob") << endl;
    }
}

AtCoder ABC 014 C - AtColor (試験管水色)

人生で最初に解きたい、いもす法の練習問題!

問題概要

サイズ 1000001 の配列 v が与えられる (index は、0, 1, ..., 1000000)。

以下の  N 回の操作を行う。

  •  i 回目の操作では、 a_{i} \le x \le b_{i} を満たす  x について、v[x] に 1 を加算する

すべての操作を行ったあとの、配列中の値の最大値を求めよ。

制約

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

考えたこと

完全にいもす法そのものな問題。いもす法のやり方は、次の資料などを。

drken1215.hatenablog.com

この ABC 183 C 問題は、今回の問題の上位互換的な問題になっている。いもす法を使うと、配列 v が求められるので、その最大値を求めれば OK。

コード

計算量は  A = 1000001 として、 O(N + A) になる。

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

int main() {
    int N;
    cin >> N;

    int A = 1000001;
    vector<int> v(A + 1, 0);
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        v[a]++;
        v[b+1]--;
    }
    for (int i = 0; i <= A; ++i) v[i+1] += v[i];

    int res = 0;
    for (int i = 0; i <= A; ++i) res = max(res, v[i]);
    cout << res << endl;
}

AtCoder ABC 014 D - 閉路 (試験管青色)

木上のパスに関する問題!!
LCA で解決できる典型問題

問題概要

頂点数  N の木が与えられる。次の  Q 個のクエリに答えよ。

  • 各クエリでは木上の 2 頂点  a, b が与えられる
  • 木に辺  (a, b) を仮に追加したとすると、閉路が 1 個形成される
  • その閉路に含まれる辺の本数を答えよ

制約

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

考えたこと

グラフ理論的には、木とは「閉路をもたないグラフ」ということになる。下図のように、それに辺を新たに付け加えると閉路ができるのだ。

一般に、辺  (a, b) を付け加えることでできる閉路の長さは、パス  a- b の長さに 1 を足したものになる。

よって各クエリは「パス  a- b の長さを答えてください (それに 1 を足して出力してください)」と言い換えられるのだ。

木のパスの長さ

木のパスの長さに答える問題は超有名問題で、蟻本上級編「グラフマスターへの道」にも解説がある。いろんなやり方があるが、LCA を求める方法が有名だ (さらに LCA を求める方法もたくさんある)。

まず、木の根を 1 つ決めて根付き木にしてしまう。そして、二頂点  a, b に対して、LCA (最近共通祖先) を求めよう (下図の頂点  v)。

LCA の求め方は蟻本参照。

LCA が求められたら、次の値を合計することでパスの長さが求められる。

  • これはパス  a- v の長さ
  • これはパス  b- v の長さ

前者は (頂点  a の深さ) - (頂点  v の深さ) で求められて、後者は (頂点  b の深さ) - (頂点  v の深さ) で求められる。つまり、


depth[a] + depth[b] - 2 * depth[v]


で求められる (depth は各頂点の深さ)。

コード

ここでは、LCA を求める処理をライブラリ化したものを用いた。

https://github.com/drken1215/algorithm/blob/master/DataStructureOnTree/LCA_doubling.cppgithub.com

計算量は  O(N + Q \log N) となる。

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

// グラフを表す構造体
using Graph = vector<vector<int>>;

// LCA を求めるライブラリ
struct LCA {
    vector<vector<int> > parent; // parent[d][v] := 2^d-th parent of v
    vector<int> depth;
    LCA() { }
    LCA(const Graph &G, int r = 0) { init(G, r); }
    void init(const Graph &G, int r = 0) {
        int V = (int)G.size();
        int h = 1;
        while ((1<<h) < V) ++h;
        parent.assign(h, vector<int>(V, -1));
        depth.assign(V, -1);
        dfs(G, r, -1, 0);
        for (int i = 0; i+1 < (int)parent.size(); ++i)
            for (int v = 0; v < V; ++v)
                if (parent[i][v] != -1)
                    parent[i+1][v] = parent[i][parent[i][v]];
    }
    void dfs(const Graph &G, int v, int p, int d) {
        parent[0][v] = p;
        depth[v] = d;
        for (auto e : G[v]) if (e != p) dfs(G, e, v, d+1);
    }
    int get(int u, int v) {
        if (depth[u] > depth[v]) swap(u, v);
        for (int i = 0; i < (int)parent.size(); ++i)
            if ( (depth[v] - depth[u]) & (1<<i) )
                v = parent[i][v];
        if (u == v) return u;
        for (int i = (int)parent.size()-1; i >= 0; --i) {
            if (parent[i][u] != parent[i][v]) {
                u = parent[i][u];
                v = parent[i][v];
            }
        }
        return parent[0][u];
    }
};

int main() {
    int N;
    cin >> N;
    Graph G(N);
    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);
    }

    // LCA ライブラリ
    LCA lca(G);

    // クエリ処理
    int Q;
    cin >> Q;
    for (int q = 0; q < Q; ++q) {
        int a, b;
        cin >> a >> b;
        --a, --b;

        // lca
        int v = lca.get(a, b);

        // パスの長さ
        int len = lca.depth[a] + lca.depth[b] - 2 * lca.depth[v];
        cout << len + 1 << endl;
    }
}

AtCoder ABC 019 D - 高橋くんと木の直径 (試験管水色)

木の直径の求め方を知っていれば解ける!!

問題概要

頂点数  N の木があるが、その形状についての情報はあらかじめわからない。あなたの目的は、この木の直径の長さを求めることである。

そのために、以下のクエリを 100 回まで投げることができる。

「2 頂点  u, v を指定して、パス  u- v の長さを聞く」

100 回以内のクエリによって、直径の長さを当ててほしい。

制約

  •  2 \le N \le 50

考えたこと

木が与えられたときに、木の直径は次の手順で求められることが知られている。

  • 適当な頂点  u を 1 つ選ぶ
  • 頂点  u から最も遠い頂点  v を求める
  • 頂点  v から最も遠い頂点  w を求める

このとき、パス  v- w が直径になるのだ。このことを知っていると、今回の問題はもう解けたも同然だ。


  1. なにか適当な頂点  u を選び、 u 以外の各頂点との距離を問いて、それが最大となる頂点  v を見つける ( N-1 回)
  2. 頂点  v から、それ以外の各頂点との距離を問いて、その最大値を求める ( N-1 回)

合計で  2N-2 回なので、制限回数以内に求められる。

コード

直径ライブラリは特に必要なかった。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, dist;
    cin >> N;

    int u = 0, vmx = -1, mx = 0;
    for (int v = 1; v < N; ++v) {
        cout << "? " << u+1 << " " << v+1 << endl;
        cin >> dist;
        if (mx < dist) {
            mx = dist;
            vmx = v;
        }
    }
    for (int w = 0; w < N; ++w) {
        if (w == vmx) continue;
        cout << "? " << vmx+1 << " " << w+1 << endl;
        cin >> dist;
        mx = max(mx, dist);
    }
    cout << "! " << mx << endl;
}