A - Connection and Disconnection ～ランレングス～(文字列ver, 数値ver)

ライブラリ AGC

Quiz

https://atcoder.jp/contests/agc039/tasks/agc039_a

AC Code

https://atcoder.jp/contests/agc039/submissions/7879593

ランレングス圧縮 (復元はできない)

// ランレングス
// 例 s = "aabccc" => [2, 1, 3]
VI run_length(string s){
  char prev = s[0];
  VI V;
  ll cnt = 1;
  FOR(i, 1, s.size()){
    char c = s[i];
    if(c!=prev){
      V.push_back(cnt);
      // reset
      cnt = 1;
      prev = c;
    }else{
      cnt++;
    }
  }
  V.push_back(cnt);
  return V;
}

通らない人のためのテストケース

aba
3

answer : 2

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

vector version (長さのみ)

// vector version
// [1 3 3 8 7 7 7] => [1 2 1 3]
VI run_length(VI& A){
  ll N = A.size();
  VI ret;
  ll last = A[0];
  ll cnt = 1;
  FOR(i, 1, N){
    if(A[i]==last){
      cnt++;
    }else{
      ret.push_back(cnt);
      cnt = 1;
    }
    last = A[i];
  }
  if(cnt) ret.push_back(cnt);
  return ret;
}

vector version (値と長さのペアのvector)

vector<PII> run_length(VI& A){
  ll N = A.size();
  vector<PII> ret;
  ll last = A[0];
  ll cnt = 1;
  FOR(i, 1, N){
    if(A[i]==last){
      cnt++;
    }else{
      ret.push_back({last,cnt});
      cnt = 1;
    }
    last = A[i];
  }
  if(cnt) ret.push_back({last,cnt});
  return ret;
}

文字情報付きバージョン

using P = pair<char, ll>;
// どの文字が長さいくつ
// のvectorで返す
vector<P> run_length(string& s){
  vector<P> ret;
  ll N = s.size();
  if(N==0) return ret;
  char cur=s[0];
  ll cnt=1;
  FOR(i, 1, N){
    if(s[i]==cur){
      cnt++;
    }else{
      ret.push_back(MP(cur, cnt));
      cur = s[i];
      cnt = 1;
    }
  }
  ret.push_back(MP(cur, cnt));  
  return ret;
}