[1] 問題の一般化

以下のように一般化された問題の解法を考えます。

長さ \(N\) の整数列 \(X=(X_1,X_2,\dots,X_N)\) であって、\(M\) 個の条件を満たすものが存在するか判定してください。

\(i\) 番目の条件は長さ \(n\) の整数列 \(p=(p_1,p_2,\dots,p_n)\) および長さ \(m\) の整数列 \(q=(q_1,q_2,\dots,q_m)\) を用いて表され、

• 整数列 \((X_{p_1},X_{p_2},\dots,X_{p_n})\) は整数列 \((X_{q_1},X_{q_2},\dots,X_{q_m})\) より辞書式順序で小さい

という条件です。

もとの問題は \(p=(A_i,A_i+1,\dots,B_i)\) 、 \(q=(C_i,C_i+1,\dots,D_i)\) という特殊ケースです。

[2] \(1\) 文字目の比較への着目

各条件について、 \(p_1=q_1\) ならば \(p,q\) を \((p_2,p_3,\dots,p_n),(q_2,q_3,\dots,q_m)\) に置き換えていいです。これを繰り返して \(q\) が空になった場合、その条件は明らかに満たすことができないので答えは No とわかります。また、\(p\) が空になった場合、条件は必ず満たされるので無視していいです。以降各条件について \(p_1\neq q_1\) を仮定します。

まず各条件について \(X_{p_1} \leq X_{q_1}\) が必要です。

ここで \(N\) 頂点の有向グラフであって、各条件について頂点 \(p_1\) から \(q_1\) に辺を張ったグラフを考えます。

[2-1] 有向グラフが閉路を持たない場合

この場合、頂点のトポロジカル順序にしたがって \(X_i\) を定めることで \(X_{p_1} < X_{q_1}\) が成り立つようにすることができます。そのように \(X\) を定めると \(M\) 個の条件がすべて成り立っているので、答えは Yes だとわかります。

[2-2] 有向グラフが閉路を持つ場合

つづいて有向グラフが閉路を持つ場合について考えます。グラフにおいて同一の強連結成分に属する \(2\) 頂点 \(u,v\) に対しては \(X_u=X_v\) が必要と分かります。

すると各条件に登場する \(X_{p_i}\) について、\(p_i\) を \(p_i\) と同じ強連結成分に属する頂点のラベル \(v\) の最小値で置き換えてよく、これにより等号に関する条件をすべて考慮できています（最小値であることに特に意味はなく、同じ強連結成分に属する頂点の番号がすべて同じ番号に書き換わっていればなんでもいいです）。また、 条件の \(p_i,q_i\) に登場する整数の種類数は元の問題より小さくなっています（閉路が存在するので）。

以上より有向グラフが閉路を持つ場合、元の問題を変数 \(X_i\) の数が減った同じ形式の問題に帰着することができます。

[3] まとめ

[2] での考察をまとめると、[1] で考えた問題は以下のようなアルゴリズムによって解くことができます。

1. 各条件について、\(p_1=q_1\) ならば \(p_1,q_1\) を削除する。これにより \(q\) が空になった場合は No を出力する。\(p\) が空になった場合は条件を取り除く

2. 各条件について、頂点 \(p_1\) から \(q_1\) へ向かう辺を張った有向グラフを考える。グラフが閉路を持たない場合、 Yes を出力する。グラフが閉路を持つ場合、各強連結成分について、強連結成分に属する頂点のラベルの最小値を \(v_{min}\) とし、条件内の \(p_i,q_i\) を \(v_{min}\) で置き換える。その後 \(1\) に戻る

このアルゴリズムの計算量を考えます。まず 2 での計算について、強連結成分分解が必要ですがこれは \(O(N+M)\) で行うことができます。つづいて \(2\) が行われる回数について考えます。\(2\) から \(1\) に戻る際、条件に登場する \(p_i,q_i\) の種類数は小さくなっており、初期値は \(N\) 以下であるため、 \(2\) が行われる回数は \(O(N)\) 回です。

以上よりこのアルゴリズムは \(O(N(N+M))\) で動作し、十分高速です。