ferinの競プロ帳

競プロについてのメモ

codeforces #469 div2-C div1-A Zebras

問題ページ
Problem - C - Codeforces

考えたこと

  • 0と1の数からつくる01列の数特定できない?みたいになるけどできない
  • 色々試してると前から貪欲に取ればいい気持ちになる
  • 前から貪欲するのになぜかO(n^2)の方法しか思いつかない
  • 括弧列みたいに+1/-1で累積和を取って途中でマイナスになったら0が足りないので不可能
  • 後ろの方の0が足りるかの判定がよくわからない
  • 判定できても構成がわからない
  • 1を元に010をつくって合成とか次の0,1の位置を覚えておくとか色々迷走する
  • 0,1が存在する位置をそれぞれsetでもっておくと次に取れる最も近い0,1の位置を二分探索でO(logN)で求められる
  • O(NlogN)で通せそうな気持ちになったので出すと通った

謎の迷走で遅解きになってしまってつらい
終了後にtwitterで0,1をそれぞれ上、下の矢印として考えて同じ高さのものをまとめて使うのを見た
とても頭がいいし括弧列の構成とかで割と汎用性がありそう

ソースコード

本番中に自分が出したO(NlogN)のコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

ll dp[200010];
signed main(void)
{
  string s;
  cin >> s;
  int n = s.size();

  if(s[0] == '1' || s.back() == '1') {
    cout << -1 << endl;
    return 0;
  }

  set<int> zero, one;
  dp[0] = 1;
  zero.insert(0);
  FOR(i, 1, n) {
    if(s[i] == '0') {
      dp[i] = dp[i-1] + 1;
      zero.insert(i);
    } else {
      dp[i] = dp[i-1] - 1;
      one.insert(i);
    }
    if(dp[i] < 0) {
      cout << -1 << endl;
      return 0;
    }
  }

  VVI ans;
  while(zero.size()) {
    bool turn = true;
    ll now = *zero.begin();
    zero.erase(zero.begin());
    VI tmp{now};
    while(true) {
      if(turn) {
        auto itr = one.upper_bound(now);
        if(itr == one.end()) break;
        tmp.PB(*itr);
        now = *itr;
        one.erase(itr);
      } else {
        auto itr = zero.upper_bound(now);
        if(itr == zero.end()) {
          cout << -1 << endl;
          return 0;
        }
        tmp.PB(*itr);
        now = *itr;
        zero.erase(itr);
      }
      turn = !turn;
    }
    ans.PB(tmp);
  }

  if(one.size()) {
    cout << -1 << endl;
    return 0;
  }

  cout << ans.size() << endl;
  REP(i, ans.size()) {
    cout << ans[i].size() << " ";
    REP(j, ans[i].size()) cout << ans[i][j]+1 << " ";
    cout << endl;
  }

  return 0;
}

O(N)の解法

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

VI dp[200010];
signed main(void)
{
  string s;
  cin >> s;
  int n = s.size();

  if(s[0]=='1' || s.back()=='1') {
    cout << -1 << endl;
    return 0;
  }

  ll now = 0;
  dp[now].PB(0);
  FOR(i, 1, n) {
    if(s[i]=='0') {
      if(s[i]==s[i-1]) now++;
    } else {
      if(s[i]==s[i-1]) now--;
    }
    if(now < 0) {
      cout << -1 << endl;
      return 0;
    }
    dp[now].PB(i);
  }

  int cnt = 0;
  REP(i, n) {
    if(dp[i].size() == 0) break;
    if(s[dp[i].back()] == '1') {
      cout << -1 << endl;
      return 0;
    }
    cnt++;
  }

  cout << cnt << endl;
  REP(i, cnt) {
    cout << dp[i].size() << " ";
    REP(j, dp[i].size()) cout << dp[i][j]+1 << " ";
    cout << endl;
  }

  return 0;
}