公式

C - Hurdle Parsing 解説 by en_translator


Solution 1: scan the string and analyze

The string starts with |.
After ignoring this initial character, the problem can be solved by scanning the string as follows:

  • Prepare a variable \(c=0\).
  • If you find -, add \(1\) to the variable \(c\).
  • If you find |, we find that \(A_i=\) (current) \(c\). Record that, and set \(c=0\).

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  string s;
  cin >> s;
  int c=0;
  vector<int> a;
  for(int i=1;i<s.size();i++){
    if(s[i]=='-'){
      c++;
    }
    else{
      a.push_back(c);
      c=0;
    }
  }
  for(int i=0;i<a.size();i++){
    if(i){cout << " ";}
    cout << a[i];
  }cout << "\n";
  return 0;
}

Solution 2: analyze from the positions of |

Suppose that | are at positions \(X_1,X_2,\dots\). Then, \(A_i = S_{i+1}-S_{i}-1\).
For example, if \(S=\) |-|-|-|------|, then \(X=(1,3,5,7,14)\), so \(S\) is indeed generated from \(A=(1,1,1,6)\).
Thus, once you find \(X\) you can also easily find \(A\). Here, \(X\) can be found with a for loop.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  string s;
  cin >> s;
  vector<int> x;
  for(int i=0;i<s.size();i++){
    if(s[i]=='|'){x.push_back(i);}
  }
  for(int i=1;i<x.size();i++){
    if(i>1){cout << " ";}
    cout << x[i]-x[i-1]-1;
  }cout << "\n";
  return 0;
}

投稿日時:
最終更新: