Educational Codeforces Round 60 D. Magic Gems
解法
dp[i]=(i個分スペースを埋める方法が何通りあるか)としたDPを考える。i個スペースを埋めるためにはmagic gemを一つ置くパターンとmagic gemを分割しnormal gemをM個置くパターンがある。したがってこのDPの遷移は
- dp[i] = dp[i-m] + dp[i-1] (i >= m)
- dp[i] = 1 (i < m)
となる。N<=10^18なので普通にDPをすることはできないがこの漸化式は行列累乗を用いることN項目をO(M^3logN)で求めることができ解けた。
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #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() 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<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } 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<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; using vec = vector<ll>; using mat = vector<vec>; // A*Bを計算 mat mul(mat &A, mat &B) { mat C(A.size(), vec(B[0].size())); for(int i=0; i<(int)A.size(); ++i) { for(int k=0; k<(int)B.size(); ++k) { for(int j=0; j<(int)B[0].size(); ++j) { C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % MOD; } } } return C; } // A*Bを計算 vec mul(mat &A, vec &B) { vec C(A.size()); for(int i=0; i<(int)A.size(); ++i) { for(int j=0; j<(int)B.size(); ++j) { C[i] = (C[i] + A[i][j]*B[j]) % MOD; } } return C; } // A^nを計算 m*m行列のn乗はO(m^3logn) mat pow(mat A, ll n) { mat B(A.size(), vec(A.size())); for(int i=0; i<(int)A.size(); ++i) B[i][i] = 1; while(n > 0) { if(n & 1) B = mul(B, A); A = mul(A, A); n >>= 1; } return B; } signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n, m; cin >> n >> m; if(n == m) { cout << 2 << endl; return 0; } if(n < m) { cout << 1 << endl; return 0; } mat a(m, vec(m)); a[0][0] = 1, a[0][m-1] = 1; REP(i, m-1) a[i+1][i] = 1; vec b(m, 1); b[0] = 2; a = pow(a, n-m); cout << mul(a, b)[0] << endl; return 0; }
Educational Codeforces Round 60 C. Magic Ship
解法
i日目に到達可能な場所がどのようになっているのか考える。(x1,y1)=(0,0)、s="UDRL"のときの例を以下に示す。
風が吹く方向と逆方向に移動すればi日目で到達したマスはi+1日目以降でも到達可能なことがわかる。したがってi日目にはi以下の地点に移動することができる。1日経過するごとにひし形の中心が風の吹く方向に移動しひし形の大きさが1大きくなることがわかる。
i日目で到達したマスがi+1日目以降でも到達できることからゴールのマスにある日数で到達できるか?という判定問題には単調性が存在する。したがって二分探索を行うことができる。n日を1周としてX周したときに到達できるか?の判定はX周でひし形の中心が移動する位置とゴールのマンハッタン距離がn*X以下か?でO(1)で判定できる。何周でゴールに到達できるかを求めその周の何日目にゴールできるかを求めればよい。
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #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() 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<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } 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<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll sx, sy, gx, gy, n; string s; cin >> sx >> sy >> gx >> gy >> n >> s; gx -= sx; gy -= sy; ll turnx = 0, turny = 0; vector<ll> cx(n), cy(n); REP(i, n) { if(s[i] == 'U') cy[i] = 1, turny++; else if(s[i] == 'D') cy[i] = -1, turny--; else if(s[i] == 'R') cx[i] = 1, turnx++; else if(s[i] == 'L') cx[i] = -1, turnx--; } auto check = [&](ll mid) { ll x = turnx * mid, y = turny * mid, sz = n * mid; return abs(gx-x) + abs(gy-y) <= sz; }; if(!check(1LL<<40)) { cout << -1 << endl; return 0; } ll lb = 0, ub = 1LL<<40; while(ub - lb > 1) { ll mid = (lb+ub)/2; if(check(mid)) ub = mid; else lb = mid; } ub--; ll x = ub * turnx, y = ub * turny, sz = ub * n; REP(i, n) { x += cx[i], y += cy[i], sz++; if(abs(gx-x) + abs(gy-y) <= sz) { cout << sz << endl; return 0; } } cout << -1 << endl; return 0; }
ARC062 E - AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer
解法
立方体の上の面と底面を決めると残りの側面に来る面の色配置は一意に定まる。色の配置がvのタイルが何枚あるか?という情報を計算しておけば何通りあるかは求めることができる。C(N,2)通りを全通り試すことで答えが求まる。
ただし、回転等をしっかり考慮してダブらないように数え上げるのが大変。まずタイルを回転することで得られる4通りの色配置に対して辞書順で最小となる並べ方を基準とすることでダブって数えないようにする。各タイルに対して回転で同じ色配置になるようなことがあるかどうかで場合分けしておく。これによって回転で同じ色配置ができるパターンが何通りあるか求められる。
- 回転して同じ色配置が出てくることがない
- 180度回転で同じ配置になる(点対称)
- 90度回転で同じ配置になる(全て同じ色)
上の面のタイルをi番目、底面をj番目に固定する。立方体の上下反転で同じになるものを数えないためi<jと条件をつける。上の面は辞書順最小のもの一つに固定し底面は回転4通りを試す。側面に必要なパネル4枚を列挙し、各色配置に対して何通りの置き方が存在しているのかを求め掛けていく。
N<-400で3乗通るしタイル3枚固定する半分全列挙?とか考えてたけど2枚固定でよかった
細かいところ詰めるのが大変、こういう実装をちゃんとできるようにしていきたい…
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #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() 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<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<typename T> istream& operator >> (istream& is, vector<T>& vec){ for(T& x: vec) {is >> x;} return is; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; // 回転の4通りのうち辞書順で最小のものを返す だぶって数えるのを防ぐ vector<int> getmin(vector<int> v) { vector<int> ret(v); REP(i, 3) { rotate(v.begin(), v.begin()+1, v.end()); chmin(ret, v); } return ret; } // n0枚、n1枚、n2枚でpanel枚を埋める方法が何通り? ll dfs(ll panel, ll n0, ll n1, ll n2) { if(panel == 0) return 1; ll ret = 0; if(n0) ret += n0*dfs(panel-1, n0-1, n1, n2); if(n1) ret += 2*n1*dfs(panel-1, n0, n1-1, n2); if(n2) ret += 4*n2*dfs(panel-1, n0, n1, n2-1); return ret; } signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n; cin >> n; // 0→回転して同じになるものはない // 1→180度回転で同じになる(対角が同じ) // 2→90度回転でも同じ(全部同じ) vector<ll> r(n); map<vector<int>, int> cnt[3]; vector<vector<int>> a(n, vector<int>(4)); REP(i, n) { REP(j, 4) cin >> a[i][j]; a[i] = getmin(a[i]); if(a[i][0] == a[i][2] && a[i][1] == a[i][3]) { r[i] = 1; if(a[i][0] == a[i][1]) r[i] = 2; } cnt[r[i]][a[i]]++; } ll ret = 0; // 上をi番目のパネルに REP(i, n) { // i番目のパネルの分を消す これが側面に来るとだぶるので再度足すことはしない cnt[r[i]][a[i]]--; // 底をj番目のパネルに FOR(j, i+1, n) { // j番目のパネルの分を消す こっちはループの最後で再度足す cnt[r[j]][a[j]]--; // 底面を4通りに回転させる REP(k, 4) { // 側面に必要なパネル4枚を列挙 map<vector<int>, int> mp; mp[getmin({a[i][1], a[i][0], a[j][1], a[j][0]})]++; mp[getmin({a[i][2], a[i][1], a[j][0], a[j][3]})]++; mp[getmin({a[i][3], a[i][2], a[j][3], a[j][2]})]++; mp[getmin({a[i][0], a[i][3], a[j][2], a[j][1]})]++; // 側面に置く方法が何通りあるか ll t = 1; for(auto p: mp) { t *= dfs(p.second, cnt[0][p.first], cnt[1][p.first], cnt[2][p.first]); if(t == 0) break; } ret += t; // 底のパネルを回転 rotate(a[j].begin(), a[j].begin()+1, a[j].end()); } cnt[r[j]][a[j]]++; } } cout << ret << endl; return 0; }
ARC084 E - Finite Encyclopedia of Integer Sequences
解法
まずKが偶数ならば(K/2, K, …, K)となる数列が答えになることがわかる。よってKが奇数のものについてのみ考える。
ナイーブな解法として答えの数列でi番目で数列のa番目をつくるにはi番目の数字が一意に定まるとして前から決めていくような解法がある。しかしk,nに大きな値がきたときにaの値がまともに持てるような大きさの値ではなくなってしまう。したがって何か別の小さい値を利用して答えを求める必要がある。X/2番目の数列に近そうな数列として ceil(K/2) を並べるものがある。この数列と答えとなる数列が何個ずれているか?というずれであればあまり大きい値ではなさそう。このずれがどの程度の大きさなのか実験してみる。
実験結果を見ると答えの数列はceil(K/2)を並べた数列とn/2ずれていることがわかる。数列を辞書順で一つ前のものに戻す操作はならしO(1)で可能なので全体でO(N)で解ける。
実験難しい…
ならしO(1)で戻す処理の雰囲気にAGC029 C - Lexicographic constraintsを感じた
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #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() 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<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<typename T> istream& operator >> (istream& is, vector<T>& vec){ for(T& x: vec) {is >> x;} return is; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; // 実験 //int n = 5, k = 3; //vector<vector<ll>> a; // //void dfs(vector<ll> v) { // if(v.size()) a.push_back(v); // if(v.size() == n) return; // // REP(i, k) { // vector<ll> u(v); // u.push_back(i+1); // dfs(u); // } //} signed main(void) { cin.tie(0); ios::sync_with_stdio(false); // 実験 // dfs({}); // sort(ALL(a)); // ll half = ceil((int)a.size(), 2); // cout << "half=" << half << endl; // for(int i=max(half-10, 0LL); i<min(half+10, (ll)a.size()); ++i) { // cout << i+1 << " " << a[i] << endl; // } // // return 0; ll n, k; cin >> k >> n; if(k%2 == 0) { cout << k/2; REP(i, n-1) cout << " " << k; cout << endl; return 0; } vector<ll> ans(n, ceil(k, 2LL)); REP(i, n/2) { if(ans.back() == 1) ans.pop_back(); else { ans[ans.size()-1]--; while(ans.size() != n) ans.push_back(k); } } REP(i, ans.size()) cout << ans[i] << " "; cout << endl; return 0; }
ARC065 E - へんなコンパス / Manhattan Compass
解法
まずマンハッタン距離なので45度回転しチェビジェフ距離に変換しておく。
コンパスの移動で穴2つの距離が変わることはない。したがって穴aと穴bの距離Dと等しい穴の組が何個あるのかを考えればよい。穴の組O(N^2)個について全て考えるのは不可能なので穴を一つ固定したときにもう一つの穴になりうる穴の個数について高速に求めたい。これはx(y)座標ごとにy(x)座標を昇順に持っておくと二分探索を用いてO(NlogN)で求められる。コンパスが指すことができる穴のこの値の和 / 2が答えとなる。
あとはコンパスが指すことのできる穴の集合を求めたい。dfsでこれを求める。普通に隣接リストの形で各穴からの遷移先を管理すると削除する対象が多く間に合わない。各穴からの遷移先を個別に持つのではなくx(y)座標ごとにy(x)を昇順に持つsetを使うことにすると削除する対象は一つだけで遷移先は二分探索で求められる。各穴は一回しかアクセスされないのでO(NlogN)でこのdfsは行える。
void dfs(ll v) { // vを使用済みに for(距離がDの穴u) { // uを遷移先から削除 if(uが使用済みでない) dfs(u); } }
合計でO(NlogN)で答えを求めることができる。
遷移先をうまく管理すると各頂点一回しか訪れないのでO(N)でdfsができる。こういう実装が苦手…
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #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() 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<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<typename T> istream& operator >> (istream& is, vector<T>& vec){ for(T& x: vec) {is >> x;} return is; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n, a, b; cin >> n >> a >> b; a--, b--; vector<ll> x(n), y(n); map<ll, vector<ll>> xy_v, yx_v; map<ll, set<PII>> xy_s, yx_s; REP(i, n) { ll xx, yy; cin >> xx >> yy; x[i] = xx - yy; y[i] = xx + yy; xy_v[x[i]].push_back(y[i]); yx_v[y[i]].push_back(x[i]); xy_s[x[i]].insert({y[i], i}); yx_s[y[i]].insert({x[i], i}); } vector<bool> used(n); ll dist = max(abs(x[a]-x[b]), abs(y[a]-y[b])); function<void(ll)> dfs = [&](ll v) { used[v] = true; // 左 while(1) { auto itr = xy_s[x[v]-dist].lower_bound({y[v]-dist, -1}); if(itr == xy_s[x[v]-dist].end() || itr->first > y[v]+dist) break; xy_s[x[v] - dist].erase(itr); if(!used[itr->second]) dfs(itr->second); } // 右 while(1) { auto itr = xy_s[x[v]+dist].lower_bound({y[v]-dist, -1}); if(itr == xy_s[x[v]+dist].end() || itr->first > y[v]+dist) break; xy_s[x[v]+dist].erase(itr); if(!used[itr->second]) dfs(itr->second); } // 下 while(1) { auto itr = yx_s[y[v]-dist].lower_bound({x[v]-dist, -1}); if(itr == yx_s[y[v]-dist].end() || itr->first > x[v]+dist) break; yx_s[y[v]-dist].erase(itr); if(!used[itr->second]) dfs(itr->second); } // 上 while(1) { auto itr = yx_s[y[v]+dist].lower_bound({x[v]-dist, -1}); if(itr == yx_s[y[v]+dist].end() || itr->first > x[v]+dist) break; yx_s[y[v]+dist].erase(itr); if(!used[itr->second]) dfs(itr->second); } }; dfs(a); for(auto &itr: xy_v) sort(ALL(itr.second)); for(auto &itr: yx_v) sort(ALL(itr.second)); ll ret = 0; REP(i, n) { if(!used[i]) continue; ret += upper_bound(ALL(xy_v[x[i]-dist]), y[i]+dist) - lower_bound(ALL(xy_v[x[i]-dist]), y[i]-dist); ret += upper_bound(ALL(xy_v[x[i]+dist]), y[i]+dist) - lower_bound(ALL(xy_v[x[i]+dist]), y[i]-dist); ret += lower_bound(ALL(yx_v[y[i]-dist]), x[i]+dist) - upper_bound(ALL(yx_v[y[i]-dist]), x[i]-dist); ret += lower_bound(ALL(yx_v[y[i]+dist]), x[i]+dist) - upper_bound(ALL(yx_v[y[i]+dist]), x[i]-dist); } cout << ret/2 << endl; return 0; }
みんなのプロコン 2019 F - Pass
解法
dp[i][j] = (結果の列のi+j番目まで見たときに赤をi個、青をj個使っているとき何通りあるか) でDPをする。DPの遷移は
- dp[i+1][j] += dp[i][j] 次に赤を置くことが可能
- dp[i][j+1] += dp[i][j] 次に青を置くことが可能
の2通りになる。次に赤、青を置くことが可能かの判定が高速にできれば解けそう。x回目の操作で持ってこれるボールがどこまでか考えるとx人目が持っているボールまでは取ってこれそう。したがってi(j)個目の赤(青)のボールをi+j人目より前の人が持っていれば取ってこれる。この判定はO(1)でできるのでO(N^2)で解けた。
異なる操作をしても同一の列になるときがあるのが厄介
与えられた列をいじくるのではなく結果の列を作ることが可能か?と考える
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #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() 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<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<typename T> istream& operator >> (istream& is, vector<T>& vec){ for(T& x: vec) {is >> x;} return is; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 998244353; ll dp[4010][4010]; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); string s; cin >> s; ll n = s.size(); vector<ll> r, b; REP(i, n) { if(s[i] == '0') { r.push_back(i); r.push_back(i); } else if(s[i] == '1') { r.push_back(i); b.push_back(i); } else { b.push_back(i); b.push_back(i); } } dp[0][0] = 1; REP(i, r.size()+1) REP(j, b.size()+1) { // x回目の操作で取れるのはx人目が持ってるボールまで if(i<r.size() && r[i]<=i+j) (dp[i+1][j] += dp[i][j]) %= MOD; if(j<b.size() && b[j]<=i+j) (dp[i][j+1] += dp[i][j]) %= MOD; } cout << dp[r.size()][b.size()] << endl; return 0; }
みんなのプロコン 2019 D - Ears
解法
とりあえず散歩によって作れる列がどのようなものであるのか実験する。ある区間を往復するときに大きく往復するのではなく一つずつ独立に往復していくと考えられるので各要素は独立に値を決められる。いろいろ実験していると数列の取りうる値は 0偶奇偶0、0奇偶0、0偶奇0、0偶0、0奇0の5パターンに分類できる。
まず簡単そうな0偶0のパターンから考えてみる。dp[i]=(i番目までで実現できる答えの最小)とするとdp[i]=min(dp[i-1]+ 0or1or2, a[0]からa[i-1]までの和 + 0or1)みたいな遷移ができる。他の条件でもdp[i][j]=(i番目までで偶奇偶のどこか(=j)で実現できる答えの最小)とすれば同様に遷移ができる。したがってO(N)で解けた。
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #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() 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<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<typename T> istream& operator >> (istream& is, vector<T>& vec){ for(T& x: vec) {is >> x;} return is; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n; cin >> n; vector<ll> a(n); REP(i, n) cin >> a[i]; vector<ll> b(a); FOR(i, 1, n) b[i] += b[i-1]; ll ans = LLINF; // ぐ { vector<ll> dp(n); if(a[0] == 0) dp[0] = 0; else if(a[0]%2) dp[0] = 1; else dp[0] = 0; FOR(i, 1, n) { if(a[i] == 0) dp[i] = min(dp[i-1] + 2, b[i-1]); else if(a[i]%2) dp[i] = min(dp[i-1] + 1, b[i-1] + 1); else dp[i] = min(dp[i-1], b[i-1]); } REP(i, n) chmin(ans, dp[i] + b[n-1] - b[i]); cerr << ans << endl; } // き { vector<ll> dp(n); if(a[0] == 0) dp[0] = 0; else if(a[0]%2) dp[0] = 0; else dp[0] = 1; FOR(i, 1, n) { if(a[i] == 0) dp[i] = min(dp[i-1] + 1, b[i-1]); else if(a[i]%2) dp[i] = min(dp[i-1], b[i-1]); else dp[i] = min(dp[i-1]+1, b[i-1]+1); } REP(i, n) chmin(ans, dp[i] + b[n-1] - b[i]); cerr << ans << endl; } // ぐき { vector<vector<ll>> dp(n, vector<ll>(2, LLINF)); if(a[0] == 0) dp[0][0] = 0; else if(a[0]%2) dp[0][0] = 1; else dp[0][0] = 0; FOR(i, 1, n) REP(j, 2) { if(a[i] == 0) chmin(dp[i][0], min(dp[i-1][0] + 2, b[i-1])); else if(a[i]%2) chmin(dp[i][0], min(dp[i-1][0] + 1, b[i-1] + 1)); else chmin(dp[i][0], min(dp[i-1][0], b[i-1])); if(a[i] == 0) chmin(dp[i][1], min(dp[i-1][j] + 1, b[i-1])); else if(a[i]%2) chmin(dp[i][1], min(dp[i-1][j], b[i-1])); else chmin(dp[i][1], min(dp[i-1][j]+1, b[i-1]+1)); } // cout << dp << endl; REP(i, n) REP(j, 2) chmin(ans, dp[i][j] + b[n-1] - b[i]); cerr << ans << endl; } // きぐ { vector<vector<ll>> dp(n, vector<ll>(2, LLINF)); if(a[0] == 0) dp[0][0] = 0; else if(a[0]%2) dp[0][0] = 0; else dp[0][0] = 1; FOR(i, 1, n) REP(j, 2) { if(a[i] == 0) chmin(dp[i][1], min(dp[i-1][j] + 2, b[i-1])); else if(a[i]%2) chmin(dp[i][1], min(dp[i-1][j] + 1, b[i-1] + 1)); else chmin(dp[i][1], min(dp[i-1][j], b[i-1])); if(a[i] == 0) chmin(dp[i][0], min(dp[i-1][0] + 1, b[i-1])); else if(a[i]%2) chmin(dp[i][0], min(dp[i-1][0], b[i-1])); else chmin(dp[i][0], min(dp[i-1][0]+1, b[i-1]+1)); } // cout << dp << endl; REP(i, n) REP(j, 2) chmin(ans, dp[i][j] + b[n-1] - b[i]); cerr << ans << endl; } // ぐきぐ { vector<vector<ll>> dp(n, vector<ll>(3, LLINF)); if(a[0] == 0) dp[0][0] = 0; else if(a[0]%2) dp[0][0] = 1; else dp[0][0] = 0; FOR(i, 1, n) REP(j, 3) { if(a[i] == 0) chmin(dp[i][0], min(dp[i-1][0] + 2, b[i-1])); else if(a[i]%2) chmin(dp[i][0], min(dp[i-1][0] + 1, b[i-1] + 1)); else chmin(dp[i][0], min(dp[i-1][0], b[i-1])); if(a[i] == 0 && j<=1) chmin(dp[i][1], min(dp[i-1][j] + 1, b[i-1])); else if(a[i]%2 && j<=1) chmin(dp[i][1], min(dp[i-1][j], b[i-1])); else if(j<=1) chmin(dp[i][1], min(dp[i-1][j]+1, b[i-1]+1)); if(a[i] == 0 && j>=1) chmin(dp[i][2], min(dp[i-1][j] + 2, b[i-1])); else if(a[i]%2 && j>=1) chmin(dp[i][2], min(dp[i-1][j] + 1, b[i-1] + 1)); else if(j>=1) chmin(dp[i][2], min(dp[i-1][j], b[i-1])); } REP(i, n) REP(j, 3) chmin(ans, dp[i][j] + b[n-1] - b[i]); cerr << ans << endl; } cout << ans << endl; return 0; }
実験したら解けた