AOJ 2334 Roads on Towns
解法
実は,A->B と C->D の少なくともどちらか一方は,直接結んでしまって良いことがわかる.そうすればあとは最短経路問題.
以下は自分のイメージ.
例えば図のように,(解が存在し,かつ)コストを最小化するためには青が迂回しなければならないケースを考える.
このとき,赤の始点と終点は,書かれている星のいずれかの2つの位置関係にあるはず.
もし左の2つの位置関係なら,青は迂回する必要がないのでおかしい.
もし上の2つの位置関係なら,赤は迂回する必要がある(か,直接結べる).直接結べない場合,その迂回ルートは,青の点線を通ることはできない.もしどのように迂回しても点線を通る場合は,同時に青の実線も通る必要が有るためである.
下の2つの位置関係なら,図のように直接結べる.
以上から,もし可能な答えが存在するなら,どちらかは直接結べば良いことがわかる.
AOJ 2592 Flowers
解法
3分探索.(自分は黄金比探索を持ってたのでそれを貼り付けた.)
使う水の量が決まれば,使う肥料の量は一位に定まる.つまり,コスト関数はWのみを引数とする関数である.
グラフをイメージしてみると,このグラフは(滑らかではないが)下に凸な関数であることがわかるので,3分探索すれば解が求まる.
3分探索でなくとも,明らかにLPの形をしてるので,双対を取ってやるのもよさそうではある.
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr double eps = 1e-8; constexpr double gratio = (std::sqrt(5)+1)/2.0; template <typename F> double golden_section_search(F f, double lb, double ub, int cnt) { double x1 = (ub-lb)/(gratio+1) + lb, x2 = (ub-lb)*gratio/(gratio+1) + lb; double v1 = f(x1), v2 = f(x2); for(int i=0; i<cnt; ++i) { if(v1 < v2) { ub = x2; x2 = x1; v2 = v1; x1 = (ub-lb)/(gratio+1) + lb; v1 = f(x1); } else { lb = x1; x1 = x2; v1 = v2; x2 = (ub-lb)*gratio/(gratio+1) + lb; v2 = f(x2); } } return (lb+ub)/2; } int main() { int N; while(cin >> N, N) { double pw; cin >> pw; vector<double> vw(N), pf(N), vf(N), th(N); double res = 0; for(int i=0; i<N; ++i) { cin >> vw[i] >> pf[i] >> vf[i] >> th[i]; res += max(0.0, th[i] / vf[i] * pf[i]); } auto f = [&](double W) { double cost = W * pw; for(int i=0; i<N; ++i) { cost += max(0.0, (th[i] - vw[i] * W) / vf[i] * pf[i]); } return cost; }; cout << fixed << setprecision(10) << f(golden_section_search(f, 0, 1e9, 300)) << endl; } }
AOJ 2595 Cookie Counter
解法
1枚も食べない日を考えるとややこしい(し,Dがでかいのでそのまま求められない)ので,D 日のうち一枚も食べない日はあとで決めることにすればよい.
つまり,まずは一日に最低1枚は食べる場合の数を求める.すると,必ずN日目までには食べきるので,O(N^2) の DP に落とし込めそう.
dp[i][j] := i 日目までに j 枚のクッキーを食べる場合の数
としてDPする.一日に X 枚"未満"だけ食べられるので,以下の遷移が成り立つ.
dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + ... + dp[i-1][j-X+1]
これを愚直に書くと O(N^3) だが,よく見ると単純に区間和を求めているだけなので,累積和を取れば O(N^2) にできる.
最後に,一日に食べない日を D 日のうちから決めるのだが,D がでかいので Cmb(D, 1) から Cmb(D, min(N, D)) まで順番に求めていけば O(N) で求められる.
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr ll M = 1e9+7; // calc x // ax %% 1 (mod M) ll inv(ll a, ll p) { return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p); } int main() { ll N, D, X; while(cin >> N >> D >> X, N) { vector<vector<ll>> dp(N+1, vector<ll>(N+1)); dp[0][0] = 1; vector<vector<ll>> dp_sum(N+1, vector<ll>(N+1)); fill(dp_sum[0].begin(), dp_sum[0].end(), 1); for(int i=1; i<=N; ++i) { for(int j=i; j<=N; ++j) { if(j-X >= 0) { dp[i][j] = (dp_sum[i-1][j-1] - dp_sum[i-1][j-X] + M) % M; } else { dp[i][j] = dp_sum[i-1][j-1]; } } for(int j=1; j<=N; ++j) { dp_sum[i][j] = (dp_sum[i][j-1] + dp[i][j]) % M; } } ll res = 0; ll cmb = 1; for(int i=1; i<=min(N, D); ++i) { cmb = (cmb * ((D-i+1) % M)) % M; cmb = (cmb * inv(i, M)) % M; res = (res + dp[i][N] * cmb) % M; } cout << res << endl; } }
AOJ 2570 Shipura
解法
> が >> なのか S < expr > の > なのかは,数字またはSの直前かどうかで判定ができる.
なので最初に式を後ろから見ていって,どれがシフト演算なのか確定させておく.
それができればあとは普通に左からパースするだけで十分.
シフト演算のときにシフトしすぎないように注意すること.
他の人は右から再帰的にやっていくという方法を取っていて,そっちのほうが良さそうだなーとは思った.
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr ll M = 1e9+7; vector<bool> f; ll expr(string const& s, int& p); ll term(string const& s, int& p); void sp(string const& s, int& p); ll number(string const& s, int& p); ll expr(string const& s, int& p) { sp(s, p); ll v1 = term(s, p); sp(s, p); while(p+1 < s.size() && f[p]) { p += 2; sp(s, p); ll v2 = term(s, p); if(v2 > 63) { v1 = 0; } else { v1 >>= v2; } sp(s, p); } return v1; } ll term(string const& s, int& p) { sp(s, p); if(s[p] == 'S') { sp(s, ++p); p++; // < sp(s, p); ll v = expr(s, p); sp(s, p); p++; // > v = (v * v) % M; return v; } return number(s, p); } void sp(string const& s, int& p) { while(p < s.size() && s[p] == ' ') { p++; } } ll number(string const& s, int& p) { int res = 0; while(p < s.size() && isdigit(s[p])) { res *= 10; res += s[p++] - '0'; } return res; } int main() { while(true) { string s; getline(cin, s); if(s[0] == '#') { break; } int p = 0; f.assign(s.size(), false); for(int i=s.size()-1; i>=0; --i) { if(isdigit(s[i]) || s[i] == 'S') { if(isdigit(s[i])) { while(i > 0 && isdigit(s[i])) { --i; } } else if(s[i] == 'S') { i--; } while(i > 0 && s[i] == ' ') { i--; } if(s[i] == '>') { i--; f[i] = true; } } } cout << expr(s, p) << endl; } }
AOJ 2512 Ononokomachi's Edit War
解法
適当に置換 or 削除でminimax法だと明らかに間に合わないので,すこし考える必要がある.
冷静に考えると,N が偶数のときは2ターン,N が奇数のときは1ターンやるのと変わらないことが分かる.
大まかには以下のように考えた.
- 任意に削除,挿入が可能なので,直前の手番をキャンセルさせることが可能
- minimax法の要領で,先手は遷移先でもっとも良いものを選ぼうとする
- 最終的に有利な手が選ばれるのだから,後手としてはキャンセルするほうがよい
- つまり結局,お互いに最後だけを考えればよい(もちろん最後の手がキャンセルでもよい)
高々 N = 2 と言っているのと同じなので,挿入,削除に関して全通り試しても十分間に合う.
毎回の操作で式として成り立っている必要が有ることに注意.
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int INF = 1e9; int expr(string const& s, int& p); int Or(string const& s, int& p); int Xor(string const& s, int& p); int And(string const& s, int& p); int Plus(string const& s, int& p); int term(string const& s, int& p); int factor(string const& s, int& p); int number(string const& s, int& p); int expr(string const& s, int& p) { return Or(s, p); } int Or(string const& s, int& p) { int res = Xor(s, p); while(p < s.size() && s[p] == '|') { res |= Xor(s, ++p); } return res; } int Xor(string const& s, int& p) { int res = And(s, p); while(p < s.size() && s[p] == '^') { res ^= And(s, ++p); } return res; } int And(string const& s, int& p) { int res = Plus(s, p); while(p < s.size() && s[p] == '&') { res &= Plus(s, ++p); } return res; } int Plus(string const& s, int& p) { int res = term(s, p); while(p < s.size() && (s[p] == '+' || s[p] == '-')) { char op = s[p++]; if(op == '+') { res += term(s, p); } else { res -= term(s, p); } } return res; } int term(string const& s, int& p) { int res = factor(s, p); while(p < s.size() && s[p] == '*') { res *= factor(s, ++p); } return res; } int factor(string const& s, int& p) { if(isdigit(s[p])) { if(s[p] == '0') { throw runtime_error(""); } return number(s, p); } if(s[p] == '(') { int res = expr(s, ++p); ++p; return res; } throw runtime_error(""); } int number(string const& s, int& p) { int res = 0; while(p < s.size() && isdigit(s[p])) { res *= 10; res += s[p++] - '0'; } return res; } string pattern = "0123456789*+-&^|"; int parse(string const& s) { try { int p = 0; int t = expr(s, p); if(p != s.size()) { return INF; } return t; } catch(...) { return INF; } } int solve(string s, int cnt, int turn) { if(cnt == 0) { return parse(s); } int res = (turn == 0 ? -INF : INF); // erase for(int i=0; i<s.size(); ++i) { string t = s; t.erase(t.begin()+i); if(t.size() == 0 || INF == parse(t)) { continue; } int tmp = solve(t, cnt-1, turn^1); if(tmp == INF) { continue; } if(turn == 0) { res = max(res, tmp); } else { res = min(res, tmp); } } // insert for(int i=0; i<pattern.size(); ++i) { for(int j=0; j<=s.size(); ++j) { string t = s; t.insert(t.begin()+j, pattern[i]); if(INF == parse(t)) { continue; } int tmp = solve(t, cnt-1, turn^1); if(tmp == INF) { continue; } if(turn == 0) { res = max(res, tmp); } else { res = min(res, tmp); } } } return res; } int main() { int n; string s; while(cin >> n >> s, n) { if(n & 1) { cout << solve(s, 1, 0) << endl; } else { cout << solve(s, 2, 0) << endl; } } }
AOJ 2255 6/2(1+2)
解法
BNFどおりに実装する必要はなくて,区間DPをすればよい.
その区間で取りうる値の集合を持たせておく.
区間 [l..r] の演算子を全て見ていって [l..i-1] と [i+1..r] に分ける.
この時,演算子で分けて括弧の対応が崩れるなら一旦スルーしておく必要がある.
たとえば,括弧が ( .. ( .. op_i .. ) .. ) となっていると,op_i で左右に分けることができない.
これは最初に括弧の対応付を調べておけばよい.
また,( expr ) となっているときは, expr に置き換えて処理するとよい.
ソースコード
#include <bits/stdc++.h> using namespace std; set<int> memo[201][201]; vector<int> par_pos; int number(string const& s, int p) { int res = 0; while(p < s.size() && isdigit(s[p])) { res *= 10; res += s[p++] - '0'; } return res; } set<int> solve(string const& s, int l, int r) { auto& res = memo[l][r]; if(res.size() != 0) { return res; } bool f = true; for(int i=l; i<=r; ++i) { f &= isdigit(s[i]); } if(f) { res.insert(number(s, l)); return res; } if(par_pos[l] == r) { return res = solve(s, l+1, r-1); } vector<int> pare(s.size()); for(int i=l; i<=r; ++i) { if(s[i] == '(') { pare[i] = 1; } if(s[i] == ')') { pare[i] = -1; } if(i != l) { pare[i] += pare[i-1]; } } for(int i=l+1; i<r; ++i) { char c = s[i]; if(pare[i] != 0) { continue; } if(c == '+' || c == '-' || c == '*' || c == '/') { set<int> s1 = solve(s, l, i-1); set<int> s2 = solve(s, i+1, r); for(auto x : s1) { for(auto y : s2) { if(c == '+') { res.insert(x + y); } else if(c == '-') { res.insert(x - y); } else if(c == '*') { res.insert(x * y); } else { if(y == 0) { continue; } res.insert(x / y); } } } } } return res; } int main() { string s; while(cin >> s, s != "#") { for(int i=0; i<201; ++i) { for(int j=0; j<201; ++j) { memo[i][j].clear(); } } par_pos.assign(s.size(), -1); stack<int> p; for(int i=0; i<s.size(); ++i) { if(s[i] == '(') { p.push(i); } if(s[i] == ')') { par_pos[p.top()] = i; p.pop(); } } cout << solve(s, 0, s.size()-1).size() << endl; } }
AOJ 1350 There is No Alternative
問題概要
連結グラフ G が与えられる.一般に G の最小全域木は複数存在しうる.G のすべての最小全域木に必ず含まれている辺を求めよ.
・制約
3 <= N <= 500
N-1 <= M <= min(50000, N(N-1)/2)
解法
最小全域木 T を一つ求める.すると,候補の辺は必ずこの T に含まれている.
よって,T に含まれる辺を一つ使えないようにした状態で,最小全域木 T2 を構築してみる.w(T) != w(T2) ならば,この時使えなくした辺は必ず使う辺である.
計算量は O(MlogM + NMα(N)).
ソースコード
#include <bits/stdc++.h> using namespace std; class union_find { public: union_find(int n) : par_(n, -1) {} void init(int n) { par_.assign(n, -1); } int root(int x) { return par_[x] < 0 ? x : par_[x] = root(par_[x]); } bool unite(int x, int y) { x = root(x); y = root(y); if(x == y) { return false; } else { if(par_[x] < par_[y]) { par_[x] += par_[y]; par_[y] = x; } else { par_[y] += par_[x]; par_[x] = y; } return true; } } bool same(int x, int y) { return root(x) == root(y); } int size(int x) { return -par_[root(x)]; } private: std::vector<int> par_; }; using weight = int; struct edge { int u, v; weight cost; bool operator<(edge const& e) const { return cost < e.cost; } }; using edges = std::vector<edge>; using graph = std::vector<edges>; int main() { int N, M; cin >> N >> M; edges es(M); for(int i=0; i<M; ++i) { cin >> es[i].u >> es[i].v >> es[i].cost; es[i].u--; es[i].v--; } sort(es.begin(), es.end()); int mst_sum = 0; edges mst; union_find uf(N); for(int i=0; i<M; ++i) { if(!uf.same(es[i].u, es[i].v)) { uf.unite(es[i].u, es[i].v); mst.push_back(es[i]); mst_sum += es[i].cost; } } int cnt = 0, res_sum = 0; for(int i=0; i<N-1; ++i) { uf.init(N); int sum = 0; for(auto& e : es) { if(!uf.same(e.u, e.v) && (mst[i].u != e.u || mst[i].v != e.v)) { uf.unite(e.u, e.v); sum += e.cost; } } if(sum != mst_sum) { cnt++; res_sum += mst[i].cost; } } cout << cnt << ' ' << res_sum << endl; }