Codeforces #157 Div1 E Little Elephant and Tree
segment treeを使って頑張ると解ける(dfsしながらやると上手く行く系)
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; #define pb push_back #define mp make_pair #define fi first #define se second #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) FOR(i,0,n) struct segtree{ int *lazy, *mi, *cnt; int sz; segtree(int n){ for(sz = 1; sz < n; sz *= 2); lazy = new int[sz * 2 - 1]; mi = new int[sz * 2 - 1]; cnt = new int[sz * 2 - 1]; } void init(){ init(0, 0, sz); } void add(int a, int b, int x){ add(a, b, x, 0, 0, sz); } pii query(int a, int b){ return query(a, b, 0, 0, sz); } void init(int k, int l, int r){ lazy[k] = mi[k] = 0; cnt[k] = r - l; if(k < sz - 1){ init(k * 2 + 1, l, (l + r) / 2); init(k * 2 + 2, (l + r) / 2, r); } } inline void spread(int k){ if(lazy[k] == 0) return ; mi[k] += lazy[k]; if(k < sz - 1){ lazy[k * 2 + 1] += lazy[k]; lazy[k * 2 + 2] += lazy[k]; } lazy[k] = 0; } inline void upd(int k){ cnt[k] = 0; mi[k] = min(mi[k * 2 + 1], mi[k * 2 + 2]); if(mi[k * 2 + 1] == mi[k]) cnt[k] += cnt[k * 2 + 1]; if(mi[k * 2 + 2] == mi[k]) cnt[k] += cnt[k * 2 + 2]; } void add(int a, int b, int x, int k, int l, int r){ spread(k); if(r <= a || b <= l) return ; if(a <= l && r <= b){ lazy[k] += x; spread(k); return ; } add(a, b, x, k * 2 + 1, l, (l + r) / 2); add(a, b, x, k * 2 + 2, (l + r) / 2, r); upd(k); } pii query(int a, int b, int k, int l, int r){ spread(k); if(r <= a || b <= l) return mp(0, INT_MAX); if(a <= l && r <= b) return mp(cnt[k], mi[k]); pii lc = query(a, b, k * 2 + 1, l, (l + r) / 2); pii rc = query(a, b, k * 2 + 2, (l + r) / 2, r); pii ret = mp(0, INT_MAX); if(lc.se <= rc.se) ret = lc; if(rc.se <= lc.se){ ret.se = rc.se; ret.fi += rc.fi; } return ret; } }; int n, m; segtree *t; vector<int> g[100010]; vector<int> op[100010]; int in[100010], out[100010]; int ans[100010]; int now; inline void tour(int v, int p){ in[v] = now++; for(int &to : g[v]) if(to != p) tour(to, v); out[v] = now; } void calc(int v, int p){ bool f = false; for(int &x : op[v]){ t->add(in[x], out[x], 1); if(!f){ f = true; t->add(in[v], out[v], 1); } } pii ret = t->query(0, n); if(ret.se > 0) ans[v] = n; else ans[v] = n - ret.fi; if(ans[v]) --ans[v]; for(int &to : g[v]) if(to != p) calc(to, v); for(int &x : op[v]) t->add(in[x], out[x], -1); if(f) t->add(in[v], out[v], -1); } int main(){ scanf("%d %d", &n, &m); rep(i, n - 1){ int a, b; scanf("%d %d", &a, &b); --a; --b; g[a].pb(b); g[b].pb(a); } rep(i, m){ int a, b; scanf("%d %d", &a, &b); --a; --b; op[a].pb(b); op[b].pb(a); } tour(0, -1); t = new segtree(n); t->init(); calc(0, -1); rep(i, n) printf("%d%c", ans[i], i == n - 1 ? '\n' : ' '); return 0; }
gcc4.9 インストール(OS X Yosemite)
珍しくパソコン系かつ問題系でない話題。(メモ)
#include<bits/stdc++.h> は前準備禁止なIOIとかICPCで特に役に立つ気がする(あとはテンプレート使わないで毎回0から書いてる人)
— hogloid (@hogloid) 2014, 11月 12
を見てbits/stdc++.hの存在に気付く
昔なにかをした時homebrewやらmac portやらを入れていたので楽勝だと思ったら意外と手こずった
まずhomebrewを用いてgccをインストールを試みたが、意味不明なエラー(検索しても出てこなかった)のせいで時間を溶かしてしまった
某potetisenseiからmac portでやってみたらと言われやると、1回目は失敗したが2回目は特にエラーも出ずスムーズにインストール出来ました。
(参考にしたページ :
mac port で gcc4.8を入れたった - Bye Bye Moore
テンプレートが短くなって嬉しみ
Codeforces #189 Div1. C Kalila and Dimna in the Logging Industry
Convex-Hull Trickを蟻本の形のまま使える問題があったのでメモ。
b[n-1] = 0に気付けると、
dp[0] = 0,
dp[i] = min[j=0, i - 1] (dp[j] + b[j] * a[i]) (i >= 1)
とすればO(N^2)で計算出来ることがわかる。
y = b[j] * x + dp[j]のa[i]での値であって、b[j] : 単調減少, a[i] : 単調増加より蟻本のまま適用できる。
直線の上下判定に超苦戦(long longをあふれるのに気付かなかった。)
#include <algorithm> #include <cstdio> using namespace std; typedef long long ll; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) FOR(i,0,n) int n; ll a[100010], b[100010]; ll dp[100010]; int deq[100010]; int s, t; ll f(int j, int pos){ return b[j] * a[pos] + dp[j]; } bool ng(int t1, int t2, int t3){ double a1 = b[t1], b1 = dp[t1]; double a2 = b[t2], b2 = dp[t2]; double a3 = b[t3], b3 = dp[t3]; return (a2 - a1) * (b3 - b2) >= (b2 - b1) * (a3 - a2); } int main(){ scanf("%d", &n); rep(i, n) scanf("%I64d", &a[i]); rep(i, n) scanf("%I64d", &b[i]); for(int i = 1; i < n; ++i){ while(s + 1 < t && ng(deq[t - 2], deq[t - 1], i - 1)) --t; deq[t++] = i - 1; while(s + 1 < t && f(deq[s], i) >= f(deq[s + 1], i)) ++s; dp[i] = f(deq[s], i); } printf("%I64d\n", dp[n-1]); return 0; }
USACO 2014 January Contest, Gold
今月と見せかけて先月のGoldを解きました。
Problem 1. Cow Curling
N点から3点選んでできる三角形の領域の和集合が凸包になっていることがわかるので、凸包を作る。
N <= 50000なためN^2ができずつらぽよするが、凸包の点を始点から見た角度でsortすると二分探索で含まれそうな三角形がわかり、外積を使って三角形の内外判定をすると判定できる。
これはテストケースがもっと強いと落ちるかもナアと思う
O(N log N)
#include <vector> #include <algorithm> #include <cstdio> #include <cmath> using namespace std; typedef long long ll; #define pb push_back #define mp make_pair #define fi first #define se second #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) FOR(i,0,n) const double EPS = 1e-10; const double PI = acos(-1.0); #define dump(x) cerr << #x << " = " << (x) << endl; #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; #undef DEBUG int n; int sa, sb; struct PO{ ll x, y; PO(){} PO(ll x, ll y) : x(x), y(y){} ll cross(PO p){ return x * p.y - y * p.x; } PO operator - (PO p){ return PO(x - p.x, y - p.y); } bool operator < (const PO& p) const{ return x == p.x ? y < p.y : x < p.x; } }; PO a[50010], b[50010]; vector<PO> conhull(PO* p){ sort(p, p + n); int now = 0; vector<PO> vec(n * 2); rep(i, n){ while(now > 1 && (vec[now - 1] - vec[now - 2]).cross(p[i] - vec[now - 1]) <= 0) --now; vec[now++] = p[i]; } for(int i = n - 2, la = now; i >= 0; --i){ while(now > la && (vec[now - 1] - vec[now - 2]).cross(p[i] - vec[now - 1]) <= 0) --now; vec[now++] = p[i]; } vec.resize(now - 1); return vec; } bool in(PO g, PO gg, PO ggg, PO ob){ if((gg - g).cross(ob - g) < 0) return false; if((ggg - gg).cross(ob - gg) < 0) return false; if((g - ggg).cross(ob - ggg) < 0) return false; return true; } int main(){ freopen("curling.in", "r", stdin); freopen("curling.out", "w", stdout); scanf("%d", &n); rep(i, n) scanf("%lld %lld", &a[i].x, &a[i].y); rep(i, n) scanf("%lld %lld", &b[i].x, &b[i].y); vector<PO> aa = conhull(a); vector<PO> bb = conhull(b); #ifdef DEBUG puts("\naa"); rep(i, aa.size()) printf("%lld %lld\n", aa[i].x, aa[i].y); puts("\nbb"); rep(i, bb.size()) printf("%lld %lld\n", bb[i].x, bb[i].y); #endif PO st = aa[0]; vector<double> v; rep(i, aa.size()) if(i) v.pb(atan2(aa[i].y - st.y, aa[i].x - st.x)); //rep(i, v.size()) cout << 180 * v[i] / PI << endl; rep(i, n){ double r = atan2(b[i].y - st.y, b[i].x - st.x); if(r < v[0] || r > v.back()) continue; if(v.size() == 1){ sa += (b[i] < aa[1]); continue; } vector<double>::iterator it; it = lower_bound(v.begin(), v.end(), r); bool f = false; if(it != v.begin()){ int t = it - v.begin() + 1; f |= in(st, aa[t-1], aa[t], b[i]); } if(it + 1 != v.end()){ int t = it - v.begin() + 1; f |= in(st, aa[t], aa[t+1], b[i]); } sa += f; } //debug(sa); v.clear(); st = bb[0]; rep(i, bb.size()) if(i) v.pb(atan2(bb[i].y - st.y, bb[i].x - st.x)); //rep(i, v.size()) cout << 180 * v[i] / PI << endl; rep(i, n){ double r = atan2(a[i].y - st.y, a[i].x - st.x); if(r < v[0] || r > v.back()) continue; if(v.size() == 1){ sb += (a[i] < bb[1]); continue; } vector<double>::iterator it; it = lower_bound(v.begin(), v.end(), r); bool f = false; if(it != v.begin()){ int t = it - v.begin() + 1; f |= in(st, bb[t-1], bb[t], a[i]); } if(it + 1 != v.end()){ int t = it - v.begin() + 1; f |= in(st, bb[t], bb[t+1], a[i]); } sb += f; } //debug(sb); printf("%d %d\n", sa, sb); return 0; }
Problem 2. Building a Ski Course
明らかに二分探索できるので、判定を考えると、逆から辿っていくと簡単に調べることができる。
こういうのは計算量がわからない
#include <vector> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) FOR(i,0,n) int n, m; int lb = 1, ub; char gri[110][110]; int gr[110][110]; bool done[110][110]; bool pr[110][110]; bool ok(int x){ memset(done, 0, sizeof(done)); memset(pr, 0, sizeof(pr)); while(true){ bool f = false; for(int i = 0; i <= n - x; ++i){ for(int j = 0; j <= m - x; ++j){ if(pr[i][j]) continue; bool s[2]; s[0] = s[1] = false; rep(k, x) rep(l, x) if(!done[i+k][j+l]){ s[gr[i+k][j+l]] = true; if(s[0] && s[1]) break; } if(!(s[0] || s[1])) continue; if(s[0] && s[1]) continue; rep(k, x) rep(l, x) done[i+k][j+l] = true; f = true; pr[i][j] = true; } } if(!f) break; } rep(i, n) rep(j, m) if(!done[i][j]) return false; return true; } int main(){ freopen("skicourse.in", "r", stdin); freopen("skicourse.out", "w", stdout); scanf("%d %d", &n, &m); ub = min(n, m) + 1; rep(i, n){ scanf("%s", gri[i]); rep(j, m) gr[i][j] = (gri[i][j] == 'R'); } while(ub - lb > 1){ int mid = (ub + lb) / 2; if(ok(mid)) lb = mid; else ub = mid; } printf("%d\n", lb); return 0; }
Problem 3. Ski Course Rating
結構面白かった。辺のコストをelevationの差の絶対値としたグリッドグラフを考える。
コストが小さい順に頂点を併合していき、集合のサイズが一定値以上に初めてなった時のコストを頑張ってunionfindに覚えさせる。つらぽよ。
O(NM*hoge)っぽい
#include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> using namespace std; typedef pair<int, int> P; typedef long long ll; #define pb push_back #define mp make_pair #define fi first #define se second #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) FOR(i,0,n) int n, m, t; struct unionfind{ vector<int> par, rank, sz, ra; unionfind(){} void init(int n_){ par.resize(n_); rank.resize(n_); sz.resize(n_); ra.resize(n_); rep(i, n_){ par[i] = i; rank[i] = 0; sz[i] = 1; ra[i] = -1; } } inline int find(int x){ if(par[x] != x) find(par[x]); if(ra[x] == -1) ra[x] = ra[par[x]] == -1 ? ra[par[par[x]]] : ra[par[x]]; return par[x] = par[par[x]]; } void unite(int x, int y){ x = find(x); y = find(y); if(x == y) return ; if(rank[x] < rank[y]){ par[x] = y; sz[y] += sz[x]; }else{ par[y] = x; sz[x] += sz[y]; rank[x] += (rank[x] == rank[y]); } } inline bool same(int x, int y){ return find(x) == find(y); } inline int get_rate(int x){ return ra[x]; } inline int get_sz(int x){ return sz[find(x)]; } }uf; pair<int, P > e[500010]; int val[510][510]; int st[250010]; int now; ll ret; int main(){ freopen("skilevel.in", "r", stdin); freopen("skilevel.out", "w", stdout); scanf("%d %d %d", &n, &m, &t); rep(i, n) rep(j, m) scanf("%d", &val[i][j]); rep(i, n * m) scanf("%d", &st[i]); rep(i, n){ rep(j, m){ if(j < m - 1) e[now++] = mp(abs(val[i][j] - val[i][j+1]), mp(i * m + j, i * m + j + 1)); if(i < n - 1) e[now++] = mp(abs(val[i][j] - val[i+1][j]), mp(i * m + j, (i + 1) * m + j)); } } sort(e, e + now); uf.init(n * m); rep(i, now){ int cost = e[i].fi; int a = e[i].se.fi, b = e[i].se.se; if(uf.same(a, b)) continue; a = uf.find(a); b = uf.find(b); int as = uf.get_sz(a), bs = uf.get_sz(b); if(as + bs >= t){ if(as < t) uf.ra[a] = cost; if(bs < t) uf.ra[b] = cost; } uf.unite(a, b); } rep(i, n * m) if(st[i]){ uf.find(i); ret += uf.get_rate(i); } printf("%lld\n", ret); return 0; }
JOI 2013-2014予選
予選敗退したのでソースだけ貼っておきます.
1. 読む
int ret; int main(){ rep(i, 5){ int t; cin >> t; ret += max(t, 40); } cout << ret / 5 << endl; return 0; }
2. 制約緩いし普通に上から見ればいいです
int n, m; int piv, now; int v[1010]; int c[1010]; int main(){ cin >> n >> m; rep(i, n) cin >> c[i]; rep(i, m){ int b; cin >> b; rep(j, n){ if(c[j] <= b){ ++v[j]; break; } } } rep(i, n){ if(v[i] > now){ now = v[i]; piv = i + 1; } } cout << piv << endl; return 0; }
3. 場合分け
int calc(P a, P b){ if(a > b) swap(a, b); if(a.se <= b.se){ int t = min(b.se - a.se, b.fi - a.fi); a.fi += t; a.se += t; return (t + b.se - a.se + b.fi - a.fi); }else{ return (b.fi - a.fi + a.se - b.se); } } int main(){ cin >> w >> h >> n; cin >> x >> y; rep(i, n - 1){ int a, b; cin >> a >> b; ret += calc(mp(x, y), mp(a, b)); x = a; y = b; } cout << ret << endl; return 0; }
4. dp[i][j] : i日目, 出席している人の集合が2進数表示でj でやる
const int MOD = 10007; int n, ret; string sa; int s[1010]; int dp[1010][8]; int main(){ cin >> n >> sa; rep(i, n){ if(sa[i] == 'J') s[i] = 0; else if(sa[i] == 'O') s[i] = 1; else s[i] = 2; } for(int i = 1; i < 8; ++i) if((i & 1) && (i & (1 << s[0]))) dp[0][i] = 1; for(int i = 1; i < n; ++i){ for(int j = 1; j < 8; ++j){ if(!(j & (1 << s[i]))) continue; for(int k = 1; k < 8; ++k){ int mask = (j & k); if(mask) dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD; } } } rep(i, 8) ret = (ret + dp[n-1][i]) % MOD; cout << ret << endl; return 0; }
5. 予選でグラフが出て驚く.
int n, k; P ta[5010]; vector<int> g[5010]; int d[5010][5010]; int dd[5010]; struct edge{ int to, co; edge(int to, int co) : to(to), co(co){} edge(){} }; vector<edge> ng[5010]; void get_dist(){ rep(i, n){ rep(j, n) d[i][j] = INT_MAX; d[i][i] = 0; queue<int> q; q.push(i); while(!q.empty()){ int v = q.front(); q.pop(); rep(j, g[v].size()){ if(d[i][g[v][j]] != INT_MAX) continue; d[i][g[v][j]] = d[i][v] + 1; q.push(g[v][j]); } } } } void build_graph(){ rep(i, n){ rep(j, n){ if(i == j) continue; if(d[i][j] <= ta[i].se) ng[i].pb(edge(j, ta[i].fi)); } } } void dijk(){ fill(dd, dd + n, INT_MAX); dd[0] = 0; priority_queue<P, vector<P>, greater<P> > q; q.push(mp(0, 0)); while(!q.empty()){ P p = q.top(); q.pop(); int v = p.se; if(dd[v] < p.fi) continue; rep(i, ng[v].size()){ edge e = ng[v][i]; if(dd[e.to] > dd[v] + e.co){ dd[e.to] = dd[v] + e.co; q.push(mp(dd[e.to], e.to)); } } } } int main(){ scanf("%d %d", &n, &k); rep(i, n) scanf("%d %d", &ta[i].fi, &ta[i].se); rep(i, k){ int a, b; scanf("%d %d", &a, &b); --a; --b; g[a].pb(b); g[b].pb(a); } get_dist(); build_graph(); dijk(); printf("%d\n", dd[n-1]); return 0; }
6. opened
JOI 模擬予選
期末とはなんだったのか.
500/600点でした. 6の部分点取りに行かなかったのは良くない....
1. 平均*5 - 残り.
int s, a; int main(){ rep(i, 4){ int t; scanf("%d", &t); s += t; } scanf("%d", &a); printf("%d\n", a * 5 - s); return 0; }
2. 素直に計算してsort.
int n, m; int ex[110]; P a[110]; int calc(int i){ int now = 1, r = ex[i]; while(r){ if(r < 100 * now) break; r -= 100 * now++; } return now; } int main(){ scanf("%d %d", &n, &m); while(m--){ int p, q; scanf("%d %d", &p, &q); ex[p-1] += q; } rep(i, n) a[i] = mp(-calc(i), i + 1); sort(a, a + n); rep(i, n) printf("%d\n", a[i].se); return 0; }
3. 特別な仕事をどこまでするかを試す.
int n; ll c, s, t; ll ret = LLONG_MAX; pair<ll, ll> wo[110]; ll calc(int idx){ ll nc = c, ns = s, mo = 0; rep(i, idx){ if(ns >= wo[i].fi){ ns -= wo[i].fi; nc += wo[i].se; }else{ ll nes = wo[i].fi - ns; ll d = (nes + nc - 1) / nc; mo += d; ns += d * nc; ns -= wo[i].fi; nc += wo[i].se; } } if(ns >= t) return mo; ll d = (t - ns + nc - 1) / nc; mo += d; return mo; } int main(){ scanf("%lld %lld %lld %d", &c, &s, &t, &n); rep(i, n) scanf("%lld %lld", &wo[i].fi, &wo[i].se); for(int i = 0; i <= n; ++i) ret = min(ret, calc(i)); printf("%lld\n", ret); return 0; }
4. dp[i][j][k] : 場所, 最後から2番目, 最後(最後から2番目は別に同じかどうかだけで良いが)
int n, m, l; const ll MOD = 100000LL; bool ban[110][110]; vector<int> v[110]; ll dp[110][110][110]; ll ret; int main(){ scanf("%d %d %d", &n, &m, &l); rep(i, l){ int a, b; scanf("%d %d", &a, &b); ban[a-1][b-1] = true; } rep(i, n){ rep(j, m){ if(!ban[i][j]) v[i].pb(j); } } rep(i, v[0].size()){ rep(j, v[1].size()){ if(v[0][i] == v[1][j]) dp[1][v[0][i]][v[0][i]] = 1; } } for(int i = 1; i < n; ++i){ rep(j, v[i-1].size()){ int p = v[i-1][j]; rep(k, v[i].size()){ int q = v[i][k]; if(p == q) rep(id, v[i+1].size()) dp[i+1][q][v[i+1][id]] = (dp[i+1][q][v[i+1][id]] + dp[i][p][q]) % MOD; else if(!ban[i+1][q]) dp[i+1][q][q] = (dp[i+1][q][q] + dp[i][p][q]) % MOD; } } } rep(i, v[n-2].size()){ rep(j, v[n-1].size()){ if(v[n-2][i] == v[n-1][j]) ret = (ret + dp[n-1][v[n-2][i]][v[n-1][j]]) % MOD; } } printf("%lld\n", ret); return 0; }
5. コンビネーションを適当にやってもできるが, 予選形式なのでサボった
int n, s, t; const ll MOD = 1000000007LL; int main(){ scanf("%d %d %d", &n, &s, &t); if(abs(s - t) >= n){ puts("0"); return 0; } if(n == 1){ if(s == t) puts("1"); else puts("0"); return 0; } t = abs(t - s); s = 0; vector<ll> v; v.pb(1LL); rep(i, n - 1){ vector<ll> nv((int)v.size() + 2); rep(j, v.size()){ nv[j] = (nv[j] + v[j]) % MOD; nv[j+1] = (nv[j+1] + v[j]) % MOD; nv[j+2] = (nv[j+2] + v[j]) % MOD; } v = nv; } printf("%lld\n", v[n - 1 - t]); return 0; }