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 で良い．
AOJ 1351 Flipping Parentheses
解法
StarrySkyTree + 二分探索で通した．
( を +1, ) を -1 として累積和をStarrySkyTree上で管理する．
文字列が balanced であることと，累積和上の最小値が 0 以上であり，かつ末尾の値が0であることは同値である．
さて，与えられた位置をとりあえず反転して考える．
( -> ) に反転した場合，明らかに反転後最も左に現れる ) の位置が答えになる（証明も簡単）．
) -> ( に反転した場合が問題である．
ある位置の ( を ) に反転できる条件は，それ以降の累積和の値の最小値が2以上であることに気がつけば，二分探索で求めるだけになる．
計算量は O(N(logN)^2) となる．
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int inf = 1e9; class starry_sky_tree { public: starry_sky_tree(int n_) : n(expand(n_)), data(n * 2, 0), lazy(n * 2, 0) {} void add(int l, int r, int val) { l += n, r += n; const int left = l, right = r; while(l != r) { if(l & 1) { lazy[l] += val; data[l++] += val; } if(r & 1) { lazy[--r] += val; data[r] += val; } l /= 2, r /= 2; } l = left, r = right - 1; while(l /= 2, r /= 2) { data[l] = min(data[l * 2], data[l * 2 + 1]) + lazy[l]; data[r] = min(data[r * 2], data[r * 2 + 1]) + lazy[r]; } } int query(int l, int r) const { l += n, r += n; int res1 = inf, res2 = inf; while(l != r) { if(l & 1) res1 = min(res1, data[l++]); if(r & 1) res2 = min(res2, data[--r]); l /= 2, r /= 2; res1 += lazy[l - 1]; res2 += lazy[r]; } --l; while(l /= 2, r /= 2) { res1 += lazy[l]; res2 += lazy[r]; } return min(res1, res2); } private: int expand(int n) { return n == 1 ? n : expand((n + 1) / 2) * 2; } private: const int n; vector<int> data, lazy; }; int main() { int N, Q; string s; cin >> N >> Q >> s; starry_sky_tree sum(N); set<int> right_paren; for(int i = 0; i < N; ++i) { if(s[i] == '(') { sum.add(i, N, 1); } else { sum.add(i, N, -1); right_paren.insert(i); } } while(Q--) { int q; cin >> q; q--; int ans = q; if(s[q] == '(') { sum.add(q, N, -2); right_paren.insert(q); ans = *right_paren.begin(); right_paren.erase(ans); sum.add(ans, N, 2); } else { sum.add(q, N, 2); int lb = 0, ub = N - 1; while(ub - lb > 1) { const int mid = (lb + ub) / 2; if(sum.query(mid, N) >= 2) { ub = mid; } else { lb = mid; } } ans = ub; sum.add(ans, N, -2); right_paren.erase(q); right_paren.insert(ans); } swap(s[q], s[ans]); cout << ans + 1 << endl; } }
感想
swap(s[q], s[ans]) を書き忘れて WA をもらってしまった．
AOJ 1333 Beautiful Spacing
解法
二分探索＋しゃくとり法．
二分探索は，普通に「スペースの隙間を X にして条件をクリアできるか」でやる．
次にしゃくとり部分．二分探索の過程で与えられた，空けていい間隔を S とする．
先に以下のテーブルを定義しておく．
dp[i] := i 番目の単語を左端にして，その後ろだけ考えた場合にクリアできるか．
更新は後ろからやる．
まず各 i について，「x[i] から x[j] まで一行に詰め込めるような，最大の j 」を考え，R1 とする．
次に，各 i について「x[i] から x[j] まで一行に詰め込んだ時に，Sをクリアできるような最小の j 」を R2 とする．
すると，R2 から R1 の間であれば，どこで一行を終えてもよい．また，位置 p を右端にして区切ってクリアできるかどうかは，dp[p + 1] をみればわかる．
したがって，
dp[i] = (dp[R2 + 1] + ... + dp[R1+1]) > 0
となる．
R1, R2, dp[R2 + 1] + ... + dp[R1 + 1] はすべてしゃくとりで計算できる．
したがって，これで計算量が O(NlogW) にできている．
ただし，最終行だけは右端に文字を置く必要がないと問題文に書かれているので，そこだけ辻褄を合わせる．
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int W, N; while(cin >> W >> N, W) { vector<int> x(N), sum(N + 1); for(int i = 0; i < N; ++i) { cin >> x[i]; sum[i + 1] = sum[i] + x[i]; } auto check = [&](int space) { vector<int> dp(N + 1); int limit_r = N, ok_r = N; int ok_cnt = 0; for(int i = N - 1; i >= 0; --i) { while(W - (sum[limit_r] - sum[i]) - (limit_r - i - 1) < 0) { ok_cnt -= dp[limit_r--]; } while(ok_r > limit_r || ok_r - i - 1 > 0 && (W - (sum[ok_r] - sum[i]) + ok_r - i - 2) / (ok_r - i - 1) <= space) { ok_cnt += dp[ok_r--]; } dp[i] = limit_r == N || ok_cnt > 0; } return dp[0] == 1; }; int lb = 0, ub = W; while(ub - lb > 1) { const int mid = (ub + lb) / 2; if(check(mid)) { ub = mid; } else { lb = mid; } } cout << ub << endl; } }
感想
無限にバグった．
最初 O(NlogNlogW) 解で通るやろと贅沢に書いていたら11secぐらいでTLEしてしまい，泣きながらしゃくとりを書いた．
終わってみればしゃくとりのほうがコードはスッキリしていた．
