AtCoder|ABC053:B - A to Z String

AtCoderの過去問対策です。ABCで解けなかった問題、ためになった問題のコードを備忘録として残します。

問題

B - A to Z String

解説

https://img.atcoder.jp/arc068/editorial.pdf

考え方

A は可能な限り先頭に近いものを用いるのが最適であり，Z は可能な限り末尾に近いものを選ぶのが最適なことが分かる。

解答例1

find()とrfind()を使った例。

#include <bits/stdc++.h>
using namespace std;

int main(){
  string s;
  cin >> s;
  
  int start = 0;
  int goal = 0;
  start = s.find('A') + 1;
  
  s = s.substr(start);  // Aより後ろの文字列を取得する(Aを含まない)
  goal = s.rfind('Z') + start + 1;
  cout << goal - start + 1 << endl;
}

メモ

文字の位置を取得する。

• 文字列.find(検索する文字列):前から検索する
  • 該当の文字がなかったときはstring::npos
• 文字列.rfind(検索する文字列):後から検索する
  • 該当の文字がなかったときはstring::npos

解答例2

find()とrfind()を使わない例。Aの位置とZの位置を別々に探す。

#include <bits/stdc++.h>
using namespace std;

int main(){
  string s;
  cin >> s;
  int start = 0;
  int goal = 0;
  
  // 先頭から探す
  for(int i = 0; i < s.size(); i++){
    if(s.at(i) == 'A'){
      start = i;
      break;
    }
  }
  // 末尾から探す
  for(int i = s.size()-1; i > 0; i--){
    if(s.at(i) == 'Z'){
      goal = i;
      break;
    }
  }
  cout << goal - start + 1 << endl;
}

解答例3

min()とmax()を使った例。Aの位置の最小値とZの位置の最大値を探す。

#include <bits/stdc++.h>
using namespace std;

int main(){
  string s; cin >> s;
  int begin = 200000;
  int end = 0;
  for(int i = 0, len = s.size(); i < len; i++){
    if(s.at(i) == 'A'){
      begin = min(begin, i);
    }
    if(s.at(i) == 'Z'){
      end = max(end, i);
    }
  }
  cout << end - begin + 1 << "\n";
}

参考

• C++ 文字列の位置を取得(find/rfind) | ITSakura