陸路か空路かそれが問題だ。(topcoder MemberSRM 468 div2 250pt)

最短時間で姫に会いにいく

photo by law_keven

　TopCoder Statistics - Problem Statement

　とても時間のかかった問題だった。アルゴリズムはすぐに浮かんだが、実装するのが大変だった。　

　問題：王様は一刻も早く姫に会いにいきたい。今居る0市から姫のいるN市に行くには間にある1~N-1市をすべて経由して行かなければならない。隣あわせの市と市をつなぐ道は陸路と空路がそれぞれ1本ずつある。空路でいければ早いのだが、技術的な問題から飛行機はK回しか使えない。
　陸路、空路ともにかかる時間が全て分かっていて、Kも与えられているとき、最短時間を求めよ。

　制約：Nは1~50まで。Kは0~50まで。空路はfligthtime[ ],陸路は roadtime[ ]　いづれも要素がN個の正の整数の配列。

　動的計画法なんて必要なし。要素ごとの空路と陸路の差を求めて、差が大きい順に並べ替える。差が大きいほうからK個を空路、のこりを陸路をとり、その数を合計すればそれが最短時間となる。ただ差がマイナス、つまり陸路の方が時間が短い場合は飛行機を使える回数が残っていも陸路をとる。

　以下、ソース。構造体の中にvectorを挿入し、ソートするのが手間取った。

//SRM468 div2
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

class RoadOrFlightEasy {
	public:
struct Chw {
    int flightT;
    int roadT;
    int gap;
    int city;
};
	int minTime(int n, vector<int> rt, vectro <int> ft, int k){
        int minsum=0,i=0,j=0;
        vector<Chw> v_hw;
        Chw a;
        for (int i=0;i<n;i++){
            a.flightT=ft[i];
            a.roadT=rt[i];
            a.gap=ft[i]-rt[i];
            a.city=i;
            v_hw.push_back(a);
        }
        printf("\n \n");
        printf("flightTime : roadTime : gap >cityNum \n");
        for(int i=0;i<n;i++){
            printf("%3d  :%3d  :%3d>%d\n",v_hw[i].flightT,v_hw[i].roadT,v_hw[i].gap,v_hw[i].city);
        }
        printf("\n sort...\n");
        sort(v_hw.begin(), v_hw.end(), Lessflight);
        for(int i=0;i<n;i++){
            printf("%3d  :%3d  :%3d>%d\n",v_hw[i].flightT,v_hw[i].roadT,v_hw[i].gap,v_hw[i].city);
        }
        printf("\n sort_gap...\n");
        sort(v_hw.begin(), v_hw.end(), Lessgap);
        for(int i=0;i<n;i++){
            printf("%3d  :%3d  :%3d>%d\n",v_hw[i].flightT,v_hw[i].roadT,v_hw[i].gap,v_hw[i].city);        
        }
        for(j=0;j<k;j++){
            if (v_hw[j].gap > 0) break;
            minsum=minsum+v_hw[j].flightT;
        }
        for(;j<n;j++){
            minsum=minsum+v_hw[j].roadT;
        }
        printf("minTime =%d\n",minsum);
    return minsum;
	}
    
    static bool Lessflight(const Chw& rLeft, const Chw& rRight) {
        return rLeft.flightT < rRight.flightT;
    }
    static bool Lessroad(const Chw& rLeft, const Chw& rRight) {
        return rLeft.roadT < rRight.roadT;
    }
    static bool Lessgap(const Chw& rLeft, const Chw& rRight) {
        return rLeft.gap < rRight.gap;
    }
};

int main(){
	RoadOrFlightEasy ob1;
	int n=7,k=5,i=0;
    int rt[50]={50, 287, 621, 266, 224, 68, 636};
    int ft[50]={797, 661, 644, 102, 114, 452, 420};
    vector <int> v_rt(&rt[0],&rt[n]);
    vector <int> v_ft(&ft[0],&ft[n]);
    for(i=0;i<n;i++){
        printf("%d ",v_rt[i]);
    }
	ob1.minTime(n,v_rt,v_ft,k);
	return 0;
}

• vector 変数名(0番目のアドレス,最後のアドレス)で配列からvectorに一気に変換できる。
• sort(v_hw.begin(), v_hw.end(), 比較関数名)　vector型の構造体の始めから終わりまでソートする。

　関数内の演算子を変えると降順、昇順を切り替えられる。

美しすぎるプログラム（追記）

　提出後、他の人のコードも観てみた。得点の高いの人のコードは美しく簡潔で力強さを感じる。自分があれほど苦しみ実装したものをからりと書いている。素晴らしい。

　algorithmをincludeしておけば、max関数が使えるようだ。max(a,b)で大きい方を返す。

for(i=0;i<N;i++)  reduce[i]=max(0,road[i]-flight[i]);
sort(reduce,reduce+N);
for(i=0;i<N;i++)  res+=road[i];
for(i=0;i<K;i++)  res-=reduce[N-1-i];

　陸路の合計時間を足してから、空路との差が大きいものからK個選び、合計時間より引く。max関数を使うことで、差が負のものは0になる。