SRM386 Div2 500

とぷこだ 過去問

問題

データベースのtableが与えられる。
superkeyとは、すべてのエントリがそれで一意に決められるような、tableの属性の集合を指す。
candidate superkeyとは、その部分集合が他のsuperkeyを形成しないようなsuperkeyを指す。
tableの中で、candidate superkeyの属性数が最小、最大のもののその属性数を返す。

考え方

属性数は最大でも10なので、その属性を使うかどうかのすべての組み合わせを試して、superkeyであるような集合を見つける。
次に、superkeyの集合の中からcandidateなものだけを残したいので、あるsuperkeyについて他のsuperkeyの部分集合かどうかを調べ、部分集合である場合取り除く。
最後に、candidateなsuperkeyの中で属性数の最大なものと最小なものを返す。
superkeyかどうかの判定は、その属性の組み合わせがすべてのエントリが一意に定まるかをチェックすればいい。



集合はbit演算を用いるとよい。

反省

bit演算で、s1がs2の部分集合かどうかを判定する時、if(s2&s1==s1)と書いてハマった。
演算子の優先順位からif( (s2&s1)==s1 )としなければならない。