AtCoder ABC371 振り返り感想戦(ほぼ緑コーダーがPythonでA〜D問題まで)

ABC371 感想まとめ

AtCoder Beginner Contest 371 - AtCoder

今回は所用によりリアルタイムでのrated参加はできず、のんびりと問題を解きました。
C問題が難しくて時間がかかった一方、D問題はあっさり解けてしまったので、本番だったら時間配分が難しかったかもしれません。
手応えとしては、100分を目一杯使ってぎりぎりD問題まで4問解けたかどうか、という感じです。
C問題のような、実装量が多い問題をサクッと解けるようになりたいですね...

A - Jiro

今回はA問題からして難しいような...。効率が良い回答が思い浮かばなかったので、素直に全パターンをif文で書きました。

AB, AC, BC = input().split()
if AB == "<":
    if BC == "<":
        print("B")
        exit()
    if BC == ">":
        if AC == "<":
            print("C")
            exit()
        else:
            print("A")
            exit()
else:
    if AC == "<":
        print("A")
        exit()
    if AC == ">":
        if BC == "<":
            print("C")
            exit()
        else:
            print("B")
            exit()

B - Taro

A問題より簡単だったような...。太郎さんがいるかどうかの判定を set(変数名 taro_set) に保存して、解きました。

N, M = map(int, input().split())
taro_set = set()
for i in range(M):
    A, B = input().split()
    if B == "M" and A not in taro_set:
        taro_set.add(A)
        print("Yes")
        continue
    else:
        print("No")

C - Make Isomorphic

これが今回の難題。Difficulty:849と、C問題としてはかなり難しめです。とにかく実装量が多かった。

解答の考え方は、例えばGの頂点 [1, 2, 3, 4, 5] があったとして、Hの対応する頂点を以下のように変化させて調べていき、コストが最小のものを求める方針でした。

[1, 2, 3, 4, 5]
[1, 2, 3, 5, 4]
[1, 2, 4, 3, 5]
....
[5, 4, 3, 2, 1]

この順列組み合わせは、 itertools.permutations() で求めています。

import itertools

N = int(input())
MG = int(input())

# Gのパスを保持
path_g = defaultdict(set)
for i in range(MG):
    u, v = map(int, input().split())
    path_g[u].add(v)
    path_g[v].add(u)

# Hのパスを保持
MH = int(input())
path_h = defaultdict(set)
for i in range(MH):
    u, v = map(int, input().split())
    path_h[u].add(v)
    path_h[v].add(u)

# コストを保持
costs = defaultdict(int)
for i in range(1, N):
    A = list(map(int, input().split()))
    for j in range(len(A)):
        costs[(i, j + i + 1)] = A[j]

# [1, 2, 3, ..., N]のリストを作成
nodes = []
for i in range(1, N+1):
    nodes.append(i)

# [1, 2, 3, ..., N]のリストを順列並び替えで全探索
answer = 10 ** 18
for v in itertools.permutations(nodes):
    cost = 0
    added = set()   # 追加の重複を防ぐためのセット
    removed = set() # 削除の重複を防ぐためのセット

    # それぞれのノードについて、GとHのパスをチェック
    for i in range(1, N+1):
        g_set = path_g[i]
        from_node = v[i-1]
        h_set = path_h[from_node]

        # Gにのみ含まれるものはコストを加算して、追加
        for g in g_set:
            to_node = v[g-1]
            if to_node not in h_set:
                f, t = min(from_node, to_node), max(from_node, to_node)
                if (f, t) not in added:
                    cost += costs[f, t]
                    added.add((f, t))

        # Hにのみ含まれるものはコストを加算して除去
        for h in h_set:
            to_node = h    
            j = v.index(h) + 1
            if j not in g_set:
                f, t = min(from_node, to_node), max(from_node, to_node)
                if (f, t) not in removed:
                    cost += costs[f, t]
                    removed.add((f, t))

    answer = min(answer, cost)

print(answer)

D - 1D Country

こちらは Difficulty408と、C問題よりかなり低くなっていました。本番だったら、C問題より先にこちらを解きたいですね。

累積和と二分探索で答えを求めました。

import bisect

N = int(input())
X = list(map(int, input().split()))
P = list(map(int, input().split()))
Q  = int(input())

# P の累積和
p_cum = [0]
for p in P:
    p_cum.append(p_cum[-1] + p)
p_cum.append(p_cum[-1])

for i in range(Q):
    L, R = map(int, input().split())

    # 2分探索でL, Rの位置を探す
    l_in_x = bisect.bisect_left(X, L)
    r_in_x = bisect.bisect_right(X, R)

    # L, R の累積和
    ans = p_cum[r_in_x] - p_cum[l_in_x]

    print(ans)