AOJ 0600 Baumkuchen
解法
累積和と二分探索．
まず，バウムクーヘンの累積和を二周分求めておく．
その後，左端を適当に定め，そこから始めて長さが (lb + ub) / 2 以上になるところを2分探索で求める．さらにそこから同様に次の地点を求めて，各地点の距離の差が(lb + ub) / 2以上であれば，下限を更新する．そうでなければ上限を更新．
解の範囲を収束させるのに O(logN)，仮定した長さが条件をみたすか調べるのにO(NlogN)かかるので，トータルO(N(logN)^2)．
しゃくとりでやるともうちょい早くなりそうだけどめんどくさそうなのでやめました（実はそんなにめんどくさくない？）
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; bool check(vector<ll> const& a, ll m) { const int N = a.size() / 2; bool ok = false; for(int i=0; i<N; ++i) { int j = lower_bound(a.begin()+i, a.begin()+i+N+1, a[i]+m) - a.begin(); int k = lower_bound(a.begin()+j, a.begin()+i+N+1, a[j]+m) - a.begin(); if(a[j] - a[i] >= m && a[k] - a[j] >= m && a[i+N] - a[k] >= m) { ok = true; break; } } return ok; } int main() { int N; cin >> N; vector<ll> a(2*N+1); for(int i=1; i<=N; ++i) { cin >> a[i]; a[i+N] = a[i]; } for(int i=1; i<2*N+1; ++i) { a[i] += a[i-1]; } ll lb = 0, ub = (a[N] + 2) / 3; while(ub - lb > 1) { ll m = (ub + lb) / 2; if(check(a, m)) { lb = m; } else { ub = m; } } cout << lb << endl; }
AOJ 0509 Sheets
問題概要
平面座標に n 個の長方形がある．重なっていることもある．
それらがつくる図形の面積と，周の長さを求めよ．
・制約
1 <= n <= 10000
長方形の左下，右上の座標の x, y 座標は，共に 0 以上 10000 以下である．
解法
累積和（いもす法）でやる．
ただし愚直に2次元累積和を取ると MLE する．
そのため，まず0行目から横一行（縦一列でもよい）ずつ見ていくようにして，次の行を見るときは前の行の値を使うようにする．
こうすると，それ以前の値を保存する必要が無いので，MLEを防げる．
流れとしては，
- 横で累積和をとる．
- そのあと，前の行の累積和を足す．
- 累積和の値が1以上であれば面積に1追加，図形の端（自身と四方の累積和を比較すればわかる）であれば周の長さに1追加する．
どこに +1 して -1 するかは，y座標をindexとする vector の vector を持っておけば良い．
これでなんとか解ける．
計算量は O(XY) = 10^8 で，定数倍かかるのでかなりギリギリになった．
賢く書けばもうちょい早くなるかも．
ソースコード
#include <bits/stdc++.h> using namespace std; using P = pair<int, int>; constexpr int MAX_Y = 10003; constexpr int MAX_X = 10003; int main() { int n, r; while(cin >> n >> r, n) { vector<vector<P>> v(MAX_Y); for(int i=0; i<n; ++i) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; v[y1+1].emplace_back(x1+1, 1); v[y1+1].emplace_back(x2+1, -1); v[y2+1].emplace_back(x1+1, -1); v[y2+1].emplace_back(x2+1, 1); } vector<vector<int>> sum(2, vector<int>(MAX_X)); int S = 0, len = 0; for(int i=0; i<MAX_Y; ++i) { int now = i % 2, pre = (i+1) % 2; fill(sum[now].begin(), sum[now].end(), 0); for(int j=0; j<v[i].size(); ++j) { sum[now][v[i][j].first] += v[i][j].second; } for(int j=0; j<MAX_X; ++j) { sum[now][j+1] += sum[now][j]; sum[now][j] += sum[pre][j]; } for(int j=0; j<MAX_X; ++j) { S += sum[now][j] > 0; len += ((sum[pre][j] > 0) != (sum[now][j] > 0)); len += ((sum[now][j] > 0) != (sum[now][j+1] > 0)); } } if(r == 1) { cout << S << endl; } else { cout << S << '\n' << len << endl; } } }
AOJ 0517 Longest Steps
解法
しゃくとり法でやった．
与えられた k 枚のカードをソートしておく．
0が含まれていれば1つだけ飛ばせるので，それは場合分けで処理．
行けるところまでいったら，左端をカードの数字が1以上飛んでいるところに更新する．
オーダーはソートがネックなので O(klogk + k)．
しかし，連続部分を pair でもっておいて，0 が含まれていれば隣り合う連続区間をつなげる，みたいな実装の方が自然かもしれない．
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int n, k; while(cin >> n >> k, n) { vector<int> v(k); for(int i=0; i<k; ++i) { cin >> v[i]; } sort(v.begin(), v.end()); int f = v[0] == 0; int l = 0+f, r = 1+f, cnt = 0, next_l = -1; int res = 0; while(true) { next_l = -1; while(r < k && (v[r] - v[r-1] == 1 || v[r] - v[r-1] == 2)) { if(v[r] - v[r-1] == 1) { r++; } else if(cnt < f) { cnt++; next_l = r; r++; } else { break; } } res = max(res, r - l + ((r == k && cnt < f) || cnt)); if(r == k) { break; } if(next_l == -1) { l = r; r++; } else { l = next_l; } cnt = 0; } cout << res << endl; } }
AOJ 0302 Star Watching
解法
星を輝度でソートする．
輝度の最小（つまり左端）を決めて，しゃくとり法でできる．
座標の最大最小は，priority_queueでもmapでもmultisetでもなんでもよい．
自分は最初 priority_queue で書いて通したが，他の人のコードを読むと multiset が一番すっきりしていたのでそちらで書き直した．
計算量は O(NlogN)
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { int N, d; cin >> N >> d; vector<tuple<int, ll, ll>> v(N); for(int i=0; i<N; ++i) { int b; ll x, y; cin >> x >> y >> b; v[i] = make_tuple(b, x, y); } sort(v.begin(), v.end()); ll res = 0; multiset<ll> x, y; int r = 0; for(int l=0; l<N; ++l) { while(r < N && get<0>(v[r]) - get<0>(v[l]) <= d) { x.insert(get<1>(v[r])); y.insert(get<2>(v[r])); r++; } res = max(res, (*x.rbegin() - *x.begin()) * (*y.rbegin() - *y.begin())); if(r == N) { break; } x.erase(x.find(get<1>(v[l]))); y.erase(y.find(get<2>(v[l]))); } cout << res << endl; }
AOJ 0299 Railroad II
解法
d(i) をソートし，かつ p が 0 となるようにずらしておく．
ちょっと考えると，解の候補としては
- d(1) まで反時計回りで一周する
- d(M) まで時計回りで一周する
- d(i) まで時計回りで訪れた後，そこから反時計回りで d(i+1) まで訪れる
- d(i+1) まで反時計回りで訪れた後，そこから時計回りで d(i) まで訪れる
の4通りしかないことが分かる．
あとはこれを実装するだけ．
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int N, M, p; cin >> N >> M >> p; vector<int> d(M); for(int i=0; i<M; ++i) { cin >> d[i]; d[i] -= p; d[i] = (d[i] + N) % N; } sort(d.begin(), d.end()); int res = min(d.back(), N - d[0]); for(int i=0; i<M-1; ++i) { res = min(res, min(2*d[i] + (N - d[i+1]), 2*(N - d[i+1]) + d[i])); } cout << res * 100 << endl; }
AOJ 0254 Scone
問題概要
数列 {a_n} と整数 M が与えられる．
適当な i <= j を選んで ( a(i) + a(i+1) + ... + a(j) ) mod M を最大化せよ．
・制約
1 <= n <= 30000
1 <= M <= 100000
0 <= a(i) <= 2^32 - 1
解法
累積和と二分探索．
mod を取った累積和を sum(i) で表すことにする．
右端 j を固定すると，j までの累積和の中で sum(j) 以上で最小のもの sum(i) を見つけて， ( sum(j) - sum(i) + M ) mod M を見ていけば良い．
sum(i) を見つけるのに二分探索する．setにつっこめば楽．
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int n, m; while(cin >> n >> m, n) { vector<int> a(n+1); for(int i=1; i<=n; ++i) { cin >> a[i]; a[i] %= m; (a[i] += a[i-1]) %= m; } int res = 0; set<int> s; for(int i=1; i<=n; ++i) { auto it = s.upper_bound(a[i]); res = max(res, a[i]); if(it != s.end()) { res = max(res, (a[i] - *it + m) % m); } s.insert(a[i]); } cout << res << endl; } }
AOJ 0613 Treasures
問題概要
N 個の財宝が与えられ，それぞれ市場価値 w(i)と貴重度 v(i) が決まっている．
この財宝をAとBで分け合う．どちらも獲得しない財宝があってもよい．
分け合った後のAとBの財宝の市場価値の総和をそれぞれ Wa, Wb とする．
また，分け合った後のAとBの財宝の貴重度の総和を Va, Vb とする．
(Wa - Wb の絶対値) <= D を満たすようにしたとき，Vb - Va を最大化せよ．
・制約
1 <= N <= 30
1 <= w(i), v(i) <= 10^15
解法
w と v がでかいので半分全列挙．各要素は pair であり，first には Wa - Wb， second には Vb - Va を保存しておく．
TLE解（？）
半分前列挙した後，片方の集合をソートしておく．この集合を S1 とする．
その集合の各要素の貴重度 V(= p1.second) を，ソートされているこの順番にセグツリに代入しておく．
セグツリでは，各区間の最大値を管理するようにする．
もう片方の集合 S2 の各要素 p2 に対し，-D <= p1.first + p2.first <= D を満たすような集合 S1 の区間は二分探索により求まる．
この区間における S1 の V の最大値は，セグツリにクエリを投げれば分かる．
これを 集合 S2 の各要素にたいして行い，最大値を求める．
計算量は O(3^(N/2) log3^(N/2)) = O(N3^N)．
なんだけど，かなりギリギリで，実際8秒制限に対して9秒とかかかってしまう．
定数倍早くしたら通ると思うけど，そんな気力はなかった．ちーん．
間に合う解法
TLE 解では S1 しかソートしてないけど，S2 もソートしておくと良い性質が得られる．
S2 のある要素について調べ終わり，次の要素について調べるときを考える．
すると，S1 のなかの条件を満たす区間は，右にずれる以外ありえないことが（少し考えれば）わかる．
なので，しゃくとり法（スライド最小値？）の要領でやれば良い．
オーダーは変わらないけど，遅いのはソート部分だけなので，セグツリ使うよりは遥かに速い．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using P = pair<ll, ll>; constexpr ll INF = 1e18; void dfs(int i, int const last, vector<P>& res, vector<P> const& input, ll diff, ll val) { if(i == last) { res.emplace_back(diff, val); return; } dfs(i+1, last, res, input, diff-input[i].first, val-input[i].second); dfs(i+1, last, res, input, diff, val); dfs(i+1, last, res, input, diff+input[i].first, val+input[i].second); } int main() { int N; ll D; cin >> N >> D; vector<P> input(N); for(int i=0; i<N; ++i) { cin >> input[i].first >> input[i].second; } int N1 = N/2; vector<P> v1, v2; v1.reserve((int)pow(3, N1)); v2.reserve((int)pow(3, N-N1)); dfs(0, N1, v1, input, 0, 0); dfs(N1, N, v2, input, 0, 0); sort(v1.rbegin(), v1.rend()); sort(v2.begin(), v2.end()); ll ans = -INF; int t = 0; deque<P> deq; for(int i=0; i<v1.size(); ++i) { while(t < v2.size() && v2[t].first + v1[i].first <= D) { while(!deq.empty() && deq.back().second <= v2[t].second) { deq.pop_back(); } deq.push_back(v2[t]); ++t; } while(!deq.empty() && deq.front().first + v1[i].first < -D) { deq.pop_front(); } if(!deq.empty()) { ans = max(ans, v1[i].second + deq.front().second); } } cout << ans << endl; }
