3108 Horn Clauses

概要

ホーン節とは，(n1&n2&... => p) という形をした論理式．(niもpも否定がつかない)
ホーン節の論理積が与えられ，それを充足するような真理値割り当てを求める．
式の長さは，20000文字以内．

解法

構文解析をして，ホーン節の集合を求める．
右辺に変数を持つものIと，持たないものNに分ける．
まず，はじめは，すべての変数の割り当てをfalseとする．
つぎに，Iの中で，充足されていない節を発見したら，右辺の変数の割り当てをtrueにする，という操作を，操作できなくなるまで行う．
さいごに，Nのすべての節が，充足されているか確かる．

計算量は，O(I^2 + N) + 構文解析のコストくらい
この問題は，変数の長さが1000文字以上になることがあって，そのせいでハマった．
文字列にユニーク整数を割り当てて変数を表現するために，文字列から一旦配列に切り出していたが，
その配列がchar [1024]だったので添字範囲外アクセスでREになるという見つけにくいバグを埋め込んでしまった．