SRM 146 Div2

250:
問題概要：略
解法：
ソートしてtoss[i]*(toss[i]と同じ値の数)の最大値をリターンする

コード：

class YahtzeeScore {
	public:
	int maxPoints(vector <int> toss) {
	  vector<int> nes;
	  nes.push_back(0);
	  int now = toss[0];
	  sort(all(toss));
	  for(int i=0;i<toss.size();i++)
	    {
	      if(now == toss[i])
		nes.back() += now;
	      else 
		{
		  now = toss[i];
		  nes.push_back(now);
		}
	    }
	  sort(all(nes));
	  return nes.back();
	}
};

500:
問題概要：
width*heightのグリッドが与えられる
その中で長方形はいくつ作れるか？

解法：
for i 1..height
for j 1..width
if i != j
cnt += (width-j+1)*(h-i+1)

としてカウントする

コード：

class RectangularGrid {
	public:
	long long countRectangles(int width, int height) {
	  long long ret = 0;
	  int h = height;
	  int w = width;
	  for(int i=1;i<=h;i++)
	    {
	      for(int j=1;j<=w;j++)
		{
		  if(i == j)
		    continue;
		  ret += (w-j+1)*(h-i+1);
		}
	    }	
	  return ret;
	}
};

1000:
問題概要：
n人の人とライトが１つある
n人の人はそれぞれ決まった時間で橋をわたる
橋は最大で2人まで同時に渡れるが、そのうち一人はかならずライトを持っていないといけない
全員を橋の向こう側につれていくためにかかる最小の時間をリターンせよ

解法：
1.速い人2人が先に橋をわたり、わたった先で最も速い人に折り返してもらい、最も遅い人とその次に遅い人がわたった後2番めに速い人が折り返す
2.最も速い人と最も遅い人で橋をわたり、速い人が折り返した後また次に遅い人をつれて橋をわたってもらい再度最もはやい人が折り返す

1と2で時間のかからない方を選択して全員が渡りきるまで繰り返す
人が３人以下になった場合には特別に処理が必要

コード：

class BridgeCrossing {
	public:
	int minTime(vector <int> times) {
	  if(times.size() == 1)
	    return times[0];
	  else if(times.size() == 2)
	    return max(times[0],times[1]);
	
	  sort(all(times));
	  deque<int> deq;
	  deq.resize(times.size());
	  for(int i=0;i<times.size();i++)
	    deq[i] = times[i];
	  int one = deq[0];
	  int two = deq[1];
	  deq.pop_front();
	  deq.pop_front();
	  int cost = 0;
	  while(!deq.empty())
	    {
	      if(deq.size() <= 1)
		{
		  cost += one;
		  cost += deq.back();
		  deq.pop_back();
		  continue;
		}

	      int rone = deq[deq.size()-1];
	      int rtwo = deq[deq.size()-2];
	      deq.pop_back(),deq.pop_back();

	      if(one+two*2+rone <= rone+rtwo+one*2)
		cost += one+two*2+rone;
	      else 
		cost += rone+rtwo+one*2;
		

	    }
	  cost += two;
	  return cost;
	}
};