ABC344備忘録【C~E】

はじめに

ABC344です。基本的に書いたコードをほとんどそのまま張り付けていますが、考えたことなども書いていますので是非見て行ってください。

C - A+B+C

問題

考えたこと

注目するべき制約は、

\begin{align}
1 \leq N, M, L \leq 100 ,　 1 \leq Q \leq 2 \times 10^5
\end{align}

です。これにより、$A,B,C$を3重ループしても計算量は$10^6$程度なので問題ありません。
ただし、リストYでの x in Y の計算量は$O(len(Y))$ となり、リストに結果を格納してしまうと厳しいです。そこで、setなどに結果を格納することでこの問題を解くことができます。

ACコード

C.py

n = int(input())
A = list(map(int, input().split()))
m = int(input())
B = list(map(int, input().split()))
l = int(input())
C = list(map(int, input().split()))
q = int(input())
X = list(map(int, input().split()))

sum_ = set()
for a in A:
    for b in B:
        for c in C:
            sum_.add(a + b + c)

for i in range(q):
    if X[i] in sum_:
        print("Yes")
    else:
        print("No")

D - String Bags

問題

考えたこと

$dp$です。各要素$dp[i][j]$を袋$i$までで$j$個の文字列まで一致させるための最小金額として考えるとうまくいきます。

実装時は2次元リストを思い浮かべて、どのように遷移していくかを考えていったため、画像を張り付けておきます。
図１はDP遷移式がどのように適用されていくのかを表しています。図２は入力例１の処理の流れを表しており、赤枠が答えとなります。

ACコード

D.py

t = input()
n = int(input())
len_t = len(t)
# 最小値を求めるので、float("inf")で初期化
dp = [[float("inf") for _ in range(len_t + 1)] for _ in range(n + 1)]

dp[0][0] = 0
for i in range(n):
    _, *S = input().split()
    for j in range(len_t + 1):
        # minを取らないと、遷移先を上書きしてしまう
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        for s in S:
            if j + len(s) > len_t or t[j : j + len(s)] != s:
                continue
            dp[i + 1][j + len(s)] = min(dp[i + 1][j + len(s)], dp[i][j] + 1)

print(dp[-1][-1] if dp[-1][-1] != float("inf") else -1)

E - Insert or Erase

問題

考えたこと

最初はグラフが適用できそうだと思い実装を進めていましたが、無向グラフは挿入部分で、有向グラフは削除部分で躓いてうまく実装できませんでした。

最終的には、公式解説と同じように前後の数字を持っておくように実装を進めることができました。辞書形式で格納していったので実装を楽にするため、先頭に-float("inf")、最後尾にfloat("inf")を導入しました。

図３は入力例１の2143を辞書形式で表したものです。

ACコード

E.py

n = int(input())
a = list(map(int, input().split()))
a = [-float("inf")] + a + [float("inf")]
n += 2  # 両端分を加算

# 実装を楽にするため、要素が2つのリストを持つように初期化
d = {a[i]: [-1, -1] for i in range(n)}
for i in range(n - 1):
    d[a[i]][1] = a[i + 1]
    d[a[i + 1]][0] = a[i]

q = int(input())
for _ in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        _, x, y = query
        d[y] = [x, d[x][1]]
        d[d[x][1]][0] = y
        d[x][1] = y
    else:
        _, x = query
        d[d[x][0]][1] = d[x][1]
        d[d[x][1]][0] = d[x][0]
        del d[x]

ans = [d[-float("inf")][1]]
while True:
    if d[ans[-1]][1] == float("inf"):
        break
    ans.append(d[ans[-1]][1])

print(*ans)