AtCoder Beginner Contest 186 C問題+D問題

AtCoder Python

前書き

今回は2問が茶色以下の難易度でしたので解きました。

C問題

難易度；灰
時間：30〜40分

atcoder.jp


アルゴリズム自体はすぐに思い浮かんだのですが、再帰関数への理解が甘く時間がかかってしまいました。
再帰関数では以下の処理をしています。

  1. a%Kの剰余が7 もしくは aがKより小さくなった場合にa%Kを返す
  2. ならない場合は関数nisin()を繰り返し実行
  3. 値を返却

以下のサイトの再帰関数sum()を実行してみると挙動がわかります。
note.com

import math
N = int(input())
count = 0
 
def nisin(a,K):
  if (a%K==7) or (a<K): return a%K
  return nisin(math.floor(a/K),K)
  
for i in range(1,N+1):
  amari10 = nisin(i,10)
  amari8 = nisin(i,8)
  if (amari10==7) or (amari8==7): 
    count+=1
print(N-count)

D問題

難易度；茶
時間：30分

atcoder.jp

問題設定は2≤N≤2*10**5でした。

a-b の形の式が最大(2*10**5)*(2*10**5 -1)/2パターン考えられます。

2重ループは間に合わないので、2重ループせずに計算する方法を模索。
するとそれぞれの値は必ず(N-1)回分、計算式に出現していることがわかります。

  1. 各数字を昇順にソート（O(nlog(n))）
  2. 最大値は全て加算され、値が小さくなるにつれて減算の回数が増加、最小値は全て減算の仕組み
  3. これによりO(n)の計算量で計算可能
N = int(input())
Lis = list(map(int, input().split()))
 
Lis.sort(reverse=True)
start,sum_ = 0,0 
N -= 1
for l in Lis:
  sum_ += (-start)*l+N*l
  start += 1
  N -= 1
print(sum_)