2020年6月

ABC169 B,C問題(2020.5.31)

  • 2020.06.03

概要 本記事は、2020/5/31に開催されたABC169のB,C問題を整理した内容を記載します。D問題までの回答を目指しているにもかかわらず、まさかのB,C問題でつまづいてしまいました。非常に不甲斐ない結果ですが、しっかりできなかったポイントを整理していきたいと思います。ただ、TwitterやYoutubeのコメントを見ていると同じようにB,Cで苦戦している人が多かったようなので、少しだけほっとしていました。 B – Multiplication2 問題 https://atcoder.jp/contests/abc169/tasks/abc169_b 解説 PDF https://img.atcoder.jp/abc169/editorial.pdf Youtube 理解 N個の整数Ajを全て掛け合わせして解を求めるという非常にシンプルな問題です。ポイントは2つあって、まず1つはAjは0になることがあるということ。もう1つはAjは最大で10の9乗であり、そのまま全てをかけるとオーバーフローを起こしてしまうということです。python3.0の場合は、int型が多倍長整数であるので基本的にメモリがある分は桁数を使用することができます。なので、単純に毎回掛けて10の18乗を超えていないかをチェックする処理で動作します。 実装 参考 – 任意精度演算 https://ja.m.wikipedia.org/wiki/%E4%BB%BB%E6%84%8F%E7%B2%BE%E5%BA%A6%E6%BC%94%E7%AE%97 C – Multiplication3 問題 https://atcoder.jp/contests/abc169/tasks/abc169_c 解説 PDF https://img.atcoder.jp/abc169/editorial.pdf Youtube 理解 与えられたAとBの2つの整数をかけて、解は小数点以下を切り捨てて表示するというC問題にしては簡単すぎる問題だと思って解いたところ、しっかりと罠が仕掛けられていました。それはfloat型の浮動小数点により掛け算を行うと精度が足りず、誤差が発生してしまうというものです。したがって、安全な方法としてはfloatからDecimalに変換して掛け算を行うことで誤差をなくすことができます。注意点としてはpythonのDecimal関数の引数は誤差をなくすためにはStringで引数を指定する必要があるということがあります。 実装 参考 – 浮動小数点数 https://ja.m.wikipedia.org/wiki/%E6%B5%AE%E5%8B%95%E5%B0%8F%E6%95%B0%E7%82%B9%E6%95%B0