AOJで最近解いた問題
AOJ-ICPCの250~500くらいの問題を何問か復習(自分用)。
2200 Mr.リトー郵便局
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2200
りとうさんが郵便局を巡る。ただし、陸路と海路があり、船が一台しかないので船の場所を考える必要がある。順番は与えられる。
一見巡回セールスマンみたいですが順番が与えられるので多項式時間に落ちます。あらかじめワーシャルフロイドかなにかで陸・海別々に最短距離を求めてから
dp[i][j] := (経路の)i番目まで回って船がjにあるときの最短距離
とすると
REP(i, 1, R) rep(j, N){ dp[i][j] = min(dp[i][j], dp[i - 1][j] + (ll)land[z[i - 1]][z[i]]); rep(k, N) dp[i][k] = min(dp[i][k], dp[i - 1][k] + (ll)land[z[i - 1]][j] + (ll)sea[j][k] + (ll)land[k][z[i]]); }
で解けます。オーバーフローに注意。
面白い問題でしたが、陸路だけのときは下の更新式で処理できないことに気づけずハマってしまいました。
2011 Gather the maps!
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011
memo[i][j] := iさんはjさんと会っている可能性がある
というのを総当りで更新していくみたいな感じで解きました。これも面白かったです。
vector<int> f[30]; bool memo[50][50]; int main(){ cin.tie(0); ios::sync_with_stdio(false); int N, _t, _f; while(cin >> N && N){ rep(i, 30) f[i].clear(); memset(memo, 0, sizeof(memo)); rep(i, N) memo[i][i] = true; rep(i, N){ cin >> _t; rep(j, _t){ cin >> _f; f[_f - 1].push_back(i); } } rep(i, 30){ for(int k : f[i]) for(int l : f[i]) rep(j, N) memo[k][j] |= memo[l][j]; for(int k : f[i]) if(count(memo[k], memo[k] + N, 1) == N){ cout << i + 1 << endl; goto success; } } cout << -1 << endl; continue; success: continue; } return 0; }
2254 Fastest Route
ビットDP
2301 Sleeping Time
普通に探索を書いた後に枝刈り。二分探索は上界と下界の間の値しか出せないので枝刈りでかなり計算量が落ちます。
const double EPS = 1.0e-10; int K; double UB, LB, P, E, T; double dfs(double lb, double ub, int turn){ if(T + E + EPS < lb) return 0.0; if(ub < T - E - EPS) return 0.0; if(T - E + EPS < lb && ub < T + E - EPS) return 1.0; double mid = (lb + ub) / 2; if(turn == 0) return abs(T - mid) <= (EPS + E) ? 1.0 : 0.0; double res = 0.0; double p1 = 1.0 - P, p2 = P; if((T - EPS) <= mid) swap(p1, p2); res += dfs(mid, ub, turn - 1) * p1; res += dfs(lb, mid, turn - 1) * p2; return res; } int main(){ scanf("%d%lf%lf%lf%lf%lf", &K, &LB, &UB, &P, &E, &T); printf("%.10f\n", dfs(LB, UB, K)); return 0; }
2176 For the Peace
これ貪欲で解けるのか……。貪欲はどうしても苦手です。要復習。
#include <bits/stdc++.h> using namespace std; typedef long long int ll; const int INF = 1000000000; #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++) #define rep(i,n) REP(i, 0, n) int N, D; int main(){ cin.tie(0); ios::sync_with_stdio(false); int _t, _s; while(cin >> N >> D && N){ vector<int> m[100]; vector<int> sum(N, 0); rep(i, N){ cin >> _t; rep(j, _t){ cin >> _s; m[i].push_back(_s); sum[i] += _s; } } while(true){ bool updated = false; rep(i, N) while(m[i].size()){ sum[i] -= m[i].back(); if(*max_element(sum.begin(), sum.end()) - sum[i] <= D){ m[i].pop_back(); updated = true; }else{ sum[i] += m[i].back(); break; } } if(!updated) break; } rep(i, N - 1) sum[i + 1] += sum[i]; if(sum[N - 1] == 0) cout << "Yes" << endl; else cout << "No" << endl; } return 0; }
めちゃくちゃ適当な内容になってしまいましたがこのへんで。