Solving with Ruby, Perl and Java AtCoder ABC 128 C

Introduction

• AtCoder Problems * Use Recommendations to solve past problems. Thanks to AtCoder and AtCoder Problems.

This theme

AtCoder Beginner Contest 128 C - Switches Difficulty: 807

The theme this time is bit operation 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

For example, if you have 10 switches, prepare the string 0000000000 and replace the switch location you want with 1. => 0010011011 Compare that string with all combinations of bits (** 2 to the nth power **) and compare it to the lighting conditions.

bit.rb

k[i] = s.to_i(2)
 # =>Convert a string to an integer in binary notation

if (i & k[j]).to_s(2).count("1") % 2 != p[j - 1]
 # =>Converts an integer to a string in binary notation and counts the number of 1s

• C ++ * uses builtin_popcount to find the number of 1s, while * Ruby * uses the count method. 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]);

In * Ruby *, the bit operation of the character string becomes an error, but in * Perl *, the product can be taken as it is. Check the number of 1s with grep.

** Addition **

• Carefully selected! 25 standard libraries that can be used to implement Perl algorithms [Part 1] * You can also use the vec function to perform bit operations. 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);
    }
}

Since it was rewritten to * Java * based on the * Perl * source, bit operations using character strings are performed, but of course, you can also answer using shift operations.

Summary

• Solved ABC 128 C
• Become familiar with Ruby
• Become familiar with Perl
• Become familiar with Java
• Became familiar with bit operations

Referenced site

• [How to perform base conversion in Java] (https://qiita.com/munieru_jp/items/6288988293958850bddd)*