naoya_t@hatenablog

いわゆるチラシノウラであります

Google Code Jam Qualification Round 2018


4/7 8:00JST〜4/8 11:00JST

とりあえず全問通しました。
今年から言語のチョイスで遊べる感じではなくなってる?のでC++で。
Round 1Aでお会いしましょう。

f:id:n4_t:20180408112912p:plain


SavingThe Universe Again (Small 5pt, Large 10pt)

https://codejam.withgoogle.com/2018/challenges/00000000000000cb/dashboard

エイリアンのロボットを動かす SCCSSC みたいな命令列(Sは「ビーム撃て」Cは「エネルギー倍増」)があって、
こちらの限られた防御力でなんとかするために命令列を(できるだけ少ない回数で)ハックしたいという話。ハックで可能なのは命令列中の隣り合った2文字をひっくり返す操作のみ。

ビームによる打撃は最初は1、倍増するにつれ2,4,8,16,...と増えていく。
・Sより先に現れるCのうち、一番最後のやつを後ろに持っていく
ことで打撃力は最も大きく減らせる。(打撃力低減効果が等しい2操作は存在しないのでgreedyに減らしていけばいい)

なんか面倒くさい実装してるけどこれ正規表現で書けたじゃん、と後で思った回。
→AC

DEBUGオプション付けたり付けなかったりしながらテストデータを食わせて結果を照合して時間も見てくれる的なツールを作って遊んでいました。
f:id:n4_t:20180408122530p:plain
f:id:n4_t:20180408122547p:plain*1

#include <bits/stdc++.h>
using namespace std;

#undef NDEBUG
#include <cassert>

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
typedef vector<int> vi;

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))

int count_damage(vector<char>& w) {
    int L = w.size();

    int strength = 1, damage = 0;
    rep(i, w.size()) {
        if (w[i] == 'C') strength <<= 1;
        else damage += strength;
    }

    return damage;
}

int hack(vector<char>& w) {
    int L = w.size();
    for (int i=L-1; i>=0; --i) {
        if (w[i] == 'S') {
            w.resize(i+1);
            break;
        }
    }

    L = w.size();
    if (L == 0) {
        return 0;
    }

    int last_c = -1;
    for (int i=L-1; i>=0; --i) {
        if (w[i] == 'C') {
            last_c = i; break;
        }
    }
    assert(IN(last_c, 0, L-2));

    swap(w[last_c], w[last_c+1]);

    return 1;
}

void solve(int D, string& P) {
    int L = P.size();
    assert(IN(D, 1, 1000000000));
    assert(IN(L, 2, 30));
    int shoot_cnt = 0, charge_cnt = L;
    rep(i, L) if (P[i]=='S') ++shoot_cnt;
    charge_cnt -= shoot_cnt;

    if (shoot_cnt > D) {
        cout << "IMPOSSIBLE";
        return;
    }
    if (charge_cnt == 0) {
        cout << 0;
        return;
    }

    vector<char> w(ALL(P));

    int ans = 0;
    int damage = count_damage(w);
    while (damage > D) {
        ans += hack(w);
        damage = count_damage(w);
    }
    cout << ans;
}

int main() {
    int T; cin >> T;
    for (int t=1; t<=T; ++t) {
        int D; string P;
        cin >> D >> P;
        printf("Case #%d: ", t);
        solve(D, P);
        printf("\n");
    }
    return 0;
}

Trouble Sort (Small 8pt, Large 15pt)

https://codejam.withgoogle.com/2018/challenges/00000000000000cb/dashboard/00000000000079cb

連続した3文字をひっくり返す操作しかできないバブルソート
入れ替わる文字は常に1つ飛びなので、偶数番目の列、奇数番目の列それぞれの内部でしかソートが起こらない。
偶数番目の列と奇数番目の列に分けて別々にソートしたものをマージすれば同じ結果が得られる。
で、全体を普通にソートしたやつと比較して最初にずれた位置を返す。
→AC

// 略
#define INTSPACE 12
char _buf[INTSPACE*1000000 + 3];

int loadint() {
    if (fgets(_buf, INTSPACE+3, stdin)==NULL) return 0;
    return atoi(_buf);
}
int loadvec(vector<int>& v, int N=-1) {
    if (N == -1) {
        N = loadint();
        if (N==0) return 0;
    }
    int bufsize = INTSPACE*N + 3;
    if (fgets(_buf, bufsize, stdin)==NULL) return 0;
    v.resize(N);

    int i=0;
    bool last = false;
    for (char *p=&_buf[0]; ;) {
        char *q = p;
        while (*q > ' ') ++q;
        if (*q == 0x0D || *q == 0x0A) last = true;
        *q = 0;
        v[i++] = atoi(p);
        if (last || i == N) break;
        p = q+1;
    }
    return i;
}

void TroubleSort(vector<int>& src, vector<int>& dest) {
    int len = src.size();
    vector<vector<int>> a(2);
    a[0].resize(len - len/2);
    a[1].resize(len/2);
    rep(i, len) a[i%2][i/2] = src[i];
    sort(ALL(a[0]));
    sort(ALL(a[1]));
    dest.resize(len);
    rep(i, len) dest[i] = a[i%2][i/2];
}

void solve(int N, vector<int>& orig) {
    vector<int> sorted;
    TroubleSort(orig, sorted);

    sort(ALL(orig));
    int bad_index = -1;
    rep(i, N) {
        if (sorted[i] != orig[i]) {
            bad_index = i;
            break;
        }
    }
    if (bad_index == -1)
        cout << "OK";
    else
        cout << bad_index;
}

int main() {
    int T = loadint();

    vector<int> a;
    a.reserve(100000);

    for (int t=1; t<=T; ++t) {
        int N = loadint();
        loadvec(a, N);
        printf("Case #%d: ", t);
        solve(N, a);
        printf("\n");
    }
    return 0;
}

Go, Gopher! (Small 10pt, Large 20pt)

https://codejam.withgoogle.com/2018/challenges/00000000000000cb/dashboard/0000000000007a30

インタラクティブ問題。
広大な果樹園を整備するべく穴掘り亀(gopher)を使役するのだけれど、亀さんは命令した区画からずれた所を掘ってしまうことがある
(指定した区画の8方向に隣接する区画も含めた9区画の中から均一にランダムに選ぶらしい)。
1000回以内の命令で、希望の区画数を上回るサイズの長方形になるように(長方形の中は全部掘ってあって、外は掘っていない状態)何とかしてくれ、という話。

3x3のブロックを単位とした長方形を考えて、各ブロックの中央に20回ぐらい行ったら9割ぐらい埋まるので、あとは掘れてないところを重点的に攻める方式で。(長方形の4辺沿いの区画ははみ出さないように、1つ内側から攻める)

問題の制約を理解していなくて、終わってるはずなのに終わった判定になってない、という所でずっと停滞→testing_tool.pyを読んで解決。(stderrをtesting_toolが食ってしまうのでデバッグやりにくい…)
→AC〈投稿してもぐるぐる回ってエラー表示になって、というのを繰り返した。サーバ側トラブルなのにペナルティ付けられるの良くない)

// 略

#define Y_OFFSET 10
#define X_OFFSET 10

#define NUM_FIRST_PHASE 20

#define ST_CLEAR  1
#define ST_OK     0
#define ST_ERROR -1

int _send_raw(int r, int c, int *ar, int *ac) {
    printf("%d %d\n", r, c);
    fflush(stdout);

    cin >> *ar >> *ac;
    if (*ar == 0 && *ac == 0) {
        return ST_CLEAR;
    }
    else if (*ar == -1 && *ac == -1) {
        return ST_ERROR;
    }
    return ST_OK;
}

int w[20][20];
int _rest_cnt, prepared;
int H, W;

int send(int r, int c, int *ar, int *ac) {
    if (_rest_cnt == 0) return ST_ERROR;

    int status = _send_raw(Y_OFFSET+r, X_OFFSET+c, ar, ac);
    --_rest_cnt;
    *ar -= Y_OFFSET;
    *ac -= X_OFFSET;
    return status;
}

int drill(int t_r, int t_c, int d_r, int d_c) {
    int ay, ax;
    int trial = 0;

    while (!w[t_r][t_c]) {
        int status = send(d_r, d_c, &ay, &ax);
        ++trial;

        if (status != ST_OK) return status;

        if (IN(ay, 0, H-1) && IN(ax, 0, W-1)) {
            if (w[ay][ax] == 0) {
                ++prepared;
                w[ay][ax] = 1;
            }
        } else {
            assert(false);
        }
    }
    return ST_OK;
}

void solve_interactive() {
    int A; cin >> A;
    memset((void *)w, 0, sizeof(w));

    int ay, ax;
    int status;

    if (A < 0) {
        _send_raw(-1, -1, &ay, &ax);
        return;
    }

    int ah = (sqrt(A) + 2)/3;
    H = ah*3;
    int b = (A + H-1)/H;
    int aw = (b + 2)/3;
    W = aw*3;

    _rest_cnt = 1000;
    prepared = 0;

    rep(t, NUM_FIRST_PHASE) {
        for (int y=0; y<H; y+=3) {
            for (int x=0; x<W; x+=3) {
                status = send(1+y, 1+x, &ay, &ax);
                if (status != ST_OK) goto end;
                if (IN(ay, 0, H-1) && IN(ax, 0, W-1)) {
                    if (w[ay][ax] == 0) {
                        ++prepared;
                        w[ay][ax] = 1;
                    }
                } else {
                    assert(false);
                }
            }
        }
    }

    for (int y=1; y<H-1; ++y) {
        for (int x=1; x<W-1; ++x) {
            status = drill(y, x, y, x);
            if (status != ST_OK) goto end;
        }
    }

    for (int y=1; y<H-1; ++y) {
        status = drill(y, 0, y, 1);
        if (status != ST_OK) goto end;
        status = drill(y, W-1, y, W-2);
        if (status != ST_OK) goto end;
    }
    for (int x=1; x<W-1; ++x) {
        status = drill(0, x, 1, x);
        if (status != ST_OK) goto end;
        status = drill(H-1, x, H-2, x);
        if (status != ST_OK) goto end;
    }

    status = drill(0, 0, 1, 1);
    if (status != ST_OK) goto end;
    status = drill(H-1, 0, H-2, 1);
    if (status != ST_OK) goto end;
    status = drill(0, W-1, 1, W-2);
    if (status != ST_OK) goto end;
    status = drill(H-1, W-1, H-2, W-2);
    if (status != ST_OK) goto end;

 end:
    if (status == ST_ERROR) goto error;
    else if (status == ST_CLEAR) goto closing;

 closing:
    return;

 error:
    return;
}

int main() {
    int T; cin >> T;
    for (int t=1; t<=T; ++t) {
        solve_interactive();
    }
    return 0;
}

Cubic UFO (Small 11pt, Large 21pt)

https://codejam.withgoogle.com/2018/challenges/00000000000000cb/dashboard/00000000000079cc

1辺の長さが1の立方体を回転させて、その影がぴったり(許容誤差範囲内で)指定の面積になるように回転させろという問題。*2
太陽がY軸正方向(無限遠)にあって、地面はXZ平面に平行(y=-3)。立方体の重心は原点にある。
(先週CourseraのAerial Roboticsの講義で剛体の回転の話をやったばかりなのでちょっと嬉しい)

・面積1〜√2 (small):X軸(ないしZ軸)を軸に0〜45度回転すれば行ける
・面積√2〜√3 (large):45度回転した後でもう一つの軸で0〜??度回転すれば行ける

回転角は二分探索で求めた。(arcsinで出せるっぽい?)
largeのときの??度の最大値を求めるのに別途三分探索を行った。

面積そのものは、愚直に立方体を回転させて正射影をとって凸包を計算して(平行四辺形か六角形になるでしょ)その多角形の面積を求めた。
精度のことをあまり考えたくなくてlong doubleを使ってるけど必要だったかは(考えたくない)。
→AC(またサーバエラーでペナルティ)

// 略
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(8, Coord(3));

const Double PI = 3.14159265358979323846;

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

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

    rep(c, 8) {
        rep(i, 3) {
            corners[c][i] = 0.5 * _corners[c][i];
        }
    }
}

inline Coord dot(Double R[][3], Coord& x) {
    Coord y(3, 0.0);
    rep(i, 3){
        rep(j, 3){
            y[i] += R[i][j] * x[j];
        }
    }
    return y;
}

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

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

Coord _rz(Coord& p, Double th) {
    Double R[3][3];
    R[0][0] = Dcos(th); R[0][1] = -Dsin(th); R[0][2] = 0;
    R[1][0] = Dsin(th); R[1][1] =  Dcos(th); R[1][2] = 0;
    R[2][0] = 0;        R[2][1] =  0;        R[2][2] = 1;
    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, double eps=1e-9) {
    dd pq = vec(p, q);
    return vlen(pq) < eps;
}

vector<dd> uniq(vector<dd>& v) {
    sort(ALL(v));
    vector<dd> res;
    res.pb(v[0]);
    for (int i=1; 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 = 1e9, xmin = 1e9;
    int at = -1;
    rep(i, N) ymin = min(ymin, points[i].second);
    rep(i, N) {
        if (points[i].second == ymin) {
            if (points[i].first < xmin) {
                xmin = points[i].first;
                at = i;
            }
        }
    }
    vector<pair<Double, dd>> tmp(N);
    rep(i, N) {
        Double th;
        if (i != at)
            th = Datan2(points[i].second - ymin, points[i].first - xmin);
        else
            th = -1e9;
        tmp[i] = make_pair(th, points[i]);
    }
    sort(ALL(tmp));
    assert(tmp[0].second == dd(xmin, ymin));

    vector<dd> pts(N+1);
    rep(i, N) pts[1+i] = tmp[i].second;
    pts[0] = pts[N];

    int M = 1;
    for (int i=2; i<=N; ++i) {
        while (ccw(pts[M-1], pts[M], pts[i]) <= 0) {
            if (M > 1) {
                --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(0, 0);

    Double area = 0;
    rep(i, N) {
        dd p = hull[i], q = hull[(i+1)%N];
        area += 0.5 * Dfabs(outer(p, q));
    }
    return area;
}

void render_ans(Double th_x, Double th_z) {
    rep(c, 3) {
        Coord p(3, 0); p[c] = 0.5;
        Coord r1 = _rx(p, th_x);
        Coord r2 = _rz(r1, th_z);
        printf("%.16Lf %.16Lf %.16Lf\n", r2[0], r2[1], r2[2]);
    }
}

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

    rep(c, 8) {
        Coord r1 = _rx(corners[c], th_x);
        Coord r2 = _rz(r1, th_z);
        points.pb( dd(r2[0], r2[2]) );
    }

    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 < 1.0) {
        assert(false);
    } else if (A <= sqrt(2.0)) {
        alpha = 0;
        beta_min = 0;
        beta_max = deg2rad(45);
    } else {
        alpha = deg2rad(45);
        beta_min = 0;
        beta_max = deg2rad(35.26438902);
    }

    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;
    rep(i, 100) {
        mi = (lo + hi) / 2;
        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=1; t<=T; ++t) {
        double A; cin >> A;
        printf("Case #%d:\n", t);
        solve(A);
    }
    return 0;
}

*1:cloud9というのはローカルのホスト名で、AWSのcloud9ではないです

*2:去年「正解するカド」ってアニメあったよね…後半ちょっと酷かったけど