Atcoder - ABC344 A - E まで復習解説

ABC344 A - E を復習してまとめてみました。初学者の方の参考になれば幸いです。

A - Spoiler

https://atcoder.jp/contests/abc344/tasks/abc344_a

問題文
英小文字と | のみからなる文字列 $S$ が与えられます。 $S$ は | をちょうど 2 個含むことが保証されます。
2 つの | の間にある文字および | を $S$ から削除した文字列を出力してください。

文字列 $S$ を split method で３つのリストにし | の間に当たるインデックス $1$ 以外の要素を再び join method で結合すればOKです。 ||abc みたいに | の間にデータがないときもワークするのかちょっと不安でしたが入力例にそのようなものがあり AC でしたので安心して提出しました。

S = input()
T = S.split("|")
ans = "".join([T[0], T[2]])
print(ans)

B - Delimiter

https://atcoder.jp/contests/abc344/tasks/abc344_b

Python ではあまり意識しないですがプログラミング言語だと入力が何行これから存在するかなどは入力として与えられていないと実装が煩雑になる場合があります。今回はその $N$ が与えられていない問題です。

代わりに $0$ が入力されたら終わりとみなすルールになっているので 0 が来るまで無限ループを回しましょう(実際に特定のワードが含まれたら入力を終わりとみなすというルールのフォーマットがあったりします)。

A = []
while True:
    a = int(input())
    A.append(a)
    if a == 0:
        break

for a in A[::-1]:
    print(a)

C - A + B + C

https://atcoder.jp/contests/abc344/tasks/abc344_c

数列 $A$, $B$, $C$ の大きさ $N$, $M$, $L$ がそれぞれ $1 \le N, M, L \le 100$ と小さいので愚直に for を３回回しても $a + b + c$ の計算が間に合います。

ただし $1 \le Q \le 2 × 10^{5}$ と配列 $X$ が大きいので $X$ と $a + b + c$ との比較を高速にする必要があります。例えば $a + b + c$ の値を配列 $Y$ に保存し、愚直に比較すると $O(|Y| × Q) = O(10^{6} × 2 × 10^{5} = 2 × 10^{11})$ となってしまいます。

そこで $a + b + c$ で得られる値を set で管理しましょう。各 $X_{i}$ が $a + b + c$ に含まれているかの判定が $O(1)$ でできるので全体の計算量は $O(N × N × M + Q)$ で AC できます。

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()))

S = set([])

for a in A:
    for b in B:
        for c in C:
            S.add(a+b+c)

for x in X:
    if x in S:
        print("Yes")
    else:
        print("No")

D - String Bags

https://atcoder.jp/contests/abc344/tasks/abc344_d

愚直にすべてのパターンを考えてしまうと $100^{10}$ パターンになってしまい TLE になってしまいます。

そこで

$dp[i][j] := S_{i} の袋まで考えた時、 T を j 文字目まで完成するのに必要な最小金額$

とおいて DP で解きましょう。

どのように各袋の文字を選んでもいいから、現在 $j$ 文字目でそこまでに何円かかっているかだけわかれば情報として十分ということから $dp[i][j]$ と置けそうだなと思いました。

遷移で少しめんどくさいのが大抵の DP の遷移は１つ前の $dp[i - 1][j - 1]$ からとなることが多いのですが、袋の中の文字の長さつまり $dp[i - 1][j - len(S_{i,Ai})]$ だけ遷移する点です。

for 文が３個になりますが、各袋の中に入っている文字は最大 10 個なので計算量は $O(N × |T| × 10)$ としても計算が間に合います。
(部分文字列の比較が計算コスト重くないかな？と少し不安でしたが Python でも AC しました。)

T = input()
N = int(input())
A = [input().split()[1:] for _ in range(N)]

INF = float("inf")
dp = [[INF] * (len(T) + 1) for _ in range(len(A) + 1)]
dp[0][0] = 0

for i in range(1, len(A) + 1):
    for j in range(len(T) + 1):
        # 袋の中のどの文字も追加しない場合
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        for s in A[i - 1]:
            k = len(s)
            # s がTの一部と一致し、文字を追加すする場合
            if j + k <= len(T) and T[j:j + k] == s:
                dp[i][j + k] = min(dp[i][j + k], dp[i - 1][j] + 1)

ans = dp[len(A)][len(T)]
if ans == INF:
    ans = -1
print(ans)

E - Insert or Erase

https://atcoder.jp/contests/abc344/tasks/abc344_e

あまりきれいではないのですがせっかくなのでコンテスト中にどう考えたかをまとめておきます。

まず、どういうデータ構造ならよいかを考えました。 Python の場合リストでデータを表現している場合、末尾以外のデータを削除すると計算量が高くなってしまいます。であれば「値 $x$ の直後にいれる」というワードから C++ でいう multiset がいいのかなと思いましたがよくみると値がソートされていません。

次に「毎回本当に値を消さずに「もう消えています」みたいな情報だけもたせる」とすれば消す作業はなくなり計算量が高くならなさそうと思いました。

そこで消さないで情報として残り続けるのであれば

• 各数字をノードとみなし、最初の配列が横に並んでいるイメージなら、新しく追加されるのはあるノード (以降、親ノード) に下方向にノード (以降、子ノード) が連結しているとみなせる
• ある値 $x$ のノードの index を管理する辞書を作成しておくと $O(1)$ でアクセスできる
• 子ノードの連結はあるノードと別のノードの間に連結することもある

と順に思いついていきました。

クエリ１で新たにノード $i$ が連結する時は

• 親ノード $p$ に対してまだノードが結合していない場合
  • 親ノードの子ノード： $-1$ → $i$ (まだノードがないのを $-1$ で表します)
  • ノード $i$ の親ノード： $-1$ → $p$
• 親ノード $p$ に対してすでにノード $c$ が結合している場合
  • 親ノードの子ノード： $c$ → $p$
  • ノード $i$ の親ノード： $-1$ → $p$
  • ノード $c$ の親ノード： $p$ → $i$

と、場合分けをして処理をすれば OK です。

クエリ２の処理は簡単で $x$ であるノード $i$ を消えているとみなせばOKです。

最後に、最初に横に並んでいた配列のノードを左から右に走査し消えていかなければ配列に追加していきます。ただし子ノードがある限り先に子ノードを走査します。

計算量はクエリ１ごとにノードを１つ増やしその前後の情報を更新し、クエリ２の時はノード１つの情報を更新するだけなので $O(Q)$ で十分高速です。

N: Final = int(input())
A: Final[list[int]] = list(map(int, input().split()))

# 消えたかどうか(消えたら 1 消えてないなら 0)、親ノード、子ノード、ノードの値
nodes = {}
for i, a in enumerate(A):
    nodes[i] = [0, -1, -1, a]

# ある値 x のノード番号を保存しておく、ある値 x は同時に１つしか存在しない
value_info = {}
for i, a in enumerate(A):
    value_info[a] = i

Q = int(input())
for i in range(N, N + Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        _, x, y = query
        x_idx = value_info[x]
        assert x_idx != -1
        # 値 x であるノード x_idx の子ノードとして Node i を値 y として追加
        # 現時点で子がいるなら間にいれる
        _, _, x_child, _ = nodes[x_idx]
        new_parent = x_idx
        new_child = x_child
        if x_child != -1:
            nodes[x_child][1] = i
        nodes[x_idx][2] = i
        nodes[i] = [0, new_parent, new_child, y]
        value_info[y] = i
    elif query[0] == 2:
        _, x = query
        # x を削除する
        nodes[value_info[x]][0] = 1

# 縦がある限り縦を表示し、なければ横にずれて表示するのを繰り返す。消されたのは表示しない。
ret = []
for i in range(N):
    deleted, _, child, value = nodes[i]
    if deleted == 0:
        ret.append(value)
    cur = child
    while cur != -1:
        deleted, _, child, value = nodes[cur]
        if deleted == 0:
            ret.append(value)
        cur = child

print(*ret)

実は、この様に前後の情報を持つデータ構造は双方向リストと呼ばれます(コンテスト終了後に気づきました)。
コンテスト後にせっかくなので時間をかけてクラスで実装してみました。

from typing import Any, Final, Optional
from dataclasses import dataclass, field


@dataclass
class Node:
    value: int
    parent: Optional["Node"] = field(default=None)
    child: Optional["Node"] = field(default=None)

    def get_value(self) -> int:
        return self.value

    def get_parent(self) -> Optional["Node"]:
        if self.parent is None:
            raise ValueError("parent is None")
        return self.parent

    def get_child(self) -> Optional["Node"]:
        if self.child is None:
            raise ValueError("child is None")
        return self.child

    def set_value(self, value: int) -> None:
        self.value = value

    def set_parent(self, parent: "Node") -> None:
        self.parent = parent

    def set_child(self, child: "Node") -> None:
        self.child = child

    def connect(self, parent: "Node") -> None:
        old_child = parent.child
        parent.set_child(self)
        self.set_parent(parent)
        if old_child is not None:
            self.set_child(old_child)
            old_child.set_parent(self)

    def disconnect(self) -> None:
        parent = self.parent
        child = self.child
        if parent and child:
            parent.child = child
            child.parent = parent
        elif parent:
            parent.child = None
        elif child:
            child.parent = None
        else:
            raise ValueError("Not connected")

    def __str__(self) -> str:
        if self.parent and self.child:
            return f"Node(value={self.value}, parent=Node({self.parent.value}, ...), child=Node({self.child.value}, ...)"
        elif self.parent:
            return f"Node(value={self.value}, parent=Node({self.parent.value}, ...), child=None"
        else:
            return f"Node(value={self.value}, parent=None, child=Node({self.child.value}, ...)"


N: Final = int(input())
A: Final[list[int]] = list(map(int, input().split()))
Q = int(input())

D = {}
head = Node(0)
parent = head
for i, a in enumerate(A):
    node = Node(a)
    node.connect(parent)
    parent = node
    D[a] = node

for _ in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        _, x, y = query
        parent = D[x]
        node = Node(y)
        node.connect(parent)
        D[y] = node
    elif query[0] == 2:
        _, x = query
        node = D[x]
        node.disconnect()

ret = []
cur = head
while cur.child is not None:
    cur = cur.get_child()
    ret.append(cur.value)

print(*ret)