Résolution avec Ruby, Perl et Java AtCoder ABC 128 C

introduction

• Utilisez les recommandations dans AtCoder Problems * pour résoudre les problèmes passés. Merci à AtCoder et AtCoder Problems.

Ce thème

AtCoder Beginner Contest 128 C - Switches Difficulty: 807

Le thème cette fois est un peu arithmétique 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

Par exemple, si vous avez 10 commutateurs, préparez la chaîne «0000000000» et remplacez l'emplacement du commutateur souhaité par 1. => 0010011011 Comparez la chaîne avec toutes les combinaisons de bits (** 2 à la nième puissance **) et comparez avec les conditions d'éclairage.

bit.rb

k[i] = s.to_i(2)
 # =>Convertir une chaîne en un entier de notation binaire

if (i & k[j]).to_s(2).count("1") % 2 != p[j - 1]
 # =>Convertit un entier en chaîne de notation binaire et compte le nombre de 1

• C +++ utilise builtin_popcount pour trouver le nombre de 1, tandis que * Ruby * utilise la méthode 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]);

Dans * Ruby *, l'opération sur les bits de la chaîne de caractères provoque une erreur, mais dans * Perl *, le produit peut être calculé tel quel. Vérifiez le nombre de 1 avec grep.

** Addenda **

• Soigneusement sélectionnés! 25 bibliothèques standard pouvant être utilisées pour implémenter des algorithmes Perl [Partie 1] * Vous pouvez également utiliser la fonction vec pour effectuer des opérations sur les bits. 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);
    }
}

Comme il a été réécrit en * Java * basé sur la source * Perl *, les opérations sur les bits sont effectuées à l'aide de chaînes de caractères, mais bien sûr, vous pouvez également répondre en utilisant des opérations de décalage.

Résumé

• Résolu ABC 128 C
• Familiarisez-vous avec Ruby
• Familiarisez-vous avec Perl
• Familiarisez-vous avec Java
• Se familiarise avec l'arithmétique des bits

Site référencé

• [Comment effectuer une conversion de base en Java] (https://qiita.com/munieru_jp/items/6288988293958850bddd)*