私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「うそつきがいる」（CodeIQ）を参照してください。
【概要】
こういう問題があります：
本当のことしか言わない「キュラ族」と、嘘しか言わない「ラゲ族」がいます。
A〜D は、「キュラ族」または「ラゲ族」のいずれかであることがわかっています。
A〜D の4人からこんな話を聞くことが出来ました：
A 「A、B、C のうち、キュラ族は2人だよ。」
B 「B、C、D のうち、キュラ族は0人だよ。」
C 「B、D のうち、キュラ族は1人だよ。」
D 「A、B のうち、キュラ族は0人だよ。」
A〜D のうち、キュラ族である人をすべて挙げてください。
これを、コンピュータで解くために以下のように記述します。
A:ABC2,B:BCD0,C:BD1,D:AB0例えば『C 「B、D のうち、キュラ族は1人だよ。」』は、「C:BD1」に対応しています。
A:ABC2,B:BCD0,C:BD1,D:AB0のような入力を与えますので、この問題を解くプログラムを書いてください。
【入出力】
前述のとおり、入力は
A:ABC2,B:BCD0,C:BD1,D:AB0
のような感じです。
出力は、
CD
のように、キュラ族の人をアルファベット順に区切り文字なしですべて出力してください。
ただし：
キュラ族がひとりもいない場合には、-を出力してください。
解がない場合にはnoneを出力してください。
解が複数ある場合にはmanyを出力してください。
※末尾の改行はあってもなくても構いません。
【例】
入力 出力 A:ABC2,B:BCD0,C:BD1,D:AB0 CD A:A0 none Z:Z1 many Z:ZA1,A:Z1 -
【補足】
登場人物の名前は、アルファベットの大文字一文字です。
登場人物が 15人以上になることはありません。
各自かならず一度しゃべります。二度以上しゃべることはありません。
不正な入力に対処する必要はありません。
Rubyで解答しています。
#!/usr/bin/ruby
$Member = [] # メンバーリスト
$Pattern = [] # 仮説リスト
$Comments = [] # メンバーの発言
$Results = [] # 結果
class Comment
attr_reader :num, :kyura
def initialize(say, member)
md = say.match(/([a-zA-Z]+)(\d+)/)
@num = md[2].to_i
splited = md[1].split("")
@kyura = 0
member.each_with_index{|who, i|
if splited.include?(who) then
@kyura |= 1 << i
end
}
end
# ビットが1の数を数える
def countBit(v)
return v.to_s(2).count('1')
end
# patternの仮説に対し、発言が真になるか偽になるかをチェックする。
# modeは発言が本当（1）か嘘（0）かを示す。
def check(pattern, mode)
c = countBit(@kyura & pattern)
if mode == 1 then
return c == @num
else
return c != @num
end
end
# DEBUG
def print()
printf("%016b,%d\n", @kyura, @num)
end
end
# 結果を求める
def checkPattern()
for ptn in $Pattern
ret = false
for i in 0...$Member.size
mode = (ptn >> i) & 1
ret = $Comments[i].check(ptn, mode)
if !ret then break end
end
if ret then $Results << ptn end
end
end
# DEBUG
def printResults()
puts "----- Results -----"
for v in $Results
printf("%016b\n", v)
end
end
# 仮説を列挙する
def makePattern()
pattern = [0]
for i in 0...$Member.size
npattern = []
for v in pattern
npattern << (v | 1 << i)
npattern << (v | 0 << i)
end
pattern = npattern
end
$Pattern = pattern
end
# DEBUG
def printPattern()
puts "----- Pattern -----"
for v in $Pattern
printf("%016b\n", v)
end
end
# 入力値をパースする
def parse(line)
splited = line.split(",")
slist = []
for s in splited
name, say = s.split(":")
$Member << name
slist << say
end
for s in slist
c = Comment.new(s, $Member)
# c.print()
$Comments << c
end
end
# 答えを表示する
def printAnswer()
if $Results.size == 0 then
puts "none"
elsif $Results.size > 1 then
puts "many"
elsif ($Results.size) == 1 && ($Results[0] == 0) then
puts "-"
else
kyura = []
$Member.each_with_index{|who, i|
if ($Results[0] >> i) & 1 == 0 then next end
kyura << who
}
puts kyura.sort.join
end
end
#main
while line = gets
line.strip!
if line.empty? then next end
parse(line)
makePattern()
# printPattern()
checkPattern()
# printResults()
printAnswer()
end
論理クイズによくある感じの問題です。が、★★★★だけあって難しいです。プログラムが難しいと言うより（実際、コードはわかりやすいと思います）、コードを書くところまでたどり着くのが遠いです。
実際は入力値などをどう表現するかでいろいろ考えたのですが、長くなるので最終的なコードの説明だけにします。
基本的な考え方は「仮説を列挙し、すべての仮説に対して発言が無矛盾である事をチェックする」です。
ここでいう仮説とは誰が本当の事を言っていて（＝キュラ族）、誰が嘘をついているか（＝ラゲ族）と言う事で、例えば例のA〜Dの場合、A（嘘）、B（本当）、C（本当）、D（本当）と言う仮説を立ててチェックするという事です。
この場合、
A（嘘）→「A、B、C のうち、キュラ族は2人ではない」→仮説ではBCがキュラ族なので正しい。
B（本当）→「B、C、D のうち、キュラ族は0人」→仮説ではBCがキュラ族なので町違い。
C（本当）→「B、D のうち、キュラ族は1人」→BDの両方がキュラ族なので間違い。
D（本当）→「A、B のうち、キュラ族は0人」→Bはキュラ族なので間違い。
よってA（嘘）、B（本当）、C（本当）、D（本当）と言う仮説は間違い、と言う具合です。
次にポイントとなるのは発言を嘘とした場合、どう表現するかです。先の例で書いてしまいましたが「A、B、C のうち、キュラ族は2人」を嘘と見做した場合、「A、B、C のうち、キュラ族は2人ではない」と表現する必要があります。
「A、B、C のうち、キュラ族は0、1、3人のいずれか」とも表現できますが、この方向で考えるとプログラムの計算量が大変な事になってしまいます。
そして、チェックは（おそらく）ビット演算にする必要があります。
仮説の数をチェックする場合の計算量をざっと見積もるとO(n×2n)です（nは人数）。n=14が最大なので229376回のチェックが発生します。これだけの回数の計算を例えば真偽値の配列などで行うと計算量が相当増えてしまうので、パラメータはビットフラグで表現する必要があります。
それではコードを解説します。
登場人物の発言を保持するクラスです。
メンバ変数は@numと@kyuraで次の通りの意味です。
@num：ABC2の2の部分です。
@kyura：キュラ族と言われた登場人物のビット位置を1、それ以外を0としたものです。ABC2なら0b0000000000000111です。最下位ビットが最初の登場人物（この場合A）になります。
コンストラクタでは登場人物の発言部分だけをパースして誰々のうち何人がキュラ族かを保持します。
引数sayは登場人物の発言部分だけを取り出したもの、memberは登場人物全員の名前が入った配列（例の場合だと['A','B','C','D']）です。memberが必要なのは入力値の登場人物の並び順の保証がないため（例えばB:AZ1,A:B0,Z:Z1,E:ABEZ:2のような入力は許される）です。ビット位置が誰を指すのかを一致させるために必要です。
@numは発言から数字部分を取り出して数値に変換して保持すれば済みます。
@kyuraはmemberを順に要素番号付きで取り出し、発言内に登場していれば要素番号分だけ左にビットシフトして論理和をとることで作成できます。
例えばmemberが['A','B','C','D']で発言が"ABC2"の場合、@num=2、Aは0b0000000000000001、Bは0b0000000000000010、Cは0b0000000000000100になるので、これらの論理和を取れば@kyura=0b0000000000000111となって発言内容を数値に変換できるというわけです。
仮説が自分の発言と無矛盾かをチェックする関数です。
引数patternは仮説のうち一つ、modeは発言を本当とみなす（true）か嘘とみなす（false）かを表します。
仮説も発言もビットフラグで表現されているのでこれらの論理積をとり、1が立っているビットの数が発言と一致しているかをチェックすれば矛盾しているかしていないかをチェックできます。矛盾している場合はfalse、矛盾していない場合はtrueを返します。
例えば仮説「A（嘘）、B（本当）、C（本当）、D（本当）と言う仮説」は0b0000000000001110で、これをDの発言「B、D のうち、キュラ族は1人」（={@kyura=0b0000000000001010, @num=1}）とチェックすると0b0000000000001110&0b0000000000001010=0b0000000000001010でビットの数は2であり@numと不一致なので矛盾しているとなりfalseを返します。
Aの発言（{@kyura=0b0000000000000111, @num=2}）はこの仮説では嘘とみなしているので、仮説0b0000000000001110との論理積は0b0000000000000110となり、ビットの数は2になります。しかし、Aの発言は嘘なのでビットの数が2であってはならないので、このチェック結果はfalseになります。
入力値をパースしてメンバのリスト$Memberと各メンバの発言$Commentsを作成します。この2つの配列の順番は一致するようにしなければなりません。また、先に説明したCommentクラスのインスタンスを作成する際にメンバの並び順が必要なので、一旦$Memberを確定してから$Commentsを作成するようにしています。
$Commentsの各要素はCommentクラスのインスタンスで先に説明した通りコンストラクタでパースします。
全てのメンバに対しそれぞれが嘘と本当を言ったとした場合の全ての組み合わせを列挙します。動的計画法で作っていますが、再帰の方が簡単かもしれません。
まず、pattern=[0]を初期値として$Memberだけループします。
$Member=['A','B','C','D']とすると、1回目のループ（Aの時）で次の2つの値が作れれます。
0b0000000000000001 = 0b0000000000000000 | (1 << 0)
0b0000000000000000 = 0b0000000000000000 | (0 << 0)
これをあたたなpatternとしてpatternの値に2回目の値を適用します。
0b0000000000000011 = 0b0000000000000001 | (1 << 1)
0b0000000000000001 = 0b0000000000000001 | (0 << 1)
0b0000000000000010 = 0b0000000000000000 | (1 << 1)
0b0000000000000000 = 0b0000000000000000 | (0 << 0)
同じように3回目、4回目のループを行えば全ての仮説パターンを列挙できます。
76行目の0をビットシフトして加える処理は不要（何もせず同じ値を追加すれば良い）ですが、コードが対称的になってわかりやすいのでわざわざ書いています。
最後に$Patternに全仮説パターンを保持します。
$Patternの全てに対し、$Commentsが無矛盾かをチェックします。
$Patternから仮説を一つずつ取り出し、$Memberの並び順で$Commentとチェックします。この時、取り出した$Patternの要素（ptn）をメンバの要素番号だけ右シフトし0b0000000000000001でマスクした値がチェック対象の仮説において当該メンバの発言が嘘（0）か本当（1）かを示します（51行目）。
あとは当該メンバの発言にptn（仮説）とmode（仮説において嘘か本当か）を与えてComment#check()を適用し、矛盾しているか(false)、矛盾していないか(true)の結果を得ます。
仮説が正しい場合というのは全ての発言が無矛盾である場合なので、その仮説において1件でも矛盾している発言があればその仮説は間違いになります。なのでComment#check()がfalseを返した時点で処理を打ち切って問題ありません。
最終的に全てのメンバの発言が無矛盾であった仮説だけを$Resultsに保持します。
なお、$Resultsの要素数が2以上になった場合、仕様上manyと出力するだけなので関数を抜けて構わない（計算量を節約できる）のですが、noneの場合は最後まで計算しなければわからないので最悪の計算量の場合には影響しません。なので、$Resultsの要素数が2以上になっても処理を続けています。
結果出力を整形して出力します。
$Resultsの要素数が0（つまり、全ての発言が全ての仮説に対して矛盾していた）の場合はnoneです。
$Resultsの要素数が2以上ならmanyです。
$Resultsの要素数が1でその値が0（つまり全発言を嘘とした場合だけが残った）の場合は全員が嘘をついた＝キュラ族がいない場合なので-です。
それ以外はキュラ族が確定しています。入力をパースした時点で作った$Memberの並び順はアルファベット順になっていないかもしれないので整形して出力します（119〜125行目）。
問題自体は分かりやすく、面白い、良問と思いますが難しかったです。最初に書いた通り、プログラムにする前の段階が難解でした。ビット演算にしないとだめだろうな、ということは最初から思ってはいましたが、仮説や発言を変数としてどう表現するのか、同時に計算量をなるべく少なくするためにはどうするのかを考えるのに苦労しました。
方針が定まってからプログラムにするのには苦労しませんでした。コード自体も見通しが良いものになったと思います（ビット演算にそこそこ馴染んでいれば）。実際は仮説パターンの列挙とチェックを同時にできるのでもう少し効率化できますが、私のコードのように段階をわけたほうがデバッグしやすい意味があるので無理に効率化しなくても良いかなぁと思います。
ちなみに、この問題の出題者の問題はビットフラグを活用する問題が多いような気がします。