【ABC344】緑コーダーの競プロ参加記録 #7

igasu_7

2024年3月12日 00:26

今回はAtCoder Beginner Contest 344。使用言語はPythonです。

A問題 - Spoiler

コンテスト中の提出
https://atcoder.jp/contests/abc344/submissions/51025521

英小文字と2つの '|' のみからなる文字列$${S}$$が与えられる。
'|' の外側にある文字列をくっつけて出力してね。

A問題としてはちょっと難しいです。

まず入力を受け取ります。文字列$${S}$$の1つなのでinput関数からそのまま受け取ればよいです。

""" 入力を受け取る """
S = input()

文字列$${S}$$の文字をforループで1文字ずつチェックしていきます。
'|' が 2つのみなので以下のように解くことができます。

1つ目の '|' が出てくるまで文字を答えに追加する。
1つ目の '|' が出てから2つ目の '|' が出てくるまでスルーする。
2つ目の '|' が出てから最後まで文字を答えに追加する。

答えを追加してよいかどうか判定するための変数を用意しておき、 '|' が現れるたびにその変数を更新します。

""" 問題を解く """
ans = ''
ok = True
for s in S:
    if s == '|':
        ok = not ok
    else:
        if ok:
            ans += s

Pythonでは '+' 演算子を使って文字列を連結することができます。

答えはprint関数で出力します。

""" 答えを出力 """
print(ans)

今回は「答えを追加してよいかどうか」を True / False で表し、not を使って反転しました。
1 / 0 の int で表すこともでき、その際の反転方法についてご紹介します。知っているとたまに役立ちます。

x = 1

""" 引き算で反転 """
x = 1 - x

""" XOR演算子 ^ で反転 """
x = x ^ 1

公式解説ではいろいろな解法が紹介されています。
解けた問題であっても解説を読むと新しい発見があるかもしれません。

【余談】
今回は問題になりませんが、実はPythonにおいて '+' 演算子で文字列を連結していると非常に時間がかかるケースがあります。そういった場合は、一旦リストに文字をまとめておいて後でjoinする必要があります。

""" 問題を解く """
ans = []
ok = True
for s in S:
    if s == '|':
        ok = not ok
    else:
        if ok:
            ans.append(s)

""" 答えを出力 """
print(''.join(ans))

B問題 - Delimiter

コンテスト中の提出
https://atcoder.jp/contests/abc344/submissions/51030771

$${N}$$個の整数が1つずつ$${N}$$行にわたって与えられる。
$${N}$$は入力で与えられない。
数列$${A}$$の要素のうち最後だけ 0 。$${(A_N = 0)}$$
数列$${A}$$を逆順に出力してね。

入力が$${N}$$行にわたって与えられるとのことですが、$${N}$$の値が分からないのでforループを使って入力を受け取ることができません。

ただし、$${N}$$個目の入力が$${A_N = 0}$$であることが保証されています。また$${A_N}$$以外に 0 である要素もないようです。
よって入力から受け取った値が 0 であることが、最後の入力であることのメッセージです。

0 を受け取るまで無限に入力を受け取るコードを書きます。 (無限と言っても多くて100回です。)

""" 入力を受け取る """
A = []
while True:
    a = int(input())
    A.append(a)
    if a == 0:
        break

すべての値を受け取ると$${N}$$が判明するので、$${N}$$を使って逆順に出力します。

""" forループで A を逆順に出力 """
N = len(A)
for i in range(N - 1, -1, -1):
    print(A[i])

$${N}$$を使わなくても解くことができます。
list.pop() はリストの一番後ろの要素を取り出す処理です。

""" pop() を利用して逆順に出力 """
while len(A) > 0:
    ans = A.pop()
    print(ans)

スライスでリストを反転することもできます。
print関数の sep キーワードを改行文字「 \n 」にしておくと、アンパックした各要素を改行区切りで出力してくれます。

""" スライスと sep キーワードを利用して逆順に出力 """
print(*A[::-1], sep='\n')

C問題 - A+B+C

コンテスト中の提出
https://atcoder.jp/contests/abc344/submissions/51035846

長さ$${N, M, L}$$の数列$${A, B, C}$$が与えられる。
長さ$${Q}$$の数列$${X}$$も与えられる。
$${X}$$の各要素について、$${A, B, C}$$からそれぞれ1個ずつ選んだ要素の値の和と等しくなるか出力してね。

入力が多い。

""" 入力を受け取る """
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()))

C問題は制約を確認します。
$${N, M, L \leq 100}$$、$${Q \leq 2 \times 10^5}$$です。

数列$${A, B, C}$$を全探索しようとすると$${100^3 = 10^6}$$であり、これを各$${X_i}$$について実行すると$${10^6 \times 10^5 = 10^{11}}$$となりTLEしてしまいます。

""" TLE !!! """
for x in X:
    for a in A:
        for b in B:
            for c in C:
                if x == a + b + c:
                    ans = 'Yes'

仮に、各$${X_i}$$と等しくなる「数列$${A, B, C}$$からそれぞれ1個ずつ選んだ要素の値の和」を毎回全探索できたとしても、候補として現れる和は毎回同じ顔ぶれです。

このことから「数列$${A, B, C}$$からそれぞれ1個ずつ選んだ要素の値の和」の一覧をあらかじめ確保しておいてよいです。

""" A, B, C の要素の和を全列挙 """
S = set()
for a in A:
    for b in B:
        for c in C:
            S.add(a + b + c)

そうすることで計算量はそれぞれ$${O(10^6), O(10^5)}$$となり、合計しても 2 sec に間に合いそうです。

ここで「数列$${A, B, C}$$からそれぞれ1個ずつ選んだ要素の値の和」の一覧の中に$${X_i}$$が含まれるかどうかを$${O(1)}$$で判定しなければなりません。
これは集合型の set を使うことで実現できます。

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

なお、set ではなくリストを使うと要素数$${M \leq 10^6}$$に対して$${O(M)}$$です。

今回は$${X_i}$$と等しくなる和があるかどうかの判定でしたが、問題によってはその和の個数を問われることもあります。
その場合は dict を使って個数をカウントしましょう。

""" dict を使って個数をカウント """
Cnt = defaultdict(int)
for a in A:
    for b in B:
        for c in C:
            Cnt[a + b + c] += 1

今回の問題でも和の個数が 0 個かどうかを判定して解くこともできます。

D問題 - String Bags

コンテスト中の提出
https://atcoder.jp/contests/abc344/submissions/51085257

空文字$${S}$$と、文字列がいくつか入った袋が$${N}$$個ある。
文字列$${T}$$が与えられる。
袋 1 から順番に操作をするかしないかを選ぶ。
操作: 1円を払って袋の中の文字列を1つ選んで$${S}$$の末尾に連結する。
$${S = T}$$にするための最小金額を出力してね。

情報を整理する

まず作れる文字列が何通りあるか考えます。

それぞれの袋の中には最大10個の文字列が含まれており、選ぶ方法10通りと選ばない1通りがあります。この袋が最大100袋あるので最終的な文字列$${S}$$としてあり得るものは$${11^{100}}$$通りありそうな気がします。

全探索は無理そうです。

さて、この問題のキーになるのは操作が「$${S}$$の末尾に連結」であることです。文字列$${S}$$は文字列$${T}$$の先頭から順に作るしかありません。

さらに袋 1 から袋$${N}$$まで操作は順番に1回ずつのみ行えるため、途中でそれ以前の袋から文字列を取ってくることは出来ません。

これら2つのことから、「袋$${i}$$の時点で」「文字列$${T}$$の$${k}$$文字目まで作れる」ことが確定している場合にのみ「袋$${i + 1}$$に対する操作によって」「$${k + 1}$$文字目以降を作れるか」を検討できます。

ここまで整理してみると、DPの香りがしてきます。

問われているのは作れるかどうかではなく最小金額なので、「袋$${i}$$の時点で文字列$${T}$$の$${k}$$文字目まで作れる」ときその最小金額をメモするようにします。
これを$${dp[i][k]}$$として管理します。

0 袋目の時点では 0 文字目まで 0 円で作ることができていると解釈すると$${dp[0][0] = 0}$$です。

inf = 1 << 60
M = len(T)
""" 
dp[i][k]: i 袋目の時点で T の k 文字目まで作るのにかかる費用の最小 
(i, k: 1-index)
"""
dp = [[inf] * (M + 1) for _ in range(N + 1)]
dp[0][0] = 0

いったん計算量について確認します。

袋が100個、文字列$${T}$$の長さが 100、1つの袋の中身が10個、袋の中身の文字列$${s}$$の長さが 10 なので$${100 \times 100 \times 10 \times 10 = 10^6}$$であり、素直に処理を進めても 2sec に間に合いそうです。

DPをする！

DPをする上で注意が必要なのが「袋$${i}$$の時点で文字列$${T}$$の$${k}$$文字目まで作れる」ことが確定しているとき、

袋$${i + 1}$$時点でも文字列$${T}$$の$${k}$$文字目まで作れることが確定します。
文字列$${T}$$の$${k-1}$$文字目以前が作れるとは限りません。

$${dp[i][k]}$$の情報を$${dp[i+1][k]}$$に伝達することが重要です。

inf = 1 << 60
M = len(T)
""" dp[i + 1][k] の初期化 """
for i in range(N):
    for k in range(M + 1):
        if dp[i][k] == inf:
            continue
        dp[i + 1][k] = min(dp[i + 1][k], dp[i][k])

「袋$${i}$$の時点で文字列$${T}$$の$${k}$$文字目まで作れる」ならば、袋$${i + 1}$$の中に$${T}$$の$${k + 1}$$文字目以降と一致する文字列$${s}$$があるかどうかチェックします。

""" T と s の一致判定 """
def completed(s: str, k: int):
    if k + len(s) > M:
        return False
    for j in range(len(s)):
        if T[k + j] != s[j]:
            return False
    return True

$${dp[i][k]}$$の$${i, k}$$は1-indexなのに対して、文字列$${T, s}$$の走査は0-indexであり添え字のミスに気を付けてください。

""" 一致するなら 1 円払う """
        for s in S[i]:
            if completed(s, k):
                last = k + len(s)
                dp[i + 1][last] = min(dp[i + 1][last], dp[i][k] + 1)

答えは$${dp[N][M]}$$です。ただし金額がメモされていない場合は$${S = T}$$とすることができないので -1 を出力します。

""" 答えを出力 """
if dp[N][M] == inf:
    print(-1)
else:
    print(dp[N][M])

$${T}$$の$${k + 1}$$文字目以降と文字列$${s}$$が一致するかのチェックはスライスを使うと楽になります。

for s in S[i]:
    last = k + len(s)
    if T[k:last] == s:
        dp[i + 1][last] = min(dp[i + 1][last], dp[i][k] + 1)

解説はここまでです。ありがとうございました。

E - Insert or Erase

upsolve
https://atcoder.jp/contests/abc344/submissions/51097811

長さ$${N}$$の数列$${A}$$が与えられる。
$${Q}$$個のクエリが与えられる。
クエリ 1: $${A}$$に含まれる要素$${x}$$の後ろに$${y}$$を挿入する。
クエリ 2: $${A}$$に含まれる要素$${x}$$を削除する。
$${A}$$に含まれる要素は常に相異なる。
最終的な$${A}$$を出力してね。

リストに対して挿入・削除するのはどう頑張っても1回につき$${O(N)}$$になりそうなので素直にやるわけにはいきません。

公式解説にあるように、ある要素の前と後ろの要素が何であるかを管理すれば挿入・削除を$${O(1)}$$で表現できます。
「$${A}$$に含まれる要素は常に相異なる」という条件のおかげで各要素の前後だけ管理したとしても、数列全体の並びは一意に定まります。

イメージとしてはグラフの隣接リストみたいな感じです。強連結成分分解をするときに逆向きの有向辺を考えるのと少し似ています。
先頭を -inf、末尾を inf としておきます。

""" D: 順向き、 E: 逆向き """
D = defaultdict(int)
E = defaultdict(int)
inf = 1 << 60
for i in range(N):
    if i - 1 >= 0:
        E[A[i]] = A[i - 1]
    else:
        E[A[i]] = -inf
    if i + 1 < N:
        D[A[i]] = A[i + 1]
    else:
        D[A[i]] = inf

クエリの処理は頑張ります。やってること自体は難しくないと思います。

""" クエリの処理 """
for _ in range(Q):
    t, *p = map(int, input().split())
    if t == 1:
        x, y = p
        nxt = D[x]
        D[y] = nxt
        D[x] = y
        E[y] = x
        E[nxt] = y
    else:
        x = p[0]
        prev = E[x]
        nxt = D[x]
        if prev != -inf:
            D[prev] = nxt
        if nxt != inf:
            E[nxt] = prev
        del D[x], E[x]

クエリの処理が終わったら先頭を探し出して、数列を復元します。

""" 数列の復元 """
curr = 0
for k, v in E.items():
    if v == -inf:
        curr = k
        break
ans = []
while curr != inf:
    ans.append(curr)
    curr = D[curr]
print(*ans)

以上で解けました。

クエリの処理の部分を以下のように書くとTLEになりました。

""" クエリの処理 (TLE) """
for _ in range(Q):
    t, *p = map(int, input().split())
    if t == 1:
        x, y = p
        D[y] = D[x]
        D[x] = y
        E[y] = x
        E[D[x]] = y
    else:
        x = p[0]
        if E[x] != -inf:
            D[E[x]] = D[x]
        if D[x] != inf:
            E[D[x]] = E[x]
        del D[x], E[x]

ABC341 - C に続き、dict は気を付けて使わないとなぁ…の気持ちになっています。
(参考)【ABC341】緑コーダーの競プロ参加記録 #3 - TLEはdictのせい？

あとがき

今回のコンテストの結果はABCD4完、順位は4077位、844 perf でした。

DPが苦手なせいでD問題にかなり時間をかけてしまいました。

ABC342で上振れした分をABC343、ABC344で回収していってます。
のんびり行きましょう。

ではまた～。

この文章を書いた後にARC173に参加してさらにレートを - 45 しました。

この記事が気に入ったらサポートをしてみませんか？