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; }
実験したら解けた
CODE THANKS FESTIVAL 2018 F - Coins on the tree
解法
辞書順最小を求めるときは前から貪欲に決めていくのが典型。まずv[1]=1と決めてみたときに残りの木の状態と操作回数とコイン枚数について条件を満たせるのであればv[1]=1と決定してしまってよい。条件を満たさないのであればv[1]=2として同様に条件を満たすか判定を行う。この処理を前から順番に行っていくことで答えを求める。
v[i]=jと決定したときにi枚目より後のコインを頂点jの子孫に置くことは不可能である。コインを置く頂点を決めていくと木の使用できる範囲が狭まっていく。操作回数はその頂点の深さ、コインの枚数は置くごとに-1と遷移していく。
答えの列を決めていくのにO(NM)かかるためO(N+M)くらいで判定を行いたい。ある木とコインを置く枚数(=coin)が与えられたときに指定された操作回数(=ope)となるような操作手順が存在するかの判定を行えればよい。根の深さを1としたとき、深さdの頂点にコインを置く場合d回操作が必要になる。したがってcoin個の頂点を選んで深さの合計がopeとなるような選び方が存在するか？という問題になる。これは部分和問題なのでDPしたくなるが計算量的に不可能である。木の深さが飛び飛びの値にはならないことを利用して計算量を落としたい。これを利用するとコインをi枚置く場合の実現可能な操作回数はある区間一つになることがわかる。実現可能な操作回数の下限、上限は貪欲に求めることができO(N+M)程度で判定することができる。
#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, m, k; cin >> n >> m >> k; ll root = -1; vector<vector<ll>> g(n); REP(i, n) { ll p; cin >> p; p--; if(p == -1) {root = i; continue;} g[p].push_back(i); } vector<ll> depth(n); function<void(ll,ll)> init = [&](ll v, ll d) { depth[v] = d; for(auto to: g[v]) { init(to, d+1); } }; init(root, 1); // cout << "depth=" << depth << endl; vector<bool> used(n); // ちょうどope回の操作でcoin枚のコインを置くことが可能か auto check = [&](ll ope, ll coin) { // cout << "ope=" << ope << " coin=" << coin << endl; vector<ll> cnt(n); function<void(ll, ll)> dfs = [&](ll v, ll d) { if(used[v]) return; cnt[d]++; for (auto to: g[v]) { dfs(to, d + 1); } }; dfs(root, 0); ll sum = 0; REP(i, n) sum += cnt[i]; if(sum < coin) return false; // 操作回数の下限を調べる ll idx = 0, lb = 0, co = coin; while(idx < n && co > 0) { ll tmp = min(cnt[idx], co); co -= tmp; lb += tmp * (idx + 1); idx++; } // 操作回数の上限を調べる idx = n-1, co = coin; ll ub = 0; while(idx >= 0 && co > 0) { ll tmp = min(cnt[idx], co); co -= tmp; ub += tmp * (idx+1); idx--; } return lb <= ope && ope <= ub; }; if(!check(k, m)) { cout << -1 << endl; return 0; } function<void(ll)> dfs2 = [&](ll v) { used[v] = true; for(auto to: g[v]) { dfs2(to); } }; vector<ll> ans(m); ll j = 0; REP(i, m) { // cout << "i=" << i << endl; REP(j, n) { // cout << " j=" << j << endl; if(used[j]) continue; used[j] = true; if(check(k-depth[j], m-i-1)) { // j以下の部分木を全部trueに dfs2(j); k -= depth[j]; ans[i] = j; break; } used[j] = false; } } REP(i, m) cout << ans[i]+1 << (i==m-1?'\n':' '); return 0; }
自力で解けたけど遅い
これ400は詐欺じゃないか
第5回 ドワンゴからの挑戦状 本選 C - Interval and MST
解法
boruvka法を使って最小全域木問題を解く。各連結成分から他の連結成分へつなぐ最もコストが小さい辺をO(N)やO(NlogN)程度で求められるときに有効な方法になる。ある区間が他の区間と交差するのは4パターンに分類できる。
- その区間の右側と他の区間が交わる
区間[l,r)に左端が含まれている場合これを満たす。このパターンの最もコストが小さい辺はr-(左端のmax)となる。左端が大きい上位2つの連結成分を保持しつつi=0から昇順に平面走査をすることで求められる。座圧しておくことで平面走査はO(N)で行える。内包する区間についてもこれは当てはまるが正しい値より大きい値となるため「その区間が他の区間を内包する」で求めるタイミングで正しい値に置き換わる。 - その区間の左側と他の区間が交わる
上記と同様に平面走査を行う。右端が小さい上位2つの連結成分を保持しつつi=(l[i],r[i]のうち最大)から降順に参照する。 - その区間が他の区間を内包する
seg[i] = (左端がiの区間で区間長が短い上位2つ) としたセグ木を持つ。右端が小さい区間から順に見ていきセグ木の更新、区間[l,r)に内包される区間のうち連結成分が異なる区間長が短い区間を求める処理を順に行っていく。 - その区間が他の区間に外包される
seg[i] = (右端がiの区間で区間長が短い上位2つ) としたセグ木を持つ。左端が小さい区間から順に見ていきセグ木の更新、区間[l,r)を外包する区間が存在すれば長さr-lで更新する処理を順に行っていく。
いずれのパターンもO(NlogN)で処理を行えるため全体でO(Nlog^2N)で求められる。
#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; struct UnionFind { vector<int> par, s; UnionFind(int n=2e5) { init(n); } void init(int n) { s.assign(n, 1); par.resize(n); iota(par.begin(), par.end(), 0); } int find(int x) { if(par[x] == x) return x; return par[x] = find(par[x]); } void unite(int x, int y) { x = find(x); y = find(y); if(x == y) return; if(s[x] < s[y]) par[x] = y, s[y] = s[x] + s[y]; else par[y] = x, s[x] = s[x] + s[y]; } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return s[find(x)]; } }; template< typename T, typename F > T boruvka(ll n, F f) { vector<ll> rev(n), belong(n); UnionFind uf(n); T ret = T(); while(uf.size(0) != n) { ll ptr = 0; REP(i, n) { if(uf.find(i) == i) { belong[i] = ptr++; rev[belong[i]] = i; } } REP(i, n) belong[i] = belong[uf.find(i)]; auto v = f(ptr, belong); bool update = false; REP(i, ptr) { if(~v[i].second && !uf.same(rev[i], rev[v[i].second])) { uf.unite(rev[i], rev[v[i].second]); ret += v[i].first; update = true; } } if(!update) return -1; // notice!! } return ret; } template <typename T> struct segtree { int n; vector<T> dat; T d; using F = function<T(T,T)>; F f, g; segtree(int n_, F f_, F g_, T d_) : f(f_), g(g_), d(d_) { n = 1; while(n < n_) n *= 2; dat.assign(n*2, d); } // [a, b) T query(int a, int b, int k, int l, int r) { if(r <= a || b <= l) return d; if(a <= l && r <= b) return dat[k]; return f(query(a, b, 2*k+1, l, (l+r)/2), query(a, b, 2*k+2, (l+r)/2, r)); } T query(int a, int b) {return query(a, b, 0, 0, n);} void update(int i, T v) { i += n-1; dat[i] = v; while(i > 0) { i = (i-1)/2; dat[i] = f(dat[i*2+1], dat[i*2+2]); } } }; /** * 点更新区間min d=INF, f=min(a,b), g=b\n * 点更新区間max d=-INF, f=max(a,b), g=b\n * 点加算区間和 d=0, f=a+b, g+=b */ signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n; cin >> n; vector<ll> v, l(n), r(n); REP(i, n) { cin >> l[i] >> r[i]; l[i]--, r[i]--; v.push_back(l[i]); v.push_back(r[i]); } sort(ALL(v)); v.erase(unique(ALL(v)), v.end()); const ll m = v.size(); vector<vector<PII>> vl(m), vr(m); REP(i, n) { l[i] = lower_bound(ALL(v), l[i]) - v.begin(); r[i] = lower_bound(ALL(v), r[i]) - v.begin(); vl[l[i]].push_back({r[i], i}); vr[r[i]].push_back({l[i], i}); } // aが小さい方上位2つになるように更新 function<pair<PII,PII>(pair<PII,PII>, PII)> fmin = [](pair<PII,PII> a, PII b) { if(a.first.second == b.second) { a.first.first = min(a.first.first, b.first); } else if(a.second.second == b.second) { a.second.first = min(a.second.first, b.first); if(a.first > a.second) swap(a.first, a.second); } else { if(b < a.first) { a.second = a.first; a.first = b; } else if(b < a.second) { a.second = b; } } return a; }; // aが大きい上位2つになるように更新 function<pair<PII,PII>(pair<PII,PII>, PII)> fmax = [](pair<PII,PII> a, PII b) { if(a.first.second == b.second) { a.first.first = max(a.first.first, b.first); } else if(a.second.second == b.second) { a.second.first = max(a.second.first, b.first); if(a.first < a.second) swap(a.first, a.second); } else { if(b > a.first) { a.second = a.first; a.first = b; } else if(b > a.second) { a.second = b; } } return a; }; function<pair<PII,PII>(pair<PII,PII>, pair<PII,PII>)> fmin2 = [&fmin](pair<PII,PII> a, pair<PII,PII> b) { a = fmin(a, b.first); a = fmin(a, b.second); return a; }; function<vector<PII>(ll, vector<ll>)> f = [&](ll sz, vector<ll> belong) { vector<PII> ret(sz, {LLINF, -1}); // 右側で交差する区間について { // 左端が大きい方から上位2つを保持 pair<PII,PII> top({-LLINF,-1}, {-LLINF,-1}); REP(i, m) { for(auto p: vr[i]) { ll u = belong[p.second]; // 今見ている区間の色と違う && 最も左端が大きい区間 PII t = top.first.second == u ? top.second : top.first; // 交差していないか区間が存在していない if(t.first <= p.first) continue; if(t.second == -1) continue; chmin(ret[u], {v[i] - v[t.first], t.second}); } for(auto p: vl[i]) top = fmax(top, {i, belong[p.second]}); } } // 左側で交差する区間について { // 右端が小さい方から上位2つを保持 pair<PII,PII> top({LLINF,-1}, {LLINF,-1}); for(ll i=m-1; i>=0; --i) { for(auto p: vl[i]) { ll u = belong[p.second]; // 今見ている区間の色と違う && 最も左端が大きい区間 PII t = top.first.second == u ? top.second : top.first; // 交差していないか区間が存在していない if(t.first >= p.first) continue; if(t.second == -1) continue; chmin(ret[u], {v[t.first] - v[i], t.second}); } for(auto p: vr[i]) top = fmin(top, {i, belong[p.second]}); } } // 内包する区間について { segtree<pair<PII,PII>> seg(m, fmin2, fmin2, {{LLINF,-1},{LLINF,-1}}); REP(i, m) { for(auto p: vr[i]) { // lの位置に区間の長さを更新 seg.update(p.first, {{v[i] - v[p.first], belong[p.second]},{LLINF,-1}}); } for(auto p: vr[i]) { pair<PII,PII> mi = seg.query(p.first, i); ll u = belong[p.second]; PII t = mi.first.second == u ? mi.second : mi.first; chmin(ret[u], t); } } } // 外包される区間について { segtree<pair<PII,PII>> seg(m, fmin2, fmin2, {{LLINF,-1},{LLINF,-1}}); REP(i, m) { for(auto p: vl[i]) { // rの位置に区間の長さを更新 seg.update(p.first, {{v[p.first] - v[i], belong[p.second]},{LLINF,-1}}); } for(auto p: vl[i]) { pair<PII,PII> mi = seg.query(p.first, m); ll u = belong[p.second]; PII t = mi.first.second == u ? mi.second : mi.first; // 外包される区間があれば[i, p.first)の長さで更新 if(t.second != -1) chmin(ret[u], {v[p.first] - v[i], t.second}); } } } return ret; }; cout << boruvka<ll, decltype(f)>(n, f) << endl; return 0; }
実装がとても大変
エイシング プログラミング コンテスト 2019 E - Attack to a Tree
解法
木DPをする。dp[v][i][j] = (頂点vを根とする部分木でi回辺を切っていて頂点vの連結成分以外は問題文の条件を満たし、頂点vの連結成分が全てバッテリー(j=0)orそれ以外(j=1)のときの連結成分の頂点の重みの和の最小) とする。不可能な場合はinfをdpに持たせる。頂点vを根とする木とvの子cを根とする木をマージしていくことでdpの遷移を行う。頂点vとcの間の辺を切らない場合と切る場合に分けて考える。
切らない場合は各部分木でi回切断、j回切断している状態をマージするのでi+j回切断したときの情報が得られる。マージするどちらかのdpの値がinfであればそれは不可能な状態なので無視する。
new_dp[v][i+j][0] = dp[v][i][0] + dp[c][i][0]
new_dp[v][i+j][1] = dp[v][i][0] + dp[c][i][1]
new_dp[v][i+j][1] = dp[v][i][1] + dp[c][i][0]
new_dp[v][i+j][1] = dp[v][i][1] + dp[c][i][1]
切る場合はi+j+1回切断したときの情報が得られる。切っているので子cの部分木の頂点の重みは足す必要がない。辺を切ってvと連結でなくなる頂点の連結成分が問題文の条件を満たすときのみ辺を切断する遷移を行えることに注意。
new_dp[v][i+j+1][0] = dp[v][i][0]
new_dp[v][i+j+1][0] = dp[v][i][0]
new_dp[v][i+j+1][1] = dp[v][i][1]
new_dp[v][i+j+1][1] = dp[v][i][1]
以上のマージはO(N^2)でこれを各頂点について行うとO(N^3)に一見思えるが部分木のサイズまでしかループを回さないようにすることでO(N^2)となっている。二乗の木 DP - (iwi) ｛ 反省します - TopCoder部
dp[root][i][0]=infかdp[root][i][1]<0であればi回切断が可能と判定でき最終的な答えが求められる。
#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; using vll = vector<vector<ll>>; ll a[5010]; vector<ll> g[5010]; vll dfs(ll v, ll p) { // dp[v] vll ret(1, vector<ll>(2, LLINF)); if(a[v]>0) ret[0][0] = a[v]; ret[0][1] = a[v]; for(auto to: g[v]) if(to != p) { // dp[c] auto vec = dfs(to, v); // new_dp[v] vll nret(ret.size() + vec.size(), vector<ll>(2, LLINF)); REP(i, ret.size()) REP(j, vec.size()) { // vからiまでの辺を切断しない if(ret[i][0] != LLINF && vec[j][0] != LLINF) { chmin(nret[i+j][0], ret[i][0]+vec[j][0]); } if(ret[i][1] != LLINF && vec[j][1] != LLINF) { chmin(nret[i+j][1], ret[i][1]+vec[j][1]); } if(ret[i][0] != LLINF && vec[j][1] != LLINF) { chmin(nret[i+j][1], ret[i][0]+vec[j][1]); } if(ret[i][1] != LLINF && vec[j][0] != LLINF) { chmin(nret[i+j][1], ret[i][1]+vec[j][0]); } // vからiまでの辺を切断する if(ret[i][0] != LLINF && vec[j][0] != LLINF && i+j+1<nret.size()) { chmin(nret[i+j+1][0], ret[i][0]); } if(ret[i][0] != LLINF && vec[j][1] != LLINF && vec[j][1]<0 && i+j+1<nret.size()) { chmin(nret[i+j+1][0], ret[i][0]); } if(ret[i][1] != LLINF && vec[j][0] != LLINF && i+j+1<nret.size()) { chmin(nret[i+j+1][1], ret[i][1]); } if(ret[i][1] != LLINF && vec[j][1] != LLINF && vec[j][1]<0 && i+j+1<nret.size()) { chmin(nret[i+j+1][1], ret[i][1]); } } ret = nret; } return ret; } signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n; cin >> n; REP(i, n) cin >> a[i]; REP(i, n-1) { ll u, v; cin >> u >> v; u--, v--; g[u].push_back(v); g[v].push_back(u); } ll ret = INF; auto ans = dfs(0, -1); REP(i, ans.size()) REP(j, 2) { if(j==0 && ans[i][j] != LLINF) chmin(ret, i); if(j==1 && ans[i][j] < 0) chmin(ret, i); } cout << ret << endl; return 0; }
TDPC T - フィボナッチ
解法
きたまさ法メモ - よすぽの日記
この記事を自分なりに理解したメモ
問題では1-indexになっているが0-indexで扱うとする。つまり以下の数列Aの第n項を求めろという問題になる。
A[i] = 1 (i<k)
A[i] = A[i-1] + A[i-2] + … + A[i-k] (i>=k)
行列累乗を使えばO(K^3N)で解ける(cf. 蟻本p114)がこれでは当然TLEする。きたまさ法と呼ばれる線形K項間漸化式の第n項をO(K^2logN)で求めるアルゴリズムを用いる。関数f(m)を数列xを返す関数とする。数列xはA[m]=x[0]A[0]+x[1]A[1]+…+x[k-1]A[k-1]を満たすとする。f(n)を求めることができればA[n]も求まる。f(m)からf(m+1)、f(2m)を高速に求めることができればダブリング・繰り返し二乗法の要領で計算することでO(logn)回の計算でf(n)が求まる。
f(m)からf(m+1)は以下の要領でO(k)で求められる。
A[m] = x[0]A[0]+x[1]A[1]+…+x[k-1]A[k-1]
A[m+1] = x[0]A[1]+x[1]A[2]+…+x[k-1]A[k]
= x[0]A[1]+x[1]A[2]+…+x[k-1]*(A[0]+A[1]+…+A[k-1])
= x[k-1]A[0] + (x[0]+x[k-1])A[1] + … + (x[k-2]+x[k-1])A[k-1]
f(m)からf(2m)はO(k^2)で求められる。まずO(k^2)かけて上記と同じ要領でf(m),f(m+1),…,f(m+k-1)を求める。f(m)が返す数列のi番目をf(m,i)と書くことにするとA[2m]は以下のように書ける。
A[2m] = x[0]A[n]+x[1]A[n+1]+…+x[k-1]A[n+k-1]
= x[0]*(f(n,0)A[0] + f(n,1)A[1] + … + f(n,k-1)A[k-1]) + … + x[k-1]*(f(n+k-1,0)A[0] + …)
= (x[0]f(n,0) + x[1]f(n+1,0) + … + x[k-1]f(n+k-1,0))A[0] + (x[1]f(n,1) + …)A[1] + … + (x[k-1]f(n,k-1) + …)A[k-1]
以上のようにf(m)からf(m+1)、f(2m)を計算することがO(k^2)でできるため第n項をO(k^2logn)で求めることができた。
#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 int MOD = 1000000007; // a_nをO(K^2logN)で求める vector<ll> dfs(vector<ll> a, vector<ll> d, ll n) { ll k = d.size(); if(n == k) return d; vector<ll> ret(k); if(n&1 || n<k*2) { auto v = dfs(a, d, n-1); ret[0] = v[k-1] * a[0] % MOD; FOR(i, 1, k) ret[i] = (v[i-1] + v[k-1] * a[i] % MOD) % MOD; } else { auto v = dfs(a, d, n/2); vector<vector<ll>> f(k, vector<ll>(k)); f[0] = v; FOR(i, 1, k) { f[i][0] = f[i-1][k-1] * a[0] % MOD; FOR(j, 1, k) f[i][j] = (f[i-1][j-1] + f[i-1][k-1] * a[j] % MOD) % MOD; } REP(i, k) REP(j, k) (ret[i] += v[j] * f[j][i] % MOD) %= MOD; } return ret; } ll kitamasa(vector<ll> a, vector<ll> d, ll n) { auto ret = dfs(a, d, n); ll ans = 0; REP(i, d.size()) (ans += d[i] * ret[i]) %= MOD; return ans; } signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n, k; cin >> k >> n; n--; if(n < k) { cout << 1 << endl; return 0; } vector<ll> d(k, 1); cout << kitamasa(d, d, n) << endl; return 0; }
