AtCoder Beginner Contest 169 B を Python で

AtCoder Beginner Contest 169 B を Python で解説していきます。とりあえず C はまだ理解が完全と言うわけではないので B を解説します。すぬけさんの生放送でなかなか苦戦されてて，これまでで一番難しい B 問題だとか言ってはったので，なかなか引っかかる問題だと思います。本当に作問者さん素晴らしいですね。いやらしい。笑
それでは，まずは問題文から。

B – Multiplication 2

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 200 点

問題文

N 個の整数 A1,…,AN が与えられます。

A1×…×AN を求めてください。

ただし、結果が 10^18 を超える場合は、代わりに -1 を出力してください。

制約

2≤N≤10^5
0≤Ai≤10^18
入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
A1 … AN

出力

値 A1×…×AN を整数として出力せよ。ただし、この値が 10^18 を超える場合は、代わりに -1 を出力せよ。

入力例 1

2
1000000000 1000000000

出力例 1

1000000000000000000

1000000000×1000000000=1000000000000000000 です。

入力例 2

3
101 9901 999999000001

出力例 2

-1

101×9901×999999000001=1000000000000000001 ですが、これは 10^18 を超えるので、代わりに -1 を出力します。

入力例 3

31
4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0

出力例 3

解説

一番簡単にパッと思いつくのは， A をリストとして受け取って，ans という変数に for 文で全要素をかけて格納していって，最後の値が10^18より大きければ -1 を出力するというものではないでしょうか。しかしこれではN と Ai の制限から，ans の値がとてつもなく大きくなってオーバーフローして TLE になってしまいます。Python では整数型の上限はありませんが，あまりに大きい値は扱う際にかなり時間がかかってしまうためです。

これを回避するために，for 文での毎回の計算において，その値が 10^18より大きいかどうか判断します。もし大きければその段階で ans に -1 を代入してあげて，break します。これでオーバーフローを回避できます。

また，入力に０がある場合にも要注意です。この場合は有無を言わさず掛けた値が０になります。Python ではリストに０が含まれているかどうかの判定は次のように行えます。

0 in A:
// 含まれていたら True，含まれていなかったら False の bool値を返す

これをやっておかないと，例えばかけていって１０^１８を超えた後に０の値が出てきた場合，仕様上先に１０^１８を超えた段階で-1を出力して終わってしまうからです。なので実装の優先順位としては次のようになります。

入力に０が含まれているか　→　含まれていたら０を出力
それぞれの掛け算で10^18を超えるか　→　超えたら -1 を出力
１と２どちらにも該当しなければ普通にかけた値を出力

それでは，解答例に移ります。

解答例

import sys
n = int(input())
A = list(map(int, input().split()))

ans = 1
if 0 in A:
  print(0)
  sys.exit()
  
for i in range(n):
  ans *= A[i]
  if ans > 1e18:
    ans = -1
    break

print(ans)

いかがだったでしょうか。
確かになかなか難しい問題だったかと思います。
すぬけさんの生放送聞きながら書いていたのですが面白かったです。w
こんなこと言ったら怒られそう()

もしおかしいところなどがあった場合はtwitterで教えてください。
それでは！

タムログ

プログラミングについての情報発信をしていきます！