ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 2002 - X-Ray Screening System

問題
解法

解法

まずは、それぞれの文字が、隠れている部分を含めて長方形になり得るかを調べます。そして、その後で、重なっている部分が矛盾していないかどうかのチェックをします。

ということで、まずは長方形になりうるかどうかのチェックをします。いま、文字Sについて調べているとするとき、まずはすべてのマスの中で、文字Sが存在する、上端、下端、左端、右端を洗い出します(それぞれu,d,l,rとします)。
その後、(u,l),(u,r),(d,l),(d,r)の4つのマス目で結ばれた長方形のマス目全てについて、.かどうかを調べます。もし、.が存在していたら、その時点でSの品物が長方形になることはないので、答えは"SUSPICIOUS"です。
また、この時に、S以外の文字Xが存在していたら、そのXの品物は、SよりもX座標が近いことになります。これをメモしておきます。

続いて、重なっている部分の矛盾を洗い出します。
サンプルケースの4つめのように、ABより手前、BCより手前、CDより手前、DAより手前に存在していなければならず、これらを全て同時に満たすことはないので、このケースは"SUSPICIOUS"になります。このようなパターンを探し出します。
まず、品物は最大で7種類なので、その7種類について、手前からどのようにならんでいるか、のパターンを全て探索するには、7!パターン探す必要があります。そして、どの文字の品物が、どの文字の品物よりも手前に存在しているべきか、というのは、先ほどのメモを利用すればO(1)で調べることができます。
よって、全ての順列に対し、任意の2つの文字について、x座標で矛盾が生じていないかどうかを調べるのは、おおよそ7! \times \  _{7}C_{2}回ほど計算すればよく、これは十分高速です。
ということで、next_permutationを利用しつつ、矛盾がないような順列が存在するかどうかを調べ、1つでも存在していれば答えは"SAFE"、していなければ答えは"SUSPICIOUS"になります。

感想

サンプル4のコーナーケースが、はじめは何故"SUSPICIOUS"なのかを理解するのに時間がかかりましたが、やるべきこと自体はすぐに思いつくことができ、バグも少なかったので良かったかと思います。