Hatena::Grouptopcoder

cou929のTopCoder日記

2009-05-02SRM438 div2(過去問)

Easy - OptimalList

格子状の地図上で、行き先が与えられている。行き先は、"EENWWSNS"といったように、四つの方向NSEWの組み合わせによって与えられている。また、各NSEW命令は、1命令で1単位の距離を進む。ここで、与えられた行き先への行き方は、必ずしも最短ではない。最短の行き方を求めよ。ただし、複数のルートがある場合は、辞書順で最も若いものを返せ。

戦略:位置を二次元座標(x, y)と表現する。各命令について、この座標の値を増減するように定義する(たとえば、Eだと(x+1, y+0)といった具合)。初期位置を(0, 0)とし、目的地の座標を求める。目的地の位置に応じて命令を生成し、ソートする。

最近覚えたコンテナpairを、位置の座標を表現するのにつかってみました。

  string optimize(string inst)
  {
    pair <int, int> cur(0, 0);
    string ret = "";

    for (int i=0; i<inst.size(); i++)
      {
	if (inst[i] == 'N')
	  cur.second++;
	else if (inst[i] == 'S')
	  cur.second--;
	else if (inst[i] == 'E')
	  cur.first++;
	else if (inst[i] == 'W')
	  cur.first--;
      }

    if (cur.first > 0)
      for (int i=0; i<cur.first; i++)
	ret += 'E';
    else if (cur.first < 0)
      for (int i=0; i<abs(cur.first); i++)
	ret += 'W';

    if (cur.second > 0)
      for (int i=0; i<cur.second; i++)
	ret += 'N';
    else if (cur.second < 0)
      for (int i=0; i<abs(cur.second); i++)
	ret += 'S';

    sort(ret.begin(), ret.end());

    return ret;
  }

Medium - LostParentheses

正の整数と、演算子+または-からなる文字列が与えられる。この式に、計算結果が最小になるように括弧付けを行い、その値を返す。

典型的なDPの問題のような気がしたのですが、解説記事によると、次の簡単な戦略で解けるそうです。

式を先頭から走査し、はじめに-が現れるまで数字を足していく。はじめの-が現れたあとは、演算子に関係なく毎回結果から引いていく。

DPの考え方にまだなれていないので、とりあえずこの戦略を実装してみました。

  int minResult(string e)
  {
    int ret = 0;
    vector <int> vals;
    vector <int> ops;

    e += 'E';

    while (!e.empty())
      {
	string s;
	int n;
	int pos;
	for (int i=0; i<e.size(); i++)
	  {
	    pos = i;
	    if (e[i] == '+')
	      {
		ops.push_back(1);
		break;
	      }
	    else if (e[i] == '-')
	      {
		ops.push_back(-1);
		break;
	      }
	    else if (e[i] == 'E')
	      {
		break;
	      }
	  }

	s = e.substr(0, pos);
	sscanf(s.c_str(), "%d", &n);
	vals.push_back(n);

	e.erase(0, pos+1);
      }

    bool appeared = false;
    ret = vals[0];
    for (int i=1; i<vals.size(); i++)
      {
	if (!appeared && ops[i-1] == -1)
	  appeared = true;

	if (appeared)
	  ret -= vals[i];
	else
	  ret += vals[i];
      }

    return ret;
  }