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; }