保存されている過去のバージョンの一覧

2014年05月10日03時23分17秒
2014年04月26日06時56分28秒
2014年04月26日06時36分32秒

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: 2024年04月26日04時48分54秒
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)

ログイン：