IOI 2008 Egypt過去問 LINEAR GARDEN

Algorithm IOI

問題概要

LとPのみからなるN文字の文字列であり、どの連続した区間をとっても一方の文字が他方の文字より3文字以上多いことがないという制約を満たす文字列がひとつ与えられる。与えられた文字列が、この制約を満たす文字列のうち辞書順で何番目かを求めよ。mod Mで。

  • 1 <= N <= 1,000,000
  • 7 <= M <= 10,000,000

解法

文字列について、次のように走査することを考える。

  • はじめ、カウンタを0に設定しておく
  • 文字Lが現れたらカウンタをインクリメント
  • 文字Pが現れたらカウンタをデクリメント

すると、条件を満たす文字列はカウンタの最大値と最小値の差が2以下におさまる。これを利用する。

dp[i][lo][hi][cnt] := i文字目までが決定している文字列で、そこまで走査したときのカウンタの最小値がlo、最大値がhi、現在の値がcntであるような状況において、ここから先、文字数がNになるようにLとPを付け加えてできる「条件を満たす」文字列の数

とおいてDPするとよい。lo, hi, cnt はそれぞれ-2以上2以下なので5通りの値をとり、iはN通りの値をとるから N*5*5*5 = 125N もの部分問題ができるのでDPでよくあるメモリ節約テクニックを使う。実行時間については、lo, hi, cnt は125通りの組み合わせがあるが、そのうちhi-lo <= 2 であり lo <= cnt <= hi であるものは少ないので問題ない。

最終的な答を求めるには、例えばサンプルにある "PLPPL" なら、 "PLPL?", "PLL??", "L????" (?は任意の文字)に対応する状態のDP表の値を全て合計すればよい。

ソース

#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

struct state {
  int lo, hi, now;
};
char S[1<<20];
state T[1<<20];

int main()
{
  int N, MOD;
  int dp[2][7][7][7] = {{{{0}}}};
  scanf("%d%d", &N, &MOD);
  scanf("%s", S);
  T[0].lo = T[0].hi = T[0].now = 3;
  if(S[0] == 'L') T[0].lo = T[0].now = 2;
  else T[0].hi = T[0].now = 4;
  for(int i=1; i<N; ++i) {
    if(S[i] == 'L') {
      T[i].now = T[i-1].now-1;
      T[i].lo = min(T[i-1].lo, T[i].now);
      T[i].hi = T[i-1].hi;
    } else {
      T[i].now = T[i-1].now+1;
      T[i].lo = T[i-1].lo;
      T[i].hi = max(T[i-1].hi, T[i].now);
    }
  }
  for(int i=1; i<=3; ++i)
    for(int j=3; j<=i+2; ++j)
      for(int k=i; k<=j; ++k)
	dp[0][i][j][k] = 1;
  int sol = 0;
  for(int i=1; i<=N; ++i) {
    int p = i&1, q = 1-p;
    if(S[N-i] == 'P') {
      int lo = min(T[N-i].lo, T[N-i].now-2);
      int hi = i == N ? 3 : T[N-i-1].hi;
      int now = T[N-i].now-2;
      sol = (sol + dp[q][lo][hi][now]) % MOD;
    }
    for(int lo=1; lo<=3; ++lo) {
      for(int hi=3; hi<=lo+2; ++hi) {
	for(int now=lo; now<=hi; ++now) {
	  dp[p][lo][hi][now] = 0;
	  if(now+1-lo <= 2) // P 
	    dp[p][lo][hi][now] = (dp[p][lo][hi][now] + dp[q][lo][max(hi, now+1)][now+1]) % MOD;
	  if(hi-now+1 <= 2)  // L
	    dp[p][lo][hi][now] = (dp[p][lo][hi][now] + dp[q][min(lo, now-1)][hi][now-1]) % MOD;
	}
      }
    }
  }
  printf("%d\n", (sol+1)%MOD);
  return 0;
}