AOJ : 0538 - IOIOI

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0538
日本語の問題文なので省略です

アルゴリズム

「先頭からループで順番に Pn と一致したらカウント」とする方法だと、TLEになりそうな気がしたため、アルゴリズムを工夫しました。

s[i] の位置から、何回続けてIOIを繰り返すことができるかを、c[i] に格納しておきます。
あとは、配列 c の先頭から見て行って、n 以上であればカウントし、カウントした結果を出力するだけです。

c[i] の配列を作成する際は、文字列 s の後ろ側から検索していけば、O(m) で計算できます。

プログラム

#include <stdio.h>
#include <string.h>

int c[1000001];
char s[1000001];

int main(void){
  int i,j;
  int n,m,ans;

  while(scanf("%d",&n) && n){
    memset(c,0,sizeof(c));

    scanf("%d%s",&m,s);
    for(i=m-1;i>1;i--){
      if(s[i] == 'I' && s[i-1] == 'O' && s[i-2] == 'I'){
        c[i-2] = c[i] + 1;
      }
    }

    ans = 0;
    for(i=0;i<m;i++){
      if(c[i] >= n){
        ans++;
      }
    }
    printf("%d\n",ans);
  }

  return 0;
}