Ruby と Perl と Java と Python で解く AtCoder ARC 066 C 繰返し二乗法 ハッシュ

はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

AtCoder Regular Contest 066 C - Lining Up
Difficulty: 927

今回のテーマ、繰返し二乗法　と　ハッシュ

Ruby

これは左右対称な問題ですので、仮にハッシュに代入した場合、奇数名では2221222、偶数名では22222222の様なvalues配列になると想定されます。
それ以外の場合は、並び方がないと判断できます。

また、以前投稿しました Ruby と Perl と Java と Python で解く AtCoder ATC 002 B が役立つ時が来ました。
2の掛け算の組合せ数ですので、上記投稿で作成した繰返し二乗法(関数|メソッド)がそのまま使用できます。

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

そのまま使用しています。

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

ハッシュを使用する場合from collections import Counterを宣言します。

mod.py

MOD = 1000000007
MOD = 1_000_000_007

俺環Python 3.8.2 (default, Apr 16 2020, 16:12:56)では、1_000_000_007と書いても通りますが、AtCoder環境では WA になるようです。

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";

そのまま...

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));
    }
}

	Ruby	Python	Perl	Java
コード長	438 Byte	535 Byte	504 Byte	1100 Byte
実行時間	75 ms	125 ms	76 ms	435 ms
メモリ	12172 KB	16096 KB	20556 KB	49896 KB

まとめ

• ARC 066 C を解いた
• Ruby に詳しくなった
• Python に詳しくなった
• Perl に詳しくなった
• Java に詳しくなった

参照したサイト
【Python】辞書（ハッシュ）
Python の or と and 演算子の罠