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

はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

AtCoder Beginner Contest 128 C - Switches
Difficulty: 807

今回のテーマは、ビット演算

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 の 標準ライブラリ【前編】
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)