【ruby】rubyで2進数を扱う

Ruby

AtCorer Beginner Contest 147 C問題

毎度おなじみAtCorder Beginner Contest C問題でつまづいた。
解き方含めて学んだことをメモしておく。

問題のポイント

今回の問題では、正直者を1, 嘘つきを0で表記していく。
例えば3人が順に
[正直者, 嘘つき, 正直者] = [1, 0, 1]
[正直者, 嘘つき, 嘘つき] = [1, 0, 0]
といった形になる。
正直者と嘘つきの組み合わせは 2 ** 3で8通りあるわけだが、どうやって表記するかがポイントとなる。
ここで、eachメソッドとtimesメソッドを使うと一気に楽になる。

eachとtimesで2進数表記

3人の時は2 ** 3通り考えるのでn人の時はコレで８回繰り返せる。

(0..2 ** n - 1).each do |k|
  puts k
  # 表示されるのは0 ~ 7
end

コレを2進数化するにはtimesを使ってやる。

n = 3
(0..2 ** n - 1).each do |k|
  n.times do |j|
    # 数字kを2進数表記した時、n桁の数列のj番目の数字
    puts k[j]
  end
end
# 結果出てくるのはこんな数字
# 0 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1
# 3つずつくくるとこんな感じに2進数に変換される
# [0 0 0][1 0 0][0 1 0][1 1 0][0 0 1][1 0 1][0 1 1][1 1 1]

解き方

とりあえず、入力する内容を受け取る準備をしておく。

n = gets.to_i
# 全員が言ったことをまとめるsays配列を作成
says = Array.new
n.times do
  i = gets.to_i
  # 各人が言ったとをまとめるwords配列を作成
  words = Array.new
  i.times do
    person, truth = gets.split.map(&:to_i)
    words << [person - 1, truth]
  end
  says << words
end

続いて、先ほどの2進数の考え方を使ってそれぞれのパターンで成立するかどうかを確認していく。

(0..2 ** n - 1).each do |mask|
  # まずは組み合わせが正しいと仮定しておく
  success = true
  n.times do |k|
    # 0は嘘つきなので評価せず次に飛ばす
    next if mask[k] == 0
    # j番目の人が言っていることをピックアップ
    words = says[k]
    words.each do |person, truth|
      # mask[k]=1なので、wordsのtruthが正しくなければ仮定をsuccess = falseとする
    if truth == 1
      success = mask[person] == 0 ? false : true
    else
      success = mask[person] == 1 ? false : true
    end
    # success = falseならそのあと調べる必要がない
    break unless success
  end
end

コレでどの組み合わせが成立しているかがわかるので、最後に一番正直者が多い組み合わせを調べる。
普通の数字を2進数表記に変えるにはto_s(2)を使ってやれば良い。

ans = 0
(0..2 ** n - 1).each do |mask|
  success = true
  n.times do |k|
    next if mask[k] == 0
    words = says[k]
    words.each do |person, truth|
    if truth == 1
      success = mask[person] == 0 ? false : true
    else
      success = mask[person] == 1 ? false : true
    end
    break unless success
  end
  if success
    # 成立していたら、2進数化して1の数を数えて、大きい方をansに置き換える。
    ans = [ans, mask.to_s(2).count('1')].max
  end
end

まとめ

今までrubyの問題で2進数を使った事がなかったのでがっつり引っかかってしまった。
プロコンだとよく使う手法のようなので、覚えておいて損はないはず。