【AtCoder】ABC303のA,B,C,D問題をpythonで解説

ABC

Atcoder ABC303のA,B,C,D,E問題をpythonで解説(&自己理解)していきます！
(自己理解が甘い部分もあるので、その点はごめんなさい)

拙い文章で分かりづらい部分がありましたら、@EitaSugiご連絡いただけると幸いです！！

A – Similar String

問題

A – Similar Stringの考察

考えた内容の概要

この問題は、与えられた2つの文字列が「似た文字列」かどうかを判定する問題です。ここで、「似た文字列」とは、同じ位置の文字が「似た文字」であるときに限ります。そして、「似た文字」とは、以下の3つの条件のうちどれか1つを満たすときに限ります。

  1. x と y は同じ文字
  2. x と y の片方が 1 で、もう片方が l
  3. x と y の片方が 0 で、もう片方が o

考えたことの内容

この問題を解くためには、文字列の各文字を順番に比較し、それぞれが「似た文字」かどうかを判定することが必要です。そのためには、上記の3つの条件を満たすかどうかを確認する必要があります。

実装した内容

この問題の解答となるPythonコードでは、forループを用いて文字列の各文字を順番に比較しています。

そして、それぞれが「似た文字」かどうかを判定し、一致しない場合はすぐに”No”を出力してプログラムを終了します(exit())。全ての文字が「似た文字」であれば”Yes”を出力します。

A – Similar Stringのコード

N = int(input())  # 文字列の長さを入力
s = input()  # 文字列Sを入力
t = input()  # 文字列Tを入力

# 文字列の各文字を順番に比較
for i in range(N):
    # 同じ文字、または「似た文字」の条件を満たす場合は次の文字へ
    if s[i] == t[i]:
        continue
    elif s[i] == "o" and t[i] == "0":
        continue
    elif s[i] == "0" and t[i] == "o":
        continue
    elif s[i] == "l" and t[i] == "1":
        continue
    elif s[i] == "1" and t[i] == "l":
        continue
    # 一致しない場合は"No"を出力してプログラムを終了
    else:
        print("No")
        exit()
# 全ての文字が「似た文字」であれば"Yes"を出力
print("Yes")

B – Discord

問題

B – Discordの考察

考えた内容の概要

この問題は、N人がM回一列に並んで集合写真を撮ったとき、一度も連続して並ばなかった二人組が不仲である可能性があるという設定です。そのような二人組の個数を求める問題となっています。

考えたことの内容

この問題を解くためには、各撮影での並び順を確認し、連続して並んでいるかどうかを判定する必要があります。
そのためには、各撮影での並び順をリストや配列に格納し、それを順に確認していくことになります。

今回、N<50より、listを二次元配列にしてもACすることができます。なので、friendsという二次元リストを作り、隣接した場合は、それぞれのリストに追加する方針とします。

実装した内容

この問題の解答となるPythonコードでは、まず各撮影での並び順をリストに格納します。そして、そのリストを順に確認し、連続して並んでいる二人組を記録します。最後に、全ての二人組から連続して並んでいる二人組を引いた数を出力します。

B – Discordのコード

N,M = map(int, input().split())  # NとMを入力
box = []

# 各人が誰と並んだかを記録するリスト
friends =  [set() for i in range(N)]
for i in range(M):
    a = list(map(int, input().split()))  # 各撮影での並び順を入力
    for i in range(N-1):
        fre1 = a[i]
        fre2 = a[i+1]
        fre1 -= 1
        fre2 -= 1
        # 連続して並んだ二人組を記録
        friends[fre1].add(fre2)
        friends[fre2].add(fre1)

# 連続して並んだ二人組の数をカウント
cnt = 0
for i in range(N):
    cnt += len(friends[i])
# もし全員が不仲じゃないなら、cntの長さはN*(N-1)
max_freind = N*(N-1)

print((max_freind-cnt)//2)
#AとBが不仲、BとAが不仲と重複しているので/2

このコードは、各撮影での並び順をリストに格納し、それを順に確認して連続して並んだ二人組を記録することで、不仲である可能性がある二人組の数を求めています。

C – Dash

問題

C – Dashの考察

考えた内容の概要

この問題は、二次元平面上で高橋君がN回の移動を行い、その間に体力が0以下にならないようにするというものです。

高橋君の初期体力はHで、平面上にはM個の体力を回復するアイテムがあります。高橋君が移動する方向は文字列Sで与えられ、Sの各文字に応じて高橋君は上下左右に移動します。

考えたことの内容

この問題を解くためには、高橋君が移動するたびに体力が1減少すること、そして移動した地点にアイテムがある場合、高橋君の体力がK未満ならばそのアイテムを消費して体力がKになることを考慮する必要があります。

実装した内容

この問題の解答となるPythonコードでは、まず各アイテムの位置を辞書に格納します。
(そうすると、その場所にアイテムがあるかO(1)で探索できる)

そして、文字列Sの各文字に応じて高橋君を移動させ、その都度体力を1減少させます。体力が0以下になった場合、すぐに”No”を出力してプログラムを終了します。移動した地点にアイテムがある場合、高橋君の体力がK未満ならばそのアイテムを消費して体力をKにします。すべての移動が終わった後で”Yes”を出力します。

C – Dashのコード

from collections import defaultdict
items = defaultdict(int)

N,M,H,K = map(int, input().split())  # N, M, H, Kを入力
s = input()  # 移動方向を示す文字列Sを入力
box = []
for i in range(M):
    x,y = map(int, input().split())  # 各アイテムの位置を入力
    items[(x, y)] += 1  # アイテムの位置を辞書に格納
directions = {'R': (1, 0), 'L': (-1, 0), 'U': (0, 1), 'D': (0, -1)}  # 各文字に対応する移動方向

hp = H  # 高橋君の初期体力
x,y = 0,0  # 高橋君の初期位置
for i in range(N):
    dx, dy = directions[s[i]]  # 移動方向を決定
    x += dx
    y += dy    hp -= 1  # 体力を1減少
    if hp < 0:  # 体力が0以下になった場合
        print('No')  # "No"を出力してプログラムを終了
        exit()
    
    if (x, y) in items and hp < K:  # 移動した地点にアイテムがあり、体力がK未満ならば
        hp = K  # 体力をKにする
        items.pop((x,y))  # アイテムを消費
    
print("Yes")  # すべての移動が終わった後で"Yes"を出力

このコードは、高橋君がN回の移動を行い、その間に体力が0以下にならないようにする問題を解くためのものです。

事前に各アイテムの位置を辞書に格納し、高橋君が移動するたびに体力を1減少させ、移動した地点にアイテムがある場合はそのアイテムを消費して体力をKにします。体力が0以下になった場合はすぐに”No”を出力してプログラムを終了し、すべての移動が終わった後で”Yes”を出力します。

このように、この問題は二次元平面上での移動と体力管理をうまく組み合わせることで解くことができます。

D – Shift vs. CapsLock

問題

時間内に解けなかったよー、くやしい

D – Shift vs. CapsLockの考察

間違った解法

今回は、a or Shift+a を押すかの二択なので、bit全探索したいです。ですが、そうするとO(2^N)でTLEしてしまいます。困りん

考えた内容の概要

この問題は、キーボード操作の最適化に関する問題です。具体的には、’a’キー、Shiftキー、CapsLockキーの3つのキーを使って、特定の文字列を生成するための最短の時間を求める問題です。

なぜ動的計画法で解けるか？

動的計画法は、大きな問題を小さな部分問題に分割して解くアルゴリズムの設計手法です。(詳しくはこちらの記事はわかりやすいです)

具体的には、各ステップでは次に表示するべき文字とCapsLockキーのランプの状態に基づいて、最小の時間を計算します。これにより、各ステップでの最適な操作を選択することができ、全体として最小の時間を求めることができます。

この問題では、与えられた文字列を生成するための最小の時間を求めるという大きな問題を、各ステップでの最小の時間を求めるという小さな部分問題に分割して解くことができます。

したがって、この問題は動的計画法を用いて解くことが適しています。

考えたことの内容と手順

この問題を解くためには、各キーの操作にかかる時間と、それぞれのキーがもたらす結果が重要です。

まず、動的計画法用のテーブルdpを初期化します。このテーブルは2次元配列で、dp[i][j]は、i番目までの文字を処理し、CapsLockの状態がjであるときの最小時間を表します。ここで、j=0はCapsLockがOFF、j=1はCapsLockがONを表します。

次に、与えられた文字列Sの各文字について処理を行います。処理する文字が’a’の場合と’A’の場合で場合分けを行います。

‘a’の場合:

  1. CapsLockがOFFのとき(j==0)、’a’キーを押すか、CapsLockをONにしてからShift+’a’キーを押すかの最小時間を計算します。
  2. CapsLockがONのとき(j==1)、Shift+’a’キーを押すか、CapsLockをOFFにしてから’a’キーを押すかの最小時間を計算します。

‘A’の場合:

  1. CapsLockがOFFのとき(j==0)、Shift+’a’キーを押すか、CapsLockをONにしてから’a’キーを押すかの最小時間を計算します。
  2. CapsLockがONのとき(j==1)、’a’キーを押すか、CapsLockをOFFにしてからShift+’a’キーを押すかの最小時間を計算します。

最後に、最後の文字まで処理したときの最小時間を出力します。これは、dp[N][0]とdp[N][1]のうち小さい方となります。

実装した内容

この問題を解くためのアプローチは、動的計画法を使用することです。具体的には、各ステップでCapsLockキーのランプがONかOFFか、そして次に表示するべき文字が何であるかに基づいて、最小の時間を計算します。

D – Shift vs. CapsLockのコード

X, Y, Z = map(int, input().split())  # キー操作にかかる時間を入力
S = input()  # 目標となる文字列を入力
N = len(S)  # 文字列の長さを取得

# 動的計画法用のテーブルを初期化。dp[i][j]は、i番目までの文字を処理し、CapsLockの状態がjであるときの最小時間
dp = [[float('inf')] * 2 for _ in range(N+1)]
dp[0][0] = 0  # 初期状態（何も文字を処理していない）の最小時間は0
dp[0][1] = Z  # CapsLockをONにするための最小時間はZ

# 各文字について処理
for i in range(N):
    if S[i] == 'a':  # 処理する文字が'a'の場合
        # CapsLockがOFFのとき、'a'キーを押すか、CapsLockをONにしてからShift+'a'キーを押す
        dp[i+1][0] = min(dp[i+1][0], dp[i][0] + X, dp[i][1] + Z + Y)
        # CapsLockがONのとき、Shift+'a'キーを押すか、CapsLockをOFFにしてから'a'キーを押す
        dp[i+1][1] = min(dp[i+1][1], dp[i][1] + Y, dp[i][0] + Z + X)
    else:  # 処理する文字が'A'の場合
        # CapsLockがOFFのとき、Shift+'a'キーを押すか、CapsLockをONにしてから'a'キーを押す
        dp[i+1][0] = min(dp[i+1][0], dp[i][0] + Y, dp[i][1] + Z + X)
        # CapsLockがONのとき、'a'キーを押すか、CapsLockをOFFにしてからShift+'a'キーを押す
        dp[i+1][1] = min(dp[i+1][1], dp[i][1] + X, dp[i][0] + Z + Y)

# 最後に処理する文字まで処理したときの最小時間を出力
print(min(dp[N][0], dp[N][1]))

感想

動的計画法の勉強頑張ります・・・EDPCやる

コメント

タイトルとURLをコピーしました