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; }
AOJ 0145 Cards
問題概要
n 個のカードの山がある．カードには数字がかかれている．
それぞれの山の一番上と下のカードの数字は a(i) と b(i) である．
2つの山を重ねる操作を繰り返して，一つの山にすることを考える．
2つの山を重ねる時，それらの山の一番上と下にある4つのカードの数字を全てかけ合わせた値だけコストがかかる．
また，重ねる場合は，必ず左の山を上に，右の山を下にする．
この時，1つの山にするために必要なコストを最小化せよ．
制約
1 <= n <= 100
1 <= a(i), b(i) <= 200
解法
dp[i][j] := i 番目の山から j 番目の山までを1つの山にするために必要な最小のコスト
とする動的計画法で解ける．
ただし，dp[i][i] = 0 である．
dp[i][j] を求めるとき，i <= k < j なる各 k について考える．
すると，dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + a(i) * b(k) * a(k+1) * b(j)) という式が成り立つ．
（なぜなら，左の山は必ず上に重ねるから．）
これを i, j の幅を少しずつ増やしていけば，dp[0][n-1] が求める答えとなる．
計算量は O(n^3)．
ソースコード
#include <iostream> #include <vector> using namespace std; using ll = long long; constexpr ll INF = 1e18; int main() { int n; cin >> n; vector<vector<ll>> dp(n, vector<ll>(n, INF)); vector<ll> a(n), b(n); for(int i=0; i<n; ++i) { cin >> a[i] >> b[i]; } for(int i=0; i<n; ++i) { dp[i][i] = 0; } for(int w=1; w<n; ++w) { for(int i=0; i+w<n; ++i) { for(int j=i; j<i+w; ++j) { dp[i][i+w] = min(dp[i][i+w], dp[i][j] + dp[j+1][i+w] + a[i]*b[j]*a[j+1]*b[i+w]); } } } cout << dp[0][n-1] << endl; }
AOJ 0098 Maximum Sum Sequence II
問題概要
n次正方行列(a_ij)が与えられる．(a_ij) の部分行列の要素の和の最大値を求めよ．
・制約
1 <= n <= 100
解法
まず，要素の横方向について累積和を取る．
その後，横方向のある区間[i, j]を固定して考えてみる．
この区間の第 k 行の和はsum[k][j] - sum[k][i] である．
Sij[k] := sum[k][j] - sum[k][i] (k = 0, ... , N-1)とおく．
すると，この区間の幅を考えたときの最大値は，Sij[k] の連続する部分列の和の最大値を求める問題に帰着できる．
これは動的計画法でとけるので，最終的な計算量は O(N^3)である．
ソースコード
#include <iostream> #include <vector> using namespace std; using ll = long long; int main() { int n; cin >> n; vector<vector<int>> a(n, vector<int>(n)); for(int i=0; i<n; ++i) { for(int j=0; j<n; ++j) { cin >> a[i][j]; } } vector<vector<int>> sum(n, vector<int>(n+1)); for(int i=0; i<n; ++i) { for(int j=0; j<n; ++j) { sum[i][j+1] += sum[i][j] + a[i][j]; } } int res = -1e9; for(int i=0; i<=n; ++i) { for(int j=i+1; j<=n; ++j) { int t = 0; for(int k=0; k<n; ++k) { if(t < 0) { t = sum[k][j] - sum[k][i]; } else { t += sum[k][j] - sum[k][i]; } res = max(res, t); } } } cout << res << endl; }
TopCoder SRM 711 Div2 Hard TreeMovingDiv2
問題概要
与えられた引数にしたがって， 頂点数が n の m 個の木を構築します．
それぞれの木を T(i) とします．
各 i = 0, 1, ..., m-1 について，辺 e(i) ∈ T(i) を一つ選びます．
e(i) を T(i) から取り除き，T(i+1) に加えます．T(m-1) のものは T(0) に加えます．
この操作を行った後，すべての T(i) がまだ木であるような操作の仕方は何通りありますか．
1e9+7 で割った余りを求めなさい．
・ 制約
2 <= n <= 50
2 <= m <= 50
解法
m, n の制約が緩いので，愚直な DP で通ります．
dp[i][j][k] := i 番目の木から j 番目の辺を選び，かつ 0 番目の木からは k 番目の辺を選んでいた場合の数
とします．
あとは，T(i) に対して，T(i-1) の j 番目の辺を選んだときに，T(i) で k 番目の木を選んだ場合，T(i) が木になっているかを Union-find 木で確認します．
木になっていれば，各 l に対して dp[i][k][l] += dp[i-1][j][l] とすればよいです．
最後に，0 番目の木に戻ってきたときは処理が特別になります．
dp[0][i][i] を一旦 0 に戻します．
同じように j, k を選んだ時に，木になっていれば，今度は各 l に対してではなく，k のみ dp[i][k][k] += dp[i-1][j][k]; とします．
こうしないと，最初に k 番目の辺を選んでいたのに，違う辺を選んでいた場合の数が含まれてしまうためです．
あとは，dp[0][i][i] の総和を取れば，答えになります．
計算量は O(mn^3 * (union-findの分)) です．
ソースコード
#include <iostream> #include <vector> #include <cmath> using namespace std; // // union_find の実装は本質でないので省略 // using ll = long long; using edge = pair<int, int>; constexpr ll mod = 1e9+7; class TreeMovingDiv2 { public: int count(int n, vector<int> roots, vector<int> a, vector<int> b, vector<int> c) { const int m = roots.size(); vector<vector<edge>> es(m, vector<edge>(n-1)); for(int i=0; i<m; ++i) { vector<int> x(n-1); x[0] = c[i]; for(int k=1; k<n-1; ++k) { x[k] = ((ll)a[i] * x[k-1] + b[i]) % mod; } for(int j=0; j<n-1; ++j) { es[i][j].first = ((ll)roots[i] + j + 1) % n; es[i][j].second = ((ll)roots[i] + (x[j] % (j+1))) % n; } } vector<vector<vector<ll>>> dp(m+1, vector<vector<ll>>(n-1, vector<ll>(n-1))); for(int i=0; i<n-1; ++i) { dp[0][i][i] = 1; } for(int i=0; i<m; ++i) { int next = (i + 1) % m; if(next == 0) { for(int j=0; j<n-1; ++j) { dp[0][j][j] = 0; } } for(int j=0; j<n-1; ++j) { int prev_v = es[i][j].first, prev_u = es[i][j].second; for(int k=0; k<n-1; ++k) { union_find uf(n); uf.unite(prev_v, prev_u); for(int l=0; l<n-1; ++l) { if(k == l) { continue; } uf.unite(es[next][l].first, es[next][l].second); } if(uf.size(prev_v) == n) { if(next == 0) { (dp[next][k][k] += dp[i][j][k]) %= mod; } else { for(int l=0; l<n-1; ++l) { (dp[next][k][l] += dp[i][j][l]) %= mod; } } } } } } ll res = 0; for(int i=0; i<n-1; ++i) { (res += dp[0][i][i]) %= mod; } return res; } };
感想
本番で通せそうで時間が足りなかった問題．全完したかった．
しかしこれ，入力に悪意があって，木の構築段階で int だとオーバーフローするような入力があるくせに，関数定義は vector(int) を強制されてます．嫌がらせかな？？？
Div 1 の 1 <= n <= 300 だと O(n^3) ってことなんだろうけど，方法が全然わからない．
