SONY GOF FOR IT ~5問目: 申告制エレベータ~
概要
GO FOR ITの第5問に挑んだ.
コード (Python)
とても長くなってしまったので、レポジトリを見てもらえればと思います。
http://code.google.com/p/k-koshikawa/source/browse/trunk/ProgrammingContest/2012/SONY_GoForIt_2012/5/solve.py
※ このソースコードのライセンスは特にありません。自由に使っていただいて構いません。
コードの説明
以下を参照していただければと思います。
http://code.google.com/p/k-koshikawa/source/browse/trunk/ProgrammingContest/2012/SONY_GoForIt_2012/5/README
感想
問題の中で一番時間をかけた問題だったが、完敗でした。
実装力,アルゴリズム力共に力不足を感じられた。出直してきます。
でも、おかげさまでとても楽しい時間を過ごすことが出来ました。SONYさんありがとうございました。
問題引用
5) 申告制エレベータ
エレベータの待ち時間でイライラしたことはないでしょうか。
利用者の生活リズムが事前に把握できるのであればもっと最適化ができそうです。
そこで完全申告制のエレベータを考えてみましょう。10F建てのオフィスビルがあります。
事前に全ての利用者から申告を受けています。
エレベータが最適に動作するアルゴリズムを考えてみましょう。エレベータには下記の制約があります。
・エレベータが1つの階を移動するのに掛かる時間は2秒です。
・一旦、エレベータの扉が開くと、閉まるまでに最低でも5秒掛かります。
※扉の開閉時間は、この5秒に含まれているものとします。
・エレベータの初期状態は1Fで扉が閉まっています。エレベータの入力データと出力データのフォーマットは決まっています。
下記ファイルを参照して下さい。
i)エレベータを1台、最大乗車人数を1人とします。
単純に入力データの識別番号順に、利用者を運ぶプログラムを作成してください。
入力データは下記ファイルとします。
ii)任意の入力データと出力データを読み込み、全ての申告が正しく満たされたこと、前述の動作制約を守ってエレベータが動作していることを確認するプログラムを作成してください。
また、希望乗車時刻から降車時刻までに掛かった全申告の時間を合計して出力してください。
プログラムの入力形式・出力形式は自由とします。iii)エレベータを1台、最大乗車人数を5人とします。
希望乗車時刻から降車時刻までに掛かった全申告の時間の合計ができるだけ小さくなるようなプログラムを作成してください。
入力データは下記ファイルとします。
iv)エレベータを2台、 最大乗車人数を5人とします。
http://www.sony.co.jp/SonyInfo/Jobs/newgrads/sus/q05.html
希望乗車時刻から降車時刻までに掛かった全申告の時間の合計ができるだけ小さくなるようなプログラムを作成してください。
入力データは下記ファイルとします。
