ABC 120 C - Unification (300)

stack の上 個をまとめて扱う問題(上2個比較して条件満たすなら 2個まとめて取り出すみたいな) で毎回めんどくさい実装をしていた気がするのでそれをサボるためのメモ

問題

0と1のみで構成された列が与えられます。
隣接した0と1を消す操作が行えるとき、最大で何回の操作ができるか出力しなさい。

本質的な解法

0と1が両方存在するときは必ずどこかで隣接している

本質的なコード

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

int main() {
  string S;
  cin >> S;

  vector<int> cnt(2);
  for (int i = 0; i < S.size(); ++i) {
    cnt[S[i] == '1']++;
  }

  cout << 2 * min(cnt[0], cnt[1]) << endl;
}

stackを用いた非本質的な解法

stack使ってシミュレーションするだけで解ける

stackを用いた非本質的なコード

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

int main() {
  string S;
  cin >> S;

  int ans = 0;


  stack<bool> st;
  for (int i = 0; i < S.size(); ++i) {
    st.push(S[i] == '1');

    while (st.size() >= 2) {
      int a = st.top();
      st.pop();
      int b = st.top();
      st.pop();

      if (a != b)
        ans += 2;
      else {
        st.push(b);
        st.push(a);
        break;
      }
    }
  }

  cout << ans << endl;
}

非本質の本質

vectorはランダムアクセス可能なstack！（素振り）

— beet (@beet_aizu) 2019年3月3日

非本質の本質のコード

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

int main() {
  string S;
  cin >> S;

  int ans = 0;

  vector<int> st;
  for (int i = 0; i < S.size(); ++i) {
    st.push_back(S[i] == '1');

    while (st.size() >= 2) {
      int sz = st.size();
      if (st[sz - 1] != st[sz - 2]) {
        ans += 2;
        st.pop_back();
        st.pop_back();
      } else {
        break;
      }
    }
  }

  cout << ans << endl;
}