AOJ-ICPC 2013 - 備忘録

昨日解いた問題のメモ。

環状鉄道路線（ここでは山手線）において、1日の運行に必要な車両の数を出す問題。
山手線の始発駅及び終着駅である大崎駅での到着、発車時刻の表から答えを出します。
うまく答えを出せば鉄子さんにデートに誘ってもらえるかもしれないんだって！やったね！

回答はこんな感じ。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
  
using namespace std;
 
int HourtoMin(string s);
 
int main()
{
    int n;
    while(1){
        cin >> n;
        if(n == 0) break;
        int time_s;
        string h_m_s;
        vector<pair<int, int> > trains(20001);
        for(int i = 0; i < 2 * n; i++){
            cin >> h_m_s;
            time_s = HourtoMin(h_m_s);
            if(i % 2 == 0) trains[i] = make_pair(time_s, 1);
            else trains[i] = make_pair(time_s, 0);
            // 到着したときは0、出発したときは1
        }
        sort(trains.begin(), trains.begin() + 2 * n);
        int osaki_now_train = 0, need_train = 0;
        for(int i = 0; i < 2 * n; i++){
            if(trains[i].second == 1){
                if(osaki_now_train == 0) need_train++;
                else osaki_now_train--;
            } else if(trains[i].second == 0) osaki_now_train++;
        }
        cout << need_train << endl;
    }
    return 0;
}
 
int HourtoMin(string s)
{
    int ans = 0;
    for(int i = 0; i <= 6; i = i + 3){
        ans += ((s[i] - '0') * 10 + s[i + 1] - '0') * (int)pow(60, ((6 - i) / 3));
    }
    return ans;
}

trainsという名前をつけたpairの配列を利用して、最初の項に時刻、次の項に到着か出発かを読み込んでいきます。0から数えて到着時刻は偶数番目、出発時刻は奇数番目なのでi % 2の結果で場合分け。
時刻は全てHourtoMinを用いて秒のみを使って表します(解き終わってから気づいたけど秒はMinじゃなくてSecだよばーか！)。

pairのソートはこちらを参考にしました↓
C++（ソートの補足） - アルゴリズム講習会

これを用いることによって、時刻が早い順に、そして到着の方を0にしていたので時刻が同じ場合は到着→出発の順に並べ替えることができるのです！これで同時刻に到着&発車の場合も安心！

その後、ソートされたpairの配列を順番に見ていき、到着の場合は大崎にいる電車の数を表すosaki_now_trainに1を加え、発車の場合はosaki_now_trainが1以上の時はこれから1減らし、0のときは必要な電車の数を表すneed_trainに1を加えます。最終的にneed_trainが答えになります。

ところで、私は最初、mapを使ってこの問題を解こうとしました。
mapの説明はこちら。
C++マニアック,STL の map の使い方,how to use STL map,標準テンプレートライブラリ,standard template library,コンテナ,container,C++言語講座

これを使ってtrains[time_s] = arrive / leave というふうに時刻をキー、値を到着か出発か、とすればものすごくわかりやすいのでは？と思ったのです。
ところがmapを用いたら答えが合いませんでした。
その原因は…mapでは重複するキーの存在は許されないということ。
つまり同時刻に到着または発車する電車の記録がちゃんと残らないということですね。
そんなこんなで結局pairを使うことにしたのでした。

今振り返ってみて、ふと到着と出発の読み込みの仕方が改善できるのではと思いました。
この回答ではiの値で場合分けしてますが、pairの二番目の項を(i + 1) % 2にすれば1行で済んだかも。

なんやかんや言ったけどわりとすっと通ったので嬉しみ。