AtCoder problems メモ

ただひたすらにAtCoderのCを解く

ABC100 C.*3 or /2

*3をしても/2ができる回数に関係ない

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

ans = 0
for i in A:
    while True:
        if i%2 == 0:
            ans += 1
            i /= 2
        else:
            break

print(ans)

ABC101 C.Minimization

何回かやってると(N-1)/(K-1)を繰り上げした回数が答え、実際に試すのが大事

import math

N,K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

print(math.ceil((N-1)/(K-1)))

ABC102 C.Linear Approxiamation

http://www5e.biglobe.ne.jp/~emm386/2016/distance/manhattan02.html
上記のサイトによれば、絶対和誤差を最小にするのは$b$が配列$A$の中央値の時らしい

import numpy as np

N = int(input())
A = [int(i)-j-1 for j,i in enumerate(input().split())]

ans = 0
b = np.median(A)
for i in A:
    ans += abs(i-b)

print(int(ans))

ABC103 C.Modulo Summation

全ての$a$をかけて$-1$すると全て$a_{i}-1$が割ったあまりになる

N = int(input())
A = [int(i)-1 for i in input().split()]

print(sum(A))

ABC104 C.All Green

解説AC
コンプする問題をbit全探索で定め、コンプした際の点数を足し目標点数より低いものを選ぶ。
その後、貪欲法で足りない点数を補っていき最小回数を出力すれば答え。

from itertools import permutations

D,G = [int(i) for i in input().split()]
L = [[int(i) for i in input().split()] for _ in range(D)]

ans = []
for i in range(2**D):
    tmp = 0
    index = 0
    index_li = []
    ans_tmp = 0
    for j in range(D):
        if (i >> j) & 1:
            tmp += L[j][0]*100*(j+1)+L[j][1]
            ans_tmp += L[j][0]
        else:
            index_li.append(j+1)
    if G >= tmp:
        for index in index_li[::-1]:
            p = 0
            while G > tmp:
                if p > L[index-1][0]:
                    break
                p += 1
                ans_tmp += 1
                tmp += index*100

    ans.append(ans_tmp)

print(min(ans))

ABC105 C.Base -2 Number

-2進数の問題、基本的には2進数と同じだがNを更新するときに注意が必要

N = int(input())

ans = 0
base = 1
N = -N
while N != 0:
    p = abs(N%(-2))
    N = (N+p)//(-2)
    ans += p*base
    base *= 10
    
print(ans)

ABC106 C.To Infinity

2の5000兆乗はKの上限を余裕で超えるので出力されるのは1 or Sの2文字目しかない。
コーナーケースにしっかり注意しよう！(戒め）

S = input()
K = int(input())

if K == 1:
    print(S[0])
    exit()
else:
    for i in range(K):
        if S[i] != '1':
            print(S[i])
            exit()
print(1)

ABC107 C. Candles

連続するK個取り出した際に、かかる時間の求め方は結局3通りなので全探索

N,K = [int(i) for i in input().split()]
X = [int(i) for i in input().split()]

ans = 10**9
for i in range(N-K+1):
    l = X[i]
    r = X[i+K-1]
    if l < 0 and r <= 0:
        tmp = -l
    elif l >= 0 and r > 0:
        tmp = r
    else:
        tmp = min(abs(l),r)*2 + max(abs(l),r)
    ans = min(ans,tmp)
print(ans)

ABC109 C. Skip

リストにXを追加し各要素ごとの距離の最大公約数をだせば答え

N,X = [int(i) for i in input().split()]
L = [int(i) for i in input().split()]

if N == 1:
    print(abs(L[0]-X))
else:
    P = [0]*N
    P[0] = abs(min(L) - X)
    for i in range(1,N):
        P[i] = abs(L[i]-L[i-1])

    def gcd( x, y ):
        while y != 0:
            x, y = y, x%y
        return x

    ans = gcd(P[0],P[1])

    for i in range(2,N):
        ans = gcd(ans,P[i])

    print(ans)