模擬地区予選2013
誰も見てないと思って担当した問題について好き勝手書くコーナー。
ソースコード載せてる以外は解法に触れてないのでご注意？
- -
E : Putter
- Testerでした(writerはir5さん)。
- サンプルが見た目より強いのでこれ通れば大体ACじゃねと思ってましたが、そうでもなかった。せめてもう1個くらいあっても良かった気もしますが、複雑なのを入れたところでデバッグできない説も。
- 提出された解答を何個か眺めた限りnext_permutationを使った実装が多かったですが、私の解答はDFS。ジャッジデータ中で答えが一番大きいものでも68なので、結構枝が刈れる(刈らなくても通りますが)。
- ライブラリゲーでなく、実装をちゃんと考える必要がありながらも重実装すぎない良い幾何の問題だったのではと思っています。
#include <iostream> #include <vector> #include <complex> using namespace std; const double EPS = 1e-8; typedef complex<double> P; struct L { P p, q; L() : p(P(0,0)), q(P(0,0)) {} L(P p, P q) : p(p), q(q) {} }; P start; vector<P> g; vector<P> dir; vector<L> seg; double dot(P a, P b) { return real(conj(a)*b); } double cross(P a, P b) { return imag(conj(a)*b); } P footPerp(const L& l, const P& p) { return l.p + (l.q-l.p)*(dot(l.q-l.p, p-l.p) / norm(l.q-l.p)); } P lineShadow(const L& l, const P& p){ return 2.0*footPerp(l, p)-p; } P getDir(const vector<int>& order, P target, int depth){ for(int i=depth-1;i>=0;i--){ target = lineShadow(seg[order[i]], target); } P res = target - start; res /= abs(res); return res; } int dfs(vector<int>& order, vector<int>& used, P dirL, P dirR, int depth){ int n = g.size(); if(depth == n) return 1; int res = 0; for(int i=0;i<n;i++){ if(used[i]) continue; order[depth] = i; P dL = getDir(order, depth%2 ? seg[i].q : seg[i].p, depth); P dR = getDir(order, depth%2 ? seg[i].p : seg[i].q, depth); if(cross(dL, dirL) > 0) dL = dirL; if(cross(dR, dirR) < 0) dR = dirR; if(cross(dL, dR) > 0){ used[i] = 1; res += dfs(order, used, dL, dR, depth+1); used[i] = 0; } } return res; } int main(){ int n; while(cin >> n && n){ cin >> start.real() >> start.imag(); g.resize(n); dir.resize(n); seg.resize(n); for(int i=0;i<n;i++) cin >> g[i].real() >> g[i].imag(); for(int i=0;i<n;i++){ seg[i] = L(g[i], g[(i+1)%n]); dir[i] = g[(i+1)%n] - g[i]; dir[i] /= abs(dir[i]); } int res = 0; vector<int> order(n, -1), used(n, 0); for(int i=0;i<n;++i){ order[0] = i; used[i] = 1; res += dfs(order, used, g[i]+EPS*dir[i]-start, g[(i+1)%n]-EPS*dir[i]-start, 1); used[i] = 0; } cout << res << endl; } }
G : Floating Islands
- writerでした。なんかMSTの変わった問題作れないかな−と、模擬国内Dと同時期に考えてた問題。模擬国内のちょっと後に出題した形にまとまり、今回採用となりました。
- 模擬国内Dではめんどい仕様を上手く問題文にできなかった事を反省したので、仕様はシンプルにまとめました。キレイにまとまったので個人的に気に入ってます。
- 提案時は、もう少し計算量落ちるような…と思いながらO(n^3)で出したのですが、某所スタッフにより即刻O(n^2)に落とされ今に至ります。
- O(n^3)解までは理詰めでいけて実装も楽ですが、O(n^2)解をキッチリ実装しきるのは意外と大変です。サンプルではO(n^2)解のデバッグが難しいので、大きめのケースを作ってO(n^3)解と答えを比較するのも手。
- 解説スライドに載せたコーナーケースは良く釣れてました。
- 今回のサンプル(誰得コーナー)
#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; const long long INF = 1000000000000000000LL; int main(){ int N; while(cin >> N && N){ vector< pair<int,int> > multi; vector<int> one; if(N == 2){ int a, b, c; cin >> a >> c >> b >> c; cout << abs(a-b) << endl; continue; } for(int i=0;i<N;i++){ int p, d; cin >> p >> d; if(d == 1) one.push_back(p); else multi.push_back(make_pair(p, d)); } sort(one.begin(), one.end()); sort(multi.begin(), multi.end()); if(multi.size() > 1){ multi[0].second--; multi.back().second--; for(int i=1;i+1<multi.size();i++) multi[i].second -= 2; } vector<int> lower(one.size()), upper(one.size()); for(int i=0;i<one.size();i++){ int idx = 0; while(idx < multi.size() && one[i] > multi[idx].first){ idx++; } lower[i] = upper[i] = idx; if(idx == multi.size()) lower[i]--; int sum = 0; while(lower[i] > 0){ if(one[i] < multi[lower[i]].first){ lower[i]--; continue; } sum += multi[lower[i]].second; if(sum >= one.size()) break; lower[i]--; } sum = 0; while(upper[i] < multi.size()){ sum += multi[upper[i]].second; upper[i]++; if(sum >= one.size()) break; } } vector<long long> dp(one.size()+1, INF); dp[0] = 0; for(int i=0;i<multi.size();i++){ int start = one.size()+1, end = 0; for(int j=0;j<one.size();j++){ if(lower[j] <= i && i < upper[j]){ start = min(j, start); end = max(j, end); } } for(int j=0;j<multi[i].second;j++){ for(int k=end;k>=start;k--){ dp[k+1] = min(dp[k+1], dp[k]+abs(multi[i].first-one[k])); } } } long long res = dp[one.size()]; cout << (res == INF ? -1 : res + multi.back().first - multi[0].first) << endl; } }
