AtCoder ABC 464 振り返り (PythonでABCD問題)

ABC464を振り返ります

今回もリハビリ目的でunrated参加です。
結果はABCDまで4問解答でした。
意外と解けるものですね...今後ぼちぼちとRatedにしていくかもしれません。

A - Decisive Battle

素直に、文字列中のWとEの数をカウントしました。

S = input()

w = 0 # Wの数
e = 0 # Eの数

for i in range(len(S)):
    if S[i] == "W":
        w += 1
    else:
        e += 1

if w < e:
    print("East")
else:
    print("West")

B - Crop

上下左右各方向から、# が存在するかしないかを探索しました。
for ループが上下左右4つぶん書いてある、力技です。
綺麗な解法ではないので、あまり真似をしないほうが良いでしょう。

H, W = map(int, input().split())
C = []
for h in range(H):
    row = list(input())
    C.append(row)

top = 0 # 上から何行を削れるか
bottom = H # 下から何行を削れるか
left = 0 # 左から何列を削れるか
right = W  # 右から何列を削れるか

# 上から下へ探索
for i in range(H):
    row = C[i]
    exist = False

    for j in range(len(row)):
        c = C[i][j]

        # "#"があったらそこで終了
        if c == "#":
            exist = True
            break
            
    if exist == False:
        top = i + 1
    else:
        break

# 下から上へ探索
for i in range(H-1, -1, -1):
    row = C[i]
    exist = False

    for j in range(len(row)):
        c = C[i][j]
        # "#"があったらそこで終了
        if c == "#":
            exist = True
            break
    if exist == False:
        bottom = i 
    else:
        break

# 左から右へ探索
for x in range(W):
    exist = False
    for y in range(H):
        c = C[y][x]

        if c == "#":
            exist = True
            break
    if exist == False:
        left = x + 1
    else:
        break

# 右から左へ
for x in range(W-1, -1, -1):
    exist = False
    for y in range(H):
        c = C[y][x]

        if c == "#":
            exist = True
            break
    if exist == False:
        right = x 
    else:
        break

# 回答を出力
for i in range(top, bottom):
    ans_row = []
    for j in range(left, right):
        ans_row.append(C[i][j])
    print("".join(ans_row))

C - Plumage Palette

dictionaryをうまく使って、ループ回数を削減するのがポイント。
あと、D日目の色の変化を、うまいこと配列で表現して解きました。

from collections import defaultdict

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

count = defaultdict(int) # 現在の色数の情報 [key=色, value=数]
query = [[] for i in range(M+10)] # D日目に実行するクエリをまとめる

for n in range(N):
    A, D, B = map(int, input().split())

    count[A] += 1 # スタート時点での色の数をカウント
    query[D].append([A, B]) # D日後に 色Aを-1, 色Bを+1 する

for m in range(1, M + 1):
    # m日目に色が変わる鳥を処理
    q = query[m]
    for i in range(len(q)):
        # 色Aを-1, 色Bを+1
        A, B = q[i]
        count[A] -= 1
        count[B] += 1

        # 鳥の数が0になったら、dictから除く
        if count[A] == 0:
            count.pop(A)

    # dictのキーの数 = 色の数
    print(len(count))

D - Celester

典型的なDP(動的計画法)の問題っぽいので、そのように解きました。

def calc_dp(n, s, x, y):
    # S=0, D=1 として、0〜n回まで実施時のスコアを記録する配列。
    dp = [[0 for j in range(2)] for i in range(n + 10)]

    for i in range(1, n + 1):
        weather = s[i-1]
        prev_s = dp[i-1][0] # 前回がSだった場合の最高スコア
        prev_r = dp[i-1][1] # 前回がRだった場合の最高スコア

        # i回目をSで終える場合のスコアを計算
        change_s = 0
        if weather == "S":
            change_s = 0
        else:
            # 天気をSに変更する場合のコスト
            change_s = x[i-1]

        # 前回W→今回S の場合、ボーナス点が入る
        bonus = y[i-2] if i > 1 else 0
        dp[i][0] = max(prev_s - change_s, prev_r - change_s + bonus)

        # i回目をRで終える場合のスコアを計算
        change_r = 0 
        if weather == "R":
            change_r = 0
        else:
            # 天気をRに変更する場合のコスト
            change_r = x[i-1]
        prev_max = max(prev_s, prev_r)

        dp[i][1] = prev_max - change_r
    
    return max(dp[n][0], dp[n][1])

# 入力から答えを求める                
T = int(input())
for i in range(T):
    N = int(input())
    S = input()
    X = list(map(int, input().split()))
    Y = list(map(int, input().split()))

    # 答えを計算して出力
    print(calc_dp(N, S, X, Y))