はじめに
この記事では、AtCoder Beginer Contest 169のA~F問題を解説します。
A - Multiplication 1
https://atcoder.jp/contests/abc169/tasks/abc169_a
1 | a, b = map(int, input().split()) |
B - Multiplication 2
https://atcoder.jp/contests/abc169/tasks/abc169_b
整数の中に0
が含まれる場合は答えが無条件で0
となります。
先頭から積を計算していき、10**18
を超えた段階で-1
を出力すれば良いです。Python
の場合、多倍長整数を扱えるのでサイズを気にしなくて良いように思えますが、巨大な数の計算は遅くなるため、最後まで計算しようとしてしまうとTLE
となります。
1 | N = int(input()) |
C - Multiplication 3
https://atcoder.jp/contests/abc169/tasks/abc169_c
浮動小数点数の誤差に気を付ける必要があります。
解法1
十進の浮動小数点数による計算を正確に行いたい場合は標準ライブラリのdecimal
を用いると良いです。
1 | from decimal import * |
解法2
文字列の置換によりb
を100倍することができます。
1 | a, b = input().split() |
解法3
float
で100倍してからint
に変換します。ただし、愚直に実装すると誤差でわずかに意図した値より小さくなる場合があります。
1 | b=9.95 |
1 | 994.9999999999999 |
そこで微小な値を足します。ここでは0.5
とします。
1 | a, b = input().split() |
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 | N = int(input()) |
E - Count Median
https://atcoder.jp/contests/abc169/tasks/abc169_e
A
の中央値M_a
がX
の中央値の最小値、B
の中央値M_b
がX
の中央値の最大値であることが分かります。
- Nが奇数の場合
- 中央値は区間[M_a,M_b]の全ての整数となります。すなわち、中央値として考えられるのは
M_b-M_a+1
個です。
- 中央値は区間[M_a,M_b]の全ての整数となります。すなわち、中央値として考えられるのは
- 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
17N = 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)
- 中央値は区間[M_a,M_b]のうち0.5刻みの実数となります。すなわち、中央値として考えられるのは
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 | N, S = map(int, input().split()) |
関連記事
過去の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日