CFR 795 J. Stepan's Series ( Ad hoc )

Problem - J - Codeforces

題意：
給一個長度為 N 的字串，由 "YN?" 組成。'?' 有可能為 'Y'，有可能為 'N'。給定一個 K，問是否有可能存在一個連續 'N' 子字串長度恰為 K。注意連續 'N' 子字串必須是最大的，也就是左界左邊和右界右邊的元素必須為 'Y'。

制約：
The first line contains two integers n and k (1 ≤ n ≤ 100, 0 ≤ k ≤ n) — the number of episodes in the series and the dissatisfaction which should be checked.
The second line contains the sequence which consists of n symbols "Y", "N" and "?". If the i-th symbol equals "Y", Stepan remembers that he has watched the episode number i. If the i-th symbol equals "N", Stepan remembers that he hasn't watched the epizode number i. If the i-th symbol equals "?", Stepan doesn't exactly remember if he has watched the episode number i or not.

解法：
先檢查是否有連續的 N，其長度大於 k，若存在則答案為 "NO"。
否則檢查是否有任一個以 i 為左界的長度為 k 的區間不存在 'Y'，且 S[ i - 1 ] 和 S[ i + k ] 都不為 'N'，若存在則答案為 "YES"，否則 "NO"。

時間 / 空間複雜度：
O( N )

package main 

import "fmt"

func Max( x, y int ) int { // math.Max() は問題を起こすらしい。。。
  if x > y {
    return x
  }
  return y
}

func main() {
	var N, K int
	fmt.Scan( &N, &K )
	var S string
	fmt.Scan( &S )
	ypfx := make( []int, N + 1, N + 1 ); // type, length, capacity
	npfx := make( []int, N + 1, N + 1 );
	qpfx := make( []int, N + 1, N + 1 );
	for i := 0; i < N; i++ { // seems like go does not support ++i.....
	  ypfx[ i + 1 ] = ypfx[ i ];
	  npfx[ i + 1 ] = npfx[ i ];
	  qpfx[ i + 1 ] = qpfx[ i ];
	  if( S[ i ] == 'Y' ) {
	    ypfx[ i + 1 ]++;
	  } else if( S[ i ] == 'N' ) {
	    npfx[ i + 1 ]++;
	  } else {
	    qpfx[ i + 1 ]++;
	  }
	}
	original_max := 0;
	for i := 0; i < N; i++ {
	  if( S[ i ] != 'N' ) { // syntax error: missing { after if clause えええええ
	    continue;
	  }
	  j := i;
	  for j < N && S[ j ] == 'N' { // while() はだめなんかい！！
	    j++;
	  }
	  original_max = Max( original_max, j - i );
	  i = j;
	}
	if( original_max > K ) {
	  fmt.Println( "NO" );
	  return;
	}
	for i := 0; i + K <= N; i++ { // i を左界とする長さ K の区間を調べる
	  if( ypfx[ i + K ] - ypfx[ i ] > 0 ) { // ええええ -> line: 34
	    continue;
	  }
	  if( i - 1 >= 0 && S[ i - 1 ] == 'N' ) {
	    continue;
	  }
	  if( i + K < N && S[ i + K ] == 'N' ) {
	    continue;
	  }
	  fmt.Println( "YES" );
	  return;
	}
	fmt.Println( "NO" );
}