TopCoder SRM618 DIV1 MEDIUM - LongWordsDiv1

Source

TopCoder SRM618 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

$N$ 文字の文字からなる文字列のうち,以下の条件1~3.を満たすものがいくつ有るかを ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題.

  1. 同じ文字は連続しない
  2. $X,Y$ を(異なるとは限らない)文字として,$XYXY$ を部分列として持たない
  3. 上の $2$ 条件を満たす文字列の中で,最も文字数が多い

解法

文字は $N$ 文字全部使わないと最長にならないので,$N$ 文字を使う.
どの順番で文字を使うかを固定して,後で $N!$ を掛けることにする.
全探索して観察してみると,最長の文字列の長さは $2N-1$ で,その数は $M_{N-1}$ であることが見て取れる.
ここで,$\{M_k\}_{k=0}^\infty$ はMotzkin数の数列を表す.
Motzkin数は,$M_0=M_1=1$ を初期値として漸化式
 $\displaystyle M_n = M_{n-1} + \sum_{k=0}^{n-2} M_k M_{n-2-k}$

 $\displaystyle M_n = \frac{ (2n+1) M_{n-1} + (3n-3) M_{n-2}}{n+2}$
を満たすので,これを用いると計算できる.
時間計算量は $1$ つ目の漸化式を用いると $O(N^2)$ で,$2$ つ目を使うと $O(N)$ 程度.
何故こうなるかというと,結果を知っていれば帰納法で確認できる.
最初の文字を $A$ とすると,まず条件2.から $A$ は高々 $3$ 回しか使えない.
$3$ 回使うとして,文字列を $AX_1AX_2AX_3$ とすると,$X_1,X_2,X_3$ は $1$ つでも同じ文字を使ってはいけない.(使うと,$XYXY$ が作れる)
また,$X_1,X_2$ は空文字列であってはいけない.
すると,$X_1,X_2,X_3$ に使える文字を振分って,$X_1,X_2,X_3$ も条件1~3.を満たすように作れば良いが,最長の長さが $2N-1$ であるので,$X_3$ は空であるべき.
(部分に別れる数が少なければ少ないほうが,最終的に長い文字列が作れる)
また,$A$ を $2$ 回しか使わないなら,$AX_1AX_2$ となるが,同様に $X_2$ は空文字列でなければいけない.
そこで,$AXAYA$ か $AXA$ というパターンになり,$X,Y$ に何文字ずつ振り分けるかを考えると,Motzkin数の $1$ つ目の漸化式が出てきて,結果的に正しいことがわかる.

C++によるスパゲッティなソースコード

// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define M 1000000007
#define ll long long

class LongWordsDiv1 {
public:
int count(int n) {
  int i, j, k;
  ll arr[5100] = {1,1,2,4,9};
  ll res;

  REP(i,5,5100){
    arr[i] = arr[i-1];
    rep(j,i-1) arr[i] = (arr[i] + arr[j] * arr[i-2-j])%M;
  }

  res = arr[n-1];
  rep(i,n) res = (res * (i+1))%M;

  return res;
}

}

C++によるスパゲッティなソースコード($O(N)$)

// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define M 1000000007
#define ll long long

template<class T>
void getMotzkinListSlow(int n, T res[], int md){
  int i, j;
  res[0] = res[1] = 1 % md;
  REP(i,2,n){
    res[i] = res[i-1];
    rep(j,i-1) res[i] = (res[i] + (ll)res[j] * res[i-2-j]) % md;
  }
}

template<class T>
void getInverseList(int n, T res[], int md){
  int i;
  res[1] = 1;
  REP(i,2,n) res[i] = md - ((ll)(md/i)*res[md%i]%md);
}

template<class S, class T>
void getMotzkinList(int n, S res[], T inv[], int md){
  int i;
  res[0] = res[1] = 1 % md;
  REP(i,2,n){
    res[i] = (((ll)(2*i+1)*res[i-1] + (ll)(3*i-3)*res[i-2]) % md) * inv[i+2] % md;
  }
}

class LongWordsDiv1 {
public:
int count(int n) {
  int i, j, k;
  int inv[5100], arr[5100];
  ll res;

  // getMotzkinListSlow(n+1, arr, inv, M);
  getInverseList(n+4, inv, M);
  getMotzkinList(n+1, arr, inv, M);

  res = arr[n-1];
  rep(i,n) res = (res * (i+1))%M;

  return res;
}

}

Current time: 2017年07月23日15時41分02秒
Last modified: 2014年05月10日03時23分17秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM618 SRM_Div1_Medium
トップページに戻る

Logged in as: unknown user (not login)

ログイン: