AOJ 1359 Wall Clocks
解法
各点から半直線が2本出て，長方形の周上の2点で交わるが，それをそのまま処理すると面倒．
なので，(0, 0) -> (0, d) -> (w, d) -> (w, 0) -> (0, 0) という4辺を展開して，[0, 2(w+d)] という数直線上の区間にしてしまうと楽になる．
半直線は 45度 なので，展開後の座標は簡単な計算により求まる．
各点 i から見える範囲が [li, ri] とすると，ri の 昇順にソートしてやるとよい．最初にどこに時計を置くかを決めれば，あとは時計回り（つまり数直線の右方向）に，置いた時計が見えなくなるまで飛ばして，見えなくなったら追加することで解が得られる．
あとは，最初に時計を置く位置を全探索すれば最適解が求まる．
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; int main() { int n, w, d; cin >> n >> w >> d; vector<pii> v; for(int i=0; i<n; ++i) { int x, y; char f; cin >> x >> y >> f; if(f == 'W') { v.emplace_back(x + y, -x + y); } else if(f == 'N') { v.emplace_back(2*d + x - y, x + y); } else if(f == 'E') { v.emplace_back(2*(d+w) - x - y, 2*d + x - y); } else { v.emplace_back(2*(d+w) - x + y ,2*(d+w) - x - y); } } sort(v.begin(), v.end()); int L = 2*(w + d); int res = 1e9; for(int i=0; i<n; ++i) { auto tmp = v; for(int j=i-1; j>=0; --j) { if(tmp[j].first < tmp[i].first) { tmp[j].first += L; tmp[j].second += L; } } sort(tmp.begin(), tmp.end()); int cnt = 1; int now = tmp[0].first; for(int j=0; j<n; ++j) { if(tmp[j].second > now) { now = tmp[j].first; cnt++; } } res = min(res, cnt); } cout << res << endl; }
AOJ 1348 Space Golf
解法
完全にやるだけ．多少無駄なことをしても入力サイズが小さいので余裕で通る．
ご丁寧に式が書かれているので，それに従って候補を全部列挙し，それらが条件をみたすか（つまり接触しないか）を判定する．条件をみたす中で最小の値が答え．
明らかに最適なのは vx = vy となるときで，これでうまくいかないならどれかに接触してしまうということ．その時は，接触するギリギリを全て試してみて，その中で条件を満たし，かつ最小の値を求める．
g = 9.8 じゃないので注意．
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr double INF = 1e9; constexpr double eps = 1e-8; int main() { double d; int n, b; cin >> d >> n >> b; vector<double> p(n), h(n); for(int i=0; i<n; ++i) { cin >> p[i] >> h[i]; } double res = INF; for(int i=0; i<=b; ++i) { double interval = d / (i+1); bool neg = false; for(int j=0; j<=i; ++j) { for(int i=0; i<n; ++i) { neg |= abs(interval * j - p[i]) < eps; } } if(neg) { continue; } vector<double> vx, vy; vx.push_back(sqrt(interval / 2)); vy.push_back(vx.back()); for(int j=0; j<=i; ++j) { double now = interval * j; for(int k=0; k<n; ++k) { double pp = p[k] - now; if(0 < pp && pp < interval) { vx.push_back(sqrt(1 / (2*h[k]) * pp * (interval - pp))); vy.push_back(interval / (2 * vx.back())); } } } for(int j=0; j<vx.size(); ++j) { bool ok = true; for(int k=0; k<=i; ++k) { double now = interval * k; for(int l=0; l<n; ++l) { double pp = p[l] - now; if(0 < pp && pp < interval) { double t = pp / vx[j]; double hh = vy[j] * t - 0.5 * t*t; ok &= (hh - h[l]) >= -eps; } } } if(ok) { res = min(res, hypot(vx[j], vy[j])); } } } cout << fixed << setprecision(10) << res << endl; }
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; } } }
