SRM618D1Med LongWordsDiv1

• July 22, 2016
• TopCoder

こういうのは大得意

問題概要(原文)

$N$ 種類の文字がある．以下の条件を満たすような文字列は何通りあるか？ MOD $10^9+7$ で求めよ．

1. 同じ種類の文字は隣り合わない
2. 部分列として $xyxy$ となるような文字の組合せ $x,y$ が存在しない( $x=y$ も許される)．
3. 上の条件を満たす，より長い文字列は存在しない

考察

条件 $2$ より同じ種類の文字は $3$ つ以下しか含まれず． $\text{A} x \text{B} y \text{A} z \text{B}$ のような文字列は答えに含まれない．

$N=1$ のときはサンプルで与えられるように自明である．以降 $N \geq 2$ を仮定する．

'A' を現在着目しているアルファベット，$x$ を 'A' を含まない文字列とする． $\text{A}x$ という文字列が答えに含まれることはない．

つまり，必ず $\text{A} x \text{A}$ のような形式か， $\text{A} x \text{A} y \text{A}$ のような形式となる． ここで $x$ と $y$ に同じ種類の文字が含まれることはない(あるとすると条件 $2$ に矛盾)．

さらに実験すると，どちらを選んでも，　$x,y$ で用いられるアルファベットの数をどのように変化させても結局同じ長さになることが分かる．

両端の文字から決めていくDPを考える．$A,B,C\ldots$ という順で両端が埋められていくことにする．

$DP[n]=$ $n$ 種類の文字が使えるときにvalidな文字列の通り数，が求まればよい． 遷移は先程述べたように $2$ 通りしかなく以下のように表せる．最後にアルファベットの使い方の通り数である $N!$ をかけた値が答え．

$DP(n) = DP(n-1) + \sum_{i=1}^{n-2}DP(i)DP(n-1-i)$

計算量は $O(N^2)$

ソースコード

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class LongWordsDiv1
{
    public int count(int n)
    {
        const long MOD = 1000000007;
        var dp = new long[n + 1];
        for (int i = 0; i <= n; i++)
            dp[i] = -1;
        dp[0] = 0;
        dp[1] = 1;
        Func<int, long> dfs = null;
        dfs = N =>
          {
              if (dp[N] >= 0) return dp[N];
              //A dp[N-1] A
              long ret = dfs(N - 1);
              //A dp[i] A dp[N-1-i] A
              for (int l = 1; l < N - 1; l++)
                  ret = (ret + dfs(l) * dfs(N - 1 - l)) % MOD;

              return dp[N] = ret;
          };
        var ans = dfs(n);
        for (int i = 1; i <= n; i++)
            ans = (ans * i) % MOD;
        return (int)ans;
    }

}

コメント

• 条件を整理すると単純なDPに落ちる
• 考察よりで実装は単純

• dynamic-programming

• Twitter