Official

A - Antichain of Integer Strings Editorial by maspy

正の整数 \(x\) について、\(f(x)\) を次のように定めます：

  • \(10\) 進法表記したときに \(x\) が \(y\) の部分文字列となるような最小の \(y>x\) を \(f(x)\) と定める。

[1] \(f(x)\) の計算、単調増加性

\(x\) が \(n\) 桁のとき、\(f(x)\) は \(n + 1\) 桁です。\(x\) が \(f(x)\) の接頭辞となるか接尾辞となるかによって場合分けをすれば、\(f(x) = \min\{10^n+x,10x\}\) であることが分かります。

また、\(10^n+x\), \(10x\) はともに \(x\) に関して狭義単調増加であることから，\(f\) も狭義単調増加であることが分かります。

[2] 解の構成、最適性の証明

\(A = \{L\leq x\leq R\mid f(x) > R\}\) とおき、これが要素数が最大の良い集合であることを示しましょう。\(f(x)\) の定義により、\(A\) が良い集合であることが分かります。

\(A\) が良い集合のうちで要素数が最大であることを示しましょう。次のように定まる有向グラフを考えます。

  • \(L\) 以上 \(R\) 以下の整数全体を頂点集合とする。
  • \(L\leq x\leq R\) かつ \(f(x) \leq R\) のとき、\(x\) から \(f(x)\) に有向辺を張る。

このグラフは DAG （サイクルのない有向グラフ）です。また、任意の頂点の出次数・入次数はともに \(1\) 以下です（入次数が \(1\) 以下であることは、\(f\) の狭義単調増加性から分かります）。

したがってこの有向グラフは、いくつかの点素なパスに分解されます。同じパス上にある \(2\) 頂点は、どちらかが他方の部分文字列となるため、良い集合は同一のパスの頂点を高々ひとつまでしか含みません。したがってパスの個数は、良い集合の要素数の上界を与えます。

一方、上で定義した良い集合 \(A\) は、このグラフにおいてはパスの終点全体と言い換えることができます。したがって、パスの個数という上界が達成されており、\(A\) が最適であることが分かりました。

[3] 答の計算

結局、本問を解くには \(A = \{L\leq x\leq R\mid f(x) > R\}\) の要素数を求めればよいことが分かりました。\(f\) が狭義単調増加であることから、二分探索により答を求めることができます（より直接的に境界を求めることもできます）。

以上をまとめると、本問はテストケースごとに \(O(\log^2 R)\) などの時間計算量で解くことができることが分かります。

[4] 参考：鎖と反鎖の関係（Dilworth の定理）

有限順序集合\(S\) について、次の概念を考えます：

  • \(A\subset S\) が反鎖 (antichain)であるとは、\(A\) の相異なる任意の \(2\) 元が比較不可能であること
  • \(C\subset S\) が鎖 (chain)であるとは、\(C\) の相異なる任意の \(2\) 元が比較可能であること

\(\{L, \ldots, R\}\) に部分文字列関係によって順序を定めたとき、本問は反鎖の要素数の最大値を求める問題であると見なすことができます。

[2] における最適性の証明では、反鎖 \(A\) の最適性を示すために、\(|A|\) 個の鎖からなる \(S\) の被覆を構成するという方法をとりました。このような反鎖と鎖による被覆の組は必ず存在することが知られており、最大反鎖を求めたり、その最大性を証明するための基本的な手段となります。

Dilworth の定理：\(S\) の反鎖の要素数の最大値は、\(S\) を鎖で被覆するための鎖の最小個数と一致する。

posted:
last update: