■ [SRM]SRM533 
http://community.topcoder.com/stat?c=coder_room_stats&cr=22744421
- 250
- 500
- サンプルを見ていると、結局行・列ごとの偶奇だけで決まるのでは？ と思う
- 必要性は証明できるが十分性がわからない
- どうせ一筆書きの条件の「次数が奇数の頂点が0個か2個」というあの法則が関係してて大丈夫なんだろう
- 提出した後で、自分で作った非連結の場合のテストを見返すと、期待値が間違っていることを発見…
- 連結性の判定でミスがあったので再提出
- Challenge
- 500で、横向きが先であることを考慮しておらず("#","#")でYESを返すのを1つ撃墜
- System Test
- 2問とも通った
- 232.36 + 229.95 + 0.00 + (50*1-25*0) = 512.31
- 54位/848人
- 2043->2131
■ [others]ZOJ Monthly, February 2012 
http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=333
相変わらずすごく難しい。簡単な問題がない
- A
- 読んだけど意味がよくわからないので飛ばした
- 正解者数0
- B
- 読んでない
- 正解者数0
- C
- SegmentTree的なもの使ってO((N+L)logL)でやったら時間制限ぎりぎりだった（N:クエリ数）
- クエリごとに開始位置と終了位置を記録したあとでL方向にスイープするとO(N+L)でできそう
- D
- 交差する直線が何組あるかに帰着される
- x座標左端で下にある直線から順に、右端に到達したとき自分より下にきた直線が何個かを数える
- 数えたら、今着目していた直線は削除する。SegmentTree使って効率よく更新する
- E
- 2点が楕円の周上に乗るような位置を列挙して試す
- 2点を取って、それぞれの位置を中心とする軸長a,bの2つの楕円の交点が、そのような楕円の中心位置になる
- 楕円の交点は、全体のy座標をa/b倍したあと半径aの円の交点として求め、y座標をb/a倍して戻せば良い
- 最初まともに二次式を計算しようとして死にそうになっていた…
- 無駄にa==0やb==0のケースも考慮してしまっていた。"positive floating number"と書いてあるやん…
- F
- 観察していると、「対角線上の赤の領域の長さ:青の領域の長さ==長方形内の赤セルの数:青セルの数」となるようだった
- ただしN=Mの場合は例外
- doubleでは誤差が出るのでlong doubleを使ったら通った
- G
- 読んでない
- 正解者数1
- H
- 四角形を置いたとき、その四角形の高さは、max(過去の四角形で今の四角形と重なっているやつの高さ)+h になる
- 良い問題だと思いました
- I
- 読んだけど難しそう
- 正解者数1
- J
- 読んでない
- 正解者数0
- 5問/10問正解
- 12位/500人くらい
C
#include#include #include #include #include #include using namespace std; typedef long long ll; int L; int table[65536]; //vector table; void init(int len){ memset(table, 0, sizeof(table)); int size = 1; while(size < len * 2) { size *= 2; } // table.clear(); // table.resize(size); } void add(int pos, int left, int right, int start, int end, int val){ if (start <= left && right <= end) { table[pos] += val; return; } int mid = (left + right) / 2; if (start < mid) { add(pos * 2+1, left, mid, start, min(end, mid), val); } if (mid < end) { add(pos * 2+2, mid, right, max(start, mid), end, val); } } int get(int pos, int left, int right, int coord){ if (left == coord && right == coord+1) { return table[pos]; } int mid = (left + right) / 2; if (coord < mid) { return get(pos * 2+1, left, mid, coord) + table[pos]; } else { return get(pos * 2+2, mid, right, coord) + table[pos]; } } int main(){ while(scanf("%d", &L) > 0){ init(L); int s,e,d; while(true) { scanf("%d %d %d", &s, &e, &d); if (s == -1) break; --s; --e; if (s > e) swap(s, e); add(0, 0, L, s, e + 1, d); } int maxV = 0; for (int i = 0; i < L; ++i) { maxV = max(maxV, get(0, 0, L, i)); } for (int i = 0; i < L; ++i) { if (get(0, 0, L, i) == maxV){ printf("%d ", i+1); break; } } for (int i = L-1; i >= 0; --i) { if (get(0, 0, L, i) == maxV){ printf("%d\n", i+1); break; } } } return 0; }
D
#include#include #include #include #include #include #include using namespace std; typedef long long ll; int A,B; vector<int> table; void init(int len){ int size = 1; while(size < len * 2) { size *= 2; } table.clear(); table.resize(size); } void add(int pos, int left, int right, int ord){ table[pos] += 1; if (ord == left && ord == right-1) { return; } int mid = (left + right) / 2; if (ord < mid) { add(pos * 2+1, left, mid, ord); } else { add(pos * 2+2, mid, right, ord); } } int get(int pos, int left, int right, int start, int end){ // cout << "get " << pos << " " << left << " " << right << " " << start << " " << end << endl; if (start <= left && right <= end) { return table[pos]; } if (start == end) return 0; int mid = (left + right) / 2; int ret = 0; if (start < mid) { ret += get(pos * 2+1, left, mid, start, min(end, mid)); } if (mid < end) { ret += get(pos * 2+2, mid, right, max(start, mid), end); } return ret; } struct Line{ int k,b; int oa, ob; }; struct line_comparator{ int x; line_comparator(int x_) : x(x_){} bool operator()(const Line& la, const Line& lb){ return (la.k*x + la.b) < (lb.k*x + lb.b); } }; int main(){ while(scanf("%d %d", &A, &B) > 0){ int n; scanf("%d", &n); vector lines(n); for (int i = 0; i < n; ++i) { scanf("%d %d", &(lines[i].k), &(lines[i].b)); } sort(lines.begin(), lines.end(), line_comparator(B)); for (int i = 0; i < n; ++i) { lines[i].ob = i; } sort(lines.begin(), lines.end(), line_comparator(A)); for (int i = 0; i < n; ++i) { lines[i].oa = i; } init(n); int count = 0; for (int i = 0; i < n; ++i) { int pb = lines[i].ob; count += pb - get(0, 0, n, 0, pb); add(0, 0, n, pb); } // cout << count << endl; printf("%d\n", count + n + 1); } return 0; }
E
#include#include #include #include #include using namespace std; typedef long long ll; typedef pair<double, double> Pos; const double EPS = 1e-12; double a,b; int n; vector cities; vector cross(int c1, int c2){ vector ret; double x1 = cities[c1].first; double y1 = cities[c1].second; double x2 = cities[c2].first; double y2 = cities[c2].second; y1 *= a / b; y2 *= a / b; double dx = x2 - x1; double dy = y2 - y1; double dist = sqrt(dx*dx + dy*dy); if (dist - EPS > 2*a) return ret; double movex = -dy/dist; double movey = dx/dist; double midx = (x1+x2)/2; double midy = (y1+y2)/2; double moveDist = sqrt(max(0.0, a*a - dist/2*dist/2)); // cout << movex << " " << movey << " " << midx << " " << midy << endl; ret.push_back(make_pair(midx + movex*moveDist, midy + movey*moveDist)); ret.push_back(make_pair(midx - movex*moveDist, midy - movey*moveDist)); ret[0].second *= b/a; ret[1].second *= b/a; return ret; } int count(Pos p) { int ret = 0; for (int i = 0; i < n; ++i) { double dx = cities[i].first - p.first; double dy = cities[i].second - p.second; if (dx*dx/a/a + dy*dy/b/b <= 1 + EPS) ++ret; } return ret; } int solve(int c1, int c2){ vector crossPos = cross(c1, c2); // cout << "c1:" << c1 << " c2:" << c2 << endl; if (crossPos.empty()) return 0; int ans = 0; for (size_t i = 0; i < crossPos.size(); ++i) { // cout << "(" << crossPos[i].first << "," << crossPos[i].second << ")" << endl; ans = max(ans, count(crossPos[i])); } return ans; } int solveLine(double len){ int ans = 0; for (int i = 0; i < n; ++i) { int count = 0; for (int j = 0; j < n; ++j) { if (cities[i].first == cities[j].first && abs(cities[j].second - cities[i].second) <= len) ++count; // このへん間違ってる } ans = max(ans, count); } return ans; } int solve(){ if (n == 0) return 0; if (n == 1) return 1; if (a == 0 && b == 0) return 1; if (a == 0) { return solveLine(b); } if (b == 0) { for (int i = 0; i < n; ++i) { swap(cities[i].first, cities[i].second); } return solveLine(a); } int ans = 1; for (int i = 0; i < n; ++i){ for (int j = 0; j < i; ++j) { ans = max(ans, solve(i, j)); } } return ans; } int main(){ while(scanf("%lf %lf %d", &a, &b, &n) > 0){ // a/=2; // b/=2; cities.resize(n); double x, y; for (int i = 0; i < n; ++i) { scanf("%lf %lf", &x, &y); cities[i].first = x; cities[i].second = y; } printf("%d\n", solve()); } return 0; }
F
#include#include #include #include #include using namespace std; typedef long long ll; ll N,M; ll gcd(ll a, ll b){ return b == 0 ? a : gcd(b, a % b); } long double solve(ll n, ll m){ long double allLen = sqrtl((long double)(n*n+m*m)); long double ratio = (n*m+1) / 2 / (1.0*n*m); return allLen * ratio; } int main(){ while(scanf("%d %d", &N, &M) > 0){ ll mod = gcd(N, M); long double ans = solve(N/mod, M/mod); printf("%.3Lf\n", ans * mod); } return 0; }
H
#include#include #include #include #include using namespace std; typedef long long ll; int N,M,C; struct Mat{ int x, y, a, b; int h; }; bool cross(const Mat& ma, const Mat& mb){ if (ma.x + ma.a <= mb.x || mb.x + mb.a <= ma.x) return false; if (ma.y + ma.b <= mb.y || mb.y + mb.b <= ma.y) return false; return true; } int main(){ while(scanf("%d %d %d", &N, &M, &C) > 0){ vector mats; int a,b,h,x,y; for (int i = 0; i < C; ++i) { scanf("%d %d %d %d %d", &a, &b, &h, &x, &y); Mat mat = {x,y,a,b,h}; int mh = 0; for (int j = 0; j < i; ++j) { if(cross(mat, mats[j])){ mh = max(mh, mats[j].h); } } mat.h += mh; mats.push_back(mat); } int ans = 0; for (int i = 0; i < C; ++i){ ans = max(ans, mats[i].h); } printf("%d\n", ans); } return 0; }
