AtCoder ABC169

2020-05-31(日)に行われたAtCoderBeginnerContest169の問題をA問題から順に考察も踏まえてまとめたものとなります．
後半ではDEの問題を扱います．前半はこちら．
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
 公式解説PDF

D問題　Div Game

問題文
正の整数$N$が与えられます。$N$に対して、以下の操作を繰り返し行うことを考えます。
　・はじめに、以下の条件を全て満たす正の整数$z$を選ぶ。
　　◦ある素数$p$と正の整数$e$を用いて、$z=p^e$と表せる
　　◦$N$が$z$で割り切れる
　　◦以前の操作で選んだどの整数とも異なる
　・$N$を、$N/z$に置き換える
最大で何回操作を行うことができるか求めてください。

とりあえず素因数分解すれば，この問題は簡単に解けることは気づいたので，いつもお世話になっている記事検索して，素因数分解の部分のコードをコピーしました．
Pythonで高速素因数分解〜競プロ用〜
今回の問題は，ある素因数$p_1$を$k$個，持っているとき，何回操作を行うことができるかを考えないといけませんが，操作回数　→　必要な素因数$p_1$の個数は
$1 → 1$
$2 → 3$
$3 → 6$
$4 → 10$
$5 → 15$
と階差数列になっています．
これを計算すると，$m$回操作をするために必要な素因数$p_1$の個数は$\frac{m(m + 1)}{2}$個となることがわかるため，素因数分解した各素因数に対して，操作が何回できるかを計算し，足していくことで答えを得ることができました．

abc169d.py

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)
else:
    x_list = factorization(n)
    ans = 0
    for x in x_list:
        n = 2
        while True:
            if x[1] < (n * n + n) // 2:
                ans += n - 1
                break 
            n += 1
    print(ans)

入力が$1$のときだけ，気を付けないとですね．

E問題　Count Median

問題文
$N$個の整数$X_1,X_2,⋯,X_N$があり、$A_i \leq X_i \leq B_i$であることがわかっています。$X_1,X_2,⋯,X_N$の中央値として考えられる値はいくつあるか求めてください。

BとC問題に時間とられ過ぎて，間に合いませんでしたが，$A$と$B$を別々にソートして，その中央値を使えば解けるのは，すぐにわかりました．
データ数が奇数個の場合までコード書いてタイムアップ．

問題に関して，まず$A_1,A_2,...,A_N$をソートした結果，得られる数列を$C_1,C_2,...,C_N$とし，$B_1,B_2,...,B_N$をソートした結果，得られる数列を$D_1,D_2,...,D_N$とする．

データ数が奇数個

答えは$D_{(N+1)/2} - C_{(N+1)/2} + 1$個となる．

データ数が偶数個

答えは$D_{N/2} - C_{N/2} + D_{N/2+1} - C_{N/2+1} + 1$個となる．
例えば，$C_{N/2}=5, C_{N/2+1}=7, D_{N/2}=7, D_{N/2+1}=9$とすると，考えられる組み合わせは，

	5	6	7
7	6	13/2	7
8	13/2	7	15/2
9	7	15/2	8

と重複しているものが多く，答えは$6,13/2,7,15/2,8$の$5$個である．
この答は，表の行数＋列数 - 1であるため，上記の計算式で，同様の答えを得ることができる．

abc169e.py

n = int(input())
a_list = []
b_list = []
for i in range(0, n):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)
a_list.sort()
b_list.sort()
if n % 2 == 0:
    x1 = n // 2 - 1
    x2 = n // 2
    print(b_list[x2] - a_list[x2] + b_list[x1] - a_list[x1] + 1)
else:
    x = n // 2
    print(b_list[x] - a_list[x] + 1)

AからCの問題セットがいつも通りの難易度であれば，5完できてたと思うが，勉強不足を感じます．
就職するまでに，少しでもプログラミングの力上がればいいなと思って始めたので，目的に合っている感じはしているので，今後も参加していきたいと思います（BとC問題通せず，rate落ちてたら距離を置くとこだった）．
F問題は，今週忙しいので時間ができたときにでも追記できたらいいなと思ってます．

後半も最後まで読んでいただきありがとうございました．