Solving with Ruby, Perl and Java AtCoder ABC 128 C


This theme

AtCoder Beginner Contest 128 C - Switches Difficulty: 807

The theme this time is bit operation Ruby


n, m =
k = []
1.upto(m) do |i|
  s = "0" * n
  h =
  h.each do |j|
    s[j - 1] = "1"
  k[i] = s.to_i(2)
p =
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
  ans += f
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.


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

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;

$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 **

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(;
        int n = Integer.parseInt(;
        int m = Integer.parseInt(;
        int k[] = new int[m];
        for (int i = 0; i < m; i++) {
            StringBuilder s = new StringBuilder("0000000000".substring(0, n));
            int x = Integer.parseInt(;
            for (int j = 0; j < x; j++) {
                int y = Integer.parseInt(;
                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(;
        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")) {
                if (c % 2 != p[j]) {
                    f = 0;
            ans += f;

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


Referenced site

Recommended Posts

Solving with Ruby, Perl and Java AtCoder ABC 128 C
Solving with Ruby, Perl and Java AtCoder ABC 129 C (Part 1)
Solving with Ruby, Perl and Java AtCoder ABC 129 C (Part 2) Dynamic programming
Solving in Ruby, Perl and Java AtCoder ABC 113 C Reference
Solving with Ruby, Perl and Java AtCoder ABC 136 D Breadth-first search
Solving with Ruby and Java AtCoder ABC129 D 2D array
Solving with Ruby and Crystal AtCoder ABC 129 D
Sorting AtCoder ABC 111 C hashes to solve in Ruby, Perl and Java
AtCoder ARC 081 C hash to solve in Ruby, Perl and Java
Encrypt with Java and decrypt with C #
AtCoder dwango Programming Contest B in Ruby, Perl and Java
Solving with Ruby AtCoder ACL Beginner Contest C Union Find (DSU)
Link Java and C ++ code with SWIG
Solve ARC104 D Multiset Mean with Scala, Java, C ++, Ruby, Perl, Elixir
AtCoder Beginner Contest 169 A, B, C with ruby
I implemented Ruby with Ruby (and C) (I played with builtin)
AtCoder ABC 169 C Floating Point Fits in Ruby
Try to link Ruby and Java with Dapr
AtCoder ABC127 D hash to solve with Ruby 2.7.1
atcoder ABC113 C problem
atcoder ABC115 C problem
ABC177 --solving E in Ruby
Ruby C extension and volatile
C # and Java Overrides Story
Kotlin post- and pre-increment and operator overload (comparison with C, Java, C ++)
Use java with MSYS and Cygwin
Distributed tracing with OpenCensus and Java
Install Java and Tomcat with Ansible
Learning Ruby with AtCoder 6 [Contest 168 Therefore]
Use JDBC with Java and Scala.
Hello World with Docker and C
Output PDF and TIFF with Java 8
Solving with Ruby AtCoder 1st Algorithm Practical Test A Exception Handling
AtCoder Beginner Contest 167 C Problem (Java)
[Ruby / Refactoring] From Ruby iterative processing like Java and C language to Ruby-like iterative processing
How to make an app with a plugin mechanism [C # and Java]
With ruby ● × Game and Othello (basic review)
Monitor Java applications with jolokia and hawtio
Getting Started with Ruby for Java Engineers
Call Java library from C with JNI
java core: HotSpot compiler and C heap
Learning Ruby with AtCoder 7 [Contest 168 Triple Dots]
Let's try WebSocket with Java and javascript!
[Java] Reading and writing files with OpenCSV
Java Direction in C ++ Design and Evolution
Java to C and C to Java in Android Studio
Convert JSON to TSV and TSV to JSON with Ruby
Read and write line by line from buffer with TCP communication between C and Ruby
[Code] Forcibly breaks through the C problem "* 3 or / 2" of [AtCoder Problem-ABC100] with Java [Code]
Build and test Java + Gradle applications with Wercker
I also tried WebAssembly with Nim and C
JSON with Java and Jackson Part 2 XSS measures
Differences in writing Java, C # and Javascript classes
Create jupyter notebook with Docker and run ruby
Summarize the differences between C # and Java writing
Prepare a scraping environment with Docker and Java
KMS) Envelope encryption with openssl and java decryption
Encrypt / decrypt with AES256 in PHP and Java
[Java] Convert and import file values with OpenCSV
[Review] Reading and writing files with java (JDK6)