TopCoder SRM 641 Div1

Tatsuya Yatagawa
Programming Contest

SRM641の解説です。

Easy (250点)

問題

2次元座標上に最大2500個の点が与えられる。これらの点のいずれの3点も同一直線状にないことが保証されており、また原点は含まれない。この点の中から3点を選んで三角形を作った時に原点が内部に含まれるようなものの個数を求めよ。

解法

普通に考えるとO(N^3)になってしまうので、工夫する方法がないかを考えます。

定数の2500という条件からO(N^2)か、O(N^2 logN)くらいの解法がありそうだと予想します。

2点を固定したときに、残りの1点として選ばれうる点を早く計算する方法がないかなぁ、と思うわけですが、実は固定している2点と原点を結ぶ直線を引いたときに4分割される領域の1つに含まれる点が求めたい点だということに気づきます(下図参照)。

srm641_easy

なので、点をatan2で求めた角度順にソートしておいて、上の領域の間にある点をlower_boundかupper_boundで求めてあげます(今回はぴったり反対側にある点がないので、どっちでも変わらない)。

細かい実装のポイントとしては、下のコードでは範囲が扱いやすいように2周分点を持っています。


#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <list>
#include <stack>
#include <tuple>
#include <utility>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
#include <typeinfo>
using namespace std;

typedef long long lint;
typedef pair<int,int> pii;
typedef pair<lint,lint> pll;

#define Integer int
#define REP(i,n) for(Integer i=0; i<n; i++)
#define REPA(i,s,e) for(Integer i=s; i<=e; i++)
#define REPD(i,s,e) for(Integer i=s; i>=e; i--)
#define SIZ(a) (Integer)(a).size()
#define ALL(a) (a).begin(), (a).end()

const double EPS = 1.0e-10;
const double PI  = 4.0 * atan(1.0); 
int sign(double r) { return r < -EPS ? -1 : r > EPS ? 1 : 0; }

class P {
public:
    double x, y;
    P() {}
    P(int x_, int y_) : x(x_), y(y_) {}
    P(double x_, double y_) : x(x_), y(y_) {}
    P(const P& p) : x(p.x), y(p.y) {}
    P operator+(P p) const { return P(x+p.x, y+p.y); } 
    P operator-(P p) const { return P(x-p.x, y-p.y); }
    P operator-() const { return P(-x, -y); }
    P operator*(double s) const { return P(x*s, y*s); }
    P operator/(double s) const { return P(x/s, y/s); }
    P& operator=(const P& p) { x=p.x; y=p.y; return (*this); }
    double dot(P p) const { return x*p.x + y*p.y; }
    double det(P p) const { return x*p.y - y*p.x; }
    double norm() const { return sqrt(x*x + y*y); }
    double norm2() const { return x*x + y*y; }
    P proj(const P& p) const { double k=det(p)/norm2(); return P(x*k, y*k); }
};

bool operator<(P p, P q) {
    if(sign(p.x - q.x) != 0) return p.x < q.x;
    return p.y < q.y;
}

bool operator>(P p, P q) {
    if(sign(p.x - q.x) != 0) return p.x > q.x;
    return p.y > q.y;
}


double tri(P a, P b, P c) { return (b - a).det(c - a); }

class TrianglesContainOrigin {
public:
    typedef pair<double,P> PP;
    int n;
    vector<PP> ang;

    long long count(vector<int> x, vector<int> y) {
        n = SIZ(x);
        ang.clear();
        REP(i,n) {
            double theta = atan2(y[i], x[i]) + PI;
            ang.push_back(make_pair(theta, P(x[i], y[i])));
            ang.push_back(make_pair(theta + 2.0 * PI, P(x[i], y[i])));
        }
        sort(ALL(ang));

        lint ret = 0;
        REP(i,n) {
            REPA(j,i+1,n-1) {
                if(ang[i].second.det(ang[j].second) > 0.0) {
                    ret += lower_bound(ALL(ang), make_pair(ang[j].first+PI, P())) - lower_bound(ALL(ang), make_pair(ang[i].first+PI, P()));
                } else {
                    ret += lower_bound(ALL(ang), make_pair(ang[i].first+PI, P())) - lower_bound(ALL(ang), make_pair(ang[j].first-PI, P()));
                }
            }
        }
        return ret / 3;
    }
};

Medium (550点)

問題

キツネのCeilちゃん(メスらしい)は1から2Nまでの番号が付いたカードを持っている。今、このカードをシャッフルしたものが与えられるので、以下の操作を繰り返して、最低何回で並べ替えられるかを求めたい。

  1. カードの山をN個ずつ前半と後半に分ける
  2. それぞれの山を好きに並べ替える
  3. カードを交互にマージする

もし、上の操作で並べ替えられないときには-1を返せ。

解法

まず、すごく単純な話として、1回シャッフルすると、前半のN枚は奇数番目、後半のN枚は偶数番目に来ます。

で、これをマージすると、どうなるかというと、前半のグループと後半のグループの間でN/2枚(整数での計算)だけが入れ替わります。

例えば、カードが10枚あるなら、前半と後半で2枚のカードが入れ替わります。この際、前半の山と後半の山の順序は好きに変えてよいので、入れ替わるカードは自由にコントロールできます。

すると、カードの操作として次のような戦略が考えられます。

  • 最終状態で奇数番目に来るものが前半、偶数番目に来る者が後半になるようなグループを目指す
  • 上のグループができたら最後にマージする

なので、上のやり方でN/2枚ずつカードを入れ替えていって、前半グループと後半グループを作ります。問題はN/2で入れ替える枚数が割り切れないときです。例えばN=4なら2枚ずつカードが入れ替わりますが、もし1枚だけ入れ替えたいなら、次のように操作する必要があります。

{oooo}, {xxxx} → {ooxx}, {xxoo} → {ooox}, {xxox}

ということは、2回の操作が必要ということになりますが、もしそれより前にN/2の入れ替えがあるなら、そこで調整することができるので、入れ替え枚数がN/2より小さいなら2回、入れ替え枚数がN/2以上ならceil(入れ替え枚数 / (N/2))となります。

あとは上のものに最後のマージの1回を足せばいいです。

ただし、上の場合にはいらない特殊ケースが2つあって、最初から同じ場合は0回、前後半が最初からきれいに分かれているときは1回になります。

場合分けが面倒ですが、実装は少ないです。


#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <list>
#include <stack>
#include <tuple>
#include <utility>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
#include <typeinfo>
using namespace std;

#define Integer int
#define REP(i,n) for(Integer i=0; i<n; i++)
#define REPA(i,s,e) for(Integer i=s; i<=e; i++)
#define ALL(a) (a).begin(), (a).end()

class ShufflingCardsDiv1 {
public:
    int shuffle(vector<int> perm) {
        int n = perm.size();
        bool same = true;
        REP(i,n) {
            if(perm[i] != i+1) {
                same = false;
                break;
            }
        }
        if(same) return 0;

        vector<int> org(n+1);
        REP(i,n) {
            org[perm[i]] = i % 2;
        }

        int change = n / 4;
        int cnt = 0;
        REPA(i,1,n/2) {
            cnt += org[i];
        }
        if(cnt == 0) return 1;
        if(cnt < change) {
            return 3;
        }
        return (cnt + change-1) / change + 1;
    }
};

まとめ

今回は割と早い段階でEasyの解法を思いついたのですが、いつものバグらせ病が発動して、Submitしたのは終了ギリギリでした。

Mediumは終わってから見たのですが、下手したらEasyより簡単だったのでは？N/2個ずつ入れ替わるということに気づけるかがポイントのような気がしました。

とはいえ、条件わけが面倒くさく、またテストケースが少し弱いのでSystem Testを通すのは結構難しいかもという気もしました。

それでは、今回の解説を終わります。最後までお読みいただきありがとうございました。