E - Reflection on Grid Editorial by en_translator
公式解説と公式解説の補足の補足解説のアルゴリズムが正当であることを厳密に証明します。
以下を定義します。
- \(H \times W\) グリッドのセルを \(\mathcal C \coloneqq \{ C_{i,j} \mid 1 \leq i \leq H, 1 \leq j \leq W \}\)、
- セルの周を構成する
- 横方向の線分を \(\mathcal X \coloneqq \{ X_{i,j} \mid 0 \leq i \leq H, 1 \leq j \leq W \}\)、
- 縦方向の線分を \(\mathcal Y \coloneqq \{ Y_{i,j} \mid 1 \leq i \leq H, 0 \leq j \leq W \}\)、
- 線分 \(X_{i,j} \in \mathcal X\) を
- 下方向に通過することに対応する頂点を \(D_{i,j}\)、
- 上方向に通過することに対応する頂点を \(U_{i,j}\)、
- 線分 \(Y_{i,j} \in \mathcal Y\) を
- 右方向に通過することに対応する頂点を \(R_{i,j}\)、
- 左方向に通過することに対応する頂点を \(L_{i,j}\)。
また、頂点集合を \[ V \coloneqq \bigcup _ {0 \leq i \leq H \atop 1 \leq j \leq W} \lbrace D _ {i,j}, U _ {i,j} \rbrace \cup \bigcup _ {1 \leq i \leq H \atop 0 \leq j \leq W} \lbrace R _ {i,j}, L _ {i,j} \rbrace \] として、辺を公式解説のように張ったグラフ \(G = (V, E)\) を考えます。
辺の貼り方の詳細 （および \(E_\star\) の定義）
各 \(C_{i,j} \in \mathcal C\) について、有向辺の集合 \(E_{C_{i,j}}\) を以下の要素からなる大きさ \(12\) の集合とします：
- \(D_{ i-1, j } \to D_{ i, j }\)
- \(D_{ i-1, j } \to R_{ i, j }\)
- \(D_{ i-1, j } \to L_{ i, j-1 }\)
- \(R_{ i, j-1 } \to D_{ i, j }\)
- \(R_{ i, j-1 } \to R_{ i, j }\)
- \(R_{ i, j-1 } \to U_{ i-1, j }\)
- \(U_{ i, j } \to R_{ i, j }\)
- \(U_{ i, j } \to U_{ i-1, j }\)
- \(U_{ i, j } \to L_{ i, j-1 }\)
- \(L_{ i, j } \to D_{ i, j }\)
- \(L_{ i, j } \to U_{ i-1, j }\)
- \(L_{ i, j } \to L_{ i, j-1 }\)
\(E = \bigcup _ {C_{i,j} \in \mathcal C} E_{C_{i,j}}\) です。 なお、\(E_{C_{i,j}}\) は互いに素です。
なお、これらは以下のように図示されます。
\(s\colon V \to \mathcal X \cup \mathcal Y\) を、頂点が与えられたときそれが乗っている線分を返す写像とします。
\(c\colon E \to \mathcal C\) を、辺が与えられたときにそれが含まれているセルを返す写像とします。
\(t\colon E \to \{\)A\(, \)B\(, \)C\(\}\) を、上の図における辺の色（赤なら A、青なら B、緑なら C）とします。
\(f\colon E \to \{0, 1\}\) を、公式解説で与えられた辺のコストとします。
厳密な定義
\(s\) の定義： 各 \(X_{i,j} \in \mathcal X\) に対して、\(s(U_{i,j}) = s(D_{i,j}) = X_{i,j}\) と定義します。 各 \(Y_{i,j} \in \mathcal Y\) に対して、\(s(R_{i,j}) = s(L_{i,j}) = Y_{i,j}\) と定義します。
\(c\) の定義： 各 \(e \in E_{C_{i,j}}\) に対して \(c(e) = C_{i,j}\) と定義します。
\(t\) の定義： 各 \(1 \leq i \leq H, 1 \leq j \leq W\) について、
- \(t((D_{ i-1, j }, D_{ i, j })) = \)
A - \(t((D_{ i-1, j }, R_{ i, j })) = \)
B - \(t((D_{ i-1, j }, L_{ i, j-1 })) = \)
C - \(t((R_{ i, j-1 }, D_{ i, j })) = \)
B - \(t((R_{ i, j-1 }, R_{ i, j })) = \)
A - \(t((R_{ i, j-1 }, U_{ i-1, j })) = \)
C - \(t((U_{ i, j }, R_{ i, j })) = \)
C - \(t((U_{ i, j }, U_{ i-1, j })) = \)
A - \(t((U_{ i, j }, L_{ i, j-1 })) = \)
B - \(t((L_{ i, j }, D_{ i, j })) = \)
C - \(t((L_{ i, j }, U_{ i-1, j })) = \)
B - \(t((L_{ i, j }, L_{ i, j-1 })) = \)
A
\(f\) の定義： 各 \(e \in E_{i,j}\) に対して、\((S_i)_j = t(e)\) のとき \(f(e) = 0\)、それ以外のとき \(f(e) = 1\) と定義します。 ここで \((S_i)_j\) は問題文中で定義された長さ \(W\) の文字列 \(S_i\) の \(j\) 文字目を表します。
\(P\) が \(G\) 上のパスであるとは、ある整数 \(k\) に対して \(P = (v_0, e_1, v_1, e_2, \ldots, e_{k-1}, v_{k-1}, e_k, v_k)\) が頂点と辺を交互に並べた列であることを言います。
このとき、パスの長さを \(|P| \coloneqq k\)、コストを \(g(P) \coloneqq \sum_{i=1}^k f(e_i)\) で定義します。
\(u, v \in V\) に対して、\(P\) が \(u-v\) パスであるとは、\((v_0, v_{|P|}) = (u, v)\) であることを指します。
\(G\) 上の \(R_{1,0} - R_{H,W}\) パスの集合を \(\mathcal P\) と置くと、
公式解説で求めている最短距離 \(M\) は、\(P \in \mathcal P\) における \(g(P)\) の最小値です。
主張1. コスト \(M\) のパス \(P = (v_0, e_1, \ldots, v_{|P|}) \in \mathcal P\) であって、以下の条件を満たすものが存在する：
- 頂点素である。 ……(1)
- 言い換えれば、\(v_i = v_j\) なる \(0 \leq i < j \leq |P|\) が存在しない。
証明
コスト \(M\) のパス \(P = (v_0, e_1, \ldots, v_{|P|}) \in \mathcal P\) を任意に取る。 もし \(v_i = v_j\) なる \(0 \leq i < j \leq |P|\) が存在するなら、 \(P' \coloneqq (v_0, \ldots, e_i, v_i = v_j, e_{j+1}, \ldots v_k) \in \mathcal P\) で、 \(g(P') \leq g(P) = M\) である。 コストの最小性から、\(g(P') = g(P)\) である。 パスの長さの有限性から、これを繰り返すことで、頂点素なパスを得ることができる。 ■
主張2. コスト \(M\) のパス \(P = (v_0, e_1, \ldots, v_{|P|}) \in \mathcal P\) であって、(1) および以下の条件を満たすものが存在する：
- \(s(v_i)\) \((0 \leq i \leq |P|)\) が相異なる。 ……(2)
直感的には、同じ線分を二度以上通過しなくてもよいことを意味します。
証明
コスト \(M\) の (1) を満たすパス \(P = (v_0, e_1, \ldots, v_{|P|}) \in \mathcal P\) を任意に取る。 もし \(s(v_i) = s(v_j)\) なる \(0 \leq i < j \leq |P|\) が存在するなら、 以下の手順で \(g(P') \leq g(P)\) なる \(P' \in \mathcal P\) を得られる。
手順
- \(i' \coloneqq i, j' \coloneqq j'\) とおく。
- 以下を繰り返す。
- もし \(s(v_{i'}) \neq s(v_{j'})\) ならば、
- \(s(v_i) = s(v_j)\) よりこのループは \(1\) 回以上回っている。
- したがって、前のステップから \(s(v_{i'+1}) \neq s(v_{j'-1})\) である。
- また、前のステップの (☆) から \(c(e_{i'+1}) = c(e_{j'})\) である。
- さらに、\(i' < i < j < j'\) より \(e_{i'+1} \neq e_j\) である。
- \(P' \coloneqq (v_0, \ldots, v_{i'}, e' \coloneqq (v_{i'}, v_{j'}), v_{j'}, \ldots, v_{|P|})\) とする。以下の理由により \(P'\) は所望の条件を満たすので、手順を終了する：
- 辺の貼り方から \(e' \in E\) であるから、\(P' \in \mathcal P\) である。
- \(P\) が頂点素なので、\(P'\) は頂点素である。
- \(f(e_{i'+1})\) と \(f(e_{j'})\) のどちらか一方は \(1\) である (※)。
- したがって \(f(e') \leq 1 \leq 1 + 0 \leq f(e_{i'+1}) + f(e_{j'})\) であり、特に \(g(P') \leq g(P)\) である。
- \(s(v_i) = s(v_j)\) よりこのループは \(1\) 回以上回っている。
- もし \(i' = 0\) ならば、
- \(P' \coloneqq (v_{i'}, e_{i'+1}, \ldots, v_{|P|})\) とする。以下の理由により \(P'\) は所望の条件を満たすので、手順を終了する：
- 明らかに \(P' \in \mathcal P\) で \(P'\) は頂点素であり、\(g(P') \leq g(P)\) である。
- \(P' \coloneqq (v_{i'}, e_{i'+1}, \ldots, v_{|P|})\) とする。以下の理由により \(P'\) は所望の条件を満たすので、手順を終了する：
- もし \(j' = |P|\) ならば、
- \(P' \coloneqq (v_0, e_1, \ldots v_{j'})\) とする。以下の理由により \(P'\) は所望の条件を満たすので、手順を終了する：
- 明らかに \(P' \in \mathcal P\) で \(P'\) は頂点素であり、\(g(P') \leq g(P)\) である。
- \(P' \coloneqq (v_0, e_1, \ldots v_{j'})\) とする。以下の理由により \(P'\) は所望の条件を満たすので、手順を終了する：
- さもなければ \(s(v_{i'}) = s(v_{j'})\)。
- このとき、辺の貼り方から \(c(e_{i'}) = c(e_{j'+1})\)。(☆)
- \((i',j') \gets (i'-1, j'+1)\) とする。
- これらはふたたび \(0 \leq i' < j' \leq |P|\) を満たす。
- もし \(s(v_{i'}) \neq s(v_{j'})\) ならば、
(※)について
直感的には、これらの辺は違う色であり、少なくとも一方のコストが \(1\) であることを意味します。
厳密には、\(c(v_{i'+1}) = c(v_{j'-1})\) (\(\eqqcolon C_{y,x}\)) から \(e_{i'+1}, e_{j'} \in E_{C_{y,x}}\) （有限集合）であり、 そのうち \(c(v_{i'+1}) = c(v_{j'-1}), c(v_{i'}) \neq c(v_{j'})\) を満たすものをすべて確認すると \(t(e_{i'+1}) \neq t(e_{j'})\) がわかります。 \(t(e_{i'+1}), t(e_{j'})\) のうち少なくとも一方が（問題文中の \(S\) について）\((S_i)_j\) と異なることから、\(c\) の定義より \(f(e_{i'+1})\) と \(f_(e_{j'})\) のうち一方は \(1\) です。
上記の手順の繰り返しは高々 \(\min(i, |P|-j)\) 回繰り返すので、手順はかならず停止して、所望の \(P'\) が得られる。 ■
コストの最小性から、\(g(P') = g(P)\) である。 パスの長さの有限性から、これを繰り返すことで、(2) を満たす頂点素な \(P \in \mathcal P\) が得られる。 ■
主張3. コスト \(M\) のパス \(P = (v_0, e_1, \ldots, v_{|P|}) \in \mathcal P\) が (1), (2) を満たすなら、以下も満たされる：
- 任意の \(1 \leq i < j \leq |P|\) について、以下が成り立つ： ……(3)
- \(c(e_i) = c(e_j)\) なら \(t(e_i) = t(e_j)\)
直感的には、同じセルを通るときは必ず同じ色の辺を通ること、言い換えれば与えられたパスを達成する鏡の配置が存在することを意味します。
証明
ある \(1 \leq i < j \leq |P|\) に対して \(c(e_i) = c(e_j) (\eqqcolon C_{y,x})\) であるとする。 このとき、\(e_i, e_j \in E_{C_{y,x}}\) （有限集合）であり、 そのうち (2) を満たすものを列挙すると \(t(e_i) = t(e_j)\) がわかる。 ■
元の問題の答えを \(M'\) とします。
主張4. 元の問題で \(M'\) 回の操作で実現できて、目的を達成できる鏡の配置であって、鏡の置き方を変更したセルを光が複数回通らないものが存在する。 ……(4)
証明
元の問題で \(M'\) 回の操作で実現できて、目的を達成できる鏡の配置を一つ取る。 今、鏡の置き方を変更したセルであって、光が複数回通るものが存在するとする。 そのようなセルを一つ取る。そのセルの周を構成する \(4\) つの線分のうち、最初に光が通るものを \(z_1\)、最後に光が通るものを \(z_2\) とする。 すると、\(z_1 \neq z_2\) であるから(※)、\(z_1\) から入射した光が \(z_2\) に出射するように鏡の置き方を変更できる。 このとき、必要な操作の回数は増加しないが、鏡の置き方を変更したセルであって、光が複数回通らないものの個数は \(1\) 減少する。 そのようなセルの個数の有限性から、この手順を繰り返すことで求める鏡の配置が得られる。 ■
最後に、\(M\) が元の問題の答え \(M'\) と一致することを示します。
- コスト \(M\) のパス \(P \in \mathcal P\) であって (1), (2) を満たすものを一つ取ります。 \(P\) が (3) を満たすことから、\(P\) に対応する光路を達成する鏡の配置が存在します。 このとき、\(g(P)\) はこの鏡の配置を実現するために鏡の置き方を変更したセルを光が通る回数に一致し、特に鏡の置き方を変更したセルの個数以上です。 元の問題の答えはこのセルの個数以下であることから、\(M' \leq g(P) = M\) が分かります。
- 逆に、(4) を用いて、元の問題で \(M'\) 回の操作で実現できて、目的を達成できる鏡の配置であって、鏡の置き方を変更したセルを光が複数回通らないものを一つとります。 このとき、光が鏡の置き方を変更したセルを通る回数は \(M'\) に一致しています。 一方、このときの光路に対応する \(G\) 上のパス \(P \in \mathcal P\) を考えると、\(g(P)\) は光が鏡の置き方を変更したセルを通る回数に一致しています。 したがって、\(M \leq g(P) = M'\) が分かります。
以上より \(M = M'\)、すなわち公式解説で定義されたグラフ上での最短距離が元の問題の答えに一致することが示されました。
posted:
last update: