AtCoder ABC396 振り返り(緑コーダーがPythonでABCD問題)

AtCoder ABC396 振り返り

今回はABCDまでの4問回答でした。レーティング的には微増になり、良い結果だったと思います。
E問題以降も解けそうな気もするのですけども、時間をかけて考えても結局は刃が立たないので、今後の課題です。

A - Triple Four

Aの先頭から、3連続で同じ文字があるかチェックしていきます。

N = int(input())
A = list(map(int, input().split()))
for i in range(N-2):
    # 3連続で同じ数字があるかチェック
    if A[i] == A[i+1] == A[i+2]:
        print("Yes")
        exit()
print("No")

B - Card Pile

• 操作1 カードの山の一番上に積み重ねる
• 操作2 カードの山の一番上のカードを取り除く

という操作があるので、これはスタックを使うと良いとわかります。B問題でスタックを使う問題が出るのは珍しい感じがします。(配列で解いても良いかもしれません)

Q = int(input())
que = deque() # 両面キューをスタックとして使う

# カードの山の初期化
for i in range(100):
    que.append(0)

for i in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        # 操作1 カードの山の一番上に積み重ねる
        que.append(query[1])
    else:
        # 操作2 カードの山の一番上のカードを取り除き、出力
        p = que.pop()
        print(p)

C - Buy Balls

B、Wともに数字が大きいものから選んでいくと、より価値を得られることがわかります。そのため、B, Wを降順でソートしておくと良いです。

また、B, Wそれぞれの累積和を求めておくと、i個選んだときの最大の価値を計算量少なく求められます。

答えの出し方としては、まずBを何個選ぶか for ループで固定します。
B から i 個を選ぶ場合、Wを何個選べばいいかは、min(i, count_plus_w)個選ぶと最大の価値になります(count_plus_w は、Wの中でプラスの価値を持つ個数)。

N, M = map(int, input().split())
B = list(map(int, input().split()))
W = list(map(int, input().split()))

# B, Wを降順にソート
B.sort(reverse=True)
W.sort(reverse=True)

# B, W の累積和を求める
ruiseki_b = list(itertools.accumulate(B))
ruiseki_w = list(itertools.accumulate(W))

# Wの中で0より大きい価値の個数を数える
count_plus_w = 0
for i in range(M):
    if W[i] > 0:
        count_plus_w += 1
    else:
        break

answer = 0
# Bをi(0からN)個選んだときの最大値を求める
for i in range(N):
    sum_b = ruiseki_b[i]
    sum_w = 0
    if count_plus_w == 0:
        answer = max(answer, sum_b)
        continue
    else:
        # Wは、min(i, count_plus_w)個選んだときが最大
        sum_w = ruiseki_w[min(i, count_plus_w - 1)]
        answer = max(answer, sum_b + sum_w)
    
print(answer)

D - Minimum XOR Path

以下の方針で解きました

手順1: 1からNまでのルートを、深さ優先探索で全て求めます。
手順2: その後、各ルートについてコストを計算して、最小値を求めました。

本来なら手順1、2を一緒にやってしまえば良いのですが、今回は N < 10 と頂点数が少ないので、多少無駄でもわかりやすく書くために分けました。

ただ、コードが長くなってしまい、逆に時間がかかってしまったかもしれません...。

N, M = map(int, input().split())
path = defaultdict(list)
for i in range(M):
    u, v, w = input().split()
    u = int(u)
    v = int(v)
    path[u].append((v, w))
    path[v].append((u, w))

route = [] # 1からNまでのルートを格納する
current = 1

# 深さ優先探索で1からNまでのルートを求める
def dfs(v, visited_list):
    visited_list.append(v)
    # Nに着いたら、1からNまでのルートを格納
    if v == N:
        route.append(visited_list) 
        return

    # 次の頂点に進む
    for next in path[v]:        
        if next[0] not in visited_list:
            dfs(next[0], visited_list.copy())

dfs(1, [])

# ルートを与えると、コストを計算する
def calc_cost(route):
    if len(route) <= 1:
        return 0
    
    # コストだけを配列を作成する
    cost_array = []
    for i in range(len(route) - 1):
        current = route[i]
        nexts = path[current]
        for next in nexts:
            next_node = next[0]
            cost = int(next[1])
            if next_node == route[i + 1]:
                cost_array.append(cost)
        
    # 各コストのXORを取る
    cost = cost_array[0]
    for i in range(1, len(cost_array)):
        cost = cost ^ cost_array[i]
    return cost

# 各ルートのコストを計算し、最小のものを求める
answer = INF
for r in route:
    cost = calc_cost(r)
    answer = min(answer, cost)

print(answer)