SRM479

TopCoder

とりあえず定期的に書けるネタとしてTopCoderのSRMとかCodeforcesの記録と反省でも書いていこうかと。
というわけでSRM479も参加してました。
Div.1でEASYだけ解いて123.85点。
Challengeは突けるところを見つけたもののデータ入力に手間取ってる間に先を越されて結局実行できず。
レーティングは1381から1489に上昇。Challengeできてたら1500超えてたかもしれないと考えるとちょっと悔しいところ。

Div.1 Easy - The Coffee Time

一列に並んだ乗客にコーヒーまたはお茶を提供するとき、乗客全員に提供するまでに要する時間を計算するという問題。入力は、nが乗客数、teaがお茶を提供すべき人の座席番号。
それぞれの動作に要する時間は以下のとおり。

動作 コスト(秒)
現在いる席に隣接する席への移動 1
乗客のカップへ瓶から飲み物をそそぐ 4
瓶に飲み物を補充する 47

その他の事項は以下のような感じ。

  • 飲み物の補充はコーヒーメーカーがあるところ(1番目の席のひとつ前、0番目の席に当たる位置)でしかできない。
  • 瓶には最大で7人分しか飲み物を入れることはできない。
  • お茶とコーヒーの補充を並行することはできない。

お茶を持ち運ぶ場合とコーヒーを持ち運ぶ場合のどちらも同じ考え方で時間を求め、それぞれの提供にかかる時間の和が解になります。
必ず7人分準備するようにして最後尾の席から順にそそぎ、手元の飲み物が切れたら7人分補充して次にそそぐべき人のところへ行って続けるようにすれば最短時間が求まります。先頭から順にやっていくと補充が必要かつ必要とする人の数が7の倍数でないときに最短ではなくなるので注意 (Example 2)。

#include <vector>
#include <algorithm>

using namespace std;

class TheCoffeeTimeDivOne {
public:
    long long find(int n, vector<int> tea){
        long long answer = 0;
        // まずは入力をソート
        sort(tea.begin(), tea.end());
        // 瓶から乗客のカップへ移すのにかかる時間の合計
        answer += 4 * n;
        // お茶とコーヒーの補充にかかる時間
        answer += 47 * ((tea.size() + 6) / 7);
        answer += 47 * ((n - tea.size() + 6) / 7);
        // 移動にかかった時間(お茶の場合)
        for(int i = tea.size() - 1; i >= 0; i -= 7){
            answer += tea[i] * 2;
        }
        // 移動にかかった時間(コーヒーの場合)
        for(int i = n, j = tea.size() - 1, rem = 0; i > 0; i--){
            if(j >= 0 && i == tea[j]){
                // すでにお茶を配っているのでスキップ
                j--;
                continue;
            }
            if(rem == 0){
                // 補充のための往復が必要な地点
                answer += i * 2;
                rem = 7;
            }
            rem--;
        }
        return answer;
    }
};

Div.1 Medium - The Air Trip

n個の都市があり、その都市間に飛行機が運行している。それぞれの航路について、最初の飛行機の出発時刻とそれ以降の出発間隔、目的地に着くまでの時間が与えられたとき、指定された時間内に都市1から都市nへ移動する経路のうち、各都市で乗り換えに使用できる時間の中で一番短いものができるだけ長くなるようなルートを選択した場合の、乗り換えにかけられる時間が一番短い箇所の長さを求める。また、目的地まで時間内に移動できない場合は-1を返す。

まだ解けてません。忘れないうちに問題を書き留めておくだけです。

Div.1. Hard - The Boarding

なんとなく開いてみたものの結局読んですらいません。正答者0人って。