2020-12-19

【Python】パナソニックプログラミングコンテスト(ABC186) 解説

A - Brick

N, W = map(int, input().split())
print(N // W)

B - Blocks on Grid

グリッド全体の最小値に揃えるのが最適となるため, 最小値を $k$ とすると,
$A_{ij}\text{の総和} - k * H * W$
が答えとなる。

H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]

k = float('inf')
S = 0
for row in A:
    k = min(k, min(row))
    S += sum(row)

print(S - k * H * W)

C - Unlucky 7

「 $8$ 進表記」「 $10$ 進表記」それぞれで $7$ が含まるどうかを愚直にチェックする

def check(n, m):
    ''' n を m 進表記 したときに7が含まれるか調べる
    '''
    while n > 0:
        if n % m == 7:
            return False
        n //= m
    return True


N = int(input())
cnt = 0
for n in range(1, N + 1):
    if check(n, 8) and check(n, 10):
        cnt += 1
print(cnt)

D - Sum of difference

$A$ をソートして $A_1\leq\cdots\leq A_N$ とする。
このとき $i\lt j$ に対して $|A_i-A_j| = A_j-A_i$ が成り立つ。
すると, 各 $i$ について

$\sum_{j=i+1}^{N}|A_i-A_j|$
$= (A_{i+1} - A_i) + (A_{i+2} - A_i) + \cdots + (A_N - A_i)$
$= (A_{i+1} + A_{i+2} + \cdots + A_N) - (A_i + A_i + \cdots + A_i)$
$= (\sum_{j=i+1}^{N}A_j)-(N-i)A_i$
となる。

よって、累積和を用いれば上記が $\mathcal{O}(1)$ で求められる。

from itertools import accumulate


N = int(input())
A = list(map(int, input().split()))
A.sort()
S = list(accumulate(A))

ans = 0
for i, a in enumerate(A):
    s = S[N - 1] - S[i]
    r = N - (i + 1)
    ans += s - r * a
print(ans)

E - Throne

解説AC。

$S + Kx \equiv 0 \pmod{N}$ を満たす最小の非負整数 $x$ を求める問題。
$d = gcd(N, S, K)$

$n = N$ // $d$
$s = S$ // $d$
$K = k$ // $d$
とすると、

$S + Kx \equiv 0 \pmod{N}$

$\Leftrightarrow s + kx \equiv 0 \pmod{n}$
$\Leftrightarrow kx \equiv -s \pmod{n}$

ここで、 $k$ と $n$ が互いに素であれば $k$ の逆元が存在する。(参考)
よって、 $x \equiv -s * k^{-1} \pmod{n}$ と $x$ が求まる。
なお逆元はPythonであれば $k^{-1} = pow(k, -1, n)$ で簡単に得られる。

from math import gcd


T = int(input())
query = [tuple(map(int, input().split())) for _ in range(T)]
for (N, S, K) in query:
    d = gcd(gcd(N, S), K)
    n, s, k = N // d, S // d, K // d
    if gcd(k, n) == 1:  # k と n が互いに素である場合のみ解が存在する
        x = pow(k, -1, n) * (-s)  # pow関数により逆元を求める
        x %= n
    else:
        x = -1
    print(x)

F - Rook on Grid