Google Code Jam 2018: Qualification Round

資格賽，除了最後一題比較有趣以外，其他都比較簡單

Saving The Universe Again

貪心

一開始想着盡可能将S往前移，但是想了想覺得這樣移動好多次，可能才等于後面的S往前移一位的成果。

是以就變成盡可能地将C往末尾移（末尾一段連續的C就不用考慮了），即，每一次移動減少的傷害最大。

int T,n;
vi a1,a2;

int main()
{
    cin>>T;
    int cases = ;
    while(T--)
    {
        cin>>n;
        a1.clear();
        a2.clear();
        for(int i = , x; i < n; i++)
        {
            cin>>x;
            if(i&)
                a2.pb(x);
            else
                a1.pb(x);
        }
        sort(a1.begin(),a1.end());
        sort(a2.begin(),a2.end());
        int ans = -;
        for(int i = ; i < n-; i++)
        {
            if(i&)
            {
                if(a2[i/]>a1[i/+] && ans==-)
                {
                    ans = i;
                    break;
                }
            }
            else
            {
                if(a1[i/]>a2[i/] && ans==-)
                {
                    ans = i;
                    break;
                }
            }
        }
        if(ans == -)
            printf("Case #%d: OK\n", cases);
        else
            printf("Case #%d: %d\n", cases, ans);
        cases++;
    }
    return ;
}
           

Trouble Sort

想法一：

實作兩種排序，比較，複雜度 O(N2) O ( N 2 )

想法二：

因為Trouble Sort僅會在奇數位和奇數位或偶數位和偶數位交換，是以将奇偶分開來排序，按順序比較大小即可。

int main()
{
    speed
    int T, cases = ;
    ll D, a[];
    string str;
    cin >> T;
    while (T--)
    {
        cin >> D >> str;
        int n = str.size();
        ll sum = ;
        int c = ;
        ll tot = ;
        for(int i = ; i < n; i++)
        {
            a[i] = -;
            if(str[i] == 'C')
                c++;
            else
            {
                a[i] = (ll << c);
                sum += a[i];
                tot++;
            }
        }
        cout << "Case #" << cases++ << ": ";
        if(tot > D)
        {
            cout << "IMPOSSIBLE" << endl;
        }
        else
        {
            int ans = ;
            while(sum > D)
            {
                for(int i = n-; i > ; i--)
                {
                    if (a[i-] == - && a[i] > -)
                    {
                        a[i] >>= ;
                        sum -= a[i];
                        swap(a[i - ], a[i]);
                        break;
                    }
                }
                ans++;
            }
            cout << ans << endl;
        }
    }
    return ;
}
           

Go, Gopher!

除了題目長一些，就是亂搞題

方法就是以 3∗3 3 ∗ 3 的正方形，構造大矩形。

可以按标的方法，做一個 3∗3×23 3 ∗ 3 × 23 的一行矩形。也可以像這裡一樣做一個 15×15 15 × 15 的矩形。

按照200個可以投1000次，命中率是 20% 20 % ，是以每一個 3∗3 3 ∗ 3 的正方形隻要投8次就行。最後再補缺補漏一下即可。

const int MAXN = ;

bool p[MAXN][MAXN];
int num[MAXN][MAXN];
int dx[] = {, , -};
int dy[] = {, , -};

int main()
{
    int T, a, n, x, y;
    read(T);
    while(T--)
    {
        CLR(p, );
        CLR(num, );
        read(a);
        if(a == )
            n = ;
        else
            n = ;
        printf("%d %d\n", , );
        fflush(stdout);
        while(read(x) && read(y))
        {
            if((x ==  && y == ) || (x == - && y == -))
                break;
            x--, y--;
            if(!p[x][y])
            {
                p[x][y] = true;
                num[x / ][y / ]++;
            }
            bool flag = true;
            for(int i = ; i < n /  && flag; i++)
                for(int j = ; j < n /  && flag; j++)
                    if(num[i][j] < )
                    {
                        printf("%d %d\n", i *  + , j *  + );
                        flag = false;
                    }
            for(int i = ; i < n -  && flag; i++)
                for(int j = ; j < n -  && flag; j++)
                {
                    int c = ;
                    for(int k = ; k < ; k++)
                        for(int d = ; d < ; d++)
                        {
                            int xx = i + dx[k], yy = j + dy[d];
                            c += p[xx][yy];
                        }
                    if(c < )
                    {
                        printf("%d %d\n", i + , j + );
                        flag = false;
                    }
                }
            fflush(stdout);
        }
    }
    return ;
}
           

Cubic UFO

超級有意思的題目

首先，你先在Y軸旋轉 45° 45 ° ，然後再二分求出X軸如何旋轉能夠使得投影面積最大。之後就可以二分了。

一開始覺得是暴力枚舉精度，但是最後沒卡過去；後來用了三分套三分，應該是找不到投影面積最大的點，也挂了。

投影面積就是用線性代數算一下投影的點坐标，然後用凸包求面積。

但是最有意思的就是The cube shadow theorem (pt.1): Prince Rupert’s paradox：unit cube的垂直投影面積和它的上下高度差相等。

這樣就可以忽略一大堆代碼，直接得出結論，美滋滋啊。

typedef long double Double;
typedef pair<Double,Double> dd;
#define Dsin   sinl
#define Dcos   cosl
#define Datan2 atan2l
#define Dhypot hypotl
#define Dfabs  fabsl

typedef vector<Double> Coord;

vector<Coord> corners(, Coord());

const Double PI = ;

inline Double deg2rad(Double deg)
{
    return deg * PI / ;
}
inline Double rad2deg(Double rad)
{
    return rad / PI * ;
}

void _init()
{
    int _corners[][] =
    {
        {, , }, {, -, }, {-, -, }, {-, , },
        {, , -}, {, -, -}, {-, -, -}, {-, , -}
    };

    for(int c = ; c < ; c++)
        for(int i = ; i < ; i++)
            corners[c][i] =  * _corners[c][i];
}

inline Coord dot(Double R[][], Coord& x)
{
    Coord y(, );
    for(int i = ; i < ; i++)
        for(int j = ; j < ; j++)
            y[i] += R[i][j] * x[j];
    return y;
}

Coord _rx(Coord& p, Double th)
{
    Double R[][];
    R[][] = ;
    R[][] = ;
    R[][] =  ;
    R[][] = ;
    R[][] = Dcos(th);
    R[][] = -Dsin(th);
    R[][] = ;
    R[][] = Dsin(th);
    R[][] =  Dcos(th);
    return dot(R, p);
}

Coord _ry(Coord& p, Double th)
{
    Double R[][];
    R[][] =  Dcos(th);
    R[][] = ;
    R[][] = Dsin(th);
    R[][] =  ;
    R[][] = ;
    R[][] = ;
    R[][] = -Dsin(th);
    R[][] = ;
    R[][] = Dcos(th);
    return dot(R, p);
}

Coord _rz(Coord& p, Double th)
{
    Double R[][];
    R[][] = Dcos(th);
    R[][] = -Dsin(th);
    R[][] = ;
    R[][] = Dsin(th);
    R[][] =  Dcos(th);
    R[][] = ;
    R[][] = ;
    R[][] =  ;
    R[][] = ;
    return dot(R, p);
}

inline dd vec(dd& a, dd& b)
{
    return dd(b.first - a.first, b.second - a.second);
}
inline Double outer(dd& u, dd& v)
{
    return u.first * v.second - v.first * u.second;
}
inline Double vlen(dd& v)
{
    return Dhypot(v.first, v.second);
}

inline Double ccw(dd& p1, dd& p2, dd& p3)
{
    return (p2.first - p1.first)*(p3.second - p1.second)
           - (p2.second - p1.second)*(p3.first - p1.first);
}

template<typename T>
vector<T> _uniq(vector<T>& v)
{
    set<T> tmp(ALL(v));
    return vector<T>(ALL(tmp));
}

inline bool dd_eq(dd& p, dd& q)
{
    dd pq = vec(p, q);
    return vlen(pq) < eps;
}

vector<dd> uniq(vector<dd>& v)
{
    sort(v.begin(), v.end());
    vector<dd> res;
    res.pb(v[]);
    for (int i=; i<v.size(); ++i)
    {
        if (!dd_eq(v[i], res.back()))
        {
            res.pb(v[i]);
        }
    }
    return res;
}

vector<dd> convex_hull(vector<dd>& points_orig)
{
    vector<dd> points = uniq(points_orig);
    int N = points.size();

    Double ymin = , xmin = ;
    int at = -;
    for(int i = ; i < N; i++) ymin = min(ymin, points[i].second);
    for(int i = ; i < N; i++)
    {
        if (points[i].second == ymin)
        {
            if (points[i].first < xmin)
            {
                xmin = points[i].first;
                at = i;
            }
        }
    }
    vector<pair<Double, dd>> tmp(N);
    for(int i = ; i < N; i++)
    {
        Double th;
        if (i != at)
            th = Datan2(points[i].second - ymin, points[i].first - xmin);
        else
            th = -;
        tmp[i] = make_pair(th, points[i]);
    }
    sort(tmp.begin(), tmp.end());
    assert(tmp[].second == dd(xmin, ymin));

    vector<dd> pts(N+);
    for(int i = ; i < N; i++) pts[+i] = tmp[i].second;
    pts[] = pts[N];

    int M = ;
    for (int i=; i<=N; ++i)
    {
        while (ccw(pts[M-], pts[M], pts[i]) <= )
        {
            if (M > )
            {
                --M;
                continue;
            }
            else if (i == N)
            {
                break;
            }
            else
            {
                ++i;
            }
        }
        ++M;
        swap(pts[M], pts[i]);
    }

    if (M < pts.size())
    {
        pts.erase(pts.begin()+M, pts.end());
    }

    return pts;
}

Double convex_hull_area(vector<dd>& hull)
{
    int N = hull.size();
    dd m(, );

    Double area = ;
    for(int i = ; i < N; i++)
    {
        dd p = hull[i], q = hull[(i+)%N];
        area +=  * Dfabs(outer(p, q));
    }
    return area;
}

void render_ans(Double th_x, Double th_z)
{
    for(int c = ; c < ; c++)
    {
        Coord p(, );
        p[c] = ;
        Coord r1 = _rx(p, th_x);
        Coord r2 = _rz(r1, th_z);
        printf("%.16Lf %.16Lf %.16Lf\n", r2[], r2[], r2[]);
    }
}

Double rotated_shadow_area(Double th_x, Double th_z)
{
    vector<dd> points;

    for(int c = ; c < ; c++)
    {
        Coord r1 = _rx(corners[c], th_x);
        Coord r2 = _rz(r1, th_z);
        points.pb( dd(r2[], r2[]) );
    }

    vector<dd> hull = convex_hull(points);
    Double area = convex_hull_area(hull);

    return area;
}

void solve(double A)
{
    Double alpha, beta_min, beta_max;
    if (A < )
    {
        assert(false);
    }
    else if (A <= sqrt())
    {
        alpha = ;
        beta_min = ;
        beta_max = deg2rad();
    }
    else
    {
        alpha = deg2rad();
        beta_min = ;
        beta_max = deg2rad();
    }

    Double lo = beta_min, hi = beta_max, mi;
    Double f_lo = rotated_shadow_area(alpha, lo);
    Double f_hi = rotated_shadow_area(alpha, hi);
    Double f_mi;
    for(int i = ; i < ; i++)
    {
        mi = (lo + hi) / ;
        f_mi = rotated_shadow_area(alpha, mi);
        if (A < f_mi)
        {
            hi = mi;
        }
        else
        {
            lo = mi;
        }
    }

    render_ans(alpha, mi);

}

int main()
{
    _init();

    int T;
    cin >> T;
    for (int t=; t<=T; ++t)
    {
        double A;
        cin >> A;
        printf("Case #%d:\n", t);
        solve(A);
    }
    return ;
}