自分用の勉強記録もかねて、Atcoderの解説をしていきたいと思います。
今回は、ABCD完答でした。A~Cは謎の掛け算攻めでしたね。桁数の扱いとかよくわかっていないですが、試行錯誤したらできました。Dも素因数分解ができればそんなに難しくないですね。
Eは解答を読んだらただの数学の問題だということが理解できました。
Fは動的計画法の問題のようですが、まだ理解が不十分なので解説はやめておきます。
A~Eについて解説していきます。
僕もプログラミングについて絶賛学習中なので、間違えなどありましたら気軽にご連絡ください。
A - Multiplication 1
問題はこちら。
a,b = map(int, input().split())
print(a*b)シンプルな掛け算。さすがにこれは…
B - Multiplication 2
問題はこちら。
n = int(input())
A = list(map(int,input().split()))
num = 1
flag = True
if A.count(0)>=1: #どこかに０があるなら掛け算しても０
print(0)
else:
for i in A:
num *= i
if num > pow(10,18): #途中で制限超えたら以降は計算しない。
print(-1)
flag =False
break
if flag:
print(num)まあ、シンプルな掛け算の問題。問題から、なるべく計算量を減らしたいという意図を感じたので
①0が含まれる場合。
②途中で制限を超えた場合（0の場合を除けば、整数の乗算なので値は増え続ける→以降は計算しなくてもー1確定）
の場合分けで計算量を減らした。
C - Multiplication 3
問題はこちら。
import math
import decimal
a,b = input().split()
a = int(a)
b = decimal.Decimal(b)
print(math.floor(a*b))浮動小数点とか誤差に関する問題ということは分かったが、いろいろ迷走してしまった。
decimalモジュールについてはこちらの解説を。
まあ今回の場合は、解説にあるように100倍して整数にすれば誤差がなくなるので問題ない。
誤差が生じる理由は、10進数の小数を2進数にすると無限に続く場合があり、そこの変換の問題という理解でいいのかな？
D - Div Game
問題はこちら。
import collections
def prime_factorize(n):
a = []
while n % 2 == 0:
a.append(2)
n //= 2
f = 3
while f * f <= n:
if n % f == 0:
a.append(f)
n //= f
else:
f += 2
if n != 1:
a.append(n)
return a
n = int(input())
a = prime_factorize(n)
c = collections.Counter(a)
num = 0
for v in c.values():
for i in range(1,n):
v -= i
if v >=0:
num +=1
else:break
print(num)流れとしては
①素因数分解する
②素因数の数を数え、eを同じ数にならないように分割していったとき何個に分けれるか数える（e = 1，2，3…）
※素因数分解についてはこちらを参考に。
E - Count Median
問題はこちら。
import statistics
import math
n = int(input())
A = []
B = []
for _ in range(n):
a, b = map(int,input().split())
A.append(a)
B.append(b)
A_m = statistics.median(A)
B_m = statistics.median(B)
if n%2 == 1:
num = B_m - A_m +1
elif n %2 ==0:
num = 2*B_m - 2*A_m +1
print(int(num))数学の問題。
解説にあるように、
①Xの最大・最小は、A,Bの中央値から求められる。
②ある値xを1動かしたときに中央値がどのように変化するか。
の2点に気づけばカンタン。
コメント