この記事は traP 2026 夏のブログリレー 15 日目の記事です。

この記事には 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$
- この記事では使わないので、分からなくても大丈夫です。

簡約律 (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$ 削除) も同様にして示せます。系として、文字列 $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)
仮定より $π_{{c, c}} (x) = π_{{c, c}} (y)$ であるから、文字 $c$ が現れる回数は $x, y$ で等しく、特に $∣ x ∣ = ∣ y ∣$ である。

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

文字列 $x$ の末尾文字を $a$ と置く。 $a$ を含む禁止ペアの射影に注目すると、 $y$ の最右 $a$ を末尾まで swap することが可能なので $y \equiv (y \div a) a$ である。同様に射影に注目して $(x \div a, y \div a)$ について文字列長 $∣ x ∣ - 1$ の Projection Lemma を適用できることが分かる。これを仮定すると $x \div a \equiv 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 に関する典型を思い浮かべてください。おまけに空間計算量が落ちます。

他の証明も載せます。アルファベット $Σ$ に全順序が定まっているとき、文字列 $x$ から変換可能な辞書順最小の文字列 $f (x)$ を標準形とすることで示します。

感覚的に自明な部分を誤魔化しています。すみません。

(証明2)
$V = {1, \dots, ∣ x ∣}, E = {(i, j) : i < j \land (x_{i}, x_{j}) \in D}$ とすると、グラフ $G_{x} = (V, E)$ は DAG である。同じ文字を指す複数の頂点がキューに同時に入ることはないことに注意すると、この DAG 上で文字 $x_{i}$ を重みとする辞書順最小のトポロジカル順序は一意に定まる。その順番で並べた文字列は $x$ から変換可能であり、求める文字列 $f (x)$ と一致することが示せる。

文字列 $x, y$ が全ての禁止ペアについて射影が一致することを仮定する。グラフ $G_{x}, G_{y}$ 上の頂点を「頂点が指す文字と、その文字が元の文字列で何回目の出現か」が一致する頂点同士で対応付けると、グラフ $G_{x}, G_{y}$ が同型かつ対応する頂点の指す文字を一致させることができると分かる。 $f$ の値は頂点が指す文字とグラフの形状のみによって定まるため $f (x) = f (y)$ である。よって $x \equiv f (x) = f (y) \equiv y$ であり Projection Lemma が示された。

グラフの辺は定義通り張る必要はなく、禁止ペアへの射影で隣接するものに張ればよいです。計算量は $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$ という順序を入れ、証明 2 のように辞書順最小の文字列を標準形に設定することで Projection Lemma を証明したものになっています。 ${0, 1}$ は swap 禁止ペアなのでどちらの順序を選んでもよいです。

あとがき

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

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

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

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

【競プロ】ざっくり Trace Monoid

定義

簡約律 (Cancellation Property)

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

ARC194E

あとがき

関連する記事

【競プロ】ざっくり Trace Monoid

定義

簡約律 (Cancellation Property)

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

ARC194E

あとがき

この記事をシェア

関連する記事