C++で解く学生出席記録II ― 動的計画法による実装

問題概要

正の整数 n が与えられます。このとき、長さ n のすべての出席記録のうち「報酬対象（rewardable）」とみなせるものの総数を求めます。答えは非常に大きな値になる可能性があるため、10⁹ + 7 で割った余りを返します。

出席記録に使用できる文字

学生の出席記録を表す文字列には、次の3種類の文字のみを含めることができます。

• 'A' … 欠席（Absent）を表します
• 'L' … 遅刻（Late）を表します
• 'P' … 出席（Present）を表します

「報酬対象」となる条件

ある出席記録が報酬対象とみなされるのは、次の両方を満たす場合です。

• 'A'（欠席）が2回以上含まれていないこと（1回以下であること）
• 連続した 'L'（遅刻）が3回以上並んでいないこと（2回以下であること）

入力例と出力例

たとえば入力が 2 の場合、出力は 8 となります。報酬対象となる長さ2の記録は [PP, AP, PA, LP, PL, AL, LA, LL] の8通りであり、これらの中で条件を満たさないのは「AA」だけだからです。

解法の考え方（動的計画法）

この問題は、動的計画法（DP）を用いることで効率的に解けます。ポイントは、状態を「'A' を既に使用したかどうか」「末尾の 'L' の並び方」といった観点で細分化し、それぞれを独立した配列で管理することです。具体的には、サイズ n+1 の5つの配列 p、a、l、ap、al を用意します。

アルゴリズムの手順

1. 剰余演算用の補助関数 add(a, b) を定義します。この関数は ((a mod m) + (b mod m)) mod m を返します（m = 10⁹ + 7）。
2. n が 1 の場合、答えは自明に 3 通り（A, L, P）なので 3 を返します。
3. 配列の初期値を次のように設定します。
   p[0]=1, p[1]=1, p[2]=3
   a[0]=1, a[1]=1, a[2]=2
   l[0]=1, l[1]=1, l[2]=3
   ap[0]=1, ap[1]=1, ap[2]=2
   al[0]=1, al[1]=1, al[2]=2
4. i = 3 から n まで、次の漸化式に従って各配列を更新していきます。
   • p[i] = add(add(p[i-1], a[i-1]), l[i-1])
   • l[i] = add(add(p[i-1], p[i-2]), add(a[i-1], a[i-2]))
   • a[i] = add(al[i-1], ap[i-1])
   • al[i] = add(ap[i-1], ap[i-2])
   • ap[i] = add(ap[i-1], al[i-1])
5. 最後に add(add(p[n], l[n]), a[n]) を返します。これが求める答えとなります。

それでは、実際のC++による実装を見ていきましょう。

C++実装例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
public:
    lli add(lli a, lli b){
        return ( (a % m) + (b % m) ) % m;
    }
    int checkRecord(int n) {
        vector <int> p(n+1), a(n+1), l(n+1), ap(n+1), al(n+1);
        if(n == 1)return 3;
        p[0] = 1;
        p[1] = 1;
        p[2] = 3;
        a[0] = 1;
        a[1] = 1;
        a[2] = 2;
        l[0] = 1;
        l[1] = 1;
        l[2] = 3;
        ap[0] = 1;
        ap[1] = 1;
        ap[2] = 2;
        al[0] = 1;
        al[1] = 1;
        al[2] = 2;
        for(int i = 3; i <= n; i++){
            p[i] = add(add(p[i-1], a[i-1]), l[i-1]);
            l[i] = add(add(p[i-1], p[i-2]),add(a[i-1] , a[i-2]));
            a[i] = add(al[i-1], ap[i-1]);
            al[i] = add(ap[i-1], ap[i-2]);
            ap[i] = add(ap[i-1], al[i-1]);
        }
        return add(add(p[n], l[n]), a[n]);
    }
};
main(){
    Solution ob;
    cout << (ob.checkRecord(3));
}

実行結果

入力

3

出力

19

入力 n = 3 のとき、条件を満たす出席記録は合計 19 通り存在し、プログラムは正しくその値を出力しています。このようにDPの状態を適切に分割することで、全列挙を避けながら線形時間で答えを求められるのがこの手法の利点です。