ABC169 - うごくものづくりのために

2WAで5完でした。
ABC参加4回目、初めての5完、そして初めての水色パフォが出ました。精進の結果が表れていて素直に嬉しいです。
一応茶色コーダーにもなりました。

f:id:tilt_silvie:20200602002745p:plain

ABCに参加するたびにパフォーマンスの色が1つずつ上がっているので、次は青パフォですね！（？）

A問

掛けるだけ。

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

B問

B - Multiplication 2

何も考えずに実装して1回TLEしました。正直なぜTLEしたのかまだ分かっていません。
とりあえず、要素中に 0 が一度でも出たら結果も 0 なので、要素に 0 があるか先にチェックしてやると計算量減るだろうなと思い実装したらACしました。

n = int(input())
a_list = list(map(int, input().split()))

if 0 in a_list:
    print(0)
    exit()

result = 1
for i in range(n):
    result *= a_list[i]
    if result > 10**18:
        print(-1)
        exit()
print(result)

C問

C - Multiplication 3

こちらも何も考えずに実装して1WA。
バグらせるのが難しいレベルの単純なコードなので、浮動小数の精度絡みの問題でWAしていると推測し、decimal.Decimalを用いて実装し直してAC。
ちょうどこの日に decimal.Decimal の使い方を勉強していました。ラッキー。

from decimal import Decimal, ROUND_FLOOR

a, b = map(Decimal, input().split())
print((a*b).quantize(Decimal('1'), rounding=ROUND_FLOOR))

b * 100 して整数に直してから計算というのも思いつきましたが、変なこと考えずにdecimal.Decimal使いました。

D問

D - Div Game

しばらく考えて、 N が割り切れ、かつ z=p^e を満たす z は、すなわちNの素因数だと気づきました。
あとは素因数分解して、各素因数の指数から、1から順に引き算していけば最大の操作数が取れるという方針を立てて実装し、AC。なんだかんだ25分かかりました。
最初、入力が1のときの例外処理を入れておらずバグらせかけました。サンプルケースにあってよかった。

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = int(input())
if n == 1:
    print(0)
    exit()

facts = factorization(n)
cnt = 0
for fact in facts:
    for i in range(1, 100000):
        if (fact[1] - i) < 0:
            break
        fact[1] -= i
        cnt += 1
print(cnt)

E問

E - Count Median

すべての X_i が A_i を取るときに中央値が最小になります。これは、1つを除く X_i を A_i にし、1つの X の要素を X_k を A_k より大きくしたときの中央値は、すべての X_i が A_i を取るときの中央値より小さくはならない、ということから分かります。同様に、すべての X_i が B_i を取るときに中央値が最大になります。

あとは、最小と最大の間でどういう中央値を取りうるか、です。中央値に影響を与えるXの要素を1ずつ変化させるという操作が可能なので、最小と最大の間のすべての範囲を取りうるだろう、と考えられます。

というところまで考えて、実装。一発ACして一人でガッツポーズしてました。回答まで30分強かかりました。

from statistics import median

n = int(input())
a_list = [0] * n
b_list = [0] * n

for i in range(n):
     a, b = map(int, input().split())
     a_list[i] = a
     b_list[i] = b
    
min_median = median(a_list)
max_median = median(b_list)

median_range = max_median - min_median

if n%2 == 0:
    print(int(median_range/0.5 + 1))
else:
    print(int(median_range/1 + 1))