Ruby と Perl と Java で解く AtCoder ABC 128 C

# はじめに
*[AtCoder Problems](https://kenkoooo.com/atcoder/#/)* の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。
# 今回のお題
*[AtCoder Beginner Contest 128 C - Switches](https://atcoder.jp/contests/abc128/tasks/abc128_c)*
<font color="green">Difficulty: 807</font>

今回のテーマは、ビット演算
# Ruby
```ruby.rb
n, m = gets.split.map(&:to_i)
k = []
1.upto(m) do |i|
  s = "0" * n
  h = gets.split.map(&:to_i)
  h.shift
  h.each do |j|
    s[j - 1] = "1"
  end
  k[i] = s.to_i(2)
end
p = gets.split.map(&:to_i)
ans = 0
0.upto(2 ** n - 1) do |i|
  f = 1
  1.upto(m) do |j|
    if (i & k[j]).to_s(2).count("1") % 2 != p[j - 1]
      f = 0
      break;
    end
  end
  ans += f
end
puts ans
```
例えばスイッチが 10個の場合、文字列`0000000000`を準備し、使用するスイッチの場所を 1 に置換します。=> `0010011011`
その文字列とビットのすべての組合せ (**2 の n 乗**)とを比較し、点灯の条件と照らし合わせます。

```bit.rb
k[i] = s.to_i(2)
 # => 文字列を2進数表記の整数へ変換

if (i & k[j]).to_s(2).count("1") % 2 != p[j - 1]
 # => 整数を2進数表記の文字列へ変換し 1 の個数をカウント
```
*C++* では builtin_popcount で 1 の個数を調べますが、*Ruby* では count メソッドを使用します。
# Perl
```perl.pl
use v5.18; # strict say state

chomp (my ($n, $m) = split / /, <STDIN>);
my @k;
for my $i (1..$m) {
  my $s = '0' x $n;
  chomp (my @in = split / /, <STDIN>);
  shift @in;
  for my $j (0..$#in) {
    substr($s, $in[$j]-1, 1) = 1;
  }
  $k[$i] = $s;
}
chomp (my @p = split / /, <STDIN>);
my $ans = 0;
for my $i (0..2**$n-1) {
  my $s = sprintf "%0".$n."b", $i;
  my $f = 1;
  for my $j (1..$m) {
    $f = 0 if ((grep {$_ == 1} split('', ($s & $k[$j]))) % 2 != $p[$j-1]);
    last if $f == 0;
  }
  $ans += $f;
}
say $ans;
```
```and.pl
$f = 0 if ((grep {$_ == 1} split('', ($s & $k[$j]))) % 2 != $p[$j-1]);
```
*Ruby* では文字列のビット演算はエラーになりますが、*Perl* ではそのまま積を取ることができます。
1 の個数は grep で調べます。

**追記**
*[厳選！Perl アルゴリズム実装に使える 25 の 標準ライブラリ【前編】](https://qiita.com/superrino130/items/ab266b53f85c181b369d#25bitset)*
vec 関数を使用してビット演算を行う方法もあります。
# Java
```java.java
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int m = Integer.parseInt(sc.next());
        int k[] = new int[m];
        for (int i = 0; i < m; i++) {
            StringBuilder s = new StringBuilder("0000000000".substring(0, n));
            int x = Integer.parseInt(sc.next());
            for (int j = 0; j < x; j++) {
                int y = Integer.parseInt(sc.next());
                s.replace(y - 1, y, "1");
            }
            k[i] = Integer.parseInt(s.toString(), 2);
        }
        int p[] = new int[m];
        for (int i = 0; i < m; i++) {
            p[i] = Integer.parseInt(sc.next());
        }
        sc.close();
        int ans = 0;
        for (int i = 0; i < Math.pow(2, n); i++) {
            int f = 1;
            for (int j = 0; j < m; j++) {
                String bin = Integer.toBinaryString(i & k[j]);
                int c = 0;
                for (int v = 0; v < bin.length(); v++) {
                    if (bin.substring(v, v + 1).equals("1")) {
                        c++;
                    }
                }
                if (c % 2 != p[j]) {
                    f = 0;
                    break;
                }
            }
            ans += f;
        }
        System.out.println(ans);
    }
}
```
*Perl* のソースを元に *Java* へ書き直しましたので、文字列を利用したビット演算を行っていますが、勿論、シフト演算を使用しても解答できます。

||Ruby|Perl|Java|
|:--:|:--:|:--:|:--:|
|コード長|395 Byte|612 Byte|1424 Byte|
|実行時間|11 ms|19 ms|123 ms|
|メモリ|3836 KB|896 KB|24020 KB|
# まとめ
+ ABC 128 C を解いた
+ Ruby に詳しくなった
+ Perl に詳しくなった
+ Java に詳しくなった
+ ビット演算に詳しくなった

参照したサイト
*[Javaで進数変換を行なう方法]
(https://qiita.com/munieru_jp/items/6288988293958850bddd)*