Codeforces Round #318 (Div.1) B. Bear and Blocks
解法
1ステップ後の h[i] の高さは min(h[i - 1], h[i] - 1, h[i + 1]) になる。
一般化して、k ステップ後の h[i] の高さは min(h[i - k], h[i - k + 1] - 1, ..., h[i] - k, ..., h[i + k]) になる。
逆に考えると、h[i] の高さが 0 になるときは、ある j に対して min(h[i - j] - (k - j)) = 0 (j = -k, ..., k) が成り立つ時なので、k = h[i - j] + j である。
これは、左（と右）から順番に見ていけば求めることができるので、線形で解ける。
問題文
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> h(n + 2); for(int i = 1; i <= n; ++i) { cin >> h[i]; } auto calc = [n] (vector<int> hs, bool rev = false) { if(rev) reverse(begin(hs), end(hs)); vector<int> vs(n + 2); int mini = 0; for(int i = 1; i <= n; ++i) { mini++; if(mini > hs[i]) mini = hs[i]; vs[i] = mini; } if(rev) reverse(begin(vs), end(vs)); return vs; }; auto left = calc(h), right = calc(h, true); int ans = 0; for(int i = 1; i <= n; ++i) { ans = max(ans, min(left[i], right[i])); } cout << ans << endl; }
感想
なんで解けなかったのか、これがわからない。
完全に変なことを考えて泥沼化していた。
AOJ 2850 Endless BFS
解法
01BFSで解いた。
まず、2部グラフだと永遠に終わらないことはわかる。
2部グラフじゃない場合、どこかのタイミングで隣接2頂点が同時に current に入り、そこからそれらの頂点は一生消えない。
そして、そこからどんどん頂点集合が広がっていくことがわかる。
どのタイミングで初めて隣接2頂点が current に入るかは普通に BFS をして、隣接頂点が同じ距離にあることが条件である。
そういう隣接2頂点を見つけたら次からは stable （消えない）状態にうつして、そっちはそっちでBFSをする。
ただし、stable のときの遷移は注意が必要である。例えば今 stable な状態で v にいたとして、隣接頂点 u に移ることを考える。stable な v に至るまでのコストを c1、u の頂点0からの距離を c2 とすると、c1, c2 のパリティが等しいときはコストを0にする（v に至ったタイミングで、u も stable とみなせるから）。
なので、01BFS をすればよいということになる。
stable であるかそうでないかで頂点の数を2倍持っておけばよく、計算量は O(n + m) である。
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int inf = 1e9; int main() { int n, m; cin >> n >> m; vector<vector<int>> g(n); for(int i = 0; i < m; ++i) { int u, v; cin >> u >> v; g[u - 1].push_back(v - 1); g[v - 1].push_back(u - 1); } vector<vector<int>> d(n, vector<int>(2, inf)); d[0][0] = 0; deque<tuple<int, int>> que; que.emplace_back(0, 0); while(!que.empty()) { int v, stable; tie(v, stable) = que.front(); que.pop_front(); if(stable == 0) { for(auto to : g[v]) { if(d[to][0] == d[v][0]) { d[v][1] = d[v][0]; que.emplace_back(v, 1); } if(d[to][0] == inf) { d[to][0] = d[v][0] + 1; que.emplace_back(to, 0); } } } else { for(auto to : g[v]) { if(d[to][1] != inf) continue; if((d[to][0] & 1) == (d[v][1] & 1)) { d[to][1] = d[v][1]; que.emplace_front(to, 1); } else { d[to][1] = d[v][1] + 1; que.emplace_back(to, 1); } } } } int ans = 0; for(int i = 0; i < n; ++i) { ans = max(ans, d[i][1]); } cout << (ans == inf ? -1 : ans) << endl; }
感想
想定解はもっと賢かった。
最初にグラフ作るタイミングですでに頂点を2倍にしておいて、偶数を表す頂点と奇数を表す頂点間に辺をはる感じだった。そうするとただのBFSやるだけになる。
まあ解けたので良し。
AOJ 2847 Ninja Map
解法
まず一行目を適当に埋める。次数が 2 の頂点を見つけて、そこから隣接する中で一番小さい次数の頂点をたどっていけば自然に一行埋められる。
一行目が埋まると、下の行の数は一意に定まるので、あとは順番に埋めていくだけ。
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<vector<int>> g(n * n); for(int i = 0; i < 2 * n * n - 2 * n; ++i) { int a, b; cin >> a >> b; g[a - 1].push_back(b - 1); g[b - 1].push_back(a - 1); } vector<bool> used(n * n); vector<vector<int>> ans(n, vector<int>(n, -1)); for(int i = 0; i < n * n; ++i) { // r1 if(g[i].size() == 2u) { int cur = i; ans[0][0] = cur; used[cur] = true; for(int j = 0; j < n - 1; ++j) { int nxt = -1; for(auto to : g[cur]) { if(used[to] || (nxt != -1 && g[nxt].size() < g[to].size())) continue; nxt = to; } cur = ans[0][j + 1] = nxt; used[nxt] = true; } break; } } for(int i = 0; i < n - 1; ++i) { for(int j = 0; j < n; ++j) { for(auto to : g[ans[i][j]]) { if(used[to]) continue; ans[i + 1][j] = to; used[to] = true; } } } for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) { cout << ans[i][j] + 1 << " \n"[j + 1 == n]; } } }
感想
O(n^4) も徳が高い人なら通りそう。
僕は試したんですがあと 0.2sec 縮めればOKだったので適当に定数倍早くすればよさそう。
AOJ 2858 Prime-Factor Prime
解法
区間篩の要領で解ける。
[1, 1e5] ぐらいまでの素数を普通に篩で検出し、素数が見つかれば [L, R] にカウントを割り振っていく。
今回の場合は、素数 p が検出できたら、[L, R] には p, p^2, ... の倍数のところに1をカウントしていくことになる。
しかしこれだけだと不十分で、素因数分解でよくある （小さい素数）*（でかい素数）のでかい素数のほうがカウントされない。
なので、カウントする配列の他に、[L, R] の値を直に持っている配列を用意し、割り振るたびにその値を p で割っていくとよい。
最後に、カウンタの値と、割られて残った数が1であるか（1でないならそれも素因数なので、追加で1カウント）によって、その値が prime factor prime であるか判定する。
計算量は、篩の中で p, p^2, ... を見ていくから、結局 O(PlogRloglogP + (R - L))
（ただし、P は篩のテーブルのサイズ）で、体感はもっと早い。
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { const int max_p = 1 << 18; int l, r; cin >> l >> r; vector<int> ns(r - l + 1); for(int i = 0; i <= r - l; ++i) { ns[i] = i + l; } vector<int> cnt(r - l + 1); vector<bool> is_prime(max_p, true); is_prime[0] = is_prime[1] = false; for(int i = 2; i < max_p; ++i) { if(is_prime[i]) { for(int j = i + i; j < max_p; j += i) is_prime[j] = false; ll x = i; while(x <= r) { for(int j = (l + x - 1) / x * x; j <= r; j += x) { cnt[j - l] += 1; ns[j - l] /= i; } x *= i; } } } int ans = 0; for(int i = 0; i < r - l + 1; ++i) { if(ns[i] > 1) cnt[i] += 1; ans += is_prime[cnt[i]]; } cout << ans << endl; }
AOJ 2593 Square in Circles
解法
辺の長さをまず決め打つと、それぞれの円と交わる部分が区間として求まる。
得られた区間の連結な部分の総長さで、決めうった値よりも長い所があれば、そのような正方形を配置することができる。
これは O(n(logn)^2) で解ける。
しゃくとりとかスタックとか使ってうまくやれば O(nlogn) でも解けそうだけど、まあ定数倍もそこまでじゃないし楽な方を選択すれば良さそう。
ありえそうな間違いといえば、隣接する2つの円だけみて判定とか？
（3つ以上の円がかなり近い位置に並んでいると、横幅で3つ以上の円を利用できることがあるのでNG）
ソースコード
#include <bits/stdc++.h> using namespace std; using pdd = pair<double, double>; double solve(vector<double> x, vector<double> r) { const int n = x.size(); auto check = [&] (double h) { vector<pdd> ps(n); for(int i = 0; i < n; ++i) { double x1 = x[i], x2 = x[i]; if(h <= r[i]) { x1 -= sqrt(r[i] * r[i] - h * h); x2 += sqrt(r[i] * r[i] - h * h); } ps[i] = make_pair(x1, x2); } sort(begin(ps), end(ps)); double lx = -1e9, rx = -2e9; for(int i = 0; i < n; ++i) { if(rx < ps[i].first) { if(rx - lx >= 2 * h) return true; lx = ps[i].first, rx = ps[i].second; } else { rx = max(rx, ps[i].second); } } return rx - lx >= 2 * h; }; double lb = 0, ub = 2e5; for(int lp = 0; lp < 60; ++lp) { const auto mid = (lb + ub) / 2; (check(mid) ? lb : ub) = mid; } return lb * 2; } int main() { int n; while(cin >> n, n) { vector<double> x(n), r(n); for(int i = 0; i < n; ++i) { cin >> x[i] >> r[i]; } cout << fixed << setprecision(10) << solve(move(x), move(r)) << endl; } }
AOJ 1620 Boolean Expression Compressor
解法
前もってすべての式を生成してしまえばOK。
真理値表は 16bit 分の情報があればよく、bitDP 的な要領で生成していけば良い。
つまり、キーが真理値表で、値がその最小長さである。
生成するのにはダイクストラが楽だと思う。
ダイクストラで遷移するときは、今見ている式（これは真理値表と長さのペアのことを指している）を、これまでに作ったすべての式と組み合わせて新しい式を作る。
これまでに作ったすべての式を見る部分の計算量がヤバそう（式としてありえるのが 2^16 個あるから）だが、式の長さが高々16文字までしか使えないことを考えると、実は生成できる真理値表はそもそもかなり少ない。
なので、なんかいい感じに作ろうと頑張らなくてもサボって通せる。
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; constexpr int inf = 1e9; int eval_impl(string const& s, int& p, const int S) { if(s[p] == '0' || s[p] == '1') { return s[p++] == '1'; } if(isalpha(s[p])) { return (S >> (s[p++] - 'a')) & 1; } if(s[p] == '-') { return !eval_impl(s, ++p, S); } if(s[p] == '(') { const bool t1 = eval_impl(s, ++p, S); const char op = s[p++]; const bool t2 = eval_impl(s, p, S); p++; // ) if(op == '^') return t1 ^ t2; else return t1 & t2; } assert(false); return -1; } int eval(string const& s) { int truth = 0; for(int S = 0; S < 1 << 4; ++S) { int p = 0; truth |= (eval_impl(s, p, S) << S); } return truth; } int main() { constexpr int all_mask = (1 << 16) - 1; vector<int> ans(1 << 16, inf); ans[0] = ans[(1 << 16) - 1] = 1; ans[eval("a")] = ans[eval("b")] = ans[eval("c")] = ans[eval("d")] = 1; vector<int> ts = {0, (1 << 16) - 1, eval("a"), eval("b"), eval("c"), eval("d")}; vector<int> len = {1, 1, 1, 1, 1, 1}; priority_queue<pii, vector<pii>, greater<>> que; for(int i = 0; i < (int)ts.size(); ++i) { que.emplace(len[i], ts[i]); } while(!que.empty()) { const auto l = que.top().first; const auto t = que.top().second; que.pop(); if(ans[t ^ all_mask] > l + 1) { ans[t ^ all_mask] = l + 1; que.emplace(l + 1, t ^ all_mask); ts.push_back(t ^ all_mask), len.push_back(l + 1); } const int m = ts.size(); for(int i = 0; i < m; ++i) { if(len[i] + l + 3 > 16) continue; if(ans[t & ts[i]] > len[i] + l + 3) { ans[t & ts[i]] = len[i] + l + 3; ts.push_back(t & ts[i]), len.push_back(len[i] + l + 3); que.emplace(len[i] + l + 3, t & ts[i]); } if(ans[t ^ ts[i]] > len[i] + l + 3) { ans[t ^ ts[i]] = len[i] + l + 3; ts.push_back(t ^ ts[i]), len.push_back(len[i] + l + 3); que.emplace(len[i] + l + 3, t ^ ts[i]); } } } string exp; while(cin >> exp, exp != ".") { const auto t = eval(exp); cout << ans[t] << endl; } }
感想
一昨年は結局本番で通せなかったなあ。
他の人のコードを読むと頑張って賢く生成しようとしていて大変そうだった。
とりあえず愚直生成で遅かったら考える、ぐらいの気持ち（運良く早くてよかった）。
AOJ 2373 HullMarathon
解法
自分は数式で捉えて、ラグランジュの未定乗数法で解いた。
ラグランジュの未定乗数法については以下のサイトがわかりやすい（ただし厳密な証明はない）。
mathtrain.jp
与えられた問題を定式化する。
今、r[0], r[1], ..., r[n - 1] をこの順に反時計回りに使うとして、それぞれの間の成す角を θ[0], ..., θ[n - 1] とする。
すると、以下の問題になる。
maximize sum(r[i] * r[(i + 1) % n] * sin(θ[i]) / 2) (for i = 0, ..., n - 1)
s.t. sum(θ[i]) = 2π (for i = 0, ..., n - 1)
ラグランジュの未定乗数法の通りに方程式を立てると、
r[0] * r[1] / (r[i] * r[(i + 1) % n]) * cos(θ[0]) = cos(θ[i]) (forall i = 0, ..., n - 1)
を満たすようなθを求める問題になる。これは二分探索でできる。
凸包パートが必要そうに見えるが、全探索するとサボれる。
r のうちどれを使うか最初に決めて、それらだけで next_permutation を行うと、単に三角形の面積の和を求めるだけでよくなる。
ただし、next_permutation をするときに先頭を固定してしわないと定数倍で落ちるので注意（最初を固定して定数倍落とすのが嬉しい場面はたまにあるので覚えて損はない）。
ソースコード
#include <bits/stdc++.h> using namespace std; using ld = long double; const ld pi = acos(-1.0); constexpr ld eps = 1e-9; int main() { int n; cin >> n; vector<ld> rr(n); for(int i = 0; i < n; ++i) { cin >> rr[i]; } sort(begin(rr), end(rr)); ld ans = 0; for(int S = 1; S < (1 << n); ++S) { vector<ld> r; for(int i = 0; i < n; ++i) { if(S & (1 << i)) { r.push_back(rr[i]); } } const int m = r.size(); if(m < 3) continue; do { ld tans = 0, ang_sum = 0; auto check = [&] (ld theta) { ang_sum = theta; tans = 0.5 * r[0] * r[1] * sin(theta); for(int i = 1; i < m; ++i) { const auto ang = acos(max(-1.0L, min(1.0L, r[0] * r[1] / r[i] / r[(i + 1) % m] * cos(theta)))); tans += 0.5 * r[i] * r[(i + 1) % m] * sin(ang); ang_sum += ang; } return ang_sum < 2 * pi; }; ld lb = 0, ub = pi; for(int lp = 0; lp < 100; ++lp) { const auto mid = (lb + ub) / 2; (check(mid) ? lb : ub) = mid; } if(abs(ang_sum - 2 * pi) < eps) { ans = max(ans, tans); } } while(next_permutation(begin(r) + 1, end(r))); } cout << fixed << setprecision(10) << ans << endl; }
