AtCoder Beginner Contest 169 - D - Div Game / E - Count Median

Eまで通せたが、もうちょっと早くやりたかった。

atcoder.jp

こっちは割と典型問題。素因数分解を行った後で、各素数pにおいて p¹, p², p³.... とzを取っていけばよい。素因数分解の実装がさくっとかけたのは満足。

def factrization(N):
    k = 2
    ret = {}
    L = N ** 0.5
    while k < L:
        if N % k == 0:
            ret.setdefault(k, 0)
            ret[k] += 1
            N //= k
        else:
            k += 1
    if N > 1:
        ret.setdefault(N, 0)
        ret[N] += 1
    return ret

def solve(N):
    f = factrization(N)
    ans = 0
    for n in f.values():
        i = 1
        while i <= n:
            n -= i
            i += 1
            ans += 1
    return ans

if __name__ == "__main__":
    N = int(input())
    print(solve(N))

atcoder.jp

中央値の問題はいつも偶数がやっかい。

まずN=奇数のときから考える。

この時、ある整数が中央値となる可能性を持つためには、 その整数よりも小さい数が(N-1)//2以上存在しかつ、 その整数よりも大きい数は(N-1)//2つ以上存在する範囲を考えればよい。

例えば３個の以下のような範囲が並べられたときには、(3 - 1) // 2 = 1個以上、 左右に存在する範囲が中央値の存在する範囲となる。

N=偶数の時はすこしやっかい。 まず、中央値の計算の元になる中央２つの数値の範囲を最初に求める。

中央二つのうち左側は その整数よりも小さい数がN//2-1つ以上存在しかつ、 その整数よりも大きい数はN//2つ以上存在すればよい。(下の図、存在範囲１）

中央二つのうち右側は その整数よりも小さい数がN//2つ以上存在しかつ、 その整数よりも大きい数はN//2-1つ以上存在すればよい。(下の図、存在範囲２）

さらにここから中央値が存在しうる範囲は、 （存在範囲１の最小と存在範囲２の最小の中点）～（存在範囲１の最大と存在範囲２の最大の中点）となる。（下図、中央値の存在範囲）

ソースコード量は大したことないが偶数の考察が厄介。

def solve(N, ABs):
    starts = []
    ends = []
    for a, b in ABs:
        starts.append(a)
        ends.append(b)
    starts.sort()
    ends.sort()

    if N % 2 == 1:
        k = (N - 1) // 2
        left = starts[k]
        right = ends[-(k + 1)]
        return right - left + 1
    else:
        k = N // 2 - 1
        left1 = starts[k]
        left2 = starts[k+1]
        left_mid = abs(left2 - left1) / 2 + left1

        right1 = ends[-(k+2)]
        right2 = ends[-(k+1)]
        right_mid = abs(right2 - right1) / 2 + right1
        d = (right_mid - left_mid) * 2 + 1
        return int(d)

if __name__ == "__main__":
    N = int(input())
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, ABs))