[Yukicoder] (^^*)

http://yukicoder.me/problems/no/457

概要

  • 間に部分列^^*を含むような(と)の組み合わせの個数を求めよ。
    • reverse.tr('()',')(')なる処理を加えれば右向きを別に考えなくて良くなる。

考察

O(S2 logS)

  • (と)の組み合わせをすべて求めて、それぞれに対し、^^*が含まれることを判定します。
  • まず^^が含まれる一番左の座標を求めます。
    • その座標までに含まれる^の個数を累積和として持ち、(の座標における累積和+2を2分探索します。
  • 次に、その座標から)の座標までについて、*が含まれるかどうかを2分探索します。
  • 以上によりO(S^2 logS)となり、C++では通すことができます。
    • 本家解説によると愚直解はTLEらしいですが、2分探索に落とし込んだことが功を奏したのでしょうか。
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

#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

int solve(char *s,int len){
  vector<int>al;
  vector<int>ar;
  vector<int>ah(len);
  vector<int>ast;
  for(int i=0;i<len;i++){
      if(s[i]=='('){
          al.push_back(i);
      }else if(s[i]==')'){
          ar.push_back(i);
      }else if(s[i]=='^'){
          ah[i]++;
      }else if(s[i]=='*'){
          ast.push_back(i);
      }
  }
  for(int i=1;i<len;i++)ah[i]+=ah[i-1];
  int ret=0;
  for(auto &l:al){
      for(auto &r:ar){
          if(l>=r)continue;
          int hidx=distance(ah.begin(),lower_bound(ah.begin(),ah.end(),ah[l]+2));
          if(hidx>=r)continue;
          auto st=lower_bound(ast.begin(),ast.end(),hidx);
          if(st!=ast.end()&&*st<r){
              ret++;
          }
      }
  }
  return ret;
}
char s[10001];
int main(){
  scanf("%s",s);
  int len=strlen(s);
  printf("%d ",solve(s,len));
  reverse(s,s+len);
  for(int i=0;i<len;i++){
      if(s[i]=='(')s[i]=')';
      else if(s[i]==')')s[i]='(';
  }
  printf("%d\n",solve(s,len));
}

O(SlogS)

  • 以下、最も重いループの計算量を減らすことを考えます。
  • まず、rは単調増加であるため、st!=ast.end()&&*st<rが一度真になれば、そのループの中では常に真になります。よってキャッシュすることができます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14

for(auto &l:al){
  bool f=false;
  for(auto &r:ar){
      if(l>=r)continue;
      if(f){ret++;continue;}
      int hidx=distance(ah.begin(),lower_bound(ah.begin(),ah.end(),ah[l]+2));
      if(hidx>=r)continue;
      auto st=lower_bound(ast.begin(),ast.end(),hidx);
      if(st!=ast.end()&&*st<r){
          ret++;
          f=true;
      }
  }
}
  • さらに、hidxおよびstはrに依存しないため、ループrの外で計算しておいて問題ないことがわかります。
1
2
3
4
5
6
7
8
9
10
11
12
13
14

for(auto &l:al){
  // if hidx>=r, l>=r is assured because hidx>l.
  int hidx=distance(ah.begin(),lower_bound(ah.begin(),ah.end(),ah[l]+2));
  // if hidx==ah.size(), st==ast.end() is assured because hidx==len.
  auto st=lower_bound(ast.begin(),ast.end(),hidx);
  bool f=false;
  for(auto &r:ar){
      if(f){ret++;continue;}
      if(st!=ast.end()&&*st<r){
          ret++;
          f=true;
      }
  }
}
  • arのループはFF...FFTT...TTのようになるので、このTになる場所を2分探索できます。
1
2
3
4
5
6

for(auto &l:al){
  int hidx=lower_bound(ah.begin(),ah.end(),ah[l]+2)-ah.begin();
  auto st=lower_bound(ast.begin(),ast.end(),hidx);
  if(st==ast.end())break;
  ret+=ar.end()-lower_bound(ar.begin(),ar.end(),*st);
}
  • 最後に、範囲を狭めるためのtweakを入れます(必要ではありませんが…)。
1
2
3
4
5
6
7
8

auto ist=ast.begin();
auto ir=ar.begin();
for(auto &l:al){
  int hidx=lower_bound(ah.begin()+l,ah.end(),ah[l]+2)-ah.begin();
  ist=lower_bound(ist,ast.end(),hidx);
  if(ist==ast.end())break;
  ret+=ar.end()-(ir=lower_bound(ir,ar.end(),*ist));
}

O(S)

  • 動的計画法によりO(S)に落とせるようです。コードがより短い実装はそうなっているものが多いようです。