Hatena::Grouptopcoder

cou929のTopCoder日記

2009-11-25

SRM453.5 div2

03:44

easy, mediumが解けて,ratingは 1101 -> 1152 (+51).今回は実力通りの結果が出たと思います.div1へ行くにはもう少し実力アップが必要そうです.

Easy - ToolsBox

いくつかの文章が与えられるので,出現する単語数を答える.

以前作っておいたsplit()関数とstd::setを使うだけです.

class ToolsBox {
vector <string> splits(const string _s, const string del)
{
  vector <string> ret;
  string s = _s;

  while (!s.empty())
    {
      size_t pos = s.find(del);
      string sub = "";
      sub = s.substr(0, pos);
      ret.push_back(sub);
      if (pos != string::npos)
        pos += del.size();
      s.erase(0, pos);
    }

  return ret;
}

public:
  int countTools(vector <string> need)
  {
    set <string> s;

    for (int i=0; i<need.size(); i++)
      {
        vector <string> v = splits(need[i], " ");
        for (int j=0; j<v.size(); j++)
          s.insert(v[j]);
      }

    return s.size();
  }
};

Medium - MazeMaker

グリッド上の迷路,スタート地点,プレイヤー(Jumping Jim)の動ける方向が与えられる.あなたは好きな場所を迷路のゴールとできる.Jimがゴールするまでに,できるだけ多くのステップが必要になるように,またはJimがゴールできないように,迷路のゴール位置を設定する.ただしJimは常に最適な移動をする.

スタート地点からBFSを行い,迷路上の各セルまで最短何ステップで到達できるかを求めます.到達できないセルがある場合は-1を,そうでない場合は,求めた中から最も大きい数値を返します.

class MazeMaker {
public:
  int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol)
  {
    int visited[maze.size()][maze[0].size()];
    memset(visited, -1, sizeof(visited));
    queue <pair <int, pair <int, int> > > q;
    q.push(make_pair(0, make_pair(startRow, startCol)));
    visited[startRow][startCol] = 0;

    while (!q.empty())
      {
        pair <int, pair <int, int> > cur = q.front();
        q.pop();

        for (int i=0; i<moveRow.size(); i++)
          {
            int row = cur.second.first + moveRow[i];
            int col = cur.second.second + moveCol[i];
            int point = cur.first+1;

            if (0 <= row && row < maze.size() && 0 <= col && col < maze[0].size())
              if (maze[row][col] == '.')
                {
                  if (visited[row][col] == -1)
                    {
                      q.push(make_pair(point, make_pair(row, col)));
                      visited[row][col] = point;
                    }
                  else
                    visited[row][col] = min(point, visited[row][col]);
                }
          }
      }

    int ret = 0;
    for (int i=0; i<maze.size(); i++)
      for (int j=0; j<maze[0].size(); j++)
        if (visited[i][j] == -1 && maze[i][j] != 'X')
          return -1;
        else
          ret = max(ret, visited[i][j]);

    return ret;
  }
};

Hard - TheProduct

数列numbersと,整数k, maxDistが与えられる.numbersから,k個の要素を取り出して,すべての値を掛け合わせる.ただし,隣り合う要素間はmaxDist以下でなければならない.この計算結果のうち,最大値を求めよ.

とてもdpっぽい問題なのですが,良い解法が思いつかなかったので,再帰でDFS風に全探索するコードを書いてみました.が,当然,numbersのサイズが50でk=50, maxDIst=50のようなケースでTLEでした.結局submitせずに時間切れ.以下がそのコードです.

class TheProduct {
public:
  long long ret;
  vector <int> numbers;
  int k;
  int maxDist;

  int r(int pos, int num, long long score)
  {
    if (num == k)
      {
        ret = max(ret, score);
      }
    else
      {
        int lim = min(pos+maxDist-1, (int)numbers.size() - k + num);

        for (int i=pos; i<=lim; i++)
          {
            r(i+1, num+1, score*numbers[i]);
          }
      }
    
    return 0;
  }

  long long maxProduct(vector <int> _numbers, int _k, int _maxDist)
  {
    ret = LLONG_MIN;
    numbers = _numbers;
    k = _k;
    maxDist = _maxDist;

    r(0, 0, 1);

    return ret;
  }
};

challenge phase

特に動きのないチャレンジフェイズでした.挑戦も防衛も0です.

system test

無事両方通りました.

result

部屋では4位,div2で87位,ratingは1101->1152 (+51).実力的には妥当な結果だったと思います.