Hatena::Grouptopcoder

cou929のTopCoder日記

2009-09-14

2004 TCCC Online Round 1

18:18

Dynamic Programming: From novice to advancedからの練習問題。

Medium - FlowerGarden

何種類かの花があり、それぞれの高さ(全てちがう値)、咲きはじめる日、枯れる日が与えられる。これらの花を、できるだけ高さの高いものを前、ただし咲く時期がかぶっていたら小さい順、というルールで並べる。

まずstateはi種類の花を適切に並べた状態。これに一本ずつ花を追加していけば良い。

問題は追加の仕方。場合分けがごちゃごちゃして、デバッグにものすごく時間がかかり、しかもまだシステムテストは通っていません。疲れた。

また、なぜかアリーナのアプレットからプラクティスルームに入ることができません。仕方ないからテストケースをサイトから落としてきて、自分でテストを書きました。

class FlowerGarden {
public:
  vector <int> b;
  vector <int> w;

  bool termCheck(int i, int j)
  {
    bool ret = false;

    if ((b[i] <= b[j] && b[j] <= w[i]) ||
	(b[i] <= w[j] && w[j] <= w[i]) ||
	(b[j] <= b[i] && b[i] <= w[j]) ||
	(b[j] <= w[i] && w[i] <= w[j]) )
      ret = true;

    return ret;
  }

  vector <int> getOrdering(vector <int> height, vector <int> bloom, vector <int> wilt)
  {
    vector <int> ret;
    vector <int> indices;
    b = bloom;
    w = wilt;

    for (int i=0; i<height.size(); i++)
      {
	vector <bool> isSameTerm;
	bool allWrongTerm = true;
	for (int j=0; j<indices.size(); j++)
	  {
	    isSameTerm.push_back(termCheck(i, indices[j]));
	    if (!termCheck(i, indices[j]))
	      allWrongTerm = false;
	  }

	int pos1 = -1, pos2 = -1, pos = 0;

	for (int j=0; j<indices.size(); j++)
	  {
	    if (isSameTerm[j])
	      if (pos1 == -1 && height[i] < height[indices[j]])
		pos1 = j;

	    if (!isSameTerm[j])
	      if (pos2 == -1 && height[i] > height[indices[j]])
		pos2 = j;
	  }

	if (pos1 == -1)
	  if (!allWrongTerm)
	    {
	      for (int j=isSameTerm.size()-1; j>=0; j--)
		if (isSameTerm[j])
		  {
		    pos1 = j+1;
		    break;
		  }
	    }

	if (pos2 == -1)
	  pos2 = indices.size();

	if (pos1 != -1)
	  pos = pos1;
	else
	  pos = pos2;


	if (indices.empty())
	  indices.push_back(i);
	else
	  indices.insert(indices.begin()+pos, i);
      }

    for (int i=0; i<indices.size(); i++)
      ret.push_back(height[indices[i]]);

    return ret;
  }
};