[JOI精進録] 難易度5「パスタ」(第11回日本情報オリンピック 予選D)

問題リンク

atcoder.jp

問題概要

3種類のパスタがある。食分の組み合わせを考えるとき、何通りが考えられるか10000で割った余りを求めなさい。
ただし3食続けて同じパスタを食べることは出来ず、食のうち食分は何を食べるか決められている。

解説

AC解法 (100/100点)

$ dp_i_k $ を一昨日のパスタを食べ、昨日のパスタを食べ時のパターン数を10000で割った余りとして、昨日今日のパターン数として更新していきます。

ACコード

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n,k,a,b,r(0); cin >> n >> k;
  vector<int> A(n); for (int i(0);i < k;++i) (cin>>a>>b),A[a-1]=b;
  vector dp(4,vector(4,0)),res=dp;
  res[0][0]=1;
  for (auto a:A){
    swap(res,dp);
    for (int i(0);i < 4;++i) for (int k(0);k < 4;++k) res[i][k]=0;
    for (int i(0);i < 4;++i) for (int k(0);k < 4;++k) {
      if (a&&i==k&&i==a) continue;
      if (a) res[k][a]+=dp[i][k],res[k][a]%=10000;
      else for (int j(1);j < 4;++j){
        if (i==k&&i==j) continue;
        res[k][j]+=dp[i][k],res[k][j]%=10000;
      }
    }
  }
  for (int i(0);i < 4;++i) for (int k(0);k < 4;++k) r+=res[i][k],r%=10000;
  cout << r << endl;
}

提出結果

atcoder.jp