TopCoder, SRM 617, Division 2, Level 2 : SlimeXSlimonadeTycoon

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=11281&rd=15850

問題概要

　あるゲームに於いて、より多くのアイテムを売ることを考える。ゲーム内での一日には、以下の事象がこの順で起こる。

1. 在庫の内、stale_limit 日以上前に生産されたものを全て廃棄する
2. 現在を i 日目とすると、morning[ i ] 個以下の任意の数だけアイテムを新たに生産する
3. 現在を i 日目とすると、最大 customers[ i ] 個のアイテムを売却できる。ただし、在庫の数が costomers[ i ] 未満のときは、最大で在庫の数と同数だけ売却できる。在庫の内どのアイテムを売るかは任意に選ぶことができる。

　このゲームを最適にプレイしたとき、N 日間に売ることができるアイテムの最大数を求めよ。

解法

　まずはアイテムの生産についてですが、アイテムを廃棄してもペナルティは発生しないので、常に作れるだけ作って在庫として抱えるのが最適となります。また、アイテムを売却するときにも、売却できるだけ売却した方がスコアが良くなります。従って、残る自由度は「どのアイテムから売るか」だけになります。ですがこれも、生存期間が短いアイテムから先に捌いてしまった方が後に残せるアイテムの数が増えて得なので、より古いアイテムから売るという戦略で確定します。あとは、この手順を適切に実装できれば問題を解くことができます。
　古いものから取り出す（ FIFO ）というのはキューの特性です。生産できるアイテムの総数は制約より 50 * 10,000 = 500,000 以下なので、愚直にキューで実装しても間に合います。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class SlimeXSlimonadeTycoon
{
public:
	int sell( vector <int> morning, vector <int> customers, int stale_limit )
	{
		 const int N = morning.size();

		 int res = 0;
		 queue<int> que;
		 REP( t, 0, N )
		 {
			 REP( i, 0, morning[t] )
			 {
				 que.push( t );
			 }

			 while ( !que.empty() && stale_limit <= t - que.front() )
			 {
				 que.pop();
			 }
			
			 const int tmp = min<int>( customers[t], que.size() );
			 res += tmp;
			 REP( i, 0, tmp )
			 {
				 que.pop();
			 }
		 }

		 return res;
	}
};