Atcoder ABC186,177 振り返り

　今までAtcoder Problemsを見て，一問もACしてないコンテストを選んでバーチャル参加してましたが，ついに今回でそのようなコンテストがなくなりました！次は灰diff, 茶diffを全て埋めます．

A - Brick【AC】

　割り算/という演算子だけでなく，//という演算子は切り捨ての割り算をしてくれます．特に，既に割り切れる割り算9÷3でも，9/3=3.0とfloat型が返ってくるが，9//3=3とint型が返ってくるのが便利です．

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

B - Blocks on Grid【AC】

　どのマスも同じ個数にするときの個数＝マスの最小の個数という所がポイントです．マスの最小値を求め，全てのマスに対し最小値との差を求めその和を出力します．

H, W = map(int, input().split())
A = []
min_a = 1 << 60
for _ in range(H):
    a = [int(i) for i in input().split()]
    min_a = min(min_a, min(a))
    A.append(a)

ans = 0
for a in A:
    ans += sum([i - min_a for i in a])

print(ans)

C - Unlucky 7【AC】

　10進数を8進数に変換するにはoct()関数を使います．この関数はstr型で返ってくるのでinをそのまま使う事が出来ます．

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【解説AC】

　ソートしても答えは変わらないと言うところがポイントでした．ソートしてi＜jの時が必ず成り立つなら，が成り立つことを使います．これが成り立つなら，を固定したときの全てのjに対する[tex: |A_i - A_j||は累積和を予め作っておくことでO(1)で求められます．累積和を使って解く方法は思い付いてましたが，ソートしても良いことに気付きませんでした……

N = int(input())
A = sorted([int(i) for i in input().split()])
cumsum_a = [0]

for a in A[::-1]:
    cumsum_a.append(cumsum_a[-1]+a)

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

print(ans)

A - Don't be late【AC】

　Dメートルを分速Sで進むときかかる時間はD/Sです．

D, T, S = map(int, input().split())
print("Yes") if D/S <= T else print("No")

B - Substring【AC】

　S<=1000と制約が小さいので，Sの部分文字列を全て列挙し，Tと異なる文字の数を数える全探索で求められます．

S = input()
T = input()
ans = 1<<60

for i in range(len(S) - len(T) + 1):
    substring = S[i:i+len(T)]
    change = 0
    for j in range(len(T)):
        if T[j] != substring[j]:
            change += 1

    ans = min(ans, change)

print(ans)

C - Sum of product of pairs【AC】

　ABC186Cとほぼ同じ問題でした．

N = int(input())
A = [int(i) for i in input().split()]
cumpro = [0]
MOD = 10**9 + 7

for a in A[::-1]:
    cumpro.append(cumpro[-1]+a)

ans = 0
for i in range(N-1):
    ans += A[i]*cumpro[-i-2] % MOD
    ans %= MOD

print(ans)

D - Friends【AC】

　初めに最終的に出力する，同じグループに友だちがいないようなグループ分けをするために必要なグループ数はどのような値になるのか考えます．同じグループに友だちがいては行けないので，3人の友だちグループがあったら，最低でも必ず3つのグループを作らないといけません．
　つまり，グループの数は友だちグループにいる人数の最大値であることが分かります．(1,2), (3,4,5), (6,7,8,9,10)だったとき，グループの人数の最大値は(6,7,8,9,10)の5人なので分けられるグループの数も5人です．
　友だちグループの管理はUnionFindを使います．友だちグループに何人の人が居るかは，parリストの値を数えれば良いです．unite時に処理を追加すればより効率良く出来そうですが，制約が2*10^5なのでこの書き方でも間に合います．

class Unionfind:
略

N, M = map(int, input().split())
uf = Unionfind(N)

for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    uf.unite(A, B)

dic = {}
for i in range(N):
    p = uf.find(i)
    dic.setdefault(p, 0)
    dic[p] += 1

ans = 0
for v in dic.values():
    ans = max(ans, v)
print(ans)