POJ 1025: Department
問題概要
10 階建ての建物があり、各階には 10 個の部屋があります。各部屋には部屋番号が定められており、x 階の y 番目の部屋 (ただし x, y は 1-indexed) の部屋番号は xxyy (x または y が一桁の場合は前に 0 を付ける) です。
この建物に何人かの人が入ります。人にはそれぞれ大文字のアルファベットで表される序列があり、序列が高い人ほど辞書順で小さいアルファベットが割り当てられます。二人以上の人が同じ序列を持つことはありません。それぞれの人にはある時刻に建物に入った後、何個かの部屋を決められた順序で訪れそれぞれの部屋に決められた時間だけ滞在します。それぞれの人は部屋を必ず部屋番号の昇順に訪れます。
現在人が入っている部屋に入りたい人がいる場合、その人は部屋の前で列を作って待つ必要があります。部屋に入っている人が出たとき、現在列に並んでいる人 (部屋から人が出た瞬間に到着した人を含む) のうち序列が最も高い人のみが部屋に入ることができます。
建物にはエレベーターが設置されています。人がエレベーターに乗れるのは一日の開始からの経過秒数が 5 の倍数であるときのみです。一日の開始から 5 秒ごとに、エレベーターに乗ろうとしている人 (その瞬間に到着した人を含む) がいるとき、そのうち序列が最も高い人のみがエレベーターに乗ることができます。別の階にいた場合でも、二人が同時刻にエレベーターに乗ることはできません。
建物の入口から 1 階の任意の部屋またはエレベーター乗り場への移動には 30 秒かかります。ある部屋と同じ階の別の部屋やエレベーター乗り場の間の移動には 10 秒かかります。エレベーターは 1 階分の昇降に 30 秒かかります。1 階の任意の部屋またはエレベーター乗り場から建物の出口への移動には 30 秒かかります。
それぞれの人が最もかかる時間が短くなるように行動したときの行動を出力してください。なお、建物を出る時刻は 24:00:00 より前になることが保証されます。
出力
序列の高い順に、それぞれの人の行動を出力してください。それぞれの人の行動は時刻の昇順に出力してください。
時刻 t1 から時刻 t2 にかけて建物の入口から 1 階の部屋またはエレベーター乗り場へ移動したとき、t1 t2 Entry と出力してください。
時刻 t1 から時刻 t2 にかけて部屋番号 x の部屋に滞在したとき、t1 t2 Stay in room x と出力してください。
時刻 t1 から時刻 t2 にかけてエレベーターに乗っていたとき、t1 t2 Stay in elevator と出力してください。
時刻 t1 から時刻 t2 にかけて部屋番号 x の部屋から同じ階にある部屋番号 y の部屋へ移動したとき、t1 t2 Transfer from room x to room y と出力してください。
時刻 t1 から時刻 t2 にかけて部屋番号 x の部屋から同じ階のエレベーター乗り場へ移動したとき、t1 t2 Transfer from room x to elevator と出力してください。
時刻 t1 から時刻 t2 にかけてある階のエレベーター乗り場から同じ階にある部屋番号 y の部屋へ移動したとき、t1 t2 Transfer from elevator to room y と出力してください。
時刻 t1 から時刻 t2 にかけて部屋番号 x の部屋の前で待っていたとき、t1 t2 Waiting in front of room x と出力してください。
時刻 t1 から時刻 t2 にかけてエレベーター乗り場で待っていたとき、t1 t2 Waiting in elevator queue と出力してください。
時刻 t1 から時刻 t2 にかけて1 階の部屋またはエレベーター乗り場から建物の出口へ移動したとき、t1 t2 Exit と出力してください。
解法
移動をそのまま実装しても解けますが、実装量が多くなるので、実装の工夫をすることを考えます。
部屋とエレベーター乗り場は性質が似ているので、エレベーター乗り場を各階の 0 番目の部屋であるとして扱うとにします。また、部屋間の移動は、直前の部屋からの移動にかかる時間・その部屋 (またはエレベーター) に滞在する時間・部屋番号で管理することにします。
出力がややこしいので、最初にそれぞれの人が各部屋に入る時刻と出る時刻を計算することにします。この情報から出力すべき情報を得ることは比較的容易なので、省略します。
優先度付きキューに時刻・人の序列・人の番号・その人が訪れる予定の部屋のうち何番目の部屋に行こうとしているかの組を入れ、人が部屋に入ろうとするという情報を時刻の昇順に処理します。それぞれの部屋についてその部屋に入っている人が出る時刻を持っておき、人が部屋に入ろうとしたが入ろうとした時刻がこの時刻より早いときはこの時刻に再び入ることを試みる、とすると、人を序列の順に正しく入れることができます。
ただし、入ろうとしている部屋がエレベーターである場合は別の条件で判定する必要があります。具体的には、最後にエレベーターに人が乗った時刻を持っておき、この時刻の 5 秒後より前にエレベーターに乗ろうとしたときはこの時刻の 5 秒後に再びエレベーターに乗ろうとする、とすればよいです。また、時刻が 5 の倍数でないときは 5 の倍数になるまで待つ必要があります。
計算量は悪いですが、序列の制約より人の人数は 26 人以下と少ないので、この解法でも実行時間 0ms で AC を得ることができました。
実装
#include <iostream> #include <vector> #include <string> #include <queue> #include <utility> #include <algorithm> using namespace std; int main(){ vector<char> code; vector<int> entry; vector<vector<string>> name; vector<vector<int>> rooms, time1, time2; while (true){ char c; cin >> c; if (c == '.'){ break; } code.push_back(c); string time; cin >> time; int h = (time[0] - '0') * 10 + (time[1] - '0'); int m = (time[3] - '0') * 10 + (time[4] - '0'); int s = (time[6] - '0') * 10 + (time[7] - '0'); entry.push_back(h * 3600 + m * 60 + s); name.push_back(vector<string>()); rooms.push_back(vector<int>()); time1.push_back(vector<int>()); time2.push_back(vector<int>()); int prev = 0; while (true){ string id; cin >> id; if (id == "0"){ break; } int t; cin >> t; int floor = (id[0] - '0') * 10 + (id[1] - '0') - 1; int room = (id[2] - '0') * 10 + (id[3] - '0'); if (prev != floor){ name.back().push_back("elevator"); rooms.back().push_back(prev * 11); time1.back().push_back(10); time2.back().push_back(abs(prev - floor) * 30); } name.back().push_back("room " + id); rooms.back().push_back(floor * 11 + room); time1.back().push_back(10); time2.back().push_back(t); prev = floor; } if (prev != 0){ name.back().push_back("elevator"); rooms.back().push_back(prev * 11); time1.back().push_back(10); time2.back().push_back(prev * 30); } time1.back()[0] = 30; } int N = code.size(); vector<pair<char, int>> P(N); for (int i = 0; i < N; i++){ P[i] = make_pair(code[i], i); } sort(P.begin(), P.end()); vector<int> next(110, 0); int last = 0; priority_queue<pair<pair<int, char>, pair<int, int>>, vector<pair<pair<int, char>, pair<int, int>>>, greater<pair<pair<int, char>, pair<int, int>>>> pq; for (int i = 0; i < N; i++){ pq.push(make_pair(make_pair(entry[i] + 30, code[i]), make_pair(i, 0))); } vector<vector<int>> ans1(N), ans2(N); while (!pq.empty()){ int time = pq.top().first.first; char agent = pq.top().first.second; int id = pq.top().second.first; int num = pq.top().second.second; pq.pop(); int room = rooms[id][num]; if (room % 11 != 0 && time < next[room]){ pq.push(make_pair(make_pair(next[room], agent), make_pair(id, num))); } else if (room % 11 == 0 && time < last + 5){ pq.push(make_pair(make_pair(last + 5, agent), make_pair(id, num))); } else if (room % 11 == 0 && time % 5 != 0){ pq.push(make_pair(make_pair((time + 4) / 5 * 5, agent), make_pair(id, num))); } else { int stay = time2[id][num]; ans1[id].push_back(time); ans2[id].push_back(time + stay); if (room % 11 != 0){ next[room] = time + stay; } else { last = time; } if (num < rooms[id].size() - 1){ int tmp = time + stay + time1[id][num + 1]; pq.push(make_pair(make_pair(tmp, agent), make_pair(id, num + 1))); } } } for (int i = 0; i < N; i++){ int id = P[i].second; int M = rooms[id].size(); vector<int> ans; vector<string> st; ans.push_back(entry[id]); for (int j = 0; j < M; j++){ int tmp = ans.back() + time1[id][j]; ans.push_back(tmp); if (j == 0){ st.push_back("Entry"); } else { st.push_back("Transfer from " + name[id][j - 1] + " to " + name[id][j]); } if (ans1[id][j] != tmp){ ans.push_back(ans1[id][j]); if (rooms[id][j] % 11 != 0){ st.push_back("Waiting in front of " + name[id][j]); } else { st.push_back("Waiting in elevator queue"); } } ans.push_back(ans2[id][j]); st.push_back("Stay in " + name[id][j]); } int T = ans.back(); ans.push_back(T + 30); st.push_back("Exit"); int cnt = st.size(); vector<string> time(cnt + 1); for (int j = 0; j <= cnt; j++){ int h = ans[j] / 3600; time[j] += (char) ('0' + h / 10); time[j] += (char) ('0' + h % 10); time[j] += ':'; int m = ans[j] % 3600 / 60; time[j] += (char) ('0' + m / 10); time[j] += (char) ('0' + m % 10); time[j] += ':'; int s = ans[j] % 60; time[j] += (char) ('0' + s / 10); time[j] += (char) ('0' + s % 10); } cout << code[id] << endl; for (int j = 0; j < cnt; j++){ cout << time[j] << ' ' << time[j + 1] << ' ' << st[j] << endl; } cout << endl; } }
