AtCoder Regular Contest 002 C – コマンド入力 をPython3で解く

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
AtCoder Regular Contest 002 C – コマンド入力

全探索+個別にDP……なのだが、実はテストケースが甘く全探索+貪欲法でも通ってしまうらしい。ここでは、きちんとした回答を作成してみている。

# AtCoder Regular Contest 002 C - コマンド入力
# https://atcoder.jp/contests/arc002/tasks/arc002_3
# tag: DP 高橋君

# ショートカットの組み合わせを全探索する。
# 各ショートカットの組み合わせごとの最小入力回数は、
# DPを用いて求める。

# dpt[i]: i文字目までのコマンドを入力するための
# 最小ボタン入力回数、とおいてDPを行う。

# ショートカットを使用しない場合、
# dpt[i+1] = min(dpt[i+1], dpt[i]+1)

# ショートカットを使用する場合、
# dpt[i+2] = min(dpt[i+2], dpt[i]+1)

from itertools import combinations, product
def main():
N = int(input())
command = input()

# ショートカットの組み合わせを作成しておく。
# ここでは itertools.product を使用してみた。
shortcuts = [''.join(sc) for sc in product('ABXY', 'ABXY')]

result = 10**10
# ショートカット 2個の組み合わせを全探索する。
for sc1, sc2 in combinations(shortcuts, 2):
# DPで最小入力回数を求める。
dpt = [10**10] * (N+1)
dpt[0] = 0

for i in range(N):
# ショートカットを使用しない場合。
dpt[i+1] = min(dpt[i+1], dpt[i]+1)

# ショートカットを使用する場合。
if command[i:i+2] in [sc1, sc2]:
dpt[i+2] = min(dpt[i+2], dpt[i]+1)

if dpt[N] < result:
result = dpt[N]

print(result)

main()
Share

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です