AOJ 2002 - X-Ray Screening System
解法
まずは、それぞれの文字が、隠れている部分を含めて長方形になり得るかを調べます。そして、その後で、重なっている部分が矛盾していないかどうかのチェックをします。
ということで、まずは長方形になりうるかどうかのチェックをします。いま、文字について調べているとするとき、まずはすべてのマスの中で、文字が存在する、上端、下端、左端、右端を洗い出します(それぞれとします)。
その後、の4つのマス目で結ばれた長方形のマス目全てについて、.
かどうかを調べます。もし、.
が存在していたら、その時点での品物が長方形になることはないので、答えは"SUSPICIOUS"です。
また、この時に、以外の文字が存在していたら、そのの品物は、よりも座標が近いことになります。これをメモしておきます。
続いて、重なっている部分の矛盾を洗い出します。
サンプルケースの4つめのように、はより手前、はより手前、はより手前、はより手前に存在していなければならず、これらを全て同時に満たすことはないので、このケースは"SUSPICIOUS"になります。このようなパターンを探し出します。
まず、品物は最大で7種類なので、その7種類について、手前からどのようにならんでいるか、のパターンを全て探索するには、パターン探す必要があります。そして、どの文字の品物が、どの文字の品物よりも手前に存在しているべきか、というのは、先ほどのメモを利用すればで調べることができます。
よって、全ての順列に対し、任意の2つの文字について、x座標で矛盾が生じていないかどうかを調べるのは、おおよそ回ほど計算すればよく、これは十分高速です。
ということで、next_permutationを利用しつつ、矛盾がないような順列が存在するかどうかを調べ、1つでも存在していれば答えは"SAFE"、していなければ答えは"SUSPICIOUS"になります。
感想
サンプル4のコーナーケースが、はじめは何故"SUSPICIOUS"なのかを理解するのに時間がかかりましたが、やるべきこと自体はすぐに思いつくことができ、バグも少なかったので良かったかと思います。