Sony GO FOR IT 5) 申告制エレベータ
就活のためエントリーしていたSonyから
「コードで世界を変えたいと思う方、現実の難しい課題をプログラミングによって解くことが好きな方向けに『GO FOR IT -コードで世界は変えられる-』を開催します。」
と題して以下のサイトでイベントを行なっているというメールで連絡が来てたので、特にプログラミング能力に自信があるという訳ではないですが、5番目の問題を解いてコンテストに応募してみる事にしました。
http://www.sony.co.jp/SonyInfo/Jobs/newgrads/sus/go_for_it.html
なお、このコンテストは2013新卒採用選考とは関係ないようです…
■5) 申告制エレベータ
実際の問題内容は以下をご覧下さい。
http://www.sony.co.jp/SonyInfo/Jobs/newgrads/sus/q05.html
問題i)
エレベータを1台、最大乗車人数を1人とします。
単純に入力データの識別番号順に、利用者を運ぶプログラムを作成してください。
回答i)
これを実現するためのアルゴリズムは以下のような規則に基づいています。
- 初期値は(1,0,1,E,0,0,0,0,0)である。
- B(開)とE(閉)は交互に起きる。
- 降車させた階数に利用者がいれば乗車させる。
- 以下の4つのパターンのどれかの繰り返しで成り立っている
- Eで利用者が乗車したらBでその人は降車する(時刻：+2*移動階数)
- Eで利用者が乗車しなかったらBで利用者は降車しない(時刻：いろいろと複雑になる)
- Bで利用者が降車したらEでエレベータの扉を閉める(時刻：+5秒もしくは希望乗車時刻まで待つ)
- Bで利用者が降車しなかったらEでエレベータの扉を閉める(時刻：+5秒もしくは希望乗車時刻まで待つ)
#include <cstdio>
#include <cstdlib>
const int MAX_N = 10; // 利用者数
const int MOVE = 2; // 移動時間
// 入力
int In1[MAX_N + 1]; // 入力データの識別番号
int In2[MAX_N + 1]; // 申告者の乗車希望時刻(開始してからの経過秒数)
int In3[MAX_N + 1]; // 申告者が乗車する階
int In4[MAX_N + 1]; // 申告者が降車する階
// 出力
int Out1 = 1; // エレベータの識別番号(1)
int Out2 = 0; // エレベータの動作時刻(開始してからの経過秒数)
int Out3 = 1; // エレベータが動作した階
char Out4 = 'E'; // エレベータの動作
int Out5 = 0; // 入力データの識別番号1
int Out6 = 0; // 入力データの識別番号2
int Out7 = 0; // 入力データの識別番号3
int Out8 = 0; // 入力データの識別番号4
int Out9 = 0; // 入力データの識別番号5
int main() {
FILE *fin, *fout;
fin = fopen("input_i.txt", "r");
fout = fopen("output_i.txt", "w");
// ファイル入力より入力
for(int i = 0; i < MAX_N; i++)
fscanf(fin, "%d,%d,%d,%d\n", &In1[i], &In2[i], &In3[i], &In4[i]);
// for(int i = 0; i < MAX_N; i++)
// printf("%d %d %d %d\n", In1[i], In2[i], In3[i], In4[i]);
int t = 0, c = 0;
while(1) {
// 開くと閉じるを交互に行う
if(Out4 == 'B') {
Out3 = Out3;
Out4 = 'E';
if(Out5 == 0) {
if(c != 0) t++;
else c++;
if(t > MAX_N - 1) break;
if(Out2 + 5 > In2[t])
Out2 += 5; // 閉時間
else
Out2 = In2[t]; // 次の希望乗車時刻
Out5 = In1[t];
}
else {
if(In3[t + 1] == Out3) {
if(c != 0) t++;
else c++;
if(t > MAX_N -1) break;
if(Out2 + 5 > In2[t])
Out2 += 5; // 閉時間
else
Out2 = In2[t]; // 次の希望乗車時刻
Out5 = In1[t];
}
else {
Out2 += 5;
Out5 = 0;
}
}
}
else if(Out4 == 'E') {
Out4 = 'B';
Out5 = Out5;
if(Out5 == 0) {
if(t == 0 && c == 0) {
if(In3[t] == 1) {
if(In2[t] > 5) {
Out2 = In2[t] - 5;
Out3 = In3[t];
}
else {
Out2 = 0;
Out3 = In3[t];
}
}
else {
if(MOVE * (In3[t] - 1) > In2[t] - 5) {
Out2 = MOVE * (In3[t] - 1);
Out3 = In3[t];
}
else {
Out2 = In2[t] - 5;
Out3 = In3[t];
}
}
}
else{
Out2 += MOVE * abs(In3[t + 1] - In4[t]);
Out3 = In3[t + 1];
}
}
else {
Out2 += MOVE * abs(In4[t] - In3[t]);
Out3 = In4[t];
}
}
Out1 = Out1;
// 出力
printf("%d,%d,%d,%c,%d,%d,%d,%d,%d\n", Out1, Out2, Out3, Out4, Out5, Out6, Out7, Out8, Out9);
fprintf(fout, "%d,%d,%d,%c,%d,%d,%d,%d,%d\n", Out1, Out2, Out3, Out4, Out5, Out6, Out7, Out8, Out9);
}
fclose(fin);
fclose(fout);
return 0;
}結果i)
実行すると利用者の乗降履歴とエレベータの動作履歴が出力されます。
$./elevator1
1,221,3,B,0,0,0,0,0
1,226,3,E,1,0,0,0,0
1,228,4,B,1,0,0,0,0
1,233,4,E,0,0,0,0,0
1,237,2,B,0,0,0,0,0
1,263,2,E,2,0,0,0,0
1,265,3,B,2,0,0,0,0
1,270,3,E,0,0,0,0,0
1,274,1,B,0,0,0,0,0
1,282,1,E,3,0,0,0,0
1,296,8,B,3,0,0,0,0
1,301,8,E,0,0,0,0,0
1,307,5,B,0,0,0,0,0
1,466,5,E,4,0,0,0,0
1,470,3,B,4,0,0,0,0
1,475,3,E,0,0,0,0,0
1,489,10,B,0,0,0,0,0
1,499,10,E,5,0,0,0,0
1,507,6,B,5,0,0,0,0
1,512,6,E,0,0,0,0,0
1,514,7,B,0,0,0,0,0
1,544,7,E,6,0,0,0,0
1,556,1,B,6,0,0,0,0
1,593,1,E,7,0,0,0,0
1,611,10,B,7,0,0,0,0
1,663,10,E,8,0,0,0,0
1,679,2,B,8,0,0,0,0
1,684,2,E,0,0,0,0,0
1,686,3,B,0,0,0,0,0
1,691,3,E,9,0,0,0,0
1,695,5,B,9,0,0,0,0
1,700,5,E,0,0,0,0,0
1,702,4,B,0,0,0,0,0
1,803,4,E,10,0,0,0,0
1,813,9,B,10,0,0,0,0
1,818,9,E,0,0,0,0,0
1,836,0,B,0,0,0,0,0
問題ii)
任意の入力データと出力データを読み込み、全ての申告が正しく満たされたこと、前述の動作制約を守ってエレベータが動作していることを確認するプログラムを作成してください。
また、希望乗車時刻から降車時刻までに掛かった全申告の時間を合計して出力してください。
プログラムの入力形式・出力形式は自由とします。
回答ii)
確認する項目をを分かりやすく捉えるために、以下の2つのチェックに分けて行なっています。
- 全ての申告が正しく満たされているかの確認
入力データを上から走査していき、出力データのOut4がEの場合で識別番号が希望乗車時刻In2以降に申告した階で乗車したかを確認する。次に、それ以降で出力データのOut4がBで該当する識別番号が申告した階で降車したかを確認する。両方を満たした時に限り、Out2-In2を計算して今までの合計に加算していく。
- 動作制約を守ってエレベータが動作しているかの確認
出力データを上から走査していき、Out4がEからBになっている場合には、現在の動作時刻+2*移動階数と希望乗車時刻との大小関係によりOut2が正しく変更されているかを確認する。また、Out4がBからEになっている場合には、現在の動作時刻+5と希望乗車時刻との大小関係によりOut2が正しく変更されているかを確認する。
この2つのチェック中にどちらかが満たされなくなると、システムがエラーをはくようになっています。
またエラーがない時の最終的な結果は、希望乗車時刻から実際の降車時刻までに掛かった全申告時間を出力するようになっています。
#include <cstdio>
#include <cstdlib>
const int MAX_N = 100; // 利用者数
const int MAX_H = MAX_N * 4 + 1; // 履歴数
const int MOVE = 2; // 移動時間
// 入力
int In1[MAX_N + 1]; // 入力データの識別番号
int In2[MAX_N + 1]; // 申告者の乗車希望時刻(開始してからの経過秒数)
int In3[MAX_N + 1]; // 申告者が乗車する階
int In4[MAX_N + 1]; // 申告者が降車する階
// 出力
int Out1[MAX_H]; // エレベータの識別番号(1)
int Out2[MAX_H]; // エレベータの動作時刻(開始してからの経過秒数)
int Out3[MAX_H]; // エレベータが動作した階
char Out4[MAX_H]; // エレベータの動作
int Out5[MAX_H]; // 入力データの識別番号1
int Out6[MAX_H]; // 入力データの識別番号2
int Out7[MAX_H]; // 入力データの識別番号3
int Out8[MAX_H]; // 入力データの識別番号4
int Out9[MAX_H]; // 入力データの識別番号5
int main(int argc, char *argv[]) {
FILE *fin1, *fin2;
if(argc != 3) {
printf("Usage: %s input_file ouput_file\n", argv[0]);
exit(1);
}
if((fin1 = fopen(argv[1], "r")) == NULL) {
printf("input_i.txt do not exist!\n");
exit(1);
}
if((fin2 = fopen(argv[2], "r")) == NULL) {
printf("output_i.txt do not exist!\n");
exit(1);
}
// ファイル入力より入力
int n = 0;
while(fscanf(fin1, "%d,%d,%d,%d\n", &In1[n], &In2[n], &In3[n], &In4[n]) != EOF) {
n++;
}
int h = 0;
while(fscanf(fin2, "%d,%d,%d,%c,%d,%d,%d,%d,%d\n", &Out1[h], &Out2[h], &Out3[h], &Out4[h], &Out5[h], &Out6[h], &Out7[h], &Out8[h], &Out9[h]) != EOF) {
h++;
}
//printf("n = %d, h = %d\n", n, h);
int c1 = 0;
int sum = 0;
// 入力データ
for(int i = 0; i < n; i++) {
for(int j = 0; j < h; j++) {
if(Out2[j] >= In2[i] &&
Out3[j] == In3[i] &&
Out4[j] == 'E' &&
(Out5[j] == In1[i] || Out6[j] == In1[i] || Out7[j] == In1[i] || Out8[j] == In1[i] || Out9[j] == In1[i])) {
for(int k = j + 1; k < h; k++) {
if(Out2[k] > Out2[j] &&
Out3[k] == In4[i] &&
Out4[k] == 'B' &&
(Out5[k] == In1[i] || Out6[k] == In1[i] || Out7[k] == In1[i] || Out8[k] == In1[i] || Out9[k] == In1[i])) {
c1++;
sum += Out2[k] - In2[i];
}
}
}
}
}
if(c1 != n) {
printf("user declaration error!\n");
exit(1);
}
int c2 = 0;
// 出力データ
for(int i = 0; i < h; i++) {
if(Out4[i - 1] == 'E') {
if(i == 0) {
if(Out2[i] >= 2 * Out3[i] &&
Out3[i] <= 10 &&
Out4[i] == 'B') {
c2++;
}
else {
printf("elevator's motion restriction error!\n");
exit(1);
}
}
else {
if(Out1[i] == Out1[i - 1] &&
Out2[i] == Out2[i - 1] + 2 * abs(Out3[i] - Out3[i - 1]) &&
Out3[i] <= 10 &&
Out4[i] == 'B') {
c2++;
}
else {
printf("elevator's motion restriction error!\n");
exit(1);
}
}
}
else if(Out4[i - 1] == 'B') {
if(Out1[i] == Out1[i - 1] &&
Out2[i] >= Out2[i - 1] + 5 &&
Out3[i] <= 10 &&
Out4[i] == 'E') {
c2++;
}
else {
printf("elevator's motion restriction error!\n");
exit(1);
}
}
}
printf("sum = %d\n", sum);
fclose(fin1);
fclose(fin2);
return 0;
}結果ii)
実行方法は対応関係のある入力ファイルと出力ファイルを続けて入力します。
希望乗車時刻から降車時刻までに掛かった全申告の時間を合計が出力されます。
$./elevator2 input_i.txt output_i.txt
sum = 103 (エラーなし)
問題iii)
エレベータを1台、最大乗車人数を5人とします。
希望乗車時刻から降車時刻までに掛かった全申告の時間の合計ができるだけ小さくなるようなプログラムを作成してください。
回答iii)
おそらく、本来ならA*とかダイクストラ法とかを使って最小解を見つけるのでしょうが、半日考えても問題の当てはめ方が分からなかったので、ここでは愚直な方法で解いてしまっています(汗)
ちゃんとした回答を知りたい人は、同じように問題を解いて回答をアップしてあるブログを参考にするといいと思います…
やってることを簡単に説明すると、基本的に問題ii)のアルゴリズムにエレベータに最大5人まで乗せて利用者を効率的に運べるように改良したもので、時間順にソートした時に同じ階数から乗車する人が連続していれば後ろの人の希望乗車時刻まで待って一緒に乗ってそれぞれ目的の降車階数で降ろすような工夫をしています。
#include <cstdio>
#include <cstdlib>
const int MAX_N = 100; // 利用者数
const int MOVE = 2; // 移動時間
// 入力
int In1[MAX_N + 1]; // 入力データの識別番号
int In2[MAX_N + 1]; // 申告者の乗車希望時刻(開始してからの経過秒数)
int In3[MAX_N + 1]; // 申告者が乗車する階
int In4[MAX_N + 1]; // 申告者が降車する階
// 出力
int Out1 = 1; // エレベータの識別番号(1)
int Out2 = 0; // エレベータの動作時刻(開始してからの経過秒数)
int Out3 = 1; // エレベータが動作した階
char Out4 = 'E'; // エレベータの動作
int Out[5] = {0, 0, 0, 0, 0}; // 入力データの識別番号
int main() {
FILE *fin, *fout;
fin = fopen("input_i3.txt", "r");
fout = fopen("output_i3.txt", "w");
// ファイル入力より入力
for(int i = 0; i < MAX_N; i++)
fscanf(fin, "%d,%d,%d,%d\n", &In1[i], &In2[i], &In3[i], &In4[i]);
// for(int i = 0; i < MAX_N; i++)
// printf("%d %d %d %d\n", In1[i], In2[i], In3[i], In4[i]);
int t = 0, c = 0;
int tt;
int flg;
while(1) {
// 開くと閉じるを交互に行う
if(Out4 == 'B') {
Out3 = Out3;
Out4 = 'E';
if(flg == 0) {
int j = 0;
while(1) {
if(c == 0) t = -1;
if(In3[t + 1 + j] == Out3) {
for(int k = 0; k < 5; k++) {
if(Out[k] == 0) {
Out[k] = In1[t + 1 + j];
break;
}
}
j++;
}
else {
if(c != 0) {
t += j;
}
else {
t = 0;
c++;
}
if(Out2 + 5 > In2[t])
Out2 += 5; // 閉時間
else
Out2 = In2[t]; // 次の希望乗車時刻
break;
}
}
if(t > MAX_N - 1) break;
}
else {
for(int k = 0; k < 5; k++) {
if(In4[Out[k] - 1] == Out3)
Out[k] = 0;
}
if(Out[0] == 0 &&
Out[1] == 0 &&
Out[2] == 0 &&
Out[3] == 0 &&
Out[4] == 0) {
flg = 0;
}
if(flg == 0) {
int j = 0;
while(1) {
if(c == 0) t = -1;
if(In3[t + 1 + j] == Out3) {
for(int k = 0; k < 5; k++) {
if(Out[k] == 0) {
Out[k] = In1[t + 1 + j];
break;
}
}
j++;
}
else {
if(j == 0) {
Out2 += 5;
}
else {
if(c != 0) {
t += j;
}
else {
t = 0;
c++;
}
if(Out2 + 5 > In2[t])
Out2 += 5; // 閉時間
else
Out2 = In2[t]; // 次の希望乗車時刻
}
break;
}
}
if(t > MAX_N - 1) break;
}
else {
Out2 += 5;
}
}
}
else if(Out4 == 'E') {
Out4 = 'B';
for(int i = 0; i < 5; i++)
Out[i] = Out[i];
if(t == 0 && c == 0) {
flg = 0;
if(In3[t] == 1) {
if(In2[t] > 5) {
Out2 = In2[t] - 5;
Out3 = In3[t];
}
else {
Out2 = 0;
Out3 = In3[t];
}
}
else {
if(MOVE * (In3[t] - 1) > In2[t] - 5) {
Out2 = MOVE * (In3[t] - 1);
Out3 = In3[t];
}
else {
Out2 = In2[t] - 5;
Out3 = In3[t];
}
}
}
else{
if(Out[0] == 0 &&
Out[1] == 0 &&
Out[2] == 0 &&
Out[3] == 0 &&
Out[4] == 0) {
flg = 0;
// 他に目的の移動場所がなければ次の識別番号に移動する
Out2 += MOVE * abs(In3[t + 1] - Out3);
Out3 = In3[t + 1];
}
else {
flg = 1;
// 現在の階数から近い目的階数に移動する
int min = 10;
for(int i = 0; i < 5; i++) {
if(Out[i] != 0) {
if(abs(In4[Out[i] - 1] - Out3) < min) {
tt = Out[i] - 1;
min = abs(In4[tt] - Out3);
}
}
}
Out2 += MOVE * min;
Out3 = In4[tt];
}
}
}
Out1 = Out1;
// 出力
printf("%d,%d,%d,%c,%d,%d,%d,%d,%d\n", Out1, Out2, Out3, Out4, Out[0], Out[1], Out[2], Out[3], Out[4]);
fprintf(fout, "%d,%d,%d,%c,%d,%d,%d,%d,%d\n", Out1, Out2, Out3, Out4, Out[0], Out[1], Out[2], Out[3], Out[4]);
}
fclose(fin);
fclose(fout);
return 0;
}結果iii)
実行すると利用者の乗降履歴とエレベータの動作履歴が出力されます。
問題iii)の方法で行うと、問題i)の場合と比較して、全申告の合計時間がだいぶ小さくなっている事が分かります。このことから乗車階数の同じ利用者を同時に運ぶことの有効性が見て分かります。
ただし、まだまだ改善できる部分はあり、これが最小の合計時間という訳ではありません。
$./elevator3
長くなるので結果は省略します…・問題i)の場合の全申告の合計時間
$./elevator2 input_i3.txt output_i1.txt
sum = 71321 (エラーなし)・問題iii)の場合の全申告の合計時間
$./elevator2 input_i3.txt output_i3.txt
sum = 65193 (エラーなし)
問題iv)
エレベータを2台、 最大乗車人数を5人とします。
希望乗車時刻から降車時刻までに掛かった全申告の時間の合計ができるだけ小さくなるようなプログラムを作成してください。
回答iv)
時間がなくて解けませんでした…(汗)
