パ研杯2019 3D パ研軍旗

この記事で使うアルゴリズム

動的計画法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_d

この問題は動的計画法を用いて解くことができます。

方針

左の列から順に評価をしていきます。n列目の色がcであるとき、塗り替えの最小値をdp[n][c]として記録します。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N = int(input())
S = []
col = {'R':0, 'B':1, 'W':2, '#':-1}
for i in range(5):
s = input()
ls = list(s)
ls = [-1] + [col[e] for e in ls] # 最も左の列にダミーを入れて奥
S.append(ls)
dp = [[0]*3 for _ in range(N+1)]



for n in range(N):
for i in range(3):
cnt = 0
for j in range(5):
cnt += (S[j][n+1] != i)
K = [0,1,2]
K.remove(i) # 同じ色は隣合えない
dp[n+1][i] = min(dp[n][K[0]] + cnt, dp[n][K[1]] + cnt)
print (min(dp[-1]))

記事情報

  • 投稿日:2020年6月12日
  • 最終更新日:2020年6月22日