Official

C - Hurdle Parsing Editorial by physics0523


解法1: 文字列を辿って解析する

最初、文字列は | から始まります。
この最初の文字を無視したうえで、以下のように文字列を辿るとこの問題に正解できます。

  • 変数 \(c=0\) を用意する。
  • - が来たら変数 \(c\)\(1\) 加算する。
  • | が来たら \(A_i=\) (現在の) \(c\) であることがわかるので、それを記録した上で \(c=0\) と初期化する。

実装例 (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;
}

解法2: | の位置から解析する

| がある位置を \(X_1,X_2,\dots\) 文字目としましょう。このとき、 \(A_i = X_{i+1}-X_{i}-1\) です。
例えば \(S=\) |-|-|-|------| のとき \(X=(1,3,5,7,14)\) で、 \(S\) は確かに \(A=(1,1,1,6)\) から生成された文字列です。
これより、 \(X\) が求まれば \(A\) も容易に求まり、 \(X\) は for ループにより求めることができます。

実装例 (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;
}

posted:
last update: