Perl で学ぶ逆元の２ + パナソニックプログラミングコンテスト2020 C で嵌った話

はじめに

C - Sqrt Inequality
おっ、サービス問題じゃん

WA
ぐぬぬ

パナソニックプログラミングコンテスト2020 C

WA.pl

if (sqrt($a)+sqrt($b)<sqrt($c)) {
  say "Yes";
} else {
  say "No";
}

これで行きそうなのですが、実数に対する誤差のため WA

BigFloat.pl

use v5.18; # strict say state
use warnings;
use Math::BigFloat;

my ($a, $b, $c) = split / /, <STDIN>;

my $x = Math::BigFloat->new($a)->bsqrt();
my $y = Math::BigFloat->new($b)->bsqrt();
my $z = Math::BigFloat->new($c)->bsqrt();

if ($x+$y<$z) {
  say "Yes";
} else {
  say "No";
}

BigFloat を使用してもダメな様子

逆元

perldoc を見ていると、Math::BigInt 系に bmodinv と bmodpow を発見
*以前の投稿*に適用してみました
D - Bouquet

ABC156D-Bouquet.pl

use v5.18;
use warnings;
use Math::BigInt;
use List::Util 'reduce';

my ($n, $e, $f) = split / /, <STDIN>;
my $MOD = 1e9 + 7;

sub combination {
  my ($n, $k) = @_;
  my $c = reduce {$a * $b % $MOD} (($n-$k+1)..$n);
  my $d = reduce {$a * $b % $MOD} (1..$k);

  $c * Math::BigInt->new($d)->bmodinv($MOD) % $MOD;
}
my $ans = Math::BigInt->new(2)->bmodpow($n, $MOD) - 1;
$ans += $MOD - combination($n, $e);
$ans += $MOD - combination($n, $f);
say $ans % $MOD;

スッキリしてる

	前回	今回
コード長	754 Byte	475 Byte
実行時間	129 ms	110 ms
メモリ	768 KB	12544 KB
実行時間も短くなってる

まとめ

• パナソニックプログラミングコンテスト2020 C で嵌った
• 本当は B も嵌っている
• 逆元の解法に詳しくなった

参照したサイト
Math::BigInt
標準添付の Math:: モジュールのご紹介
perl で bignum の精度の設定方法ならびに bignum 実装での log 関数のバグについて
Perl で学ぶ剰余計算
Perl AtCoderのアップデートを先取りしてライバルに差をつけよう(List::Util他)

追記

Math::BigInt は perl の bigint は圧倒的に遅い 様です。
ABC156D-Bouquet は計算箇所が少ないので問題ないのですが、ABC151E-Max-Min Sums の様に多い場合は自作関数の方がいいと思われます。
Perl で学ぶ逆元の３ ABC 151 E が解けた！