Plugs(プラグ) - joi2010-day4 解説

筆者: qnighy

与えられた条件に基づき、n個とn個の間に唯一存在する正しいマッチングを見つける問題である。

条件の整理

与えられた条件は使いにくい形で提供されている。これを使いやすい形(隣接行列)に直す必要がある。

ここでは、この隣接行列を、「aとbの関係は何個の証言によって否定されるか」という表現だとする。

いきなり行列を埋めるとコストがかかるので、端っこにマークをつけてから、総和を計算するという方法を用いる。

[A,B)と[C,D)の間に証言が存在するとき、座標(A,C)と(B,D)に1を足し、(A,D)と(B,C)から1を引く。すると1つ1つの証言は以下の形になる。

これを縦と横に一回ずつ総和にすると、以下のような形になる。

総和計算は最後に一回だけ行えばいいので、O(M+N^2)で計算できる。

推論

問題文中で「これらの証言によって解が唯一に定まる」と指定されているのは、実は重要なヒントである。

実はこの唯一性が保証されている限り、簡単な貪欲法によって解を定めることができることがわかる。(証明は省略する。)

そこで、「プラグかソケットで、対応するソケットかプラグが一意に定まるものがあれば、その組を決定する。」という操作を繰り返すことで、答えを得る。

ただし、それぞれのプラグとソケットについて、対応しうるプラグとソケットの個数を予め計算するなどとして、どの箇所も計算量がO(N^2)をオーバーしないように気をつける。

この方法によってO(M+N^2)で解を得ることができ、満点を獲得できる。