AOJ 1324 Round Trip
解法
最短経路（それはそう）．
同じ高さの街が高々10しかないので，どの街に行ったか 2 ^ 10 で表現したい．
どの街に行ったかを保存しつつ最短経路をやりたいね，となる．
それにはまず，元のグラフの辺の向きをすべて逆に張った逆グラフをもう一つ用意する．
すると，戻りの条件が行きと全くおなじになる（低い方から高い方へ）．
ここまでやって以下の最短路を解く．
d[i][j][S] := 行きのパスの最後が i ，戻りのパスの最後（厳密に言うと先頭）が j であり，max(h[i], h[j]) の街の集合の使用状態がSであるときの最小コスト
ただし h[i] は街 i の高さ．
遷移するときは，max(h[i], h[j]) 以上のところしか行けないようにする．
遷移する条件は i を動かすときも j を動かすときも同じ．
計算量は O(n ^ 2 * 2^10 * log(...)) 程度．複数テストケースだから若干怖いけど，通るらしい．
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int inf = 1e9; struct edge { int to, cost; }; using edges = vector<edge>; using graph = vector<edges>; int main() { int n, m; while(cin >> n >> m, n) { vector<int> height(n), fee(n), bit(n); height[n - 1] = 1000; vector<int> h_cnt(1000); for(int i = 1; i < n - 1; ++i) { cin >> fee[i] >> height[i]; bit[i] = h_cnt[height[i]]++; } graph g(n), rg(n); for(int i = 0; i < m; ++i) { int a, b, c; cin >> a >> b >> c; g[a - 1].push_back(edge{b - 1, c}); rg[b - 1].push_back(edge{a - 1, c}); } vector<vector<vector<int>>> d(n, vector<vector<int>>(n, vector<int>(1 << 10, inf))); d[0][0][1] = 0; using state = tuple<int, int, int, int>; priority_queue<state, vector<state>, greater<state>> que; que.emplace(0, 0, 0, 1); while(!que.empty()) { int cur_d, u, v, S; tie(cur_d, u, v, S) = que.top(); que.pop(); const int cur_h = max(height[u], height[v]); for(auto& e : g[u]) { if(height[e.to] < cur_h) continue; const int nS = (1 << bit[e.to]) | (height[e.to] > cur_h ? 0 : S); const int nxt_d = cur_d + (height[e.to] == cur_h && (S & (1 << bit[e.to])) ? 0 : fee[e.to]) + e.cost; if(nxt_d < d[e.to][v][nS]) { d[e.to][v][nS] = nxt_d; que.emplace(nxt_d, e.to, v, nS); } } for(auto& e : rg[v]) { if(height[e.to] < cur_h) continue; const int nS = (1 << bit[e.to]) | (height[e.to] > cur_h ? 0 : S); const int nxt_d = cur_d + (height[e.to] == cur_h && (S & (1 << bit[e.to])) ? 0 : fee[e.to]) + e.cost; if(d[u][e.to][nS] > nxt_d) { d[u][e.to][nS] = nxt_d; que.emplace(nxt_d, u, e.to, nS); } } } cout << (d[n - 1][n - 1][1] == inf ? -1 : d[n - 1][n - 1][1]) << endl; } }
感想
実装重い系かと思いきや，そんなことはなかった．
Codeforces Round #176 (Div.1) E. Ladies' Shop
解法
FFT．
まず，答えの集合から生成できる任意の重さは，ある2個以下のカバンを使って（同じカバンを2つでもいい）作ることができる．
なぜなら，もしある重さを p1 + p2 + p3 で生成したとする．もちろん p3 は与えられたカバンに含まれているはずである．また，p1 + p2 も同様に，与えられたカバンに含まれているはずである．そうでなければ集合の選び方に矛盾する．
したがって，問題を言い換えると，
「与えられたかばんの重さからちょうど2つ（同じものを選んで良い）選んで作れる重さの集合が，与えられたかばんの集合の部分集合であることを判定し，さらにその集合を生成する最小の元の個数を求めよ」
となる．
これはFFTで計算できる．第 a[i] 項を1としてそれ以外を0とする多項式 P をつくり，FFT で P^2 を求めれば良いからである．
また，答えの集合に含めなければならない重さは，P^2 のうち係数が0 かつ かばんにその重さが含まれているものである．
このために，Pの第0項は場合の数を求めるときとはうってかわって0にして置かなければならない．
ソースコード
// convolution は略 // data_type := complex<double>; int main() { int n, m; scanf("%d %d", &n, &m); vector<int> a(n); vector<data_type> p(m + 1); unordered_set<int> s; for(int i = 0; i < n; ++i) { scanf("%d", &a[i]); p[a[i]] = data_type(1, 0); s.insert(a[i]); } auto p2 = convolution(p, p); vector<int> ans; bool ok = true; for(int i = 0; i <= m; ++i) { const int c = real(p2[i]) + 0.1; if(c == 0) { if(s.count(i) == 1) ans.push_back(i); continue; } ok &= s.count(i); } if(ok) { printf("YES\n%d\n", (int)ans.size()); for(int i = 0; i < (int)ans.size(); ++i) { if(i != 0) printf(" "); printf("%d", ans[i]); } printf("\n"); } else { printf("NO\n"); } }
感想
入出力が重いので注意．
自分のFFTはお世辞にも早いとは言えないので，TLEしてしまった．scanf/printf すると通る．
AOJ 2703 Dice Stamp
解法
明らかに全てのサイコロを使うのが最適．
あとは，後ろから見るbitDPで解く．
これは，最後に使うサイコロから決めていくと，その直前に使うサイコロによる得点が，今まで使ったサイコロでカバーされていない座標での得点と確定するからである．
前から見ると，今のサイコロが得た得点が最後まで残っているかを判断するのが厳しい．(追記 よく考えたら使ってないやつで被るところは得点に加えない、とやれば同じなので後ろからやらなくていいですね。後ろからのほうが楽だとは思うけど…)
サイコロ転がす部分は4方向しか無いのでそんなに辛くない．
計算量は一番重いところで O(2^n * n * |rot|) となり（ふつうのset とか使うと log つくけど），テストケースが 40 個あるとすると少し怪しいが AOJ のサーバーは速いので通る．
早くしたいなら，val[x][y] みたいに座標の値が小さいのを利用して2次元配列で管理すると良さそう．
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; enum { LEFT, RIGHT, FRONT, BACK, DOWN, UP }; class dice { public: dice(vector<int> score) : score(score) { assert(score.size() == 6); } void roll(char dir) { assert(dir == 'L' || dir == 'R' || dir == 'B' || dir == 'F'); vector<int> nscore = score; if(dir == 'L') { nscore[LEFT] = score[UP]; nscore[UP] = score[RIGHT]; nscore[RIGHT] = score[DOWN]; nscore[DOWN] = score[LEFT]; } else if(dir == 'R') { nscore[RIGHT] = score[UP]; nscore[UP] = score[LEFT]; nscore[LEFT] = score[DOWN]; nscore[DOWN] = score[RIGHT]; } else if(dir == 'F') { nscore[FRONT] = score[UP]; nscore[UP] = score[BACK]; nscore[BACK] = score[DOWN]; nscore[DOWN] = score[FRONT]; } else { nscore[BACK] = score[UP]; nscore[UP] = score[FRONT]; nscore[FRONT] = score[DOWN]; nscore[DOWN] = score[BACK]; } score = move(nscore); } int get_value(int dir) const { return score[dir]; } private: vector<int> score; }; int main() { const string dirs = "LRFB"; constexpr int dx[4] = {-1, 1, 0, 0}; constexpr int dy[4] = {0, 0, -1, 1}; int n; while(cin >> n, n) { // (x, y -> value); using traj = map<pii, int>; vector<traj> trajs; for(int i = 0; i < n; ++i) { int x, y; cin >> x >> y; vector<int> score(6); for(int j = 0; j < 6; ++j) { cin >> score[j]; } string rot; cin >> rot; dice d(score); traj t; t[make_pair(x, y)] = d.get_value(DOWN); for(char to : rot) { int dir = dirs.find(to); x += dx[dir], y += dy[dir]; d.roll(to); t[make_pair(x, y)] = d.get_value(DOWN); } trajs.push_back(move(t)); } vector<int> dp(1 << n); for(int S = 0; S < (1 << n); ++S) { set<pii> used; for(int i = 0; i < n; ++i) { if(S & (1 << i)) { for(auto& p : trajs[i]) { used.insert(p.first); } } } for(int i = 0; i < n; ++i) { if(S & (1 << i)) continue; map<pii, int> new_values; for(auto& p : trajs[i]) { if(used.count(p.first)) continue; new_values[p.first] = p.second; } int value = 0; for(auto& p : new_values) { value += p.second; } dp[S | (1 << i)] = max(dp[S | (1 << i)], dp[S] + value); } } cout << dp.back() << endl; } }
感想
8sec 制限だと高速化をサボりがち．
AOJ 2572 Venn Diagram
解法
頑張って実装するだけ．
円の半径は入力からすぐわかる．
2つの円の距離を二分探索で求めたら，でかい方を左下隅に配置．
小さいほうは [0, pi/2] でどの角度に置くとよいかを判定．計算したくないので二分探索もどきでサボる．
最後にはみ出ないか確認して終わり．
ソースコード
#include <bits/stdc++.h> using namespace std; using ld = long double; using point = complex<ld>; constexpr ld eps = 1e-5; constexpr ld pi = acos(-1.0); struct circle { circle(point p, ld r) : p(p), r(r) {} point p; ld r; }; vector<point> is_cc(circle const& c1, circle const& c2) { vector<point> res; ld d = abs(c1.p - c2.p); ld rc = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d); ld dfr = c1.r * c1.r - rc * rc; if(abs(dfr) < eps) { dfr = 0; } else if(dfr < 0) { return res; } ld rs = sqrt(dfr); point diff = (c2.p - c1.p) / d; res.push_back(c1.p + diff * point(rc, rs)); if(dfr != 0) { res.push_back(c1.p + diff * point(rc, -rs)); } return res; } // assert: c1 is left position ld intersect_area(circle c1, circle c2) { const ld d = abs(c1.p - c2.p); if(d >= c1.r + c2.r - eps) return 0; if(c1.r < c2.r) swap(c1.r, c2.r); if(d < eps) return (c2.r * c2.r * pi); auto ps = is_cc(c1, c2); assert(!ps.empty()); ld rad1 = abs(arg(ps[0] - c1.p)); ld S = c1.r * c1.r * rad1 - 0.5 * c1.r * c1.r * sin(2 * rad1); ld rad2 = pi - abs(arg(ps[0] - c2.p)); S += c2.r * c2.r * rad2 - 0.5 * c2.r * c2.r * sin(2 * rad2); return S; } int main() { cout << fixed << setprecision(10); ld w, h, a, b, ab; while(cin >> w >> h >> a >> b >> ab) { if(w == 0) break; const ld ra = sqrt(a / pi); const ld rb = sqrt(b / pi); if(min(w, h) < ra * 2 || min(w, h) < rb * 2) { cout << "impossible" << endl; continue; } circle c1(point(0, 0), ra); ld d = 0; { // calc dist ld lb = abs(ra - rb), ub = ra + rb; for(int loop = 0; loop < 100; ++loop) { const ld mid = (ub + lb) / 2; circle c2(point(mid, 0), rb); if(intersect_area(c1, c2) + eps < ab) { ub = mid; } else { lb = mid; } } d = lb; } // check bool swapped = ra < rb; c1.r = swapped ? rb : ra; c1.p = point(c1.r, c1.r); circle c2(point(c1.r + d, c1.r), swapped ? ra : rb); assert(abs(intersect_area(c1, c2) - ab) < 2 * eps); { ld lb = 0, ub = pi / 2; for(int loop = 0; loop < 60; ++loop) { const ld mid = (lb + ub) / 2; c2.p = c1.p + point(cos(mid) * d, sin(mid) * d); if(imag(c2.p) + c2.r > h + eps || real(c2.p) - c2.r < -eps) { ub = mid; } else if(real(c2.p) + c2.r > w + eps || imag(c2.p) - c2.r < -eps) { lb = mid; } else { break; } } } if(imag(c2.p) + c2.r <= h + eps && real(c2.p) + c2.r <= w + eps && imag(c2.p) - c2.r >= -eps && real(c2.p) - c2.r >= -eps) { if(swapped) swap(c1, c2); cout << real(c1.p) << ' ' << imag(c1.p) << ' ' << c1.r << ' '; cout << real(c2.p) << ' ' << imag(c2.p) << ' ' << c2.r << endl; } else { cout << "impossible" << endl; } } }
感想
こういうのを15分ぐらいで通せるようにならないとなあという感じ．
AOJ 1252 Confusing Login Names
解法
以下の4パターン全部試すだけ．
- swap しない（単に編集距離の問題）
- 1回swapしたあと編集距離
- 2回swap
- 消した後 swap
最悪 200(200-1)/2 * 16 * (16 * 16) なので，まあ適当にやると 2sec ぐらいで通る．
#include <bits/stdc++.h> using namespace std; constexpr int inf = 1e9; int levenshtein_distance(string s1, string s2) { const int n = s1.size(), m = s2.size(); vector<vector<int>> dp(n + 1, vector<int>(m + 1, inf)); for(int i = 0; i <= n; ++i) dp[i][0] = i; for(int j = 0; j <= m; ++j) dp[0][j] = j; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { dp[i][j] = min({dp[i][j], dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (s1[i - 1] != s2[j - 1])}); } } return dp[n][m]; } int main() { int n; while(cin >> n, n) { int d; cin >> d; vector<string> name(n); for(int i = 0; i < n; ++i) { cin >> name[i]; } vector<string> ans; for(int i = 0; i < n; ++i) { for(int j = i + 1; j < n; ++j) { auto s1 = name[i], s2 = name[j]; if(s1.size() < s2.size()) swap(s1, s2); const int m = s1.size(); int min_d = levenshtein_distance(s1, s2); // swap -> levenshtein for(int k = 0; k + 1 < m; ++k) { swap(s1[k], s1[k + 1]); min_d = min(min_d, levenshtein_distance(s1, s2) + 1); swap(s1[k], s1[k + 1]); } // swap -> swap for(int k = 0; k + 1 < m && min_d >= 3; ++k) { swap(s1[k], s1[k + 1]); for(int l = 0; l + 1 < m; ++l) { swap(s1[l], s1[l + 1]); if(s1 == s2) min_d = 2; swap(s1[l], s1[l + 1]); } swap(s1[k], s1[k + 1]); } // delete -> swap for(int k = 0; k < m && min_d >= 3; ++k) { auto ss1 = (k == 0 ? string("") : s1.substr(0, k)) + (k + 1 == m ? string("") : s1.substr(k + 1)); for(int l = 0; l + 1 < m - 1; ++l) { swap(ss1[l], ss1[l + 1]); if(ss1 == s2) min_d = 2; swap(ss1[l], ss1[l + 1]); } } if(min_d <= d) { ans.push_back(min(name[i], name[j]) + "," + max(name[i], name[j])); } } } sort(begin(ans), end(ans)); for(auto x : ans) { cout << x << endl; } cout << ans.size() << endl; } }
Helvetic Coding Contest 2018 E2. Guard Duty (medium)
解説
わからなかったので上位陣のコードから解法を得た．
とりあえずソートして隣接項の差を作ると，以下の問題になる．
n - 1 要素からなる数列から，k 個えらんでその和を最小化せよ．ただし，隣接2要素を取ってはならない．
基本は貪欲的に取っていく．つまりコストが小さい方から順に取る．
ここで，取ったやつの隣をどう扱うか考えるのだが，頭のいいやり方がある．
それは，今現在選んだ要素と，それに隣接している要素の集合の集合（集合の集合という表現であっている）を1つの整数値にまとめて set で管理するというものである．
たとえば，初期状態から考えると，それは n - 1 要素からなる集合となる（各集合は1つの要素からなる）．
この時 a[i] を選択したとすると，集合から a[i - 1], a[i], a[i + 1] を削除して新たに a[i - 1] + a[i + 1] - a[i] を追加する．そして，仮に次に a[i - 1] + a[i + 1] - a[i] の要素を選択するとするなら，それは a[i - 1] と a[i + 1] を選択したのを同じ状態になる．
したがって，この貪欲アルゴリズムを k 回行えば，最適解が求まる．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr ll inf = 1e18; int main() { int k, n; cin >> k >> n; vector<int> a(n); for(int i = 0; i < n; ++i) { cin >> a[i]; } sort(begin(a), end(a)); set<pair<ll, ll>> index_value, value_index; for(int i = 0; i + 1 < n; ++i) { index_value.emplace(i, a[i + 1] - a[i]); value_index.emplace(a[i + 1] - a[i], i); } index_value.emplace(-1, inf); index_value.emplace(n, inf); value_index.emplace(inf, -1); value_index.emplace(inf, n); ll res = 0; for(int lp = 0; lp < k; ++lp) { int v, l, r; ll val, lval, rval; tie(val, v) = *begin(value_index); auto it = index_value.lower_bound(make_pair(v, val)); tie(l, lval) = *prev(it); tie(r, rval) = *next(it); index_value.erase(make_pair(v, val)); index_value.erase(make_pair(l, lval)); index_value.erase(make_pair(r, rval)); value_index.erase(make_pair(val, v)); value_index.erase(make_pair(lval, l)); value_index.erase(make_pair(rval, r)); index_value.emplace(v, lval + rval - val); value_index.emplace(lval + rval - val, v); res += val; } cout << res << endl; }
感想
これめっちゃ頭いい…．思いつけたら気持ちいいだろうなあ．
賢い人は自明とかいうんだろうな…．
AOJ 1371 Infallibly Crack Perplexing Cryptarithm
解法
現れうる文字は高々8種類しかない．
なので各文字に対して何を割り当てるか全探索して構文解析するだけ．
ソースコード
#include <bits/stdc++.h> using namespace std; using ret_type = double; constexpr ret_type eps = 1e-8; ret_type expr(string const& s, int& p); ret_type term(string const& s, int& p); ret_type factor(string const& s, int& p); ret_type number(string const& s, int& p); ret_type expr(string const& s, int& p) { ret_type val = term(s, p); while(p < (int)s.size() && (s[p] == '+' || s[p] == '-')) { if(s[p] == '-') { val -= term(s, ++p); } else { val += term(s, ++p); } } return val; } ret_type term(string const& s, int& p) { ret_type val = factor(s, p); while(p < (int)s.size() && s[p] == '*') { val *= factor(s, ++p); } return val; } ret_type factor(string const& s, int& p) { if(s[p] == '-') { return -factor(s, ++p); } else if(s[p] == '(') { ret_type res = expr(s, ++p); if(p >= (int)s.size() || s[p] != ')') throw std::logic_error(""); ++p; return res; } else if(isdigit(s[p])) { return number(s, p); } else { throw std::logic_error(""); } } ret_type number(string const& s, int& p) { if(s[p] != '0' && s[p] != '1') throw std::logic_error(""); if(p + 1 < (int)s.size() && s[p] == '0' && isdigit(s[p + 1])) throw std::logic_error(""); ret_type res = 0; while(p < (int)s.size() && isdigit(s[p])) { res *= 2; res += (s[p++] == '1'); } return res; } int main() { string s; cin >> s; const int n = s.size(); vector<char> cs; for(auto c : s) { if(isalpha(c)) { cs.push_back(c); } } sort(begin(cs), end(cs)); cs.erase(unique(begin(cs), end(cs)), end(cs)); vector<char> v = {'0', '1', '+', '-', '*', '=', '(', ')'}; sort(begin(v), end(v)); if(cs.size() > v.size()) { cout << 0 << endl; return 0; } int ans = 0; set<string> checked; do { string t; for(auto c : s) { if(isalpha(c)) { t += v[find(begin(cs), end(cs), c) - begin(cs)]; } else { t += c; } } if(count(begin(t), end(t), '=') != 1) continue; int lp = 0, rp = find(begin(t), end(t), '=') - begin(t) + 1; if(rp == 1 || rp == n || checked.count(t) == 1) continue; checked.insert(t); try { auto lval = expr(t, lp), rval = expr(t, rp); if(t[lp] == '=' && rp == n && abs(lval - rval) < eps) { ans += 1; } } catch(...) { continue; } } while(next_permutation(begin(v), end(v))); cout << ans << endl; }
感想
これぞやるだけ問題って感じがする．
ret_type = double になってるのは，01しか現れないけどけど10進数解釈をするんだと勘違いして（しかもそれでサンプルが全部合う），31桁も来ると困るなあと思ったからです．普通に int で良い．
