👏

ABC 229 A-D メモ

1 min read

A - First Grid

条件はYesが4パターンでNoが2パターンなのでNoを実装。

x1 = input()
x2 = input()
if x1 == ".#" and x2 == "#.":
    print("No")
elif x1 == "#." and x2 == ".#":
    print("No")
else:
    print("Yes")

B - Hard Calculation

1の位から計算すると楽。a //= 10a /= 10にすると除算のときに余りが発生し、値が途中で変化してしまうので注意。

a, b = map(int, input().split())

while a > 0 and b > 0:
    if a % 10 + b % 10 >= 10:
        print("Hard")
        exit()
    a //= 10
    b //= 10
print("Easy")

C - Cheese

問題文を読んだとき、「動的計画法だ!」と思わないこと。私はわくわくでDPを書きました。途中で気づいて全部消しましたが...。この問題は単純に1gあたりの美味しさが大きいチーズから使えばいい、という単純なもの。

N, weight = map(int, input().split())
cheese = [list(map(int, input().split())) for i in range(N)]
cheese.sort(key=lambda x: x[0], reverse=True)

result_num = 0
for value, w in cheese:
    weight -= w
    result_num += w * value
    if weight <= 0:
        result_num -= abs(weight) * value
        break
print(result_num)

D - Longest X

区間の最大、最小などのキーワードがあれば尺取り法と累積和を検討する。

s = list(input())
k = int(input())

# 累積和
cumulative_sum = [0] * (len(s) + 1)

for i, value in enumerate(s):
    if value == ".":
        cumulative_sum[i + 1] = cumulative_sum[i] + 1
    else:
        cumulative_sum[i + 1] = cumulative_sum[i]

right = 0
ans = 0
for left, value in enumerate(s):
    while right < len(s) and cumulative_sum[right + 1] - cumulative_sum[left] <= k:
        right += 1
    ans = max(ans, right - left)

print(ans)

Discussion

ログインするとコメントできます