Codeforces334-div2C Alternative Thinking

長さの'0'と'1'で構成された文字列が与えられる．ある区間を1度だけ反転して'0'と'1'が交互となる列の長さを最大化する．

考察

まず，文字列の交互列の長さをとすると，一度の反転で最大2しか増えないことが分かる．例えば，

のように出来る．また，の時以外に，区間を反転して長さが増えないケースを考えると，そのようなケースは無いと分かる．反転する区間で01を内包している場合，反転後をその部分は10で交互列になるからである．

よって，を超えないように，+1，+2したらACが貰えた

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

#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;
  cin >> n;

  string s;
  cin >> s;

  int cnt = 0;
  bool flag = true;

  if(s[0] == '1') cnt++;

  rep(i, n) {
      if(flag) {
          if(s[i] == '1') continue;
          else {
              cnt++;
              flag = false;
          }
      } else {
          if(s[i] == '1') {
              cnt++;
              flag = true;
          } else continue;
      }
  }

  if(cnt + 2 <= n) cout << cnt + 2 << endl;
  else if(cnt + 1 <= n) cout << cnt + 1 << endl;
  else cout << cnt << endl;

  return 0;
}
Dec 15th, 2015
codeforces