Official
C - Hurdle Parsing Editorial
by
解法2:
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: