ABC81 メモ

A - Placing Marbles

s1,s2,s3がそれぞれ1であれば1を足す、0であれば何もしない、ので、各文字を数字として足していく。

81A.py

s = input()

ans = 0
for i in range(3):
    ans += int(s[i])

print(ans)

B - Shift only

数列の各要素のうち、2で割り切れる回数が最小のものの、その回数が答えとなるので、各要素を2で割り切れなくなるまで割り続け、その回数が最小のものを答えとする。

計算量は$O(N\log(\max(A_i)))$より、今回の制約では十分間に合う。

81B.py

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

ans = float('inf')
for i in range(N):
    A = Alst[i]
    cnt = 0
    while A%2 == 0:
        A //= 2
        cnt += 1

    ans = min(ans, cnt)

print(ans)

C - Not so Diverse

書き換える個数を少なくしたいので、個数が多い数字は変えない方が良い。そのため、各数字の個数をカウントして、個数が多い方から$K$種類だけそのままにしておく。それ以外の数字を、数が多い数字に変更すれば良い。

よって、個数が多い方から$K$種類の数字の個数の合計を$N$から引けば良い。

計算量は$O(N)$。

81C.py

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

lst = []
N, K = map(int, input().split())
Alst = list(map(int, input().split()))

lst = [0]*(N+1)

for i in range(N):
    lst[Alst[i]] += 1

lst.sort(reverse=True)

ans = N - sum(lst[:K])
print(ans)

D - Non-decreasing

最初は、隣接する項の間で大小関係を比較して、操作を行えば良いと考えた。大小関係が逆の場合、両方とも非負なら右の項に左を足す、両方とも負ならば左の項に右の項を足す、そうでなければ絶対値の小さい方に絶対値の大きい方を二回足す、といった方法を考えた。この場合、左から順に操作をした場合、左の項を変化させた場合に条件を満たさなくなる場合がある。

全ての項が非負、または全ての項が負の場合であれば、変化する項が一方向であるので、いかにして全ての項の符号を合わせるかを考えた。このとき、絶対値が最も大きいものが正であれば、それぞれの項に足してあげれば、正にできる。逆に、絶対値が最も大きいものが負であれば、それぞれの項に足してあげれば、負にできる。

符号を揃えた後は、上の操作を行うことで、解くことができる。

81D.py

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

ans = []
M = -float('inf')
m = float('inf')
a_M = 0
a_m = 0

for i in range(N):
    if M < alst[i]:
        a_M = i
        M = alst[i]

    if m > alst[i]:
        a_m = i
        m = alst[i]


if M + m >= 0:
    for i in range(N):
        if i != a_M:
            ans.append([a_M, i])
            alst[i] += M

    for i in range(N-1):
        a_i = alst[i]
        a_j = alst[i+1]

        if a_i > a_j:
            alst[i+1] += a_i
            ans.append([i, i+1])

else:
    for i in range(N):
        if i != a_m:
            ans.append([a_m, i])
            alst[i] += m

    for i in range(N-1, 0, -1):
        a_i = alst[i-1]
        a_j = alst[i]

        if a_i > a_j:
            alst[i-1] += a_j
            ans.append([i, i-1]) 

print(len(ans))
for x, y in ans:
    print(x+1, y+1)