# 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.

#### `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.

Ruby Perl Java
Code length 395 Byte 612 Byte 1424 Byte
Execution time 11 ms 19 ms 123 ms
memory 3836 KB 896 KB 24020 KB

# 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)*