Ruby と Python で解く AtCoder ABC057 C 素因数分解 ビット全探索

はじめに

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

尚、昨日より過去問においても言語のアップデートが実施されました。
追記
一旦、旧環境に戻された様です。

ruby
"2.7.1"

python
Python: 3.8.2
NumPy:  1.18.2
SciPy:  1.4.1

pypy3
Python: 3.6.9

cython
Python: 3.8.2

Numo::NArrayのバージョン確認方法は不明でした。

今回のお題

AtCoder Beginner Contest C - Digits in Multiplication
Difficulty: 834

今回のテーマ、素因数分解 ＋ ビット全探索

Ruby

以前解きました、Ruby と Perl と Java と Python で解く AtCoder CADDi 2018 C 素因数分解 の類題の様ですので、早速コピペ解きましょう。

ruby.rb

require 'prime'

n = gets.to_i
if n == 1
  puts 1
else
  h = Prime.prime_division(n).to_h
  p = []
  h.each do |k, v|
    while v > 0
      p << k
      v -= 1
    end
  end
  min = Float::INFINITY
  0.upto(2 ** p.size - 1) do |bit|
    a = 1
    b = 1
    p.size.times do |i|
      if bit[i] == 0
        a *= p[i]
      else
        b *= p[i]
      end
    end
    if a >= b
      min = a if min > a
    else
      min = b if min > b
    end
  end
  puts min.to_s.size
end

素数を降順に割り振る方法ですとWAを貰いますので、ビット全探索を使用しています。

bit.rb

  0.upto(2 ** p.size - 1) do |bit|

  [0, 1].repeated_permutation.each do |bit|

ビット全探索では、repeated_permutationも使用されますが、ここではTLEになる様です。

Python

pypy.py

from math import sqrt
from itertools import product
import sys

n = int(input())
p = []
def factorization(arg):
    while arg % 2 == 0:
        p.append(2)
        arg //= 2
    for i in range(3, int(sqrt(arg)) + 1, 2):
        while arg % i == 0:
            p.append(i)
            arg //= i
    if arg > 1:
        p.append(arg)
if n == 1:
    print(1)
else:
    factorization(n)
    min = sys.maxsize
    for bit in range(2 ** len(p)):
        a = 1
        b = 1
        for i in range(len(p)):
            if ((bit >> i) & 1):
                a *= p[i]
            else:
                b *= p[i]
        if min > a and a >= b:
            min = a
        elif min > b and b > a:
            min = b
    print(len(str(min)))

int.py

            arg //= i

/=ですとWAになる様です。

	Ruby(2.3.3)	Ruby(2.7.1)	Python	PyPy3(2.4.0)	PyPy3(7.3.0)
コード長 (Byte)	506	506	763	763	763
実行時間 (ms)	TLE	1355	TLE	643	352
メモリ (KB)	2300	9284	3064	52736	30112

まとめ

• ABC 057 C を解いた
• AtCoder の過去問の言語がバージョンアップされた
• Ruby に詳しくなった
• Python に詳しくなった