ABC169

はじめに

この記事では、AtCoder Beginer Contest 169のA~F問題を解説します。

A - Multiplication 1

https://atcoder.jp/contests/abc169/tasks/abc169_a

1
2
a, b = map(int, input().split())
print(a*b)

B - Multiplication 2

https://atcoder.jp/contests/abc169/tasks/abc169_b

整数の中に0が含まれる場合は答えが無条件で0となります。

先頭から積を計算していき、10**18を超えた段階で-1を出力すれば良いです。Pythonの場合、多倍長整数を扱えるのでサイズを気にしなくて良いように思えますが、巨大な数の計算は遅くなるため、最後まで計算しようとしてしまうとTLEとなります。

1
2
3
4
5
6
7
8
9
10
11
12
13
N = int(input())
A = list(map(int, input().split()))
INF = 10**18
if 0 in A:
print(0)
exit()
ans = 1
for a in A:
ans*=a
if ans > INF:
print(-1)
exit()
print (ans)

C - Multiplication 3

https://atcoder.jp/contests/abc169/tasks/abc169_c

浮動小数点数の誤差に気を付ける必要があります。

解法1

十進の浮動小数点数による計算を正確に行いたい場合は標準ライブラリのdecimalを用いると良いです。

1
2
3
4
from decimal import *
a, b = input().split()
ans = Decimal(a) * Decimal(b)
print (int(ans))

解法2

文字列の置換によりbを100倍することができます。

1
2
3
4
5
a, b = input().split()
b = b.replace('.','')
ans = int(a) * int(b)
ans = ans//100
print (int(ans))

解法3

floatで100倍してからintに変換します。ただし、愚直に実装すると誤差でわずかに意図した値より小さくなる場合があります。

1
2
3
b=9.95
print (int(float(b)*100))
print(float(b*100))
1
2
994.9999999999999
994

そこで微小な値を足します。ここでは0.5とします。

1
2
3
4
a, b = input().split()
ans = int(a)*int(float(b)*100+0.5)
ans = ans//100
print(ans)

D - Div Game

https://atcoder.jp/contests/abc169/tasks/abc169_d

素因数分解を行います。素因数分解がp1^e1 * p2^e2 * ...のようになるとして、各pi^eiについて、zの候補として小さい順すなわちpi^1, pi^2, pi^3,...の順に割ることができるかを確認していけば良いです。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
N = int(input())
def factorize(N):
n = N
r = []
for i in range(2,int(N**0.5)+1): # intに変換すること
cnt = 0
while(n%i==0):
cnt += 1
n //= i # 整数除算(//)を使うこと
if cnt!=0:
r.append((i,cnt))
if n!=1: # root(N)以上の素数がある場合
r.append((n,1))
return r

ans = 0
for _, cnt in factorize(N):
i = 1
while(i <= cnt):
cnt-=i
i+=1
ans+=1
print (ans)

E - Count Median

https://atcoder.jp/contests/abc169/tasks/abc169_e

Aの中央値M_aXの中央値の最小値、Bの中央値M_bXの中央値の最大値であることが分かります。

  • Nが奇数の場合
    • 中央値は区間[M_a,M_b]の全ての整数となります。すなわち、中央値として考えられるのはM_b-M_a+1個です。
  • Nが偶数の場合
    • 中央値は区間[M_a,M_b]のうち0.5刻みの実数となります。すなわち、中央値として考えられるのは2*(M_b-M_a)+1個です。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      N = int(input())
      A = []
      B = []
      for n in range(N):
      a,b = map(int,input().split())
      A.append(a)
      B.append(b)

      A.sort()
      B.sort()

      if N%2==1:
      print (B[N//2]-A[N//2]+1)
      else:
      b = B[N//2]+B[N//2-1] # 中央値はこれを2で割るがあとで2を掛けるので相殺する
      a = A[N//2]+A[N//2-1]
      print (b-a+1)

F - Knapsack for All Subsets

https://atcoder.jp/contests/abc169/tasks/abc169_f

dp[i][s]1~i番目までの要素を使って構成しうる集合に対して、任意の要素を選択した際に和がsとなるような場合の数とします。

dp漸化式に登場する*2は、 A[i]を集合に加えるかどうかで分岐し場合の数が2倍になることに対応しています。

この実装ではPythonではTLEとなったため、PyPyを用いました。

1
2
3
4
5
6
7
8
9
10
11
12
N, S = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
for s in range(S+1):
if s-A[i] >= 0:
dp[i+1][s] = (dp[i][s] * 2 + dp[i][s-A[i]]) % MOD
else:
dp[i+1][s] = dp[i][s] * 2 % MOD # A[i]を集合に加えるかどうかで分岐するので、場合の数は2倍になる
print(dp[N][S])

関連記事

過去のABC解説記事です。

  • ABC168
    • A-E問題を解いています。
  • ABC167
    • A-E問題を解いています。
  • ABC166
    • A-F問題を解いています。
  • ABC165
    • A-F問題を解いています。
  • ABC164
    • A-E問題を解いています。
  • ABC163
    • A-D問題を解いています。
  • ABC162
    • A-E問題を解いています。

記事情報

  • 投稿日:2020年5月31日
  • 最終更新日:2020年6月13日