この記事は traP 2026 夏のブログリレー 15 日目の記事です。明日の記事は @Oxojo さんの予定です。

この記事には ARC194E Swap 0^X and 1^Y のネタバレが存在します。

文字列に連結演算を入れた構造は、モノイドの公理以外の関係式を持たないことから free monoid と呼ばれています。ここに一部の文字間での可換性を課した構造は free partially commutative monoid あるいは trace monoid と呼ばれ、並列計算におけるジョブ同士の関係を表現できることからコンピュータサイエンス方面でも研究されているらしいです。

「一部の文字ペアについて、その 2 文字での隣接 swap が禁止されている。このとき隣接 swap を繰り返して文字列 $S$ から文字列 $T$ に変換できるか？」という問題の判定法を提示することを目標とし、trace monoid の性質をざっくりと紹介していきます。

この記事は Trace monoid (en-Wikipedia) を参考にして作成されました。有名な本・記事とは異なる表記をしている可能性があることに注意してください。

定義

以下において "swap" は文字列上で隣接した文字を入れ替える操作を指します。
$Σ$ をアルファベットとします。種類数を $σ = ∣Σ∣$ と書くことにします。
$Σ^{*}$ を文字列全体の集合とします。特に空文字列を含みます。
dependency relation $D \subset Σ \times Σ$
- 対称的かつ反射的である必要があります。
- swap が禁止されたペアの集合です。同じ文字同士は swap 禁止とします。
independency relation $I := Σ \times Σ ∖ D$
- $D$ の性質から、 $I$ は対称的かつ非反射的になります。
- swap が可能なペアの集合です。
trace $\equiv$
- 文字列 $x$ から swap を何回か行って文字列 $y$ に変換できるときに $x \equiv y$ と書きます。
- 正確には $x ab y \sim x ba y (x, y \in Σ^{*}, (a, b) \in I)$ で定義される二項関係 $\sim$ の反射推移閉包で定まる同値関係です。
trace monoid $M := Σ^{*} / \equiv$
- この記事では使わないので、分からなくても大丈夫です。
- $[x] [y] := [x y]$ は well-defined なので商集合にも連結演算が入ります。

簡約律 (Cancellation Property)

文字列に対し、文字 $a$ として一番右に現れる位置を最右 $a$ と呼ぶことにします。
文字 $a$ を含む文字列 $x$ について、最右 $a$ を削除して得られる文字列を $x \div a$ と書きます^[1]。

右簡約律 $x \equiv y ⟹ x \div a \equiv y \div a$ が成立することを示します。

(証明)
$x$ から $y$ に変換する過程を $x = w_{0} \to \dots \to w_{n} = y$ と置く。また、文字列 $w_{i}$ を最右 $a$ で分割して $w_{i} = p_{i} a q_{i}$ と置く。過程 $w_{i} \to w_{i + 1}$ について

操作に最右 $a$ が関わらないときは $p_{i} \equiv p_{i + 1}$ かつ $q_{i} \equiv q_{i + 1}$
関わるときは $p_{i} q_{i} = p_{i + 1} q_{i + 1}$

であるから $p_{i} q_{i} \equiv p_{i + 1} q_{i + 1}$ が成立する。 $x \div a = p_{0} q_{0} \equiv p_{n} q_{n} = y \div a$ より示された。

左簡約律 (最左削除) も同様にして示せます。系として、文字列 $a, b$ に対し $a x b \equiv a y b ⟺ x \equiv y$ が成立します。

射影による trace 判定 (Projection Lemma)

文字集合 $S \subset Σ$ に対し、文字列 $x$ から $S$ に含まれる文字だけを残してできる文字列を $π_{S} (x)$ と書きます。これは $S$ への射影と呼ばれます。

任意の swap 禁止ペア $(a, b) \in D$ について、swap の前後で ${a, b}$ への射影が不変量になることは簡単に分かります。逆に変換可能かどうかは、禁止ペアへの射影が全て一致しているかを見ればよいというのが、以下の Projection Lemma^[2] です。

^{\forall} (a, b) \in D, π_{{a, b}} (x) = π_{{a, b}} (y) ⟺ x \equiv y

証明 1

$⟹$ を文字列長に関する数学的帰納法で示します。

(証明1)
仮定より $π_{{c, c}} (x) = π_{{c, c}} (y)$ であるから、文字 $c$ が現れる回数は $x, y$ で等しく、特に $∣ x ∣ = ∣ y ∣$ である。

文字列長 $0$ のとき明らかに成立する。 $∣ x ∣ \geq 1$ のときを考える。

文字列 $x$ の末尾文字を $a$ と置く。仮定から $y$ の最右 $a$ を末尾まで swap させることが可能であると分かるので $y \equiv (y \div a) a$ である。

文字列長 $∣ x ∣ - 1$ の Projection Lemma を仮定すると、 $(x \div a, y \div a)$ に適用することにより $x = (x \div a) a \equiv (y \div a) a \equiv y$ が得られて、文字列長 $∣ x ∣$ の Projection Lemma が示される。以上の議論に数学的帰納法を用いればよい。

文字列長の和を $N = ∣ x ∣ + ∣ y ∣$ と置きます。射影ごとに文字列を走査するナイーブな方法で $O (∣ D ∣ \cdot N)$ で計算できます。文字ごとの出現位置リストから計算したり、一回の走査で並行して射影を構築したりすることで $O (σ N)$ になります。

後者の方法について、射影を Rolling Hash で表現させると面白い気がします。モノイドが載るデータ構造を利用して部分文字列を調べたり、文字列の累乗が計算できるので例えば $w^{p} x^{q} \equiv y^{r} z^{s}$ かどうか判定したりすることができます。ここにお好みの Rolling Hash に関する典型を追加してください。おまけに空間計算量が落ちます。

証明 2

他の証明も載せます。アルファベット $Σ$ に全順序が定まっているとき、文字列 $x$ から変換可能な辞書順最小の文字列 $f (x)$ を構築できます。これを標準形 (すなわち同値類の代表元) とすることで trace 判定ができます。

射影は元の文字列のインデックスに関する情報を持たないため dependency graph (en-Wikipedia) というものを経由して Projection Lemma を証明します。

(証明2)
文字列 $x$ に対し、 $V = {1, \dots, ∣ x ∣}, E = {(i, j) : i < j \land (x_{i}, x_{j}) \in D}$ としてグラフ $G = (V, E)$ を定義する。このグラフは DAG である。

$G$ のトポロジカル順序を受け取り、その順番で文字を並べてできる文字列を返す写像は単射である。また、この写像の像は $x$ から変換可能な文字列全体の集合である。よって、文字 $x_{i}$ を重みとする辞書順最小のトポロジカル順序により生成される文字列が求める文字列 $f (x)$ である。

$(V, E, ϕ : V \to Σ)$ が次の条件を満たすとき dependency graph と呼ぶ。

グラフ $(V, E)$ は DAG である。
$(ϕ (i), ϕ (j)) \in D$ ならば頂点 $i, j$ 間にいずれかの向きの辺が張られている。

また、dependency graph $(V, E, ϕ), (V^{'}, E^{'}, ϕ^{'})$ の同型性は次のような全単射 $g : V \to V^{'}$ が存在するかで定義される。

グラフ $(V, E), (V^{'}, E^{'})$ は $g$ によって同型である。
任意の頂点 $i \in V$ に対して $ϕ (i) = ϕ^{'} (g (i))$

Projection Lemma の仮定を満たすとき、作られる dependency graph は同型を除いて一意であり、関数 $f$ の値を求めるアルゴリズムは dependency graph の同型性に関して不変なので $f (x) = f (y)$ が導ける。

グラフの辺は定義通り張る必要はなく、射影において隣接する頂点に張ればよいです。計算量は $O (σ N)$ です。

ARC194E

ARC194E Swap 0^X and 1^Y / 公式解説

正整数 $X, Y$ および長さ $N$ の 01 文字列 $S, T$ が与えられる。 $S$ の部分文字列 $0^{X} 1^{Y}$ を $1^{Y} 0^{X}$ に置き換えたり、その逆ができるとき、 $S$ を $T$ に一致させることは可能か判定せよ。

公式解説の前半の言い換えは同様に行います。
$0^{X}, 1^{Y}$ の塊を表す文字 $A, B$ を導入してアルファベット $Σ = {0, 1, A, B}$ とします。現れる $0^{X}, 1^{Y}$ の塊を貪欲に $A, B$ に置き換えるようにして 01 文字列を $Σ$ 文字列に変換したのち、 ${0, A}, {1, B}, {A, B}$ でのみ swap 可能としてもよいです。あとは $S \equiv T$ かどうかの判定をするだけです。

公式解説の後半はアルファベットに $A < 1 < 0 < B$ あるいは $A < 0 < 1 < B$ という順序を入れ、射影から辞書順最小の文字列が一意に定まることを ad-hoc に証明しています。 ${0, 1}$ は swap 禁止ペアなのでどちらの順序を選んでもよいです。

この性質が一般の場合で成り立つという話でした。以上。

あとがき

Gemini に上の問題を投げたら面白そうな話題を返してくれたので、少し勉強して記事にしてみました。よく見返したら Projection Lemma の証明に簡約律を使っていないことに気付いたのですが、消すのも勿体ないので残すことにしました。

trace monoid には面白い話が残っていそうなので、誰か書いてください、頼みました……

この記事は traP 2026 夏のブログリレー 15 日目の記事です。ぜひリンクから他の記事も閲覧してみてください。明日の記事は @Oxojo さんの予定です。

参考にした Wikipedia の記事では文字 $a$ を含まない文字列についても定義されていたが、ここでは未定義とする。 ↩︎
Mathematics Stack Exchange の回答において Projection Lemma と呼ばれているが、一般的に何と呼ばれるかは調べていない。 ↩︎

【競プロ】ざっくり Trace Monoid

定義

簡約律 (Cancellation Property)

射影による trace 判定 (Projection Lemma)

証明 1

証明 2

ARC194E

あとがき

関連する記事

【競プロ】ざっくり Trace Monoid

定義

簡約律 (Cancellation Property)

射影による trace 判定 (Projection Lemma)

証明 1

証明 2

ARC194E

あとがき

この記事をシェア

関連する記事