アルゴリズム忘備録

競技プログラミングとかデータ分析とか

E: Jigsaw - AtCoder Grand Contest 017

agc017.contest.atcoder.jp

 

+字型の図形の情報が幾つか与えられる(正確な定義は問題文参照)。この図形を下辺が地面にピッタリ付くように並べていく。例えば┴みたいなのは延々と並べていける。与えられた図形をすべて用いてそのように並べることは可能か?

 

まず分かることは+と┴みたいなのは交互に来る必要があることがわかる。そこで、+の左の高さ(問題文でいうC)と┴の右の高さ(問題文でいうA)などが一致する、ということをグラフで表現する。高さと上に来る or 下に来るということを頂点として表し、n+ またはn-という頂点を作る。図形はそれぞれの形状に応じてとm±を結ぶエッジになる。また、下に来る頂点同士は常に接続可能なので連結にしておく。(図形でいうと┴を並べることに相当する) これらのことをUnionFindで確認し、全体が連結でない場合は不可能と判定する。

 

また、全体が連結であった場合でもある頂点に対して、右から接続する図形と左から接続する図形の数が合わない場合は不可能である。ただこの場合どちらかは┴型の図形なので、この図形よりも+型の図形の方が少ない、という判定のみでよい。

 

以上の条件ですべてNGと判定されなかった場合は可能と返す。O(N) (UnionFindを定数関数をみなすとだが)。

 

要は与えられた有向グラフがEulerグラフになっているかどうかの判定なんだとおもうけど、一般的なアルゴリズムでは計算量が間に合わない。そこで上のような方法を取る。