Zenn
🐙

AtCoder ABC186 個人的メモ

2020/12/20に公開
Python
競技プログラミング
AtCoder
tech

所感

abc3完
abc186score

A - Brick 

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

print(N // W)

B - Blocks on Grid

最もブロックの個数が少ないマスのブロックの数をA_{min}とする
全てのマスでA_{min}との差を計算し，その総和が答え

ブロックの個数は2次元のリストで保持する必要は無いので，1次元のリストで保持した

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

res = min(A)
print(sum([a - res for a in A]))

C - Unlucky 7

全探索

N = int(input())

ans = 0
for i in range(1, N + 1):
    if "7" in str(i):
        continue
    if "7" in oct(i):
        continue
    ans += 1

print(ans)

D - Sum of difference

Aを降順(大きい順)にソートする
こうすると，常にA_i\geqq A_jが成り立つ
ソートの前後でA_iとA_jの組み合わせは変化しないので，単純に絶対値を考えなくて良くなる
後はAの累積和を取っておけば，A_i毎にO(1)で答えが求まる

ソート気づかなかった

from itertools import accumulate

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

A.sort(reverse=True)
cumsum = list(accumulate(A))

ans = 0
for i in range(N):
    ans += A[i] * (N - i - 1) - (cumsum[-1] - cumsum[i])

print(ans)

E - Throne

公式解説通りに解説ac
https://atcoder.jp/contests/abc186/editorial/401
以下のツイートも参考にした

acはしたけど，要復習

というわけで復習した
xを答えとなる行動回数，yを正の整数とすると以下が成り立つ

Kx+S=Ny\tag{1a}

これを余剰演算に変形する

Kx+S\equiv0\ (mod\ N)\tag{2a}

これをxについて求めれば良いから，以下の様に変形できる

x\equiv -SK^{-1}\ (mod\ N)\tag{3a}

ここでK^{-1}\ (mod\ N)が存在するには，NとKが互いに素である必要がある
NとKを互いに素にするには，それぞれをNとKの最大公約数gで割れば良い
なので，(1a)式の両辺をgで割ればよい
すると，(1a)(2a)(3a)式は以下のように書き直せる

\frac{K}{g}x+\frac{S}{g}=\frac{N}{g}y\tag{1b}
\frac{K}{g}x+\frac{S}{g}\equiv 0\ \left(mod\ \frac{N}{g}\right)\tag{2b}
x\equiv -\frac{S}{g}\left(\frac{K}{g}\right)^{-1}\ \left(mod\ \frac{N}{g}\right)\tag{3b}

(3b)より，xは整数だからS/gも整数である必要がある
よって，SもN，Kと同じ様にgで割り切れなければならない
(3b)の右辺にマイナスがついているが，余剰の計算で正になるので気にしなくておｋ

以上より，以下の順で実装すればおｋ

  1. g=gcd(N,K)(NとKの最大公約数)を求める
  2. 解が存在するか(Sがgで割り切れるか)調べる
  3. N，S，Kをgで割って，xを求める

python3.8なら，余剰演算の逆元a^{-1}\ (mod\ m)はpow(a,-1,m)で求まる

from math import gcd

T = int(input())
for _ in range(T):
    N, S, K = map(int, input().split())
    g = gcd(N, K)
    if S % g:
        ans = -1
    else:
        N //= g
        S //= g
        K //= g
        ans = -S * pow(K, -1, N) % N
    print(ans)

参考

Discussion