Home / Python /

日鉄ソリューションズプログラミングコンテスト2023（AtCoder Beginner Contest 303）をPythonで解く

投稿日：　 更新日：2023/05/29

Atcoder Python

B!
Daniel AgreloによるPixabay(https://pixabay.com/)からの画像

こんにちは, Shinoryoです.

今回は日鉄ソリューションズプログラミングコンテスト2023（AtCoder Beginner Contest 303）を, Pythonで解いてみた結果を書き連ねていこうと思います.

NS Solutions Corporation Programming Contest 2023（AtCoder Beginner Contest 303） - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

目次[非表示]

A - Similar String

文字列S, Tのそれぞれi文字目同士に対して, 以下のいずれかを満たすかどうかを確認すればよいです.

  • SiとTiが同じ文字
  • SiとTiの片方が1, もう片方がi
  • SiとTiの片方が0, もう片方がo

例では, 引数に指定した要素がすべてTrueと判定されるとTrueを返すall()を用いています. 全ての0≤i<Nにおいて, S[i] == T[i] or {S[i], T[i]} == {"1", "l"} or {S[i], T[i]} == {"0", "o"}が成り立てばTrueとなり, Yesを出力します.

# 入力
N = int(input())
S = input()
T = input()
# 似た文字かの調査
ok = all(S[i] == T[i] or {S[i], T[i]} == {"1", "l"} or {S[i], T[i]} == {"0", "o"} for i in range(N))
# 出力
if ok:
print("Yes")
else:
print("No")
view raw atcoder-abc-303-a.py hosted with ❤ by GitHub

B - Discord

ある人i連続して並んで撮影したことがある人の集合をfriendiとして格納します. 最終的に, ある人iと不仲である可能性のある人の数を調べ足し上げて, 2で割ったものが答えになります.

単に足し上げるだけだと, 例えば人Aと人Bの組に関して, 人A目線と人B目線で2倍足し上げてしまうことに注意が必要です.

# 入力
N, M = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(M)]
# friend[i]：人iと不仲ではないことが確定した人のリスト
friend = [set([i]) for i in range(N + 1)]
for i in range(M):
for j in range(N - 1):
friend[a[i][j]].add(a[i][j + 1])
friend[a[i][j + 1]].add(a[i][j])
# 出力
print(sum(N - len(f) for f in friend[1:]) // 2)
view raw atcoder-abc-303-b.py hosted with ❤ by GitHub

C - Dash

基本的には以下を繰り返せばよいです.

  1. Hを−1させて実際に移動させる(現在座標を表す変数を更新する).
  2. H<0の場合, 終了.
  3. そこにアイテムがあってH<Kの場合, そのアイテムを消費してH=Kとする.

アイテムは同じ場所に存在しないことを利用して, アイテムの場所を表すリストはset()にして保存しておくと良いです. list()で保存してしまうと, inの計算に時間がかかってしまいTLEとなってしまいます.

なお, set()の要素としてリストを加えることはできないため, 例では座標の数値を文字列で結合してset()の要素に加えています.

# 入力
N, M, H, K = map(int, input().split())
S = input()
kaifuku = set(input() for _ in range(M))
# 実際に移動させる
now = [0, 0]
for i in range(N):
H -= 1
if S[i] == "R":
now[0] += 1
elif S[i] == "L":
now[0] -= 1
elif S[i] == "U":
now[1] += 1
else:
now[1] -= 1
# 体力が負になったらNo
if H < 0:
print("No")
exit()
# 今いる場所にアイテムがあるかを調べる
now_str = " ".join(map(str, now))
if now_str in kaifuku and H < K:
# アイテムを消費して体力を変更する
kaifuku.remove(now_str)
H = K
print("Yes")
view raw atcoder-abc-303-c.py hosted with ❤ by GitHub

D - Shift vs. CapsLock

動的計画法を使用します. 公式解説を引用します.

dpi,jを「i文字目まで入力した時点でCapsLockキーのランプがj=0ならばOFF, j=1ならばONである状態にするために必要な時間の最小値」として動的計画法を行います.
(出典元：https://atcoder.jp/contests/abc303/editorial/6442)
(参照：2023年5月28日)

例えば, dp0,0=0, dp0,1=Zとなります. dp1,0は「1文字目まで入力した時点でCapsLockキーのランプがOFFである状態にするために必要な時間の最小値」ですので, 1文字目がaだとすれば, dp0,0+X=Xまたはdp0,1+Y+Z=Y+2Zのどちらか小さい方が入ります.

このようにして, dpN,0, dpN,1まで計算していきます. 最終状態におけるCapsLockキーのON・OFFは問わないので, dpN,0またはdpN,1のどちらか小さい方を出力します.

# 入力
X, Y, Z = map(int, input().split())
S = input()
# 動的計画法を実行
dp = [[float("inf"), float("inf")] for _ in range(len(S) + 1)]
dp[0][0] = 0 # 初期状態
dp[0][1] = Z # 初期状態からcapslockキーを押す
for i in range(1, len(dp)):
if S[i - 1] == "a":
dp[i][0] = min(dp[i - 1][0] + X, dp[i - 1][1] + Y + Z)
dp[i][1] = min(dp[i - 1][0] + X + Z, dp[i - 1][1] + Y)
else:
dp[i][0] = min(dp[i - 1][0] + Y, dp[i - 1][1] + X + Z)
dp[i][1] = min(dp[i - 1][0] + Y + Z, dp[i - 1][1] + X)
# dp[-1][0]かdp[-1][1]のどちらか小さい方(最終的にcapslockはどちらでもよい)
print(min(dp[-1]))
view raw atcoder-abc-303-d.py hosted with ❤ by GitHub

動的計画法は, 例えば再帰的な構造を持つ問題に有効です. 問題をより小さな部分問題に分割(i文字目までの状況に分割)し, 再帰的に解を計算することで(i文字目までの結果でi+1文字目までの状況に対する解を求める), 最終的な解を得ることができるような問題です.

本ブログでも, 過去に以下のような動的計画法を用いる問題を取り扱っています.

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等