SRM 479 250pt: TheCoffeeTimeDivOne

TopCoder

問題概要

0,1,...,N(N<4*10^7)の列がある。1..Nのマスには客がいて、そのうちいくつか(T<50個)のマスだけがお茶希望の客で、それ以外はコーヒー希望である。各客に希望の飲み物を出すには定数の時間がかかるし、7杯分しか入らないポットが空になったら0番まで補充しにいかなければならない。補充にも定数時間がかかる。全ての客に飲み物を渡すまでの時間を最小化する問題。

考えたこと

  • (本番はO(N)でTLEした記憶がある。定数倍の速度差に負けた)。
  • TLE厳しいので、本意ではないが真面目に早いのを書こう。
  • 基本的にはgreedy。後ろから7席置きに選んでいけばよい。
  • 補充や配るのにかかる時間は先に計算しておく。
  • お茶の配膳にかかる時間はすぐに求められる。
  • 問題はコーヒーの配膳にかかる時間だ。
  • まず、お茶の人をいないものとして考える。こうすると単なる公差7の等差数列の和なので計算できる。
  • 次に、各お茶の人について、コーヒーを配りにいくときに何回通りすぎたかを計算して足しあげる。
  • 後ろから数えた方がよかった。こういうのは混乱する。1回WAをもらった後AC。

practiceで通ったコード

計算量O(T*log T)。

#include <vector>
#include <algorithm>
using namespace std;

typedef long long int64;

struct TheCoffeeTimeDivOne {

	int64 find(int64 n, vector <int> tea) {

		sort(tea.rbegin(), tea.rend());
		int64 tee = tea.size(), coffee = n - tee;

		//給仕にかかる時間
		int64 ret = 4*n;

		//充填にかかる時間
		ret += 47 * ((tee + 6)/7);
		ret += 47 * ((coffee + 6)/7);

		//移動にかかる時間
		//tea
		for(int i=0; i<tee; i+=7){
			ret += tea[i]*2;
		}

		//coffee
		int64 time = (coffee+6)/7;
		ret += ((coffee%7 == 0 ? 7 : coffee%7) + coffee) * time;
		//追い越したのが何回か
		for(int i=0; i<tee; i++){
			ret += ((n - tea[i] - i + 6) / 7) * 2;
		}

		return ret;
	}

};