LoginSignup
0

More than 3 years have passed since last update.

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

Last updated at Posted at 2020-03-14

はじめに

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 系に bmodinvbmodpow を発見
以前の投稿に適用してみました
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::BigIntperl の bigint は圧倒的に遅い 様です。
ABC156D-Bouquet は計算箇所が少ないので問題ないのですが、ABC151E-Max-Min Sums の様に多い場合は自作関数の方がいいと思われます。
Perl で学ぶ逆元の3 ABC 151 E が解けた!

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0