AtCoder Beginner Contest 169のA,B,C問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
AtCoder Beginner Contest 169
全提出人数: 11355人
| パフォ | AC | 点数 | 時間 | 順位 | 目安 |
|---|---|---|---|---|---|
| 400 | AB---- | 300 | 38分 | 7119位 | 茶パフォ |
| 600 | A--D-- | 500 | 41分 | 5771位 | 8回で茶レート |
| 800 | AB-D-- | 700 | 102分 | 4384位 | 緑パフォ |
| 1000 | ABCD-- | 1000 | 105分 | 3137位 | 8回で緑レート |
| 1200 | ABCD-- | 1000 | 50分 | 2149位 | 水パフォ |
(参考)私：パフォ1726 B,CでWAを出しました
- A問題 (11268人AC) 『Multiplication 1』
- 普段は使わないようにしているワードなのですが、本当に「書くだけ」です。
- B問題 (7017人AC) 『Multiplication 2』
- 面倒なうえに、0を含む場合を特別に考える必要があって難しいです。
- C問題 (5525人AC) 『Multiplication 3』
- 「浮動小数点数の丸め誤差」を知らないと無理です。 これも難しいです。
- D問題 (4591人AC) 『Div Game』[この問題では解説しません]
- とりあえず素因数分解しましょう。素直な問題なので、Cより簡単に感じるかもしれません。
A問題 『Multiplication 1』
問題ページ：A - Multiplication 1
むずかしさ：☆☆☆☆☆
ポイント：プログラミングの基本
あまりに簡単なので引っ掛けを疑いたくなりますが、普通に書くだけで大丈夫です。
A問題はいつもこれくらいのレベルでいいと思います。
解き方
「書くだけ」とかあまり言いたくないですが、本当に書くだけです。
コード
a, b = map(int, input().split())
print(a * b)
B問題 『Multiplication 2』
問題ページ：B - Multiplication 2
むずかしさ：★★★★★
ポイント：ポイントを書く
$A$ と $N$ が大きいので、普通にやるとTLEになります。（他の言語だとオーバーフローします）
工夫する必要がありますが、0を含む場合は必ず0であることに注意しましょう。私は見逃してWAを出しました。
解き方
1. 問題文を読む
2. 実装を考える
ステップ1：問題文を読む
数字がたくさん与えられるので、全部掛けた結果を出力する問題です。
ただし、結果が $10^{18}$ を超える場合、-1を出力します。
ステップ2：実装を考える
先に計算して、最後に $10^{18}$ を超えているか確認すると、TLEになります。
桁数が大きくなるにつれて、掛け算にかかる時間も大きくなるからです。
そこで、結果が $10^{18}$ を超えたらすぐにprint(-1)として計算を打ち切りたくなります。
これは罠です。1つでも0があれば、答えは0になるからです。
$10^{18}, 10^{18}, 0$ という入力を考えてみてください。本当の答えは0ですが、2つ目の時点で $10^{36}$ になって $10^{18}$ を超えるので、print(-1) されてWAになります。
そこで、入力中に0があるか確認してから計算をはじめましょう。2つやり方があります。
1. 0を含む場合を分ける方法
2. 昇順にソートして先頭に0を持ってくる方法
コード1：0を含む場合を分ける方法
配列中に0が1つでも含まれるか判定する方法です。これは、if 0 in a:とすればいいです。
import sysして、sys.exit()と書くと、プログラム自体を終了させることができます。
計算打ち切りフラグをTrueにして、breakしてif文で-1を出力するよりも楽です。
なお、超える場合なので、>を使うことに気をつけてください。以上ではないので、>=ではありません。この間違いをしても、サンプル1が $10^{18}$ ちょうどなので、しっかり確認するようにしていれば気づけます。
import sys # sys.exit()を使いたいので
n = int(input())
a = list(map(int, input().split()))
if 0 in a:
# 0が1つでもあれば0です
print(0)
else:
# 0がない場合
cur = 1 # 現在の数値
for x in a:
cur *= x
if cur > 10 ** 18:
# 10**18を超えたので終了します
print(-1)
sys.exit()
print(cur) # 10**18以下なので、出力します
コード2：昇順にソートして先頭に0を持ってくる方法
もう1つの解き方に、aを昇順にソートするやり方があります。ソートすると、0があれば必ず一番最初に来るので、0判定を書かなくて済みます。
こちらのほうが少し楽かもしれません。私はこちらで解きました。
import sys # sys.exit()を使いたいので
n = int(input())
a = list(map(int, input().split()))
a.sort() # 0があれば先頭に来ます
cur = 1 # 現在の数値
for x in a:
cur *= x
if cur > 10 ** 18:
# 10**18を超えたので終了します
print(-1)
sys.exit()
print(cur) # 10**18以下なので、出力します
C問題 『Multiplication 3』
問題ページ：C - Multiplication 3
むずかしさ：★★★★★★
ポイント：浮動小数点数の誤差の知識
コンピュータは小数のある数字を正確に表せないので、普通に書くと誤差が出てWAになります。
この「浮動小数点数の誤差」の知識がないと、なぜWAになるかすらも全くわからないので、大変苦戦すると思います。
この解説では、2つの解き方を解説します。
1. 整数同士の計算で解く方法
2. decimalモジュールを使う方法
解き方1：整数同士の計算で解く方法
1. 問題文を読む
2. 解法を考える
3. 実装を考える
ステップ1：問題文を読む
整数 $A$ と、 プラスの実数 $B$ を掛け算して、結果を切り捨て整数として出力する問題です。まずは制約を確認しましょう。
$0 \le A \le 10^{15}$
$0 \le B \lt 10$
の範囲で、$A$は整数、$B$は小数第2位まで与えられます。つまり、 $A$ は超大きくなるかもしれない整数で、 $B$ は0.00～9.99です。
ステップ2：解法を考える
一見そのまま掛け算して切り捨てればいいように見えますが、それではWAになります。
なぜなら、コンピュータは整数を正確に表すことはできますが、小数のある数字を正確に表せない仕組みになっているからです。（詳しく知りたい方は、「浮動小数点数 誤差」などと検索してみてください）
>>> a = 198
>>> b = 1.10
>>> a * b # 一見正しいのですが……
217.8
>>> "{:.20f}".format(a * b) #小数点以下20桁まで表示してみます
'217.80000000000001136868'
このように、わずかですが誤差が発生しています。この例では大丈夫ですが、$A$ が非常に大きいときなどに、切り捨ての結果が本来の答えとズレてしまうことがあります。
小数点を含んで計算をすると誤差が出るので、整数同士の計算だけで済ませれば正確な結果を得られます。
そうするために、$B$ が小数第2位まで与えられると決まっていることを利用します。$B$ を100倍すれば、キリのいい整数になります。例えば、$1.10$ の100倍は $110$ です。
$A$ と $B\times{100}$ を掛け算して、最後に100で整数除算（//）をすれば、整数同士の計算だけで済ませることができます。
ステップ3：実装を考える
実装にも罠があります。$B$ を100倍すると書きましたが、素直に $B$ をfloat型で受け取って100倍する方法だとWAになります。
floatで受け取った時点で値がズレて、正確な値ではなくなるからです。（私はこれでWAを出しました）
>>> b = 9.99
>>> "{:.20f}".format(b)
'9.99000000000000021316'
正確な値を得るには、$B$ をstr型で受け取って、文字列のまま扱って加工して100倍した整数に変換すればいいです。
文字列のまま扱うといっても複雑なことはなく、ただ小数点'.'を取り除けばいいだけです。
どういうことかというと、b = '1.10'（str型）なら、小数点を取り除いた b[0] + b[2] + b[3] は '110'（str型）です。これをint型に変換すれば 110になるので、正確な結果を得られます。
>>> b = "1.10"
>>> s = b[0] + b[2] + b[3]
>>> s
'110'
>>> p = int(s)
>>> p
110
Pythonはかしこいので、頭に余計な0がついていても、しっかり整数に変換してくれます。
>>> b = "0.01"
>>> s = b[0] + b[2] + b[3]
>>> s
'001'
>>> p = int(s)
>>> p
1
コード1：整数同士の計算で解く方法
a, b = input().split() # まず文字列で受け取ります
p = int(a) # aはそのままint型にします
q = int(b[0] + b[2] + b[3]) # b[0] + b[2] + b[3]を整数に変換すれば、bの100倍を正確に得られます
print(p * q // 100) # 掛けて100で整数の割り算をすれば終わりです
解き方2：decimalモジュールを使う方法
もう1つ方法があります。「正確な十進浮動小数点数」の計算をするためのdecimalモジュールを使うやり方です。
数字をdecimal.Decimal型に変換して、decimal.Decimal型同士で計算するコードを書けば、勝手に内部でうまいこと十進数とズレないように計算してくれます。
decimal型を生成するには、a = decimal.Decimal(x)とすればいいです。入力のxには、int型、str型などが使えます。
>>> import decimal
>>> a = decimal.Decimal('198')
>>> a
Decimal('198')
>>> b = decimal.Decimal('1.10')
>>> b
Decimal('1.10')
>>> a * b
Decimal('217.80')
>>> int(a * b)
217
float型を入力することもできますが、そもそもfloat型にした瞬間から誤差が生じるので、Decimal型に変換しても誤差がそっくりそのまま反映されてしまいます。
>>> import decimal
>>> b = decimal.Decimal(1.10)
>>> b
Decimal('1.100000000000000088817841970012523233890533447265625')
大変なことになっています。float型を入力するのはやめておきましょう。
コード2：decimalモジュールを使う方法
切り捨てはint(x * y)としています。
この問題は常にプラスなので気にしなくてもいいですが、int()は「0方向に丸める」という処理で、math.floor()の「負の無限大の方向に丸める」とは違っているので、マイナスの数に対する挙動に気をつけしょう。
import decimal
Deci = decimal.Decimal # いちいちdecimal.Decimal(a)とか書きたくないので
a, b = input().split() # str型で受け取ります
x, y = Deci(a), Deci(b) # Decimal型に変換します
ans = int(x * y) # Decimal同士を掛け算した結果を、int型に変換します
print(ans)
補足：Decimalのまま切り捨てをしたい場合
ans = int(x * y)とした時点でint型になります。最終的な答えでこれ以上計算する必要がないのでこうしていますが、Decimal型のまま切り捨てをしたい場合もあります。
その場合は、こうすればいいです。
>>> z = (x * y).quantize(Deci('0'), rounding=decimal.ROUND_FLOOR)
>>> z
Decimal('217')
x * yをDecimal('0')と同じ形式にするために、小数部分を切り捨てる（FLOOR）という意味です。
>>> z = (x * y).quantize(Deci('0.0'), rounding=decimal.ROUND_FLOOR)
>>> z
Decimal('217.8')
Decimal('0.0')に変えてみます。'0.0'同じ形式、つまり小数点第1位まで表示するために、第2位以下を切り捨てるという意味になりました。
decimalモジュールでできることは多いので、ここですべてを説明することはできません。もっと詳しく知りたい方は調べてみてください。