AtCoder Problemas Boot camp for Beginners Normal 3

問題

A - ><

思考

• >< で挟まれている値は0になる
• < の右は左より1大きい
• >の左は右より1大きい
• a[i]を0で初期化する
• 左から走査していき < の場合は a[i+1] = a[i] + 1
• 右から走査し、>の場合は a[i] = max(a[i], a[i+1] +1)

S = input()

N = len(S) + 1
a = [0 for _ in range(N)]

for i in range(N - 1):
    if S[i] == "<":
        a[i + 1] += a[i] + 1

for i in range(N - 2, -1, -1):
    if S[i] == ">":
        a[i] = max(a[i], a[i + 1] + 1)

answer = sum(a)
print(answer)

AtCoder Problemas Boot camp for Beginners Normal 2

問題

A - Irreversible operation

思考

• N<= 2* 10⁵なのでO(N)で間に合う
• BWをWBに入れ替えるのとWが左に移動していくことになる
• Wより左のBの数だけBWの組ができあがる

S = input()

answer = 0
black = 0
for s in S:
    if s == "B":
        black += 1
    else:
        answer += black
print(answer)

AtCoder Problemas Boot camp for Beginners Normal 1

問題

B - Trained?

思考

• N <= 10⁵のため、全探索が可能そう
• 愚直にボタン1から順に辿っていって、ボタン2を押せるかをシミュレーションする
• 無限ループは避けたいので、訪れたボタンは記録するようにする

N = int(input())
a = list(int(input()) for _ in range(N))

cur = 1
answer = 0
visited = {1}
while cur != 2:
    cur = a[cur - 1]
    if cur in visited:
        answer = -1
        break
    visited.add(cur)
    answer += 1
print(answer)

AtCoder Problemas Boot camp for Beginners Easy 70, 74, 81

70

問題

C - 100 to 105

思考

• Xが100の倍数の場合は、100円のおにぎりを買うことで達成できる
• Xが100の倍数でない場合は、101~105円の商品を組み合わせて達成する必要がある
  • X mod 100が1 ~ 5の足し算で作れればいいので、大きい方から順番に引い確認する
  • 合計金額 >= 引いた回数 * 100であれば達成となる

X = int(input())

m = X % 100
p = [5, 4, 3, 2, 1]

if m == 0:
    answer = 1
else:
    count = 0
    for i in p:
        while m > 0:
            if m - i >= 0:
                m -= i
                count += 1
            else:
                break
    answer = 1 if int(X / (count * 100)) > 0 else 0
print(answer)

74

問題

C - Half and Half

思考

• Aピザ + Bピザ < Cピザの場合、AピザとBピザの購入でOK
• Aピザ + Bピザ > Cピザの場合、Cピザの購入が必要
  • CピザをX, Yの小さい方の枚数 * 2枚購入する
  • 残りのピザはmin(A or Bピア, 2Cピザ)を購入する

A, B, C, X, Y = map(int, input().split())

answer = 0
if (A + B) < C * 2:
    answer = A * X + B * Y
else:
    answer += C * (min(X, Y) * 2)
    if X > Y:
        answer += min(A * (X - Y), 2 * C * (X - Y))
    elif X < Y:
        answer += min(B * (Y - X), 2 * C * (Y - X))
print(answer)

81

問題

C - *3 or /2

思考

• 2で割れなくなる終了なので、各回数で2で割るのは1回にしたい
• 値を何回3倍しても2で割れる回数は変わらない
• 元の数字が何回2で割れるかを求めてその総和をとればいい

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


def count_divisons_by_two(x):
    count = 0
    while x % 2 == 0:
        x /= 2
        count += 1
    return count


answer = sum([count_divisons_by_two(x) for x in a if x % 2 == 0])
print(answer)

AtCoder Problemas Boot camp for Beginners Easy 98~100

98

問題

A - Divide a Cuboid

思考

• A,B,Cのどれかが偶数の場合は、ブロック差なく2分割にできるので0にある
• A,B,Cが奇数の場合は、min(AxB, AxC, BxC)が回答となる

A, B, C = list(map(int, input().split()))

if A * B * C % 2 == 0:
    answer = 0
else:
    answer = min(A * B, A * C, B * C)
print(answer)5

99

問題

B - AtCoDeerくんとボール色塗り

思考

• 最初だけK通りの塗り方があり、以降はK-1通りの塗り方がある

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

answer = K * (K - 1) ** (N - 1)
print(answer)

100

問題

B - 仲良しうさぎ

思考

• N<=10⁵なので全探索できそう
• 先頭から順に相思相愛な数をカウントしてく
• A❤BとB❤Aは同じなので最後に2で割った値が解となる

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

answer = 0
for i in range(1, N + 1):
    answer += int(i == a[a[i - 1] - 1])

answer /= 2
print(int(answer))

AtCoder Problemas Boot camp for Beginners Easy 97

問題

C - Energy Drink Collector

思考

Aを小さい順にソートして、M本になるまで順番に買い集めるのが早そう。

import sys

N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

AB.sort(key=lambda x: x[0])

amount = 0
answer = 0
for ab in AB:
    for i in range(1, ab[1] + 1):
        answer += ab[0]
        amount += 1
        if amount == M:
            print(answer)
            sys.exit()

AtCoder Problemas Boot camp for Beginners Easy 96

問題

B - Similar Arrays

思考

• N <= 10以下のため全探索できそう
• Aと数列bを算出する
• Aから以下の2数列を算出する
  • A'：A[i] + 1の数列
  • A''：A[i] - 1の数列
• A, A', A''でzip処理（縦横変換）することでi番目の要素のプールを求められる
• その結果から直積を求めることですべての数列bを求めることができる
• あとは計算するのみ

import functools
import itertools
import operator

N = int(input())
A = list(map(int, input().split()))
A_plus = [x + 1 for x in A]
A_minus = [x - 1 for x in A]
answer = 0

z = list(zip(A, A_plus, A_minus))
for b in itertools.product(*z):
    product = functools.reduce(operator.mul, b, 1)
    answer += int(product % 2 == 0)
print(answer)