こんにちは、yesです。
突然ですが、皆さんは「問題文にグラフとは書いてないけど実はグラフで解ける」問題に遭遇したことがありますか？私はあります。
このような問題はad-hoc感が強くてどう思いつけばいいか分からなくなりがちなので、今回は3パターンに分けて紹介していこうと思います。
①順序関係を有向辺として捉える
とりあえずこの問題について考えてみましょう。
あなたの運営するWebサービスには$N$人のユーザがいます。
$i$番目のユーザの現在のユーザ名は$S_i$ですが、$T_i$への変更を希望しています。
ここで、$S_1,...,S_N$は相異なり、$T_1,...,T_N$も相異なります。
ユーザ名を変更する順序を適切に定めることで、以下の条件を全て満たすように、全てのユーザのユーザ名を希望通り変更することができるか判定してください。
- ユーザ名の変更は$1$人ずつ行う
- どのユーザもユーザ名の変更は一度だけ行う
- ユーザ名の変更を試みる時点で他のユーザが使っているユーザ名に変更することはできない
この問題において重要なのは、どういう状況で詰むかを考えることです。
詰む状況というのは、具体的には
-
taroからhanakoに変えたい人 -
hanakoからtaroに変えたい人
が同時にいる場合などが考えられます。デッドロックみたいな感じですね。
ここで、ユーザに希望する名前の変更を$S_i$から$T_i$に伸びる有向辺として解釈してみます。($T_i$がどの$S_j$と被ってなかったら$S_i$を変えることができる、というイメージです)
すると、上の状況はtaroとhanakoで有向サイクルが出来ていると考えることが出来ます。
逆に有向サイクルが出来ていない場合詰まないか？ということを考えると、以下の手順を繰り返すことで全てのユーザの希望通りユーザ名を変更出来ます。
- 出次数が0の頂点を選択する
- その頂点とその頂点から伸びる辺を削除する
実は、この手順がトポロジカルソートの逆順になっています。
どうしたら思いつけるか？
このような2つの間で順序関係がある場合は有向グラフとして捉えてみると良いと思います。
例えば「$A$より先に$B$を終わらせる必要がある」「$A \leq B$」みたいなやつです。
こう考えると大抵有向サイクルで詰んだり場合分けが必要になってきます。
なので、この類の問題はトポロジカルソートだったり強連結成分分解で上手く行くことが多いと思います。
類題
- ABC223D - Restricted Permutation
- ABC216D - Pair of Balls
- ABC291E - Find Permutation
- ABC387F - Count Arrays
②制約を辺として考える
これだけ見ると何を言ってるのかさっぱりだと思うので、この問題について考えてみます。
$N$枚のカードが一列に伏せられており、各カードには整数$1$または$2$が書かれています。
$i$番目のカードに書かれている整数を$A_i$とします。
あなたの目的は$A_1,A_2,...,A_N$を当てることです。
次のことが分かっています。
- $i = 1,2,...,M$について$A_{X_i}+A_{Y_i}+Z_i$は偶数である。
あなたは魔法使いです。次の魔法を何度でも使うことができます。
魔法: コストを$1$払う。カードを$1$枚選び、そのカードに書かれた整数$A_i$を知る。
最小で何コスト払えば、$A_1,A_2,...,A_N$全てを確実に当てることができるでしょうか。
なお、与えられる入力には矛盾がないことが保証されます。
この問題を初めて見て「本当にグラフの問題…？」という方も少なくないと思います。
この問題の制約として重要な部分は
$i = 1,2,...,M$について$A_{X_i}+A_{Y_i}+Z_i$は偶数である。
の部分です。これを式として置き換えると
$A_{X_i}+A_{Y_i}+Z_i \equiv 0\pmod 2 (1 \leq i \leq M)$
ということになります。この条件の何が嬉しいかというと、$A_{X_i}$または$A_{Y_i}$が分かればもう片方の値が確定するという点にあります。(これは実際に代入するとわかりやすいです)
ここで、$A_1$と$A_2$の間の条件と$A_2$と$A_3$の間の条件が分かっているとしてみます。すると$A_1,A_2,A_3$のうちいずれか1つが分かれば全ての値が確定するということが分かります。
そこで、この条件式を$A_{X_i}$と$A_{Y_i}$に辺を貼るとして考えると、同じ連結成分内の頂点の値が1つ分かればその連結成分に属する頂点は全て値を確定出来るので、答えは連結成分の数ということになります。
どうしたら思いつけるか？
この類の問題としてあるあるなのは
- 何かしらの条件式がいっぱい与えられる
- 式に2つのまだ良く分かっていない値がある
- 2つの値のうち1つが確定すれば、もう片方が自動的に確定する
というところでしょうか。この場合頂点を変数、辺を2つの間の制約として考えれば連結成分内で情報が広がると捉えられます。
類題
- ABC238E - Range Sums
- ABC087D - People on a Line
- 競プロ典型90問068 - Paired Information (★5)
- ABC328F - Good Set Query
③選択を辺にする
これが一番難しいタイプだと思います。一旦この問題について考えてみましょう。
$1$から$N$の番号がついた$N$枚のカードがあり、各カードの両面には正整数で表される色がついています。
カード$i$の片面の色は$a_i$,もう片面の色は$b_i$です。
各カードについてどちらの面を表にするか自由に選べるとき、表側に見える色の種類数の最大値はいくつになるか求めてください。
この問題がグラフへ帰着することに驚いた方が多いのではないでしょうか。僕もその一人です。
ではどうやってグラフに直して解くのかというと、
- カードを辺として捉える
- 色を頂点として捉える
- 表にする面を選ぶことを片方の頂点を光らせると定義し直す
と考えてみます。すると、色の種類数の最大値は光らせる頂点の最大数と考えることが出来ます。
問題文の言い換えは出来たのでこの問題をどう解くか考えていきましょう。
まずある2頂点の連結成分が異なる場合、お互いに影響し合わないことが分かると思います。なのである連結成分1つについて考えます。
辺1本につき光る頂点は最大1増えるので、とりあえず辺が一番少ない場合、つまり連結成分が木である時を考えます。連結成分内の頂点数を$X$とすると、木であるならば辺の数は$X-1$本なので光る頂点の上限は$X-1$です。ここでこの種類数の上限を達成出来るかを考えると、適当な頂点を根と置いて根から遠い方を光らせることで達成できることが分かります。
木の場合は考えたので木以外の場合を考えると、サイクル上のある一点を根とした全域木を取って、使われなかった辺で根を光らせると頂点を$X$個光らせることが出来ます。
よって、Union-Findで連結成分を分けた後各連結成分が木であるかを判定すればAC出来ます。(実装する時は各連結成分の辺の数を数えると楽です)
ここまで聞いて、自力で思いつけるの…？と思う人が多いと思います。というか僕もその一人です。
どうしたら思いつけるか？
問題の条件として各要素が高々2択のものがいっぱい出てくるときに疑うと良いと思います。「各要素が$X,Y$のどちらかを選ぶ」みたいなやつですね。
あとは問題文の条件を上手く言い換えられるか？を考えれば上手く実装に落とし込める問題も多いと思います。
類題
- ABC434E - Distribute Bunnies
- ABC436E - Minimum Swap
- ABC282E - Choose Two and Eat One
- ABC247F - Cards
まとめ
今回の内容をまとめると、
- とある2つのものが何かしらの関係(二項関係)を持っていたらグラフを疑う
- 順序関係があるなら有向グラフとしてみる
- 制約なら連結成分ごとに考える
- 2択の選択が続くなら辺として置けないか考えてみる
という感じです。すごく主観が強い記事になってしまいましたが、良ければ参考にしてください。