Codeforces354-div2C Vasya and String

Problem - C - Codeforces

High school student Vasya got a string of length n as a birthday present. This string consists of letters 'a' and '' only. Vasya denotes beauty of the string as the maximum length of a substring (consecutive subsequence) consisting of equal letters. Vasya can change no more than k characters of the original string.

長さの文字で構成された文字列が与えられる．回変更可能な時に，同じ文字で構成される部分文字列の最大長を答える．

文字 だけで構成される部分文字列を考える．区間の中に文字が 個以下ならば，その区間では全て にすることができる．これをずらしながらやっていく．文字で構成される部分文字列も同様にやり，最大値を取った． ．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
  int n, k;
  cin >> n >> k;

  string s;
  cin >> s;

  int ans = 0;

  int l = 0, r = 0, cnt = 0;
  rep(i, n) {
      r = i;
      if(s[i] == 'b') cnt++;

      if(cnt <= k) {
          ans = max(ans, r - l + 1);
      }

      while(cnt > k) {
          if(s[l] == 'b') cnt--;
          l++;
      }
  }

  l = 0, r = 0, cnt = 0;
  rep(i, n) {
      r = i;
      if(s[i] == 'a') cnt++;

      if(cnt <= k) {
          ans = max(ans, r - l + 1);
      }

      while(cnt > k) {
          if(s[l] == 'a') cnt--;
          l++;
      }
  }

  cout << ans << endl;


  return 0;
}

本番では落ちた．区間 の中のがを超えた時，というのは今見ている文字がでその文字を に変えて， をずらす，ということなので は必ず今見ている場所 となる．ということがよく整理できていなかった．反省．

May 26th, 2016
codeforces, しゃくとり法