GCJ 2017 Round 1B - aki33524’s blog

B問題をクッソバグらせて絶望していたがCが瞬殺されてギリギリ964位だった。初Round1突破っっぽいので記念に解説を書く。

A

略解

一番ゴールするのが遅い馬と同時にゴールする。

証明

一番ゴールするのが遅い馬（以下B）に注目する。

Bと自身（以下A）が同時にゴールするようにした時、AはゴールするまでBに追いつかない。 AとBは共に等速であるから、距離は線形に縮まる。最初正の距離が開いており、ゴールする時に0であるからそれまで追いつかない。
BとA以外の馬（以下まとめてCとする）について、Cは必ずBに追いつく。順番待ちルールがない場合、CはBより先にゴールする為これは明らか。Bに追いついてからは1よりAはCにも追いつかない。
CがBに追いつくまでに、AはCに追いつかない。順番待ちルールが無いとすると、CはAより先にゴールする。1と同様の議論からAはCに追いつけない。

以上から、Bのみを考えればCは考察する必要が無い事がわかる。

文字で書くと冗長だが、馬の変位軸と時間軸のx-tグラフを描けば直感的に理解できると思う。

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

int D, N;
vector<double> K, S;

void solve(){
    double mtime = 0;
    for(int i=0; i<N; i++){
        mtime = max(mtime, (D - K[i]) / S[i]);
    }
    cout << D / mtime << endl;
}

int main(){
    cout.precision(16);
    cout.setf(ios::fixed);
    
    int T; cin >> T;
    for(int i=1; i<=T; i++){
        cout << "Case #" << i << ": ";
        cin >> D >> N;
        K.resize(N);
        S.resize(N);
        
        for(int i=0; i<N; i++)
            cin >> K[i] >> S[i];
        
        solve();
    }
    
    return 0;
}

B

略解

small

最も多い色を並べ、残り2色を左右から一つ飛ばしで挿入していく。

large

R -= G, Y -= V, B -= Oとしてsmallと同様の問題を解いた後、残った色を挿入。

証明

対称性から、Rを最も数が多い色として一般性を失わない。

R > Y+Bであるなら、IMPOSSIBLEとなる（必要性）。どのように挿入してもRが隣り合うので自明。
IMPOSSIBLEであるなら、R > Y+Bである（十分性）。対偶をとって、R <= Y+Bであるなら必ず解を構成できることを示す。これはRの左右からY, Bをそれぞれ挿入すると良い。
GはR、OはB、VはYとしか隣合えない（題より）。 small解けてlarge解けてない人はこの制約を見逃していそう（僕がそうでした）。
GとRしか存在しない時、G == Rの場合しか解が存在しない（対称性よりO, Vは略）。 GRGR…となるケース以外は明らかに同じ色が隣り合う（鳩ノ巣原理？）
GとR以外にも色が存在する時、R -= Gとして問題を解くことが等価（対称性より(ry）。 Gは（Gを含めて）R以外と隣合えないので、RGR…RGRという風にRで両端をサンドイッチする必要がある。これは先頭のRGR…RGを取り除いてRのみとして問題を解くのと同じ。

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

int N;
int R, O, Y, G, B, V;

string solve(){
    string table = "ROYGBV";
    if(R == G && (Y|V|B|O) == 0){
        string res = "";
        for(int i=0; i<R; i++)
            res += "RG";
        return res;
    }
    if(Y == V && (R|G|B|O) == 0){
        string res = "";
        for(int i=0; i<Y; i++)
            res += "YV";
        return res;
    }
    if(B == O && (R|G|Y|V) == 0){
        string res = "";
        for(int i=0; i<B; i++)
            res += "BO";
        return res;
    }
    
    R -= G;
    Y -= V;
    B -= O;
    
    if(R < 0 || Y < 0 || B < 0)
        return "IMPOSSIBLE";
    
    if((R==0 && G!=0) || (Y==0 && V!=0) || (B==0 && O!=0))
        return "IMPOSSIBLE";
    
    if(R>Y+B || Y>R+B || B>R+Y)
        return "IMPOSSIBLE";
    
    bool ymax = Y > B && R < max(Y, B);
    bool bmax = B > Y && R < max(Y, B);
    
    if(ymax){
        swap(R, Y);
        swap(G, V);
        swap(table[0], table[2]);
        swap(table[3], table[5]);
    }
    if(bmax){
        swap(R, B);
        swap(G, O);
        swap(table[0], table[4]);
        swap(table[3], table[1]);
    }
    
    vector<int> vec;
    for(int i=0; i<R; i++)
        vec.push_back(0);
    for(int i=0; i<Y; i++){
        if(i < R)
            vec.insert(vec.begin()+i*2+1, 2);
        else
            vec.push_back(2);
    }
    reverse(vec.begin(), vec.end());
    for(int i=0; i<B; i++){
        if(i < R+Y)
            vec.insert(vec.begin()+i*2, 4);
        else
            vec.insert(vec.begin(), 4);
    }

    for(int i=0; i<vec.size(); i++){
        if(vec[i] == 0){
            for(int j=0; j<G; j++){
                vec.insert(vec.begin()+i, 3);
                vec.insert(vec.begin()+i, 0);
            }
            break;
        }
    }
    for(int i=0; i<vec.size(); i++){
        if(vec[i] == 2){
            for(int j=0; j<V; j++){
                vec.insert(vec.begin()+i, 5);
                vec.insert(vec.begin()+i, 2);
            }
            break;
        }
    }
    for(int i=0; i<vec.size(); i++){
        if(vec[i] == 4){
            for(int j=0; j<O; j++){
                vec.insert(vec.begin()+i, 1);
                vec.insert(vec.begin()+i, 4);
            }
            break;
        }
    }
        
    string res = "";
    for(auto v: vec)
        res += table[v];
    return res;
}

int main(){
    int T; cin >> T;
    for(int i=0; i<T; i++){
        cout << "Case #" << i+1 << ": ";
        cin >> N;
        cin >> R >> O >> Y >> G >> B >> V;
        
        cout << solve() << endl;
    }
    return 0;
}

C

略解

まず1頭の馬だけを使った場合の最小時間を求め、その後任意の馬を使った場合の最小時間を求める。

証明？

正直この問題は証明が殆ど存在しないと思う……

任意の2点間を1頭の馬だけを使って移動する場合の最小時間を求める。 Warshall-Floydで全点対最短経路を求めた後、始点の馬で移動できる場合はその場合に掛かる時間で更新する。
任意の2点間を任意の馬を使って移動する場合の最小時間を求める。 1により任意の2点間を1頭の馬だけを使い移動する場合の最小時間の配列が求まっている。これを用いて同様にWarshall-Floydをすると任意の馬を使った場合の最小時間が求まる。

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

typedef long long ll;

int N, Q;
vector<double> E, S;
vector<vector<ll>> D;

void solve(){
    for(int k=0; k<N; k++){
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++) if(D[i][k] != -1 && D[k][j] != -1){
                if(D[i][j] == -1)
                    D[i][j] = D[i][k] + D[k][j];
               else
                    D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
            }
        }
    }
    vector<vector<double>> nD(N, vector<double>(N, 1e100));
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++) if(D[i][j] != -1 && D[i][j] <= E[i]){
            nD[i][j] = min(nD[i][j], D[i][j]/S[i]);
        }
    }
    for(int k=0; k<N; k++)
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                nD[i][j] = min(nD[i][j], nD[i][k] + nD[k][j]);
    for(int i=0; i<Q; i++){
        int s, t;
        cin >> s >> t; s--; t--;
        cout << " " << nD[s][t];
    }
    cout << endl;
}

int main(){
    cout.precision(16);
    cout.setf(ios::fixed);
    
    int T; cin >> T;
    for(int i=0; i<T; i++){
        cout << "Case #" << i+1 << ":";
        cin >> N >> Q;
        E.resize(N);
        S.resize(N);
        for(int i=0; i<N; i++)
            cin >> E[i] >> S[i];
        D.clear();
        
        for(int i=0; i<N; i++){
            vector<ll> vec(N);
            for(int j=0; j<N; j++){
                cin >> vec[j];
            }
            D.push_back(vec);
        }
        solve();
    }
    
    return 0;
}