naoya_t@hatenablog

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

Google Code Jam 2017 - Round 1B

Round 1C進出。あと6分あれば…
(54pts, 1595th place)

A. Steed 2: Cruise Control

A. Steed 2: Cruise Control

small (11pt)

一番遅く着くやつと同時にゴールするように出かけるだけ、だよね。
AC。もっとサクッと書いて通すべき問題だった。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

double solve(ll D, vector<pair<ll,int> >& KS) {
    int N = KS.size();
    sort(all(KS));

    double maxt = 0.0;
    for (int i=N-1; i>=0; --i) {
        ll k = KS[i].first;
        int s = KS[i].second;
        double r = (double)(D - k);
        double t = r / s;
        maxt = max(maxt, t);
    }
    return (double)D / maxt;
}

int main(){
  int _T; cin>>_T;
  rep(_t,_T){
    ll D; int N; cin >> D >> N;
    vector<pair<ll,int> > KS;
    rep(i, N) {
        ll k; int s; cin >> k >> s;
        KS.push_back(make_pair(k, s));
    }
    double ans = solve(D, KS);

 answer:
    printf("Case #%d: %.6f\n", 1+_t, ans);
  }
}
large (14pt)

精度が不安になってdouble→long doubleに書き直した。AC。

...(略)...
typedef long double Double;
...(略)...
    printf("Case #%d: %.6Lf\n", 1+_t, ans);
...(略)...

B. Stable Neigh-bors

B. Stable Neigh-bors

small (13pt)

3色限定。同じ色が連続しないように並べるだけ。一番多いやつを1つ飛びに置いた隙間に、他の2色を詰めていっただけ。AC。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> ii;

#include <cassert>

string sub(vector<ii>& s) {
    int L = s[0].first;
    vector<vector<int> > p(L*2);

    int c0 = s[0].second;
    rep(i, L) p[2*i].push_back(c0);

    int c1 = s[1].second;
    for (int i=0,c=s[1].first; i<c; ++i) {
        p[2*i+1].push_back(c1);
    }

    int c2 = s[2].second;
    for (int i=0,c=s[2].first; i<c; ++i) {
        p[2*(L-1-i)+1].push_back(c2);
    }

    stringstream ss;
    rep(i, L*2) {
        int np = p[i].size();
        assert(np == 1 || np == 2);
        rep(j, np) {
            int c = p[i][j];
            ss << ("ROYGBV"[c]);
        }
    }
    return ss.str();
}

string solve_s(int N, vector<int>& ROYGBV) {
    int R = ROYGBV[0], Y = ROYGBV[2], B = ROYGBV[4];
    if (R > Y+B || Y > B+R || B > R+Y) {
        return "IMPOSSIBLE";
    }
    vector<ii> s;
    s.push_back(ii(R,0));
    s.push_back(ii(Y,2));
    s.push_back(ii(B,4));
    sort(all(s)); reverse(all(s));
    return sub(s);

    return "POSSIBLE";

}

int main(){
  int _T; cin>>_T;
  rep(_t,_T){
    vector<int> ROYGBV(6);
    int N; cin >> N;
    rep(i, 6) cin >> ROYGBV[i];

 answer:
    cout << "Case #" << (1+_t) << ": ";
    cout << solve_s(N, ROYGBV);
    cout << endl;
  }
}
large (22pt)

悩んで悩んで堂々巡りして解けなかった…

C. Pony Express

C. Pony Express

small (16pt)

1本道なので1番から順番に馬を走らせていけばいい。
priority_queueで書いたけど最初のバージョンは遅くてTLE。
枝刈りして2投目でAC。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())
#define cons  make_pair
#define car   first
#define cdr   second
typedef pair<int,int> ii;

#include <cassert>

int N, nQ;
vector<int> E, S;
vector<vector<int> > D;

typedef long double Double;
typedef pair< pair<int,Double>,pair<int,int> > ST;

Double solve_s(int uk, int vk) {
    assert(uk == 0 && vk == N-1);

    priority_queue<ST> pq;
    pq.push( cons(cons(0,0),cons(0,0)));
    Double fastest = 1e20;

    vector<Double> arrived;
    while (!pq.empty()) {
        ST st = pq.top(); pq.pop();

        int town = st.car.car; Double at = -st.car.cdr;
        if (town == N-1) {
            arrived.push_back(at);
            fastest = min(fastest, at);
            continue;
        } else {
            if (at >= fastest) continue;
        }

        int rest = st.cdr.car, speed = st.cdr.cdr;

        int dist = D[town][town+1];
        assert(dist >= 0);
        if (rest >= dist) {
            Double next_at = at + (Double)dist / speed;
            pq.push( cons(cons(town+1, -next_at), cons(rest-dist, speed)) );
        }
        if (E[town] >= dist) {
            Double next_at = at + (Double)dist / S[town];
            pq.push( cons(cons(town+1, -next_at), cons(E[town]-dist, S[town])) );
        }
    }

    assert(arrived.size() > 0);

    sort(all(arrived));
    return arrived[0];

}

int main(){
  int _T; cin>>_T;
  rep(_t,_T){
      cin >> N >> nQ;

      E.resize(N); S.resize(N);
      rep(i, N) cin >> E[i] >> S[i];

      D.assign(N, vector<int>(N, -1));
      rep(i, N) rep(j, N) { cin >> D[i][j]; }

      vector<Double> ans(nQ);

      rep(k, nQ) {
          int uk, vk; cin >> uk >> vk;
          --uk; --vk;
          ans[k] = solve_s(uk, vk);
      }

 answer:
    cout << "Case #" << (1+_t) << ": ";
    rep(k, nQ) {
        printf("%.7Lf", ans[k]);
        putchar((k == nQ-1) ? '\n' : ' ');
    }
  }
}
large (24pt)

実装してデータDLしてsubmitしても間に合わないと思って諦めながら、あと10分切ったところで思いついたのがこんな解法。

・距離テーブル:とりあえず、全ノード相互間の距離をワーシャル・フロイド法で求めるよね。O(N^3)。
・馬時間距離テーブル:あるノードの馬が、ある別のノードまで行けるとしたらどれだけ時間がかかるか(体力どれだけ残すとかはいいから)求める。距離は計算済みだから、その距離以上走れるなら速度で割るだけ。O(N^2)。
・馬時間距離テーブルでワーシャル・フロイド法したら、全ノード相互間の時間距離が求められる。O(N^3)。
・あとはクエリをテーブルからのルックアップで処理するだけ。

Practiceで計算あっという間に終わって、終了6分後にAC。自分を信じてれば通せた(し、これ取れてれば1000位以内に入れてた)のか。そういうのも含めて実力なんだよな。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())
#define cons  make_pair
#define car   first
#define cdr   second
typedef pair<int,int> ii;

#include <cassert>

typedef long long ll;

int N, nQ;
vector<int> E, S;
vector<vector<ll> > D;

typedef long double Double;
typedef pair< pair<int,Double>,pair<int,int> > ST;

#define INFTY 1e30

int main(){
    int _T; cin>>_T;
    rep(_t,_T){
        cin >> N >> nQ;

        E.resize(N); S.resize(N);
        rep(i, N) cin >> E[i] >> S[i];

        D.assign(N, vector<ll>(N, 2000000000LL));
        rep(i, N) rep(j, N) {
            Double d; cin >> d;
            if (d >= 0) D[i][j] = d;
        }
        rep(i, N) D[i][i] = 0;

        rep(k, N) rep(i, N) rep(j, N) {
			if (D[i][j] > D[i][k] + D[k][j])
				D[i][j] = D[i][k] + D[k][j];
		}

        vector<vector<Double> > T(N, vector<Double>(N, INFTY));
        rep(i, N) {
            rep(j, N) {
                Double d = D[i][j];
                if (d <= E[i]) {
                    T[i][j] = d / S[i];
                }
            }
        }
        rep(k, N) rep(i, N) rep(j, N) {
			if (T[i][j] > T[i][k] + T[k][j])
				T[i][j] = T[i][k] + T[k][j];
		}

        vector<Double> ans(nQ);
        rep(k, nQ) {
            int uk, vk; cin >> uk >> vk;
            --uk; --vk;
            ans[k] = T[uk][vk];
        }

 answer:
    cout << "Case #" << (1+_t) << ": ";
    rep(k, nQ) {
        printf("%.7Lf", ans[k]);
        putchar((k == nQ-1) ? '\n' : ' ');
    }
  }
}

(翌日)

B-largeどうやったら解けるの?と思ってanalysis読んだけど意味わからない

あ。。。
問題、というか制約をちゃんと読めてなかった…orz
2色毛のたてがみのユニコーン (Orange,Green,Violet)の場合、そのうちの1色でもかぶる個体とは隣接できない、ってことは、R-O-Y-G-B-V- で隣接する2種だけじゃなくて、構成色がかぶるやつもダメ。Orange(Red+Yellow) は、Green(Yellow+Blue) とも Violet(Blue+Red) とも隣接できない。ということは、隣接できるのは補色?のBlueだけ(O-B)。同様にGreenはRedとだけ(G-R)、VioletはYellowとだけ(V-Y)隣接できる。
とすると。2色毛ユニコーンはその補色となる単色毛ユニコーンで挟む形でしか配置できない。Orangeを取って言えば BOB[OB]*-other- みたいな。例外として、OとBしかいない場合(最後と最初が隣りになるから) BOBOBO- の配置のみが可能。
・2色毛とその補色毛、の2種類のみの場合→同数でなければIMPOSSIBLE。同数なら交互に配置。
・そうでない場合。すべての2色毛は補色単色毛で挟む。挟むのにそれと同数の補色単色毛を消費する。挟む位置はバラバラでもまとまってても構わない。(BOBOB-other-B-other- でも BOB-other-BOB-other- でも消費B量は変わらないしどちらも合法な配列)。てことは、挟むために消費する単色毛量分を引いたサブ問題(これはsmallの制約と等価なのでsmallソルバで解けばいい)を解いて、結果がIMPOSSIBLEならそこに補色が来てもどうにもならないのでIMPOSSIBLE、そうでなければ、解の文字列に最初に現れるR,Y,Bそれぞれを R[OR]{Oの個数だけ}, Y[VY]{Vの個数だけ}, B[OB]{Oの個数だけ} に置き換えたものが最終的な答えになる。
・単色毛ユニコーンは、その補色2色毛ユニコーンが存在する場合、補色2色毛の個体数を上回るだけの個体が挟み込みに必要(ie. |R|>|G|, |Y|>|V|, |B|>|O|)。存在しない場合はこの制約は不要(eg. |G|=0のときは|R|=0でもいい)←後者のチェックが間違ってて最初Practiceで落とした… B-small の入力を通せばIMPOSSIBLEが出まくるから分かることなのだが

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> ii;

// #define NDEBUG
#include <cassert>

#define RED       0
#define ORANGE    1
#define YELLOW    2
#define GREEN     3
#define BLUE      4
#define VIOLET    5

#define M_RED     (1 << RED)
#define M_ORANGE  (1 << ORANGE)
#define M_YELLOW  (1 << YELLOW)
#define M_GREEN   (1 << GREEN)
#define M_BLUE    (1 << BLUE)
#define M_VIOLET  (1 << VIOLET)

#define IMPOSSIBLE "IMPOSSIBLE"

// sub(), solve_s() はB-smallの時のやつ
string sub(vector<ii>& s) { 
    int L = s[0].first;
    vector<vector<int> > p(L*2);

    int c0 = s[0].second;
    rep(i, L) p[2*i].push_back(c0);

    int c1 = s[1].second;
    for (int i=0,c=s[1].first; i<c; ++i) {
        p[2*i+1].push_back(c1);
    }

    int c2 = s[2].second;
    for (int i=0,c=s[2].first; i<c; ++i) {
        p[2*(L-1-i)+1].push_back(c2);
    }

    stringstream ss;
    rep(i, L*2) {
        int np = p[i].size();
        assert(np == 1 || np == 2);
        rep(j, np) {
            int c = p[i][j];
            ss << ("ROYGBV"[c]);
        }
    }
    return ss.str();
}

string solve_s(int N, vector<int>& ROYGBV) {
    int R = ROYGBV[RED], Y = ROYGBV[YELLOW], B = ROYGBV[BLUE];
    if (R > Y+B || Y > B+R || B > R+Y) {
        return IMPOSSIBLE;
    }

    vector<ii> s;
    s.push_back(ii(R, RED));
    s.push_back(ii(Y, YELLOW));
    s.push_back(ii(B, BLUE));
    sort(all(s)); reverse(all(s));
    return sub(s);
}

string solve_two(const char* colors, int each_n) {
    stringstream ss;
    rep(i, each_n) ss << colors;
    return ss.str();
}

string solve_l(int N, vector<int>& ROYGBV) {
    unsigned int pattern = 0;
    for (int i=0,m=1; i<6; ++i, m<<=1) {
        if (ROYGBV[i] > 0) pattern |= m;
    }

    switch (pattern) {
        case (M_RED|M_GREEN):
            if (ROYGBV[RED] == ROYGBV[GREEN])
                return solve_two("RG", ROYGBV[RED]);
            else
                return IMPOSSIBLE;
        case (M_YELLOW|M_VIOLET):
            if (ROYGBV[YELLOW] == ROYGBV[VIOLET])
                return solve_two("YV", ROYGBV[YELLOW]);
            else
                return IMPOSSIBLE;
        case (M_BLUE|M_ORANGE):
            if (ROYGBV[BLUE] == ROYGBV[ORANGE])
                return solve_two("BO", ROYGBV[BLUE]);
            else
                return IMPOSSIBLE;
        default:
            break;
    }

    if ((ROYGBV[GREEN] > 0 && ROYGBV[GREEN] >= ROYGBV[RED])
        || (ROYGBV[VIOLET] > 0 && ROYGBV[VIOLET] >= ROYGBV[YELLOW])
        || (ROYGBV[ORANGE] > 0 && ROYGBV[ORANGE] >= ROYGBV[BLUE]))
    // ここの ROYGBV[GREEN] > 0 && みたいなのが重要。さもないと該当2色毛がいない時、補色単色毛数が0でもアウトになる
    {
        return IMPOSSIBLE;
    }

    vector<int> RYB(all(ROYGBV));
    RYB[RED]    -= RYB[GREEN];
    RYB[GREEN]   = 0;
    RYB[YELLOW] -= RYB[VIOLET];
    RYB[VIOLET]  = 0;
    RYB[BLUE]   -= RYB[ORANGE];
    RYB[ORANGE]  = 0;

    int nRYB = accumulate(all(RYB), 0);
    string s_sol = solve_s(nRYB, RYB);
    if (s_sol == IMPOSSIBLE) return IMPOSSIBLE;

    stringstream ss;
    rep(i, nRYB) {
        char ci = s_sol[i];
        ss << ci;
        switch (ci) {
            case 'R':
                if (ROYGBV[GREEN] > 0) {
                    rep(j, ROYGBV[GREEN]) ss << "GR";
                    ROYGBV[GREEN] = 0;
                }
                break;
            case 'Y':
                if (ROYGBV[VIOLET] > 0) {
                    rep(j, ROYGBV[VIOLET]) ss << "VY";
                    ROYGBV[VIOLET] = 0;
                }
                break;
            case 'B':
                if (ROYGBV[ORANGE] > 0) {
                    rep(j, ROYGBV[ORANGE]) ss << "OB";
                    ROYGBV[ORANGE] = 0;
                }
                break;
            default:
                assert(!(ci == 'R' || ci == 'Y' || ci == 'B'));
                break;
        }
    }
    return ss.str();
}

int main(){
  int _T; cin>>_T;
  rep(_t,_T){
    vector<int> ROYGBV(6);
    int N; cin >> N;
    rep(i, 6) cin >> ROYGBV[i];

 answer:
    cout << "Case #" << (1+_t) << ": ";
    string ans = solve_l(N, ROYGBV);
    assert(ans == IMPOSSIBLE || ans.size() == N);
    cout << ans << endl;
  }
}

おまけ



ほんとそれ