Résolution avec Ruby, Perl, Java et Python AtCoder ARC 066 C Hash carré itératif

introduction

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

Ce thème

AtCoder Regular Contest 066 C - Lining Up Difficulty: 927

Ce thème, méthode carrée itérative et hachage Ruby C'est un problème symétrique, donc si vous l'assignez à un hachage, il devrait s'agir d'un tableau de valeurs tel que «2221222» pour les noms impairs et «22222222» pour les noms pairs. Dans d'autres cas, il peut être déterminé qu'il n'y a pas d'arrangement.

De plus, le moment est venu pour que le * [Résolution avec Ruby, Perl, Java et Python AtCoder ATC 002 B] publié précédemment (https://qiita.com/superrino130/items/adbb485637e45a024fa1) * soit utile. Puisqu'il s'agit du nombre de combinaisons de multiplication de 2, la méthode du carré itératif (fonction | méthode) créée dans l'article ci-dessus peut être utilisée telle quelle.

ruby.rb

n = gets.to_i
a = gets.split.map(&:to_i)
h = Hash.new(0)
a.each do |x|
  h[x] += 1
end
f = true
h.each do |k, v|
  if n.odd? && k == 0
    if v != 1
      f = false
      break
    end
  elsif v != 2
    f = false
    break
  end
end
MOD = 1_000_000_007
def mpow(n, p, mod)
  r = 1
  while p > 0
    r = r * n % mod if p & 1 == 1
    n = n * n % mod
    p >>= 1
  end
  r
end
puts (f ? mpow(2, n / 2, MOD) : 0)

mpow.rb

def mpow(n, p, mod)
  r = 1
  while p > 0
    r = r * n % mod if p & 1 == 1
    n = n * n % mod
    p >>= 1
  end
  r
end

Je l'utilise tel quel. Python

python.py

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
h = Counter()
for x in a:
    h[x] += 1
f = True
for k, v in h.most_common():
    if n % 2 == 1 and k == 0:
        if v != 1:
            f = False
            break
    elif v != 2:
        f = False
        break
MOD = 1000000007
def mpow(n, p, mod):
    r = 1
    while p > 0:
        if p & 1 == 1:
            r = r * n % mod
        n = n * n % mod
        p >>= 1
    return r
print(mpow(2, n // 2, MOD) if f else 0)

hash.py

from collections import Counter

Déclarez from collections import Counter lorsque vous utilisez des hachages.

mod.py

MOD = 1000000007
MOD = 1_000_000_007

Dans mon anneau Python 3.8.2 (par défaut, 16 avril 2020, 16:12:56), il peut être écrit 1_000_000_007, mais il semble être WA dans l'environnement AtCoder. Perl

perl.pl

chomp (my $n = <STDIN>);
chomp (my @a = split / /, <STDIN>);
my %h;
$h{$_}++ for @a;
my $f = 1;
for my $k (keys %h) {
  if ($n % 2 == 1 && $k == 0) {
    if ($h{$k} != 1) {
      $f = 0;
      last;
    }
  } elsif ($h{$k} != 2) {
    $f = 0;
    last;
  }
}
my $MOD = 1_000_000_007;
sub mpow {
  my ($n, $p) = @_;
  my $r = 1;
  while ($p > 0) {
    $r = $r * $n % $MOD if $p & 1;
    $n = $n * $n % $MOD;
    $p >>= 1;
  }
  $r;
}
print ($f ? mpow(2, int($n / 2)) : 0), "\n";

Tel quel ... Java

java.java

import java.math.BigInteger;
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        HashMap<Integer, Integer> h = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int a = Integer.parseInt(sc.next());
            if (h.containsKey(a)) {
                h.put(a, h.get(a) + 1);
            } else {
                h.put(a, 1);
            }
        }
        sc.close();
        boolean f = true;
        for (int k : h.keySet()) {
            if (n % 2 == 1 && k == 0) {
                if (h.get(k) != 1) {
                    f = false;
                    break;
                }
            } else if (h.get(k) != 2) {
                f = false;
                break;
            }
        }
        BigInteger bn = new BigInteger("2");
        BigInteger bm = new BigInteger("1000000007");
        BigInteger bp = new BigInteger(Integer.toString(n / 2));
        System.out.println((f ? bn.modPow(bp, bm) : 0));
    }
}

Résumé

• ARC 066 C résolu
• Familiarisez-vous avec Ruby
• Familiarisez-vous avec Python
• Familiarisez-vous avec Perl
• Familiarisez-vous avec Java

Site référencé

• [Python] Dictionary (Hash) *
• Piège d'opérateur ou et et de Python *