https://community.topcoder.com/stat?c=round_overview&er=5&rd=16084
Easy
原点と2つの頂点がつくる角度a,b,cについて、
a+b+c=2*π,a<π,b<π,c<πが成り立っていればいいです。
よって2つ頂点を決めれば最後の頂点は2*π-a-b < c < πを満たせばよくて、これは前処理をしておけば二分探索で求めることができます。O(N^2logN)(N=2500)でめちゃくちゃ重いけどギリギリ通ったw
本当はx軸からの角度でsortして解くのが正しくて、そうすればO(N^2)になりますね。
struct TrianglesContainOrigin { vector<int> x; vector<int> y; vector<pair<double, int> > P[2510]; long long count(vector<int> _x, vector<int> _y) { x = _x, y = _y; int n = sz(x); rep(i, 0, n) { rep(j, 0, n) { if(i == j) continue; comp b = comp(x[j], y[j]), a = comp(x[i], y[i]); double ag = arg(b / a); if(ag < 0) continue; P[i].pb(make_pair(ag, j)); } sort(all(P[i])); } ll res = 0; rep(i, 0, n) { rep(j, 0, sz(P[i])) { double arg = P[i][j].fst; int at = P[i][j].sec; int tmp = upper_bound(all(P[at]), make_pair(PI - arg, -1)) - P[at].begin(); res += sz(P[at]) - tmp; } } return res / 3; } };
211 minutes 4 secs
普通に全然思いつかなかったんですが…。幾何全然手をつけてないのもある。
Medium
操作を逆から見ます。例えば6,3,5,2,4,1について考えると、
まず6,5,4と3,2,1に分けて、２つを好きなように並び替えてそのままくっつける作業になります。
なので5,4,6,1,3,2や4,5,6,1,2,3などにできます。すると2つ分けたあとは好きに入れ替えることができるので、nより大きいか小さいかだけが重要になります。よって奇数番目に位置しているn以下の数をa個として(例えば上の例だと6,5,4なのでa=0)次に何個の状態に移動できるか考えます。そうしてできたグラフ上でダイクストラすればいいです。と思ったけど辺の長さが全部同じなので幅優先してください。
struct ShufflingCardsDiv1 { vector<int> permutation; vector<int> G[2010]; int d[2010]; int shuffle(vector<int> _permutation) { permutation = _permutation; int n2 = sz(permutation), n = n2 / 2; bool found = false; rep(i, 0, n2) { if(permutation[i] != i + 1) found = true; } int cnt = 0; rep(i, 0, n2) if(permutation[i] <= n) cnt += ((i + 1) % 2); if(!found) return 0; rep(i, 0, n + 1) { int j = n - i; int minx = max(n / 2 - i, 0), maxx = min((n + 1) / 2, i); int miny = max((n + 1) / 2 - j, 0), maxy = min(n / 2, j); for(int k = minx + miny; k <= maxx + maxy; k++) { G[i].pb(k); } } fill(d, d + n + 1, inf); d[cnt] = 0; priority_queue<pi, vector<pi>, greater<pi>> que; que.push(pi(0, cnt)); while(!que.empty()) { pi p = que.top(); que.pop(); int td = p.fst, v = p.sec; if(td > d[v]) continue; rep(i, 0, sz(G[v])) { int to = G[v][i]; if(d[v] + 1 < d[to]) { d[to] = d[v] + 1; que.push(pi(d[to], to)); } } } return d[n] + 1; } };
133 minutes 38 secs。これは難しい。
