はじめに

AtCoder の AtCoder Beginner Contest 162 の C問題がTLE寸前でしたので、復習を兼ねて投稿します。

お礼

オフィシャルの解説やネット上の解説・解答を参照して理解を進めております。
AtCoder さん、競技プロプレイヤーさん、ありがとうございます。

なぜTLE

ループを三重にしていることもありますが、Perl では、最小公倍数を求める関数が遅いことが要因と考えられます。

そこで、もっとプログラマ脳を鍛える数学パズルアルゴリズムが脳にしみ込む70問 にて再三紹介されているメモ化による高速化を行いたいと思います。

今回のC問題
AtCoder Beginner Contest C - Sum of gcd of Tuples (Easy)

TLE した Perl ソース

TLE.pl

use v5.26; # strict say state biwise
use warnings;

chomp (my $k = <STDIN>);
sub gcd {
  my ($x, $y) = @_;
  while ($y) {
    my $r = $x % $y;
    $x = $y;
    $y = $r;
  }
  $x;
}
my $ans = 0;
for my $i (1..$k) {
  for my $j (1..$k) {
    my $c = gcd($i, $j);
    for my $l (1..$k) {
      $ans += gcd($c, $l);
    }
  }
}
say $ans;

自作の gcd 関数を使用しています。
（Mathモジュールにgcd関数が用意されていますが、更に遅くなることが分かっています。）

	Perl 自作gcd
実行時間	TLE

Ruby の gcd メソッド

Ruby では Integer クラスに gcd メソッドが用意されていますので、それを使用します。

rubygcd.rb

k = gets.to_i

ans = 0
1.upto(k) do |i|
  1.upto(k) do |j|
    n = i.gcd(j)
    1.upto(k) do |k|
      ans += n.gcd(k)
    end
  end
end
puts ans

毎度のことながら、Ruby のスッキリ感は凄いですね。

	Perl 自作gcd	Ruby gcd
実行時間	TLE	741 ms

Perl メモ化による高速化

perlmemo.pl

use v5.26; # strict say state biwise
use warnings;

chomp (my $k = <STDIN>);
my @memo;
sub gcd {
  my ($x, $y) = @_;
  return $memo[$x][$y] if $memo[$x][$y] > 0;
  my ($u, $v) = ($x, $y);
  while ($y) {
    my $r = $x % $y;
    $x = $y;
    $y = $r;
  }
  $memo[$u][$v] = $x;
}
for my $i (1..$k) {
  for my $j (1..$k) {
    gcd($i, $j);
  }
}
my $ans = 0;
for my $i (1..$k) {
  for my $j (1..$k) {
    my $c = $memo[$i][$j];
    for my $l (1..$k) {
      $ans += $memo[$c][$l];
    }
  }
}
say $ans;

ここでは、予め gcd の計算結果を配列 memo にメモしておき、配列の値として呼び出します。

	Perl 自作gcd	Ruby gcd	Perl memo
実行時間	TLE	741 ms	408 ms

Ruby メモ化による高速化

rubymemo.rb

k = gets.to_i

@memo = Array.new(k + 1).map{Array.new(k + 1, 0)}
def gcdmemo(i, j)
  return @memo[i][j] if @memo[i][j] > 0
  u, v = i, j
  while (j > 0) do
    r =  i % j
    i = j
    j = r
  end
  @memo[u][v] = i
end
1.upto(k) do |i|
  1.upto(k) do |j|
    gcdmemo(i, j)
  end
end
ans = 0
1.upto(k) do |i|
  1.upto(k) do |j|
    c = @memo[i][j]
    1.upto(k) do |l|
      ans += @memo[c][l]
    end
  end
end
puts ans

上記 Perl メモ化による高速化と同じ手法で、自作の gcd メソッドを使用しています。

	Perl 自作gcd	Ruby gcd	Perl memo	Ruby memo
実行時間	TLE	741 ms	408 ms	437 ms

メモ化　凄い

まとめ

ABC 162 C の解法を改良した
メモ化の応用ができるようになった

参照したサイト
Rubyの配列で使えるメソッド、二次元配列の使い方

Ruby と Perl で解くAtCoder ABC 162 C メモ化による高速化