JOI2012予選D パスタ

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

動的計画法

はじめに

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

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

問題

https://atcoder.jp/contests/joi2012yo/tasks/joi2012yo_d

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

方針

iを一日前に食べjを二日前に食べているような、n日目までのパターン数をdp[n][i][j]として表します。

一日前、二日前が存在しない場合もあるので、ダミーのパスタとして0を用います。すなわちdp[0][0][0]=1として初期化します。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
MOD = 10**4
N, K = map(int, input().split())
A = [0] * N
for k in range(K):
a, b = map(int, input().split())
A[a-1] = b
dp = [[[0]*4 for i in range(4)] for j in range(N+1)]
dp[0][0][0] = 1
for n in range(N):
for i in range(4):
for j in range(4):
for k in range(1,4):
if A[n]!=0 and A[n]!=k: # パスタが指定されているのにkが違えばスキップ
continue
if k != i or i != j: # 三日連続ではない場合
dp[n+1][k][i] += dp[n][i][j]
dp[n+1][k][i] %= MOD

ans = 0
for i in range(4): # 最終日、全ての状態の分を足す
for j in range(4):
ans += dp[-1][i][j]
ans %= MOD

print (ans)

記事情報

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