miscalc のブログ

主に競プロの話をします

Range Chmin Point Get

書いた動機

range chmin でググるとなぜか beats の話しかヒットしないので

区間 chmin 一点取得 だけならもっと簡単にできます。(当たり前ですが chmin を chmax に替えても可)

ACL の遅延セグ木を使う

ABC179 解法 • knshnbのブログ の F のようにすればできます。

区間積などを呼び出すと壊れますが、呼び出さないことで解決

双対セグ木

双対セグメント木 - HackMD あたりを読みましょう(面白いです)

問題例

JMO 2017 予選 9 を母関数で解いてみた

競プロにもありそうな教育的な問題だと思いました。

問題

問題リンク

 1, 2, \ldots, 2017 の並べ替え  \sigma = (\sigma(1), \sigma(2), \ldots, \sigma(2017)) について、 \sigma(i) = i となる  1 \leq i \leq 2017 の個数を  F(\sigma) とする。すべての並べ替え  \sigma について  F(\sigma) ^ 4 を足し合わせた値を求めよ。

解答

 a _ {n, m} を、 F(\sigma) = m であるような  1, \ldots, n の順列  \sigma の個数とします。

 m = 0 のときは撹乱順列の個数で、包除原理から  \displaystyle a _ {n, 0} = \sum _ {k=0} ^ {n} (-1) ^ k \binom{n}{k} (n-k)! = n! \sum _ {k=0} ^ {n} \frac{(-1) ^ k}{k!} とわかります(母関数による導出もあります:指数型母関数入門 – 37zigenのHP)。

一般の  m に対しては、一致する箇所  m 個を選んだ後、残り  n-m 個の場所で撹乱順列を作ると考えて、 \displaystyle a _ {n,m} = \binom{n}{m} a _ {n-m, 0} = \frac{n!}{m!} \sum _ {k=0} ^ {n-m} \frac{(-1) ^ k}{k!} となります。

答えは  \displaystyle \sum _ {m=0} ^ n m ^ 4 a _ {n, m} = n! \sum _ {m=0} ^ n \frac{m ^ 4}{m!} \sum _ {k=0} ^ {n-m} \frac{(-1) ^ k}{k!} (で  n = 2017 としたもの)です。

母関数を使って考察します。まずは撹乱順列の個数  \displaystyle \sum _ {k=0} ^ {n-m} \frac{(-1) ^ k}{k!} の母関数を考えましょう。 \displaystyle \frac{(-1) ^ k}{k!} = \lbrack x ^ k \rbrack e ^ {-x} であり、撹乱順列の個数はその累積和なので  \displaystyle \frac{1}{1 - x} をかけたものが母関数になります。つまり  \displaystyle \sum _ {k=0} ^ {n-m} \frac{(-1) ^ k}{k!} = \lbrack x ^ {n-m} \rbrack \frac{e ^ {-x}}{1 - x} です。

次に  \displaystyle \frac{m ^ 4}{m!} の母関数を考えましょう。このままでは考えにくいので、 m ^ 4 = m + 7m(m-1) + 6m(m-1)(m-2) + m(m-1)(m-2)(m-3) と変形します(このように冪乗を下降冪の級数で表したときの係数は 第 2 種スターリング数 です)。すると

 \begin{align*}
 \frac{m ^ 4}{m!} &= \frac{1}{(m - 1)!} + \frac{7}{(m - 2)!} + \frac{6}{(m - 3)!} + \frac{1}{(m - 4)!} \\
&= \lbrack x ^ {m-1} \rbrack e ^ x + 7 \lbrack x ^ {m-2} \rbrack e ^ x + 6 \lbrack x ^ {m-3} \rbrack e ^ x + \lbrack x ^ {m-4} \rbrack e ^ x \\
&= \lbrack x ^ m \rbrack ( x e ^ x + 7 x ^ 2 e ^ x + 6 x ^ 3 e ^ x + x ^ 4 e ^ x) 
\end{align*}

となります(負の階乗の逆数や負冪の係数は  0 とみなしておきます)。よって答えは

 \begin{align*}
&\phantom{{}={}} n! \sum _ {m=0} ^ n \frac{m ^ 4}{m!} \sum _ {k=0} ^ {n-m} \frac{(-1) ^ k}{k!} \\
&= n! \sum _ {m=0} ^ n \lbrack x ^ m \rbrack (x + 7 x ^ 2 + 6 x ^ 3 + x ^ 4) e ^ x \cdot \lbrack x ^ {n-m} \rbrack \frac{e ^ {-x}}{1 - x} \\
&= n! \lbrack x ^ n \rbrack \frac{x + 7 x ^ 2 + 6 x ^ 3 + x ^ 4}{1 - x} \\
&= n! \lbrack x ^ n \rbrack (x + 8 x ^ 2 + 14 x ^ 3 + 15 x ^ 4 + 15 x ^ 5 + 15 x ^ 6 + \cdots) \\
&= 15 \cdot 2017!
\end{align*}

となります。(補足:2 行目から 3 行目は FPS の積の定義、3 行目から 4 行目は  \displaystyle \frac{1}{1 - x} 倍が累積和)

競プロ

 2017 n に、 4 d に一般化したときの答えを  \mathrm{ans}(n, d) とすると、 \displaystyle \mathrm{ans}(n, d) = n! \sum _ {k = 0} ^ {\min(n, d)} S(d, k) です( S(\cdot, \cdot) は第 2 種スターリング数)。これを(mod 998 とかで)計算する競プロの問題だと思うことにします。[多項式・形式的べき級数] 高速に計算できるものたち | maspyのHP を参考にすると、次のことがわかります。

  •  D 固定、クエリ  n に対して  \mathrm{ans}(n, D) を求める:「第 2 種 Stirling 数」の項の「前者」の方法で  S(D, 0), \ldots, S(D, D) O(D \log D) で前計算して累積和をとることで、各クエリについて(階乗の計算を除いて) O(1) で求まる。

  •  N 固定、 d = 0, 1, \ldots, D \ (D \leq N) に対して  \mathrm{ans}(N, d) を求める: S(d, k) がすべての  k = 0, 1, \ldots, d について足されることから Bell 数になって、 O(D \log D) で求まる(「Bell 数」の項も参照)。

  •  N 固定、 d = 0, 1, \ldots, D に対して  \mathrm{ans}(N, d) を求める:「第 2 種 Stirling 数」の項の「後者」を参考にすると  \displaystyle \sum _ {k=0} ^ {\min(N, D)} \frac{1}{k!} (e ^ x - 1) ^ k D 次まで求めればよい。これは  \displaystyle \sum _ {k=0} ^ {\min(N, D)} \frac{1}{k!} x ^ k を Polynomial Taylor Shift した後  e ^ x を代入すればよいので(「Polynomial Taylor Shift」および「特殊な合成」の項を参照)、(階乗の計算を除いて)全体  O(D \log ^ 2 D) で求まる。

Stern–Brocot Tree についてのメモ

この記事の目標

SBT についてざっくり理解して、次の機能を実装できるようになります。

おことわり

  • 新規性は特になく、既存の記事を自分用にまとめた程度の内容になっています。

  • 気持ち寄りの説明が多めで、議論がやや雑な部分があるかもしれません。

Stern–Brocot Tree について

定義

Stern–Brocot Tree (SBT) は、次のように定められる、(無限に続く)完全二分木です。

  • 各頂点は非負整数の  4 つ組  (p, q, r, s) を持ち、正の有理数  \dfrac{p+r}{q+s} が対応する。*1

  • 根は  (0, 1, 1, 0) である(対応する有理数 \dfrac{1}{1})。

  •  (p, q, r, s) の左の子は  (p, q, p+r, q+s)、右の子は  (p+r, q+s, r, s) である。

性質

Stern–Brocot Tree には次の重要な性質があります。

  1. 二分探索木である。つまり、 (左の子孫の値) \lt (親の値) \lt (右の子孫の値) である。(cf. 加比の理)

  2. 根から右の子に  a_0 回、左の子に  a_1 回、 \ldots、( k-1 が奇数 ? 右の子 : 左の子) に  a_{k-1} 回進んだ頂点が対応する有理数は、連分数  a _ 0 + \dfrac{1}{a _ 1 + \dfrac{1}{\ddots + \dfrac{1}{a _ {k-1} + 1}}} として表される。

  3. 正の有理数がすべて現れる。(2. からわかる。すべての正の有理数は連分数展開を持つので)

  4. 逆に、各頂点に対応する正の有理数は相異なる。(1. からわかる。あるいは、正の有理数の連分数展開は  a_i \geq 1 \: (i \geq 1) に限定すれば一意なので、と思ってもよい)

  5. 根から始めて、有理数  \dfrac{p}{q} に対応する頂点に到達するまでのパスを考える。「右の子/左の子 に  d 回進む」ことをひとまとまりの操作とみなしたときの操作回数(パスの連長圧縮の長さ、2. での  k の値 *2)は  O(\log(p+q)) である。(2. からわかる。連分数展開は実質的に互除法なので)

  6. 頂点  (p, q, r, s) の子孫の集合は、開区間  \left(\dfrac{p}{q}, \dfrac{r}{s} \right) になる( \dfrac{1}{0} \infty とみなす)。(気持ちとしては、左の子に  d 回進むと  \dfrac{p + (dp + r)}{q + (dq + s)}、右の子に  d 回進むと  \dfrac{(p + dr) + r}{(q + ds) + s} で、 d \to \infty とするとそれぞれ  \dfrac{p}{q} \dfrac{r}{s}

Library Checker - Stern–Brocot Tree

ENCODE_PATH

有理数から SBT 上のパス(の連長圧縮)を得る問題です。性質 2. を利用して連分数展開すればよいです。(性質 5. より、出力は多くなりません)

DECODE_PATH

SBT 上のパス(の連長圧縮)から有理数を得る問題ですが、素直に根から辿ると有理数だけでなく頂点の  4 整数  (p, q, r, s) を得ることができます(そう実装すると後々楽です)。(これも性質 5. より、入力は多くなりません)

LCA

 2 つの有理数LCA(に対応する有理数)を求める問題です。 2 つの有理数を ENCODE_PATH したのち、根から辿っていってどこまで一致するか見ればよいです。性質 5. より間に合います。

ANCESTOR

有理数  \dfrac{p}{q} の祖先であって深さ  d の頂点(に対応する有理数)を求める問題です。これも  \dfrac{p}{q} を ENCODE_PATH したのち、根から深さ  d まで辿っていけば性質 5. より間に合います。

RANGE

有理数が与えられて、その子孫の下限と上限を求める問題です。性質 6. そのものです。ENCODE_PATH してから DECODE_PATH すると  (p, q, r, s) が得られるので、それが答えです。

ABC333 G - Nearest Fraction

SBT 上を探索する話です。

より一般に、次の形で考えましょう。(この定式化は [2], [3] をかなり参考にしています)

関数  f \colon \mathbb{R} _ {\gt 0} \to \{ \mathrm{true}, \mathrm{false} \} は単調性がある。すなわち、ある  \alpha \in \mathbb{R} _ {\gt 0} が存在して、 x \leq \alpha \implies f(x) = \mathrm{true}, x \gt \alpha \implies f(x) = \mathrm{false} といった形になっている(等号・不等号や true/false は入れ替わってもよい)。このとき、境界  \alpha を分母・分子が  n 以下の有理数で近似したい。 \dfrac{p}{q} \leq \alpha \lt \dfrac{r}{s} *3 を満たす  0 \leq p,q,r,s \leq n のうち、 \alpha - \dfrac{p}{q} および  \dfrac{r}{s} - \alpha が最小になるものを求めよ。

性質 1. を利用して、二分探索木を探索することを考えます。性質 6. より、探索の途中で頂点  (p, q, r, s) にいるとき、 (p, q, r, s) \dfrac{p}{q} \leq \alpha \lt \dfrac{r}{s} を満たしています。よって、素直に二分探索木を探索して、 n を超えたら打ち切る、とすると  O(n) で解けます。性質 5. を利用して、「その方向にどれだけ進むか」を二分探索 *4 すれば速くなります(log ふたつに見えて実は  O(\log n) です。証明は [2])。


実装で自分が苦労した細かい部分を解説します。まず、頂点  (p, q, r, s) に到達したとき、そこからはもう進まずに  (p, q, r, s) を答えとする条件は  p + r > n または  q + s > n です。 (p + r, q + s) は、左および右に  1 個進んだときの  (r, s) および  (p, q) だからです。

同様に、進む深さ  d を二分探索するときの  d の上限  \mathrm{ng} は、(左に進むのであれば) dp + r > n または  dq + r > n を満たす最小の  d、というようにして決めることができます *5

こういったことは分母・分子が  n 以下という制限が強い場面でなければ(例:[2] のように、真の値が有理数で、かつ分母・分子がある値以下であることが示せる場合)気にしなくてもあまり問題はありませんが、今回の問題のような場面では出力が  n を超えてしまうバグの原因になるので、注意して実装する必要があります。

実装例

クリックして展開

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

// stern-brocot tree
namespace sbt
{
  // (p, q, r, s) から (isleft ? 左 : 右) に d 個進んだ頂点を返す
  template<class T>
  tuple<T, T, T, T> child(T d, T p, T q, T r, T s, bool isleft)
  {
    if (isleft)
      r += d * p, s += d * q;
    else
      p += d * r, q += d * s;
    return make_tuple(p, q, r, s);
  }

  // (p, q, r, s) の親を返す
  // (p, q, r, s) が根なら (0, 0, 0, 0) を返す
  template<class T>
  tuple<T, T, T, T> parent(T p, T q, T r, T s)
  {
    if (p == 0 && q == 1 && r == 1 && s == 0)
      return make_tuple(0, 0, 0, 0);
    if (p < r || q < s)
      r -= p, s -= q;
    else
      p -= r, q -= s;
    return make_tuple(p, q, r, s);
  }

  // 1/1 から p/q へのパスが右に a_1 回、左に a_2 回、… としたときの a を返す
  // (a_1, …, a_k + 1) は p/q の連分数展開になっている
  template<class T>
  vector<T> encode_path(T p, T q)
  {
    vector<T> a;
    if (p < q)
    {
      a.emplace_back(0);
      swap(p, q);
    }
    while (p != 1)
    {
      a.emplace_back(p / q);
      p %= q;
      swap(p, q);
    }
    if (!a.empty())
    {
      if (a.back() == 1)
        a.pop_back();
      else
        a.back()--;
    }
    return a;
  }

  // 1/1 から右に a_1 回、左に a_2 回、… 移動した頂点 (p, q, r, s) を返す
  // (a_1, …, a_k + 1) は (p+r)/(q+s) の連分数展開になっている
  template<class T>
  tuple<T, T, T, T> decode_path(const vector<T> &a)
  {
    T p = 0, q = 1, r = 1, s = 0;
    for (int i = 0; i < (int)a.size(); i++)
      tie(p, q, r, s) = child(a[i], p, q, r, s, i & 1);
    return make_tuple(p, q, r, s);
  }

  // p/q と r/s の LCA (f, g, h, k) を返す
  template<class T>
  tuple<T, T, T, T> lca(T p, T q, T r, T s)
  {
    vector<T> a = encode_path(p, q), b = encode_path(r, s);
    int n = min(a.size(), b.size());
    T f = 0, g = 1, h = 1, k = 0;
    for (int i = 0; i < n; i++)
    {
      T c = min(a[i], b[i]);
      tie(f, g, h, k) = child(c, f, g, h, k, i & 1);
      if (a[i] != b[i])
        break;
    }
    return make_tuple(f, g, h, k);
  }

  // p/q の祖先であって深さが d のノード (f, g, h, k) を返す
  // 存在しなければ (0, 0, 0, 0)
  template<class T>
  tuple<T, T, T, T> ancestor(T d, T p, T q)
  {
    vector<T> a = encode_path(p, q);
    T f = 0, g = 1, h = 1, k = 0;
    for (int i = 0; i < (int)a.size(); i++)
    {
      T c = min(d, a[i]);
      tie(f, g, h, k) = child(c, f, g, h, k, i & 1);
      d -= c;
      if (d == 0)
        break;
    }
    return d == 0 ? make_tuple(f, g, h, k) : make_tuple(0, 0, 0, 0);
  }

  // p/q の子孫の下限 f/g と上限 h/k を返す
  // p/q に対応する頂点 (f, g, h, k) でもある
  template<class T>
  tuple<T, T, T, T> range(T p, T q) { return decode_path(encode_path(p, q)); }

  // judge: [0, ∞] → {true, false}
  // judge は単調性を持つ、すなわち、ある実数 α を境に true と false が切り替わる
  // 分母・分子が max_value 以下の有理数のうち、α に最も近いもの (下側: p/q, 上側: r/s) を返す
  template<class T>
  tuple<T, T, T, T> search(const function<bool(T, T)> &judge, const T &max_value)
  {
    T p = 0, q = 1, r = 1, s = 0;
    const bool judge_01 = judge(0, 1), judge_10 = judge(1, 0);
    assert(judge_01 != judge_10);
    while (p + r <= max_value && q + s <= max_value)
    {
      const bool judge_now = judge(p + r, q + s);
      const bool isleft = judge_now ^ judge_01;
      T maxd;
      if (isleft)
        maxd = p == 0 ? (max_value - s) / q : min((max_value - r) / p, (max_value - s) / q);
      else
        maxd = s == 0 ? (max_value - p) / r : min((max_value - q) / s, (max_value - p) / r);
      T dl = 1, dr = 2;
      while (dr <= maxd)
      {
        auto [np, nq, nr, ns] = child(dr, p, q, r, s, isleft);
        if (judge(np + nr, nq + ns) != judge_now)
          break;
        dl = dr, dr = min(2 * dr, maxd + 1);
      }
      while (dr - dl > 1)
      {
        T dm = dl + (dr - dl) / 2;
        auto [np, nq, nr, ns] = child(dm, p, q, r, s, isleft);
        if (judge(np + nr, nq + ns) == judge_now)
          dl = dm;
        else
          dr = dm;
      }
      tie(p, q, r, s) = child(dl, p, q, r, s, isleft);
    }
    return make_tuple(p, q, r, s);
  }
}

// 使用例 (https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1208)
int main()
{
  while (true)
  {
    int p, n;
    cin >> p >> n;
    if (p == 0 && n == 0)
      break;
    const function<bool(int, int)> judge = [&](int x, int y) -> bool
    { return y * y * p < x * x; };
    auto [u, v, x, y] = sbt::search(judge, n);
    cout << x << "/" << y << " " << u << "/" << v << endl;
  }
}

参考文献

[1] Stern–Brocot tree - Wikipedia

[2] Editorial - AtCoder Beginner Contest 294

[3] 有理数上の二分探索(ざっくり導入編) - えびちゃんの日記

*1:有理数だけを対応させる定義もあります。私にとっては  4 つ組が対応すると思ったほうがわかりやすかったのでこの記事ではそちらを採用します

*2:ちょっと嘘で、 a_0 = 0 のとき  1 ずれます

*3:等号・不等号は  f が満たす条件の等号・不等号で変わる

*4:指数探索すればこれより速いです。定数倍の違いだと思っています

*5:このあたりは「分母が  n 以下、分子は気にしない」といった場面でも同じ考え方でできますね

「周期性」の問題の抽象化(ライブラリ)

概要

競プロでは「周期性」を利用して解く問題がたまに出ます。例:

  • D - Teleporter

    長さ  N の数列  A = (A_1, A_2, \ldots, A_N) が与えられる( 1 \leq A_i \leq N)。 x = 1 から始めて、 x \leftarrow A_x という置き換えを  K 回行ったときの  x の値を求めよ。 N \leq 2 \times 10 ^ 5, K \leq 10 ^ {18}

  • E - Sequence Sum

    漸化式  A_1 = X, A _ {n+1} = (A _ n ^ 2 \bmod M) で定まる数列  A に対し、 \sum_{i=1}^N A_i を求めよ。 N \leq 10 ^ {10}, 0 \leq X \lt M \leq 10 ^ 5

難しくはないのですが、毎回書くと意外と頭を壊しがちなので、抽象化してライブラリにしてみました。この記事ではそのライブラリについて書きます。なお、問題の解法自体は既知として進めます。

抽象化

これらの問題は次のように抽象化できます。

モノイド  (\mathrm{Data}, \bullet) およびインデックスの集合  \mathrm{Index} があり、各インデックス  x \in \mathrm{Index} にはデータ  \mathrm{get \_ data}(x) \in \mathrm{Data} が対応づけられている。また、インデックス列  (x _ i) _ i が漸化式

 \displaystyle x _ 0  = \mathrm{start}, x _ {i+1} = \mathrm{next \_ index}(x _ i)

で定まっている。これについて、先頭からの区間

 \mathrm{get \_ data}(x _ 0) \bullet \mathrm{get \_ data}(x _ 1) \bullet \cdots \bullet \mathrm{get \_ data}(x _ {K-1})

を求めるクエリを処理したい( K がクエリで与えられる)。

これは、

  •  x _ \lambda = x _ {\lambda + \mu} となる  (\lambda, \mu) が存在する(特に最小のものをとる)。つまり、インデックスは ρ のような形で周期性を持ち、非循環部分の長さが  \lambda、循環部分の長さが  \mu である

  •  a \in \mathrm{Data}, n \in \mathbb{N} に対して冪  a ^ n = \underbrace{a \bullet \cdots \bullet a} _ {n \ \mathrm{個}} を高速に求められる(簡単のため、この冪演算およびその他必要な演算は  O(1) で行えるものとする)

という条件のもとで、前計算  O(\lambda + \mu)、クエリ  O(1) で処理できる。

「冪が高速に計算できるモノイド」である必要があるのは、( K が大きいとき)

 \begin{align}
&{\phantom{\bullet}} \left( \mathrm{get \_ data}(x _ 0) \bullet \cdots \bullet \mathrm{get \_ data}(x _ {\lambda - 1}) \right)  \tag{非循環部分} \\
&\bullet \left( \mathrm{get \_ data}(x _ \lambda) \bullet \cdots \bullet \mathrm{get \_ data}(x _ {\lambda + \mu - 1}) \right) ^ n \tag{循環部分} \\
&\bullet \left( \mathrm{get \_ data}(x _ {\lambda + n\mu}) \bullet \cdots \bullet \mathrm{get \_ data}(x _ {K - 1}) \right) \tag{あまり}
\end{align}

と変形して計算するためです*1。クエリ  O(1) にできるのは、クエリで計算する区間積が  0 スタートのものと  \lambda スタートのものしかなく前計算できるためです。

設計

コンストラク

Period<Index, Data, next_index, get_data, op, e, power> pe(start); *2

  • インデックスの型 Index演算子 != が定義されている必要があります)
  • データの型 Data
  • 一つ後のインデックスを得る関数 Index next_index(Index x)
  • インデックスからデータを得る関数 Data get_data(Index x)
  •  \mathrm{Data} 上の二項演算 Data op(Data a, Data b)
  •  (\mathrm{Data}, \bullet)単位元 Data e()
  •  a ^ n = \underbrace{a \bullet \cdots \bullet a}_{n \ \mathrm{個}} を計算する関数 Data power(Data a, long long n)

を定義する必要があります。start は最初のインデックス  x _ 0 です。

query

Data query(long long K)

 \mathrm{get \_ data}(x _ 0) \bullet \mathrm{get \_ data}(x _ 1) \bullet \cdots \bullet \mathrm{get \_ data}(x _ {K-1}) を返します。

実装

  • 既に訪れたかどうかを配列で管理するのが最も思いつきやすいと思いますが、Index の型によっては連想配列を用いる必要が出てきてしまいます。フロイドの循環検出法 *3 を用いることでこれを回避しています。

  • 限界高速化とかはしていません。

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

template <typename Index, typename Data, Index (*next_index)(Index), Data (*get_data)(Index), Data (*op)(Data, Data), Data (*e)(), Data (*power)(Data, long long)>
struct Period
{
private:
  vector<Data> dat, prod_head, prod_tail;
  int lambda, mu;
  Data head, tail;

public:
  Period(Index start)
  {
    Index a = start, b = start;
    do
    {
      dat.emplace_back(get_data(a));
      a = next_index(a);
      b = next_index(next_index(b));
    } while (a != b);
    mu = dat.size();
    Index c = start;
    while (a != c)
    {
      dat.emplace_back(get_data(a));
      a = next_index(a);
      c = next_index(c);
    }
    lambda = (int)dat.size() - mu;

    prod_head.resize((int)dat.size() + 1);
    prod_tail.resize((int)dat.size() + 1);
    prod_head[0] = e(), prod_tail[lambda] = e();
    for (int i = 1; i < (int)prod_head.size(); i++)
      prod_head[i] = op(prod_head[i - 1], dat[i - 1]);
    for (int i = lambda + 1; i < (int)prod_tail.size(); i++)
      prod_tail[i] = op(prod_tail[i - 1], dat[i - 1]);

    head = prod_head[lambda];
    tail = prod_tail[lambda + mu];
  }

  Data query(long long k)
  {
    if (k <= (int)dat.size())
      return prod_head[k];

    Data mid = prod_tail[lambda + (k - lambda) % mu];
    return op(op(head, power(tail, (k - lambda) / mu)), mid);
  }
};

使用例

 A_i をインデックス  x_i にして、 \mathrm{get \_ data}(A_i) A_i をそのまま返すようにします。二項演算  \bullet は整数の足し算  + にすればよいです。このとき power は掛け算(個数倍)になります。

using Index = long long;
using Data = long long;
int M;
Index next_index(Index x) { return x * x % M; }
Data get_data(Index x) { return x; }
Data op(Data a, Data b) { return a + b; }
Data e() { return 0; }
Data power(Data a, long long n) { return n * a; }

int main()
{
  long long N;
  int X;
  cin >> N >> X >> M;

  Period<Index, Data, next_index, get_data, op, e, power> pe(X);
  cout << pe.query(N) << endl;
}
  • D - Teleporter

    長さ  N の数列  A = (A_1, A_2, \ldots, A_N) が与えられる( 1 \leq A_i \leq N)。 x = 1 から始めて、 x \leftarrow A_x という置き換えを  K 回行ったときの  x の値を求めよ。 N \leq 2 \times 10 ^ 5, K \leq 10 ^ {18}

各操作の後の  x の値をインデックス(兼データ)にします。二項演算 op がややトリッキーです。直感的には「最も右のもの」としたいですが、このままだと単位元がないので困ってしまいます。単位元 e を「意味のないデータ」にしておいて、op は「意味のあるデータのうち、最も右のもの(なければ『意味のないデータ』)」を返すようにするとよいです。

using Index = int;
using Data = int;
vector<int> A;
Index next_index(Index x) { return A[x]; }
Data get_data(Index x) { return x; }
Data e() { return -1; }
Data op(Data a, Data b) { return b == e() ? a : b; }
Data power(Data a, long long) { return a; }

int main()
{
  int N;
  long long K;
  cin >> N >> K;
  A.resize(N);
  for (int i = 0; i < N; i++)
  {
    cin >> A[i];
    A[i]--;
  }

  Period<Index, Data, next_index, get_data, op, e, power> pe(0);
  cout << pe.query(K + 1) + 1 << endl;
}

その他の問題例

*1:単位元が必要なのは、それぞれの部分の長さが  0 になることがあるためです

*2:英語は cycle の方が正しいような気もしますが、閉路と紛らわしいので period にしました

*3:高速素因数分解のポラード・ロー法に使われていることのほうが有名?

JAG 夏合宿 2023 参加記

JAG 夏合宿 2023 に参加した。

ICPC のチームは Magical Fish で、メンバーは自分と magsta, confeito の 3 人。今回 confeito 君に合宿に誘われたので行くことにした。(本当は 3 人で行きたかったけど magsta 君が来れなかったみたいで残念)

1 日目

コンテスト

ぎりぎりに家を出たら電車が遅延して 10 分遅刻(すみません……)。

チームのもう 1 人として kumakuma さんに加わっていただいた。戦略としては、kumakuma さんは英語がかなり得意らしいので長めの問題文担当 + US 配列使いらしいので基本的に実装はしないで自分か confeito 君がやる、という感じになった。

confeito 君が A を読む。自分は B を読もうとしたが長そうだったので、kumakuma さんと交代して C を読むことにした。C を読むと一瞬で解けた(というか ABC で既出なのを思い出した)ので書いてすぐ通る。A も簡単らしいので書いてもらい、すぐ通る。

B は大変らしいということで、シンプルそうな E を読む。一瞬むずそうに見えたけど最適戦略が貪欲っぽい? ということで 2 人に相談、正しそうということになる。細かい解法がすぐに出てこなかったが kumakuma さんが二分探索でできるというのを出してくれて、たしかにとなる。実装して AC。後で考えたら(ソート後は)差分更新で線形でいけるけど、にぶたんのほうがバグらせにくそう。

その後は F ができそうという話になる。DAG の最大パスは EDPC にあって、一般の有向グラフだと最大パスは解けないけど今回の問題は「ウォークを取ってきてそこに含まれる distinct な頂点の数」という解釈になる(はず)なので強連結成分の中を好きなだけぐるぐる回れるから、SCC して頂点に重みがついた DAG とみなした後同様の DP で解ける。とすると出次数が  1 以下という制約は何に使うんだ? と一瞬疑ったけどそのまま書き始めてしまった(これがよくなかった)。kumakuma さんの蟻本から SCC を写経(蟻本が昔の本すぎて範囲 for すら使ってなくてやや困った)、DP はメモ化再帰が楽そうだからそれをすることにして書き終えた。サンプルも試して提出すると TLE、よく見たらメモ化になっていない。提出、TLE。この辺で  N \leq 10 ^ 6 と TL 1 sec に気づく。やめてくれ〜 入力を scanf にしたけどだめで、そもそも SCC で再帰 2 回するのが重くて出次数  1 以下を活かした定数倍がより高速な解法が必要なのでは? という話になって一旦後回しに。

K が解けるらしい。問題概要と解法(DP)を kumakuma さんから聞く。えそれ DP じゃだめでダイクストラでは? と一瞬なったけど話し合ったところ自分が勘違いしていて、DP であっている。サッと実装して AC。

confeito 君が G 解けたというので実装を任せて、kumakuma さんと 2 人で F を詰める。出次数  1 以下なことからサイクルから辺が出ていくことはない、よって普通に DP した後サイクルだったらサイクル長を足した値を考えればよさそうで、queue を使うサイクル検出を DP しながらやる、という解法が生えた。定数倍がまだ不安だが、これ以上のものは出なかった。G の実装がまだ終わらないらしいので順位表で解かれている J も見る。既視感があって、ABC に  O(N ^ 2 \log N) 想定で既出 + 誰かが  O(N \sqrt{N}) で解ける旨を言っていたような気がするところまで思い出したけど、肝心の  O(N \sqrt{N}) 解法を知らず、ちょっと考えたけどよくわからず、諦めた。

G サンプルが合わないらしい。問題概要と解法を聞くとかなり茨の道なことをやっていて、さらに勘違いがあったらしく MLE しそう。一旦諦めて F をやることに。実装して出したけど TLE、グラフを持つのが vector<vector<int>> ではなく vector<int> でいい、とかもやったけどだめだった。結局 ACEK の 4 完で 17 位、激冷え。

コンテスト後

G は DP の値に First / Second / Draw を持たせることばかり考えていたけど、実は普通に得点の差を評価値にしてよくてこれで状態数が削れる。これは気づくべきだった……。

F は confeito 君によると JOI 典型らしく、じゃあ F と G の担当逆にすべきだったねという話になった。サイクルが高々 1 個なのを利用するの、なるほどね。(しかしそこまでの定数倍高速化を要求するのはちょっと不快だなあという気持ちもあり)

夕食をとったり解説を聞いたりした後は部屋で交流した。入浴を済ませた後談話室で ABC に出た。机が低かったり他の団体の声が響いたりしてあまり集中できなかった。SSRS さんのタイピングが速すぎてびびっていた。

部屋に戻って、作問の話とかをしつつ就寝。

2 日目

コンテスト

1 日目チームを組んでいただいた kumakuma さんは 2 日目からソロ参加(元々ソロ参加の予定だったが 1 日目 PC を忘れたらしい)ということで、2 日目は漁師さんとチームを組んでいただいた。

昨日の反省を活かして、ある程度難しい問題は実装を始める前に人に相談しようということにした。

A を見るといかにも FPS 使いそうな 998 で、自分がやることに。ざっと眺めると他にも 998 がいっぱいあって、これは modint 書いたほうがよさそうという話になる。漁師さんに modint を写経してもらっている間に A が解けて AC。

順位表で解かれている C を見る。簡単。confeito 君と 2 人で詰めて AC。

confeito 君が B を、漁師さんが D, E を読んでいて、両方からいろいろ聞いた。confeito 君によると B はいけそうらしいので D, E を考えるけどよくわからず。

順位表で解かれている H を読んで問題概要を伝えると confeito 君から天才考察が返ってくる。コンビネーションを H でも B でも使うっぽいので H の実装ついでに写経する。あとは和が  s で積が  p な 2 数のパートだけちょっと詰めて実装、AC。

confeito 君が B を実装している間に順位表で解かれている K を漁師さんと 2 人で考える。超頂点作ってダイクストラかなーとかいろいろ考えたけどよくわからず。B を通して戻ってきた confeito 君(FA、すごい!)に助けを求めると、値に  (\mathrm{cost}, \mathrm{from}) の配列を持つ DP をすると遷移回数がいい感じに抑えられるらしい。たしかにじゃん。実装してもらって AC。この人天才か?

このあたりで順位がだいぶよかった。順位がいいということは逆に解く問題の見極めを順位表に頼れないということでもある。残っている問題で唯一 AC が出ている F を考える。括弧列まではすぐ言い換えられて、カタラン数の証明が思い出せればちょっと進展がありそうだと思ったけど思い出せなくて苦しんでいた。(実際はこれがわかっても解けなかった気がする)

J に AC が出る。読むとゲーム。通したのは上位チームではない。とすると実験エスパーで解けるやつじゃねということになって、漁師さんが実験を書いてくれた。自分は F を考え続けるけど進展なし。

実験が書けたらしいので結果を見にいく。長方形に A, B をプロットすると見やすいという話になって(ここ地味に偉い)、見ると大きいところでは規則性がありそう。 3 \times 3 3 \times 5 がコーナーなので  H,W \leq 5 なら愚直、そうでなければ規則性、のコードを漁師さんが書いて提出。WA。実験結果を  H,W \leq 7 とかじゃなくて  H \times W \leq 50 とかで表示すると、 2 \times \mathrm{BIG} のケースが処理できていないことに気づく。ここを自分が詰めて書いてもらって AC。

F を考え続けるけど進展がない。

confeito 君が L 解けた気がするらしい。聞くと MCF でできそうとのこと。これを正しいと思ってしまった(実際は嘘だったけど、指摘できなかった。とてもよくない)。漁師さんに kactl の MCF を写経してもらうと、謎の機能を使っていてコンパイルが通らない。こうならないように持ち込むライブラリはちゃんと把握しておくべきですね。Gifted Infants の MCF を見ると変なことはしていなさそうでコンパイルが通った。いざ実装、というところで confeito 君が解法の誤りに気づく。聞くとたしかに嘘だ。残り 10 分くらい、ここから立て直すのは厳しい。結局 ABCHJK の 6 完で 5 位。だいぶいい順位。この日は confeito 君がかなり強かったという印象。

コンテスト後

解説を聞くと F も L も激ヤバでびっくり。チャンスがあったとしたら D, E なのかなあ。まあ今の実力だとこの 6 完が限度という気もする。

談話室でボドゲをした後、部屋で ARC に出た。B が通せなくて激冷え・青落ちで険しい気持ちになった。

その後談話室で Kite_kuma さんと将棋を指した。tokusakurai さんとも指したかったが時間がなくて残念。また機会があればよろしくお願いします。

部屋では 1 行ずつ作問をして遊んだ。滅茶苦茶な問題になっても面白いし、それに混じってたまに良さげな雰囲気の問題が生えても面白いので、レクとしていいかもしれない。nonon さんの参加記 に問題が載っているのでよければ考えてみてください。

3 日目

コンテスト

3 日目はチームが組めず、2 人でやることになった。

confeito 君が A を、自分が B を読む。A は簡単ですぐ通る。B も簡単なはずだが、実装にちょっと手間取ってしまった。

C の概要を聞く。「過半数が同じ」が条件ということの正当性を 2 人で確認。confeito 君曰くこういう数え上げは自信ないらしいので自分が考えることに。その間 I を考えてもらう。

C を立式すると解けた気になる。998 が他にもあるので modint とコンビネーションを写経して(結果的には modint 書くべきだったかは怪しい)、実装。この modint を普段使いしていないせいでなぜかコンパイルが通らなかったりして手間取る。実装すると合わない。よく確認すると立式が間違っていることに気づく。この式だと今の解法では解けないので一旦後回しに。

I を考える。いろいろ議論すると ( を prique にためて ) がきたら「まだペアになっていない ( と組ませる」「もうペアになった ) と交代」のどっちかをやるという感じになりそう。たぶん正しいとは思ったがちょっと自信がなかった。confeito 君が実装。

その間に順位表で解かれている J を見るとド典型。C とか I より先にこっちやればよかった。

I を提出、WA。実装に細かいミスがあるのか方針がそもそも嘘なのかよくわからないので、コードを印刷してリカバリしてもらっている間に J を実装。実装中に DP だとうまくいかなくて 01BFS にする必要があることに気づく。実装重くないか心配されたけど、B でも BFS をやったこともあり大丈夫だった。AC。この間に I のバグに気づいてもらって I もすぐ AC。

あとは C, E と心中するしかないかなという感じ。C はあれから進展がなく、E を 2 人で考える。valid な順番だと区間を広げていく感じになることに confeito 君が気づいて、それを逆から見て立式すると  \mathrm{dp}(i, j) := 左から  i 個、右から  j 個取ったときのなんかの積の総和 という感じになりそう。あとはこれが線形になればいいんだけど、わからない。自分は C と E を行ったり来たりしたが、最後までわからなかった。結局 ABIJ の 4 完で 14 位、激冷え 2。

コンテスト後

2 人だと 3 人のときに比べて明らかに思考が凝り固まっているのを感じた。やっぱり 3 人いるべきだなあ。

C 分割統治はなるほどなあ。ただもしコンテスト中に通すなら二項係数こねこねをしないといけなかった気がする。

E はもっとうまい考え方をすると自然に線形になるっぽい。2 乗を高速化することに固執しすぎたのがよくなかったかも。

さいごに

コンテスト時間が 3 日間合計で 3 + 5 + 5 (+ 1.67 + 2) = 16.67 時間というとても濃い合宿で、競プロモチベがとても高まった。来年は絶対に国内予選を通過したい。

最後になりますが、このような素晴らしい会を運営してくださった JAG の皆様や関係者の方々、また交流していただいた皆さん、誠にありがとうございました。

miscalc 作問一覧

ABC 寄り?

問題 難易度 コメント
SLASH 100 わかる人には元ネタがわかりそう
Time Bomb Game 250 わかる人には元ネタがわかりそう 2
Strong String 300 初作問
Sum of Slide Max 500
K Consecutive Ks (Easy) 550
FizzBuzz Difference 575 ARC 寄りのつもりで作ったが ABC 寄りらしい
K Consecutive Ks (Hard) 650 ? 想定解は天才だけど別解があって、現代なら ABC-Ex 程度?

ARC 寄り?

問題 難易度 コメント
→↑↓ 300 自明すぎるかと思ったがそうでもないらしい A 問題って感じの問題
Sequence 400 ABC 寄りに入れるか迷った わかる人には元ネタがわかりそう 3
I Want AC 400 ARC-A っぽいのが欲しいと思って B - Postdocs を改造 難易度は ARC-B くらいかも
Flat Permutation 500 散歩してたら生えた たくさんの fav ありがとうございます
Time Bomb Game 2 500 面倒という意見が多かった(すみません)
Copy and Paste 2 800 自作問で一番好きかも 直前に似た問題が出てアドベコン行きになった
Small RPS Tournament 800 タイトルの元ネタは C - Large RPS Tournament だけど設定が似ているのは F - Random Tournament AC 数の割にはそんなに難しくない(と思っている)のでぜひ考えてみてください
Odd Insertion 900 当初 ★3 を主張していた(え?) 解法に寄り添って設定をいじる作り方をすると難易度推定を外しやすいですね

競プロで使う Dilworth の定理

大学の授業で Dilworth の定理が出てきたので、この機会に(競プロer 的な視点から)まとめてみたいと思います。

例題 1

atcoder.jp

長さ  N の数列  A = (A_1, A_2, \ldots, A_N) がある。 N 個それぞれの整数に対して、色を  1 つ選んで塗る。ただし、次を満たす必要がある:

  •  A_i A_j i \lt j)が同じ色で塗られているならば、 A_i \lt A_j

このとき、最小で何種類の色を用いればよいか?  N \leq 10^5

最小パス被覆

 A = (2, 4, 3, 6, 1, 5) という例で考えてみましょう。まず、二次元平面上に  (i, A_i) をプロットしてみます(横軸が  i で、縦軸が  A_i です)。

次に、これらをグラフの頂点と考えます。 (i, A_i) に対応する頂点を頂点  i と呼ぶことにします。 i \lt j かつ  A_i \lt A_j のとき、 i \rightarrow j の辺*1を張ります。つまり、「左下から右上」なものすべてにその向きで辺を張ります。こうしてできるグラフを  G とします。

ここで、この  G は DAG(Directed Acyclic Graph:有向非巡回グラフ。閉路が存在しない有向グラフのこと)であり、さらに

  •  i \rightarrow j の辺、 j \rightarrow k の辺がともに存在するならば、 i \rightarrow k の辺も存在する

ことに注意です。これは

  • 頂点  i から頂点  j i \neq j)にたどり着けるならば、頂点  i から頂点  j への(直接の)辺が存在する

と思ってもいいです(こちらのほうが直感的かも)。この性質のことを、この記事では(後で紹介する半順序集合との対応になぞらえて)推移律 と呼ぶことにします。

このときもとの問題は、「同じ色で塗られている頂点の間には、必ず辺が存在する」という条件を満たすように各頂点に色を塗り、そのうえで使う色の個数を最小化すること、と言い換えられます。たとえば次のように  3 色で塗れて、これが最適です*2

なお、ここで同じ色で塗られた頂点集合のように、

  • その頂点集合に含まれるどんな異なる  2 頂点の間にも、辺が存在する

という条件を満たす  G の頂点集合は、 Gパス と対応します(下図)。ここで  G の推移律が効いています。

そう考えると、この問題は「 G の頂点をパスに分割*3するとき、パスの個数を最小化する」問題といえます(パスへの分割を パス被覆、サイズ(パスの数)が最小のパス被覆を 最小パス被覆 といいます)。

最大独立集合

ここで、下図の斜線を引いた頂点について考えます。

斜線を引いた頂点は、どの異なる  2 つについても辺が張られていません。ですから、これらはすべて違う色で塗る必要があります

なお、この斜線を引かれた頂点の集合のように、

  • その頂点集合に含まれるどんな異なる  2 頂点の間にも、辺が存在しない

という条件を満たす  G の頂点集合のことを、 G独立集合 といいます。また、サイズが最大の独立集合を 最大独立集合 といいます。上の考察をこの言葉を使って言い換えると、 G が推移律を満たす DAG ならいつでも、次が成り立つといえます。

 \begin{align} (G \ の最小パス被覆のサイズ) \geq (G \ の最大独立集合のサイズ) \tag{1} \label{dilworth_geq} \end{align}

Dilworth の定理

実は、\eqref{dilworth_geq} よりも強い主張である次が、 G が推移律を満たす DAG ならいつでも成り立ちます:

 \begin{align} (G \ の最小パス被覆のサイズ) = (G \ の最大独立集合のサイズ) \tag{2} \label{dilworth_eq} \end{align}

上の例でいうと、斜線を引いた  3 頂点は違う色で塗る必要があるが、実は全体を塗るのもそれに使った  3 色で事足りる、ということですね。これが Dilworth の定理 です*4*5。証明は、例題 2 のほうで重要になってくるのでいったん後回しにします。

これを使うことで、最小パス被覆問題を、最大独立集合問題に変換できるというわけです。今回の問題では、最大独立集合のサイズは単調非増加部分列の長さの最大値であり、LIS と同様に  O(N \log N) で計算できます。

(補足)半順序集合とそのグラフ表現

半順序集合の定義

半順序集合 とは、集合  P *6とその上の二項関係  \preceq の組  (P, \preceq) であって、

  • 反射律:どんな  a \in P に対しても、 a \preceq a
  • 推移律:どんな  a,b,c \in P に対しても、 (a \preceq b かつ  b \preceq c) ならば  a \preceq c
  • 反対称律:どんな  a,b \in P a \neq b)に対しても、 a \preceq b b \preceq a の両方は成り立たない

を満たすもののことをいいます。気持ち的には、不等号っぽい比較が(定義されていれば)いい感じにできる、という感じだと思えばよさそうです。今回の問題の  (i, A_i) も、二項関係  \preceq

  •  (i, A_i) \preceq (j, A_j) \Leftrightarrow i = j または  (i \lt j かつ  A_i \lt A_j)

で定義したときに、半順序集合をなします。

半順序集合のグラフ表現

上で考えたように、半順序はグラフ(より具体的には、推移律を満たす DAG)で表現できます。ちゃんと書くと、 P の要素に対応する頂点をもつ有向グラフ  G であって、

  •  a \preceq b a,b \in P, a \neq b)のとき、 a に対応する頂点から  b に対応する頂点に有向辺が張られている

ものを考えます。このとき、反対称律は  G が DAG であることに、推移律は  G の推移律に対応します。

半順序集合の言葉での Dilworth の定理

 P の部分集合  C鎖(chain)であるとは、 C の異なる  2 つの要素をどのようにとってきても、 \preceq による比較が可能であることをいいます。より形式的には、「どんな  x,y \in C に対しても  x \preceq y または  y \preceq x が成り立つ」と書けます。これは  Gパスに対応します。

 P の部分集合  A反鎖(antichain)であるとは、 A の異なる  2 つの要素をどのようにとってきても、 \preceq による比較が不可能であることをいいます。より形式的には、「どんな  x,y \in A, x \neq y に対しても  x \preceq y とはならない」と書けます。これは  G独立集合に対応します。

有限半順序集合  (V, \preceq) において、

 \min(V \ を鎖に分割したときの鎖の個数) = \max(V \ の反鎖のサイズ) \tag{3} \label{dilworth_poset}

が成り立つ、というのが(本当の)Dilworth の定理です*7。これは(当然ですが)上の \eqref{dilworth_eq} に対応します。

グラフで表現したときに推移律を満たす DAG になっている、という思考をするよりも、半順序集合をなしていると捉えるほうが直感的な場面も多いと思ったので、紹介しました。

例題 2

atcoder.jp

文字列  S がある。 S の連続部分文字列のうちで回文であるものをいくつか選びたい。ただし、次を満たす必要がある:

  • 選んだ回文のうち  2 つであって、一方が他方の連続部分文字列であるものが存在してはいけない

このとき、最大で何個の回文を選べるか?  |S| \leq 200

ABC-Ex ではあるものの、ここまでの内容を理解していればそう身構える必要はないと思います。

文字列の集合に対して、一方の文字列が他方の文字列の連続部分文字列である、という二項関係を定義すると、これは半順序集合をなします。よって、文字列の集合として  S の連続部分文字列である回文の集合をもってくると、求めるものはその反鎖のサイズの最大値です。これは Dilworth の定理から、鎖に分割するときの鎖の個数の最小値になります。

Dilworth の定理を使う向きが例題 1 と逆になっていますね。

最小パス被覆の、二部グラフの最大マッチングへの帰着

先ほどもみたように、「鎖に分割するときの鎖の個数の最小値」はグラフの言葉でいうと「最小パス被覆」です。実は、DAG の最小パス被覆は二部グラフの最大マッチングに帰着します

二部グラフとは? 頂点を  2 グループに分けるとき、「同じグループに属する  2 頂点の間には、辺が存在しない」ようにできるグラフのことです。

グラフのマッチングとは? グラフの辺をいくつか選ぶ方法であって、「どの頂点も、選んだ辺のうち異なる  2 つ以上の辺の端点になっていることはない」ようなもののことです。このうちサイズ(選んだ辺の数)が最大のものが最大マッチングです。

 N 個の頂点  1, 2, \ldots, N をもつ DAG  G を、 N 個の左側頂点  1, 2, \ldots, N N 個の右側頂点  1', 2', \ldots, N' *8 をもつ二部グラフ  H に対応させることを考えます。対応のさせ方としては、 G i \rightarrow j の辺を、 H i \ – \ j' 間の辺に対応させます。

このとき、

 (G \ の最小パス被覆のサイズ) = N - (H \ の最大マッチングのサイズ) \tag{4} \label{pathcover_matching}

が成り立ちます。

この理由を説明します。まず、 G のパス被覆について、

 (パス被覆のサイズ) = N - (パス被覆に含まれる辺の数) \tag{5} \label{pathcover_edge}

が成り立ちます。これは、パス被覆に使ったパスのどれについても、

 (頂点数) = (辺数) + 1 \tag{6} \label{vertex_edge}

となっているからです。\eqref{vertex_edge} をすべてのパスについて足し上げると \eqref{pathcover_edge} になります。\eqref{pathcover_edge} は、「パス被覆のサイズを最小化することは、パス被覆に含まれる辺の数を最大化することと同じである」とも捉えられます。

次に、 G のパス被覆と  H のマッチングは上図のように一対一対応します。つまり、

  •  G のパス被覆について、使った辺に対応する  H の辺を使ったものは  H のマッチングです。

    • パス被覆に含まれる辺について、同じ頂点から出ている  2 辺や、同じ頂点に入っている  2 辺はないため、対応する  H の辺についても端点を共有する  2 辺は存在しないことになるからです。
  • 逆に、 H のマッチングについて、使った辺に対応する  G の辺を使ったものは  G のパス被覆です。

    • マッチングに含まれる辺について、端点を共有する  2 辺は存在しないので、対応する  G の辺について、同じ頂点から出ている  2 辺や、同じ頂点に入っている  2 辺はありません。ここで、 G は DAG なので、この辺集合はパス被覆をなします*9

以上より、\eqref{pathcover_matching} が成り立つといえます*10

これで、二部グラフの最大マッチングが解ければよいことになったので、この問題が解けました*11。細かい計算量評価はここではしません(気になる方はこちらを見るとよいです)が、少なくとも多項式時間にはなっていることがわかると思います。最大独立集合問題は一般のグラフでは NP-hard なのですが、推移律を満たす DAG という特殊ケースでは Dilworth の定理により多項式時間で解けるようになっている、というのはなかなかすごいことだと思います。

Dilworth の定理の証明

DAG の最小パス被覆が二部グラフの最大マッチングに帰着する、つまり、

 (G \ の最小パス被覆のサイズ) = N - (H \ の最大マッチングのサイズ) \tag{3) (再掲}

という事実は、実は Dilworth の定理の証明の根幹の一つになっています*12。他に示すことは次の  2 つです。

 (H \ の最大マッチングのサイズ) = (H \ の最小点被覆のサイズ) \tag{7} \label{konig}

 (G \ の最大独立集合のサイズ) \geq N - (H \ の最小点被覆のサイズ) \tag{8} \label{mis_vertexcover}

これらが示せれば  (G \ の最大独立集合のサイズ) \geq (G \ の最小パス被覆のサイズ) がわかります。\eqref{dilworth_geq}( \leq のほうが成り立つこと)がすでにわかっているので、それとあわせて \eqref{dilworth_eq}( = が成り立つこと)がわかります。

グラフの点被覆とは? グラフの頂点をいくつか選ぶ方法であって、「どの辺についても、その端点の少なくとも一方が選んだ頂点に含まれる」ようなもののことです。このうちサイズ(選んだ頂点の個数)が最小のものが最小点被覆です。

二部グラフでの、最大マッチングと最小点被覆の関係(Kőnig の定理)

 (H \ の最大マッチングのサイズ) = (H \ の最小点被覆のサイズ) \tag{7) (再掲}

これは一般の二部グラフで成り立ちます(Kőnig の定理*13 と呼ばれます)。

まず、(二部グラフに限らず)どんなグラフでも、明らかに

 (点被覆のサイズ) \geq (マッチングのサイズ) \tag{9} \label{konig_geq}

です。マッチングに含まれる辺について、その端点の少なくとも片方は選ばないと、点被覆になりません。これらの端点は重複して出てこないので(これはマッチングの定義からわかります)、マッチングのサイズと同じだけの個数の頂点は最低でも選ぶ必要があるということです。

次に、最大マッチングのサイズと等しいサイズの点被覆が存在することを示します。これがいえたら、(最小点被覆のサイズは当然この点被覆のサイズ以下なので) (最大マッチングのサイズ) \geq (最小点被覆のサイズ) がいえて、\eqref{konig_geq} とあわせて \eqref{konig} が示せます。

ここで、マッチングに使わない辺を黒、使う辺を橙で塗ることにしたとき、通る辺の色が交互になっているパスを 交互道 といい、交互道の中でも端点がいずれもマッチングに使われていないものを 増加道 といいます。最大マッチングには増加道は存在しません*14。なぜなら、もし存在したら、それに含まれる辺の色をすべて反転させることで、マッチングのサイズを  1 増やせるからです。

さて、最大マッチングをひとつとってきたとき、マッチングに使われていない左側頂点を黄色く塗り、そこから左側から右側へは黒い辺、右側から左側へは橙の辺を使って(言い換えると、黒 → 橙 → 黒 → 橙 → … という交互道を使って)到達可能な頂点を黄色で、到達不可能な頂点を白で塗ることにします。このとき、左側の白い頂点と右側の黄色い頂点をすべて選ぶと、これは点被覆になります。

なぜなら、これが点被覆にならないのは左側の黄色い頂点と右側の白い頂点の間に辺が存在する場合のみ*15ですが、そのようなことは起こらないからです。

  • もし左側の黄色い頂点と右側の白い頂点の間に黒い辺が存在したら、それを使って左側の黄色い頂点から右側の白い頂点に行けているはずなのでおかしいです。

  • もし左側の黄色い頂点と右側の白い頂点の間に橙の辺が存在したら、左側の黄色い頂点に行けているのはおかしいです(マッチングに使われているので最初には黄色く塗られませんから、右側の黄色い頂点から橙の辺を使って来たことになります。このときこの左側頂点を端点とする橙の辺が  2 本あることになってしまいます。マッチングのはずなのでおかしいです)。

この点被覆が、欲しかった「最大マッチングのサイズと等しいサイズの点被覆」です。これは、次のことからわかります。

  • 左側の白い頂点には、それを端点とする橙の辺がある。

    • もしなかったら、その頂点はマッチングに使われていないので最初に黄色く塗られるはずである。
  • 右側の黄色い頂点には、それを端点とする橙の辺がある。

    • もしなかったら、増加道が存在していることになる(マッチングに使われていない左側頂点から、交互道を使って、マッチングに使われていないこの右側頂点まで来たことになるので)。これは、最大マッチングであることに矛盾する。
  • 左側の白い頂点と右側の黄色い頂点を結ぶ橙の辺はない。

    • もしあったら、それを使って右側の黄色い頂点から左側の黄色い頂点に行けているはずである。

これで示せました。

最大独立集合と、二部グラフの最小点被覆の関係

 (G \ の最大独立集合のサイズ) \geq N - (H \ の最小点被覆のサイズ) \tag{8) (再掲}

 G の独立集合であって、サイズが  N - (H \ の最小点被覆のサイズ) 以上のもの」が存在することを示します。これが示せれば、最大独立集合のサイズは当然この独立集合のサイズ以上なので、\eqref{mis_vertexcover} が成り立つといえます。これは \eqref{konig} を示すときに使った論法にもよく似ていると思います。

 H の最小点被覆について、 G の頂点集合を次のルールで対応させます。

  • 頂点  i も頂点  i' もその点被覆に含まれていないとき、 G の頂点  i を選ぶ。

このとき、選ばれた  G の頂点の集合は  G の独立集合になっています(もしなっていなかったら、点被覆になっていません)。

この独立集合のサイズは「頂点  i と頂点  i' が、両方  H の最小点被覆に含まれる」ような  i の個数によって変わってくるのですが、もしそのような  i が存在しなければ、サイズは  N - (H \ の最小点被覆のサイズ) に等しいです。

実は、 G が推移律を満たすときは必ずそうなることがわかる*16のですが、別にそうでなくてもいいです。もし「頂点  i と頂点  i' が、両方  H の最小点被覆に含まれる」ような  i が存在したら、独立集合のサイズはそのような  i の個数のぶんだけ増えます。

よって \eqref{mis_vertexcover} が成り立つことが示せました。

まとめ

例題 1 では、「鎖に分割するときの鎖の個数の最小値」を「反鎖のサイズの最大値」に変換して問題を解きました。この問題の設定において、変換後の問題が LIS という性質がよくて少ない計算量で解ける問題だったので、これが使えました。

例題 2 では逆に、「反鎖のサイズの最大値」を「鎖に分割するときの鎖の個数の最小値」に変換して問題を解きました。こちらは最小パス被覆になり、計算量が(例題 1 の制約では使えない程度には)かかりますが、いつでも二部グラフの最大マッチングを使って(多項式時間で)解ける問題でした。

また、半順序集合を表して得られるグラフ(つまり、推移律を満たす DAG) G と、それにうまく対応する二部グラフ  H を考えたときに

  •  G の最小パス被覆

  •  H の最大マッチング

  •  H の最小点被覆

  •  G の最大独立集合

がすべて互いに対応する(しかも不等号ではなく等号の関係で!)ということをみました。この関係と、それに用いた仮定をまとめたのが下図です:

参考にしたものなど

*1:頂点  i から頂点  j に向かう有向辺のことをこう書くことにします

*2:ほかにも最適な塗り方はあります

*3:ちゃんと言うと、パスの集合であって、どの頂点もそのうちちょうど  1 つに含まれるようなものです

*4:ちょっと嘘です。本当は半順序集合に対しての定理のことをそう呼んでいる気がします(たぶん)。これについてはこの次の節で触れます

*5:この記事では詳細には触れませんが、似たような定理として Mirsky の定理というのもあります。主張だけ述べると、同じく推移律を満たす DAG  G に対して、 (G \ の最長パスの頂点数) = (G \ を独立集合に分割するときの独立集合の数) というもの(と等価)です。最大のものをとってくる側と最小個数で覆う側がちょうど Dilworth の定理と逆転していることがわかると思います。こちらは Dilworth の定理に比べると証明が簡単です

*6:半順序集合の英語 partially ordered set(poset)の頭文字です

*7:こういうふうに、順序の話を先に導入して、後からグラフとつなげる、という流れのことが多い気がします?(あまり知らないので自信なし)この記事では、競プロer はグラフのほうが馴染みがある人が多いと思ったのでグラフの話を先に紹介していました

*8:これ以降、二部グラフの  2 グループを「左側」と「右側」のように呼ぶことにします

*9:入次数が  0 の頂点から始めて、辺が出ているうちは進め続ける、という感じでできます

*10:なお、 G が DAG ではない場合は  G のパス被覆から  H のマッチングへの対応づけはできますが、 H のマッチングから  G のパス被覆への対応づけはできるとは限らないので、 \geq は成り立ちますが  \leq は必ずしも成り立ちません

*11:二部グラフの最大マッチングの解法はここでは扱いませんでしたが、たとえば、最大フローに帰着させて求めることができます

*12:実際は、Dilworth の定理を証明するだけだったら  \leq だけで OK です

*13:ケーニヒ と読みます

*14:逆に、増加道が存在しないマッチングは最大マッチングである、ということもいえます。証明はたとえば 二部グラフの最大マッチングと増加道 | 高校数学の美しい物語 に載っています

*15:他のパターンは「左の白と右の白」「左の白と右の黄」「左の黄と右の黄」を結ぶ辺の場合で、左の白、右の黄はすべて選ばれているので OK

*16:方針だけ書くと、頂点  i と頂点  i' を両方含む点被覆は、「頂点  i を除いても点被覆である」「頂点  i' を除いても点被覆である」のいずれかが成り立つ、ということがいえます