Hatena::Grouptopcoder

cou929のTopCoder日記

2009-11-26

SRM453.5 div2 (再チャレンジ)

16:44

Hard - TheProduct

dynamic programming で解きます.kの値を1からひとつずつ増やしていくというアプローチをとります.二次元配列dpを作り,dp[i][j]にnumbers[j]よりも右側の要素から,i個取り出したときの最適解を保存するようにします.最終的にdp[k][i] (iは 0-numbers.size()) のうち最大値が解です.ただし今回の場合は,numbersの要素が負の値をとりうるので,負の値同士の乗算が奇数回起こった場合に,最適でない答えが出てしまいます.よって二次元配列を二つ作り,それぞれ最大値・最小値を保存するようにします.

class TheProduct {
public:
  long long maxProduct(vector <int> numbers, int K, int maxDist) {
    long long dpmax[11][51];
    long long dpmin[11][51];
    
    for (int i=0; i<11; i++)
      for (int j=0; j<51; j++)
        {
          dpmax[i][j] = LLONG_MIN;
          dpmin[i][j] = LLONG_MAX;
        }

    for (int i=0; i<numbers.size(); i++)
      dpmax[1][i] = dpmin[1][i] = numbers[i];

    for (int k=2; k<=K; k++)
      for (int i=0; i<numbers.size(); i++)
        for (int j=0; j<i; j++)
          if (i - j <= maxDist && dpmax[k-1][i] != LLONG_MIN)
            {
              dpmax[k][j] = max(dpmax[k][j], max(numbers[j] * dpmax[k-1][i], numbers[j] * dpmin[k-1][i]));
              dpmin[k][j] = min(dpmin[k][j], min(numbers[j] * dpmax[k-1][i], numbers[j] * dpmin[k-1][i]));
            }

    long long ret = LLONG_MIN;
    for (int i=0; i<numbers.size(); i++)
      ret = max(ret, dpmax[K][i]);

    return ret;
  }
};

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).実力的には妥当な結果だったと思います.

2009-11-21

SRM453 div2

09:47

前回のsrmは,tcのサーバがダウンしノーコンテストになりました.本番中は重すぎて250しか開けなかったので,あとでpractice roomでやった記録です.

Easy - TheTournamentDivTwo

勝ち点が,勝つと2点,ドローで1点,負けると0点与えられるトーナメント.各チームの勝ち点が与えられるので,最小で何回の試合が行われたかを返す.あり得ない点数の場合は-1.

はじめに全てのチームの点数を2で割り,何勝したかを調べます.勝ち点が奇数のチームは一試合ドローだったと考えられるので,カウントしておいてあとで結果に足し込みます.点数が正しいかどうかは,奇数点のチームが偶数か奇数かでわかります.

class TheTournamentDivTwo {
public:
  int find(vector <int> points)
  {
    int ret = 0;
    int zeros = 0;

    for (int i=0; i<points.size(); i++)
      {
        ret += points[i]/2;
        zeros += points[i]%2;
      }

    if (zeros%2 == 1)
      return -1;
    else
      return ret + zeros/2;
  }
};

Medium - TheBasketballDivTwo

バスケットのトーナメント.各チーム同士はホーム・アウェイで2試合戦う.必ず勝敗がつき,ドローはなし.この条件の下で,現在の試合結果が与えられる.残りの試合結果は任意に決められると仮定したとき,優勝するチームが勝った回数の最小値を求める.

チーム数は高々5チーム.試合は勝つ・負けるの2通りしかない.ワーストケースは5チームが一度もまだ試合をしていない状態で,その場合20試合行われる.この20試合について,全ての可能性を計算した場合,2^20 = 1048576 なので,bruto-forceで行けそうです.再帰を使って全ての状態を探索しました.

vector <string> tbl;
int ret;
int cc = 0;

int r(int x, int y)
{
  if (x == (int)tbl.size())
    {
      int win = 0;
      for (int i=0; i<tbl.size(); i++)
        {
          int sum = 0;
          for (int j=0; j<tbl.size(); j++)
            {
              if (tbl[i][j] == 'W')
                sum++;
              if (tbl[j][i] == 'L')
                sum++;
            }
          win = max(win, sum);
        }
      ret = min(ret, win);
    }
  else if (y == tbl.size())
    {
      r(x+1, 0);
    }
  else if (tbl[x][y] != '?')
    {
      r(x, y+1);
    }
  else
    {
      tbl[x][y] = 'W';
      r(x, y+1);
      tbl[x][y] = 'L';
      r(x, y+1);
      tbl[x][y] = '?';
    }
  cc++;
  return 0;
}

class TheBasketballDivTwo {
public:
  int find(vector <string> table)
  {
     tbl = table;
     ret = INT_MAX;

     r(0, 0);

     return ret;
  }
};

Hard - TheSoccerDivTwo

現実のサッカーリーグのように,勝つと勝ち点3,ドローで勝ち点1,負けると0というトーナメントがある.トーナメントの全ての試合が終わったあと,勝ち点に応じて順位が決まる.勝ち点がタイの場合は,インデックスが低いチームを上位とする.現在の得点(この得点はvalidであることを保証)が与えられるので,残りの試合の勝ち負けを自由に決められると仮定すると,チーム0は最大で何位になるか.

問題文が理解できませんでした.残りの試合数を何回でもできるとすると,100%チーム0が優勝ですし,テストケースから残り1節(各チーム1試合ずつ)ぽいなあと予想したんですが,問題文にそのような記述が見つけられませんでした.またあとで読み直して最チャレンジします.

2009-11-13

SRM430 div2 (過去問)

00:23

Easy - CreateGroups

あなたは塾を経営している.いくつかのクラスがあり,それぞれの参加希望者が与えられる.また全ての授業はminSize以上maxSize以下の人数しか受け入れられない.参加希望者を別のクラスへ何人移動させれば,授業を開講できるか.

面倒くさい問題でした.ごちゃごちゃしちゃっていますが,アルゴリズムは以下です.

  1. 定員オーバーしている人数と,定員を下回っている人数のそれぞれのトータルを出す.
  2. オーバーの人数とアンダーの人数(下回っているクラスの足りない人数)を比べる.
    1. オーバーしている人が多い場合,他のクラスにどれだけ空きがあるか調べる.空きが余っている人より多ければ,オーバーしている人数を返す.そうでなければ不可能なので-1を返す.
    2. アンダーしている人が多い場合,他のクラスから何人まわせるかを調べる.まわせる数が足りていればアンダー人数を,足りていなければ不可能で-1を返す.
class CreateGroups {
public:
  int minChanges(vector <int> groups, int minSize, int maxSize)
  {
    int ret = 0;
    vector <int> flgs(groups.size(), 0);
    vector <int> nums(groups.size(), 0);
    int overs = 0;
    int unders = 0;

    for (int i=0; i<groups.size(); i++)
      {
	if (groups[i] < minSize)
	  unders += minSize - groups[i];
	else if (groups[i] > maxSize)
	  overs += groups[i] - maxSize;
      }

    if (unders == overs)
      ret = overs;
    else if (unders < overs)
      {
	int capacity = 0;
	for (int i=0; i<groups.size(); i++)
	  {
	    if (groups[i] > maxSize)
	      capacity += 0;
	    else if (groups[i] < minSize)
	      capacity += maxSize - minSize;
	    else
	      capacity += maxSize - groups[i];
	  }

	if (capacity < (overs - unders))
	  ret = -1;
	else
	  ret = overs;
      }
    else if (overs < unders)
      {
	int capacity = 0;
	for (int i=0; i<groups.size(); i++)
	  {
	    if (groups[i] > maxSize)
	      capacity += maxSize - minSize;
	    else if (groups[i] < minSize)
	      capacity += 0;
	    else
	      capacity += groups[i] - minSize;
	  }

	if (capacity < (unders - overs))
	  ret = -1;
	else
	  ret = unders;
      }

    return ret;
  }
};

Medium - BitwiseEquations

xとkが与えられるので,次の式を満たすyのうち,小さい方からk番目のyをもとめよ.

x + y = x | y (|はビット演算のor)

たとえばx=10の時を考えると,yは以下のように1, 4, 5, 16, ... という系列になります.

 01010
+    1 => 1
------
  1011

 01010
+  100 => 4
------
  1110

 01010
+  101 => 5
------
  1111 

 01010
+10000 => 16
------
 11011

つまり,xを2進数表現にして,0の部分だけでkの数をカウントしていく,というイメージです.よってアルゴリズムはこうなります.

  1. x, kをそれぞれ2進数で考える.
  2. xの一桁目を調べる.
    1. 1の場合,解(2進数表現)の先頭に0を加える.
    2. 0の場合,解の先頭に,kの一桁目を加える.kを右に一桁シフト
  3. xを左に1桁シフト
  4. 以上をx, yがともに0になるまで繰り返す.

例えば,テストケース2(x=10, y=3)の場合.

  1. x=10の2進数表記は1010, y=3の2進数表記は11
  2. xの一桁目は0.解の先頭にkの一桁目である1を加え,解は現在1(1).kを右にシフトし,k=1(1).xを右にシフトし,x=5(101).
  3. xの一桁目は1.解の先頭に0を加え,解は現在1(01).xを右にシフトし,x=2(10).
  4. xの一桁目は0.解の先頭にkの一桁目である1を加え,解は現在5(101).kを右にシフトし,k=0(0).xを右にシフトし,x=1(1).
  5. xの一桁目は1.解の先頭に0を加え,解は現在5(0101).xを右にシフトし,x=0(0).

よって解は5となります.

実際にはxの一桁目が0かつkの一桁目が1のときにのみ操作をすればいいので(0のビットを先頭に立てても値はかわらないため),以下のコードはそのような実装になっています.

また,以下でコメントしてある解を作る行で,はじめ定数1にLLをつけていなかったため,計算中はint扱いとなり,オーバーフローしてしまい,一度システムテストに落ちてしまいました.

class BitwiseEquations {
public:
  long long kthPlusOrSolution(int x, int k)
  {
    long long ret = 0;
    int n = 0;

    while (x != 0 || k != 0)
      {
	if ((x & 1) == 0)
	  {
	    if ((k & 1) == 1)
	      ret = ret | (1LL << n);    // "LL"をつけ忘れてオーバーフローした
	    k = k >> 1;
	  }
	x = x >> 1;
	n++;
      }

    return ret;
  }
};

2009-11-11

SRM184 div2 (過去問)

00:15

Hard - TeamBuilder

グラフが与えられるので、他の全てのノードへ行けるノードの数と、他の全てのノードから入って来れるノードの数を求める。

Floyd-Warshallを使って、ノードのつながりを調べます。最小コストを求める訳ではないので、つながっているパスには単に1を入れていきます。また、自分から自分へのパスに1を設定するのがポイントです。

今回の問題は、tutorialでFloyd-Warshallの例題として出されていたものなので、このアルゴリズムを使う事ができたんですが、このヒントなくこの問題に取り組んでいたら、もっと力づくで長くなるコードを書いてしまって、バグを埋め込んだりして時間がかかってしまいそうです。

追記

tutorialをよく読んでみると、ワーシャルフロイドはグラフの接続性を調べるのにもよく使われるようです。推移閉包問題と呼ばれるそうです。

There are other uses for Floyd-Warshall as well; it can be used to find connectivity in a graph (known as the Transitive Closure of a graph). 

見落としていました。

class TeamBuilder {
public:
  vector <int> specialLocations(vector <string> paths)
  {
    vector <int> ret(2, 0);

    for (int i=0; i<paths.size(); i++)
      paths[i][i] = '1';

    for (int k=0; k<paths.size(); k++)
      for (int i=0; i<paths.size(); i++)
	for (int j=0; j<paths.size(); j++)
	  if (paths[i][k] == '1' && paths[k][j] == '1')
	    paths[i][j] = '1';

    for (int i=0; i<paths.size(); i++)
      {
	int row = 0, col = 0;
	for (int j=0; j<paths.size(); j++)
	  {
	    if (paths[i][j] == '1')
	      row++;
	    if (paths[j][i] == '1')
	      col++;
	  }
 
	if (row == paths.size())
	  ret[0]++;
	if (col == paths.size())
	  ret[1]++;
      }

    return ret;
  }
};

2009-11-07

SRM452 div2 再チャレンジ

02:53

Hard - HamiltonPath

id:yutoyutori さんのアドバイスを参考に組みました(ありがとうございます!)。グラフは両端点のみを保持するにし、中間ノードはブラックリストとして別のベクタで持つようにしました。また最後の階乗の計算の部分で、毎回modをとってもどうしてもintがオーバーフローしてしまうので、計算の途中経過はlong longで保持するようにしました。

グラフを操作する部分のコードがとても長くなってしまい、デバッグにも時間がかかり、とても1時間そこらじゃ終わりませんでした。ここをもっとスマートにできないか、あるいは他のもっとシンプルなアプローチがあるのか、考える必要があります。

class HamiltonPath {
public:
  vector <int> search(int x, vector <vector <int> >  & rootAndLeaf)
  {
    vector <int> ret(2, -1);

    for (int i=0; i<rootAndLeaf.size(); i++)
      for (int j=0; j<rootAndLeaf[i].size(); j++)
	if (rootAndLeaf[i][j] == x)
	  {
	    vector <int> tmp;
	    ret[0] = i;
	    ret[1] = j;
	  }

    return ret;
  }


  int countPaths(vector <string> roads)
  {
    int ret = 1;
    vector <int> intermediates;
    vector <vector <int> > rootAndLeaf;

    for (int i=0; i<roads.size(); i++)
      for (int j=i; j<roads[i].size(); j++)
	if (roads[i][j] == 'Y')
	  {
	    if (find(intermediates.begin(), intermediates.end(), i) == intermediates.end() && find(intermediates.begin(), intermediates.end(), j) == intermediates.end())
	      {
		vector <int> resi = search(i, rootAndLeaf);
		vector <int> resj = search(j, rootAndLeaf);

		if (resi[0] == -1 && resj[0] == -1)
		  {
		    vector <int> tmp;
		    tmp.push_back(i);
		    tmp.push_back(j);
		    rootAndLeaf.push_back(tmp);
		  }
		else if (resi[0] != -1 && resj[0] != -1)
		  {
		    if (resi[0] == resj[0])
		      return 0;

		    intermediates.push_back(i);
		    intermediates.push_back(j);
		    rootAndLeaf[resi[0]][resi[1]] = rootAndLeaf[resj[0]][(resj[1]+1)%2];
		    rootAndLeaf.erase(rootAndLeaf.begin() + resj[0]);
		  }
		else
		  {
		    int inter = 0;
		    int leaf = 0;
		    vector <int> pos;
		    if (resi[0] != -1)
		      {
			inter = i;
			leaf = j;
			pos = resi;
		      }
		    else
		      {
			inter = j;
			leaf = i;
			pos = resj;
		      }

		    intermediates.push_back(inter);
		    rootAndLeaf[pos[0]][pos[1]] = leaf;
		  }
	      }
	    else
	      {
		return 0;
	      }
	  }

    int notRoadNum = roads.size() - (rootAndLeaf.size() * 2 + intermediates.size());
    int noads = notRoadNum + rootAndLeaf.size();
    long long tmpret = 1;

    for (int i=noads; i>0; i--)
      tmpret = tmpret * i % 1000000007;

    for (int i=0; i<rootAndLeaf.size(); i++)
      tmpret = tmpret * 2 % 1000000007;

    ret = tmpret;

    return ret;
  }
};

2009-11-05

SRM452 div2

00:07

250と500ができて、ratingは1041->1101と増加。今年のsrmはあと3回しかないので、がんばらないと今年中に青になるという目標が厳しくなってきました。

ちなみに問題のwriterはrng_58さんだったそうです。

Easy - EggCartons

整数nが与えられるので、それを8と6の組み合わせで表す。例えば22=8*2+6*1。nを表すのに用いる最小の8と6の個数を返す(先の例なら3)。不可能なら-1。

nが高々100なので、0-100全てについて解を求めました。

class EggCartons {
public:
  int minCartons(int n)
  {
    int ans[101];
    memset(ans, -1, sizeof(ans));

    for (int i=0; i<=12; i++)
      for (int j=0; j<=16; j++)
	{
	  if (8*i + 6*j <= 100)
	    if (ans[8*i + 6*j] == -1)
	      ans[8*i + 6*j] = i+j;
	    else
	      ans[8*i + 6*j] = min(ans[8*i + 6*j], i+j);
	}

    return ans[n];
  }
};

Medium - NotTwo

グリッド上に石を置く。石と石の間のユークリッド距離は2であってはいけない。グリッドの幅と高さが与えられるので、置ける石の最大数を求める。

証明はできてないんですが、最適解では、以下のように2x2の市松模様っぽく石を置くことができます。

**--**--**--**--**--
**--**--**--**--**--
--**--**--**--**--**
--**--**--**--**--**
**--**--**--**--**--
**--**--**--**--**--
--**--**--**--**--**
--**--**--**--**--**

与えられた幅と高さに応じて、このように石が置かれていると仮定し、個数を数える事で解が求まります。

class NotTwo {
public:
  int maxStones(int width, int height)
  {
    int ret = 0;

    for (int i=0; i<width; i++)
      for (int j=0; j<height; j++)
	{
	  int row = i;
	  int col = j;
	  if (row % 2 != 0)
	    row--;
	  if (col % 2 != 0)
	    col--;

	  if (row%4==0 && col%4 == 0 ||
	      row%4 != 0 && col%4 != 0)
	    ret++;
	}

    return ret;
  }
};

Hard - HamiltonPath

問題文は省略。

できませんでした。アルゴリズムは思いついたのですが、実装ができませんでした。以下のようなアルゴリズムを考えました。

  • roadsが有効かチェック。
  • roadsのうち、つながっている道同士をつなげる。例えば、(0, 1) (4, 0)があった場合、(4, 0, 1)とする。
  • 上記処理後のroadsの各道を一つのノードとみなし、経路の数を計算する。これはノード数の階乗となる。
  • 上記の計算結果について、roadsの各道について2方向のパターンがあるので、2^(道の数)を掛ける。

例えばテストケース0の場合、ノードは0-2の三つで、通らなければならないパスは0-1間です。0-1を一つのノードとみなすと、2と(0, 1)の二つのノードとなり、経路は2!=2種類となります。0-1の道は、0->1という方向と1->0という方向の2種類があるので、2! * 2 = 4通りとなり、これが解です。

グラフには不慣れなので、実装に時間がかかり、間に合いませんでした。特に、グラフをどういうデータ構造で表すか。グラフをどう走査し、チェックするかという基本的な部分ができていません。

また、ワーストケースでは50!の計算が発生するので、オーバーフローが起こり、普通に上記の計算をしてから1000000007のmodをとる事はできません。この場合は毎回の乗算ごとにmodを計算するという方法で対処します。例えば、(A*B*C)%X は A%X * B%X * C%X (左から順に計算)という順で計算する事ができます。

challenge

一度もできませんでした。

rating

1041 -> 1101。部屋では2位、div2全体では110位でした。

yutoyutoriyutoyutori2009/11/07 04:12グラフですが、この場合はグラフとしては始端と終端を保持すればいいと思います。つまりint型変数2つでひとつのグラフを表現すれば足ります。
短絡グラフを合成した際に出た中間ノードはブラックリストに登録しておけばいいです(vector<int>)。何故ならば、ブラックリストに登録された中間ノードが尚別の短絡グラフに現われる時、その様な経路を使って全体のノードを一度だけ走査する事はできないからです。なので、0を返します。
1000000007のmodは僕も分かりませんでした。システムテストでは、ベタな階乗計算だとひとつのケースだけエラーが返るみたいです。

cou929cou9292009/11/08 02:58ありがとうございます!大変参考になりました。別エントリとしてポストしました。
http://topcoder.g.hatena.ne.jp/cou929/20091107/1257616436

modの件は、途中経過をlong longで保存する事で、僕の場合はうまくいきました。

2009-11-04

SRM211 div1 (過去問)

00:48

Easy - grafixCorrupt

辞書(stringvector)とある単語(string)が与えられる。辞書の中から単語と一番一致度が高い単語を取り出す。

普通に一つ一つ調べていくだけです。

class grafixCorrupt {
public:
  int selectWord(vector <string> dictionary, string candidate)
  {
    int maximum = 0;
    int index = -1;

    for (int i=0; i<dictionary.size(); i++)
      {
	int c = 0;
	for (int j=0; j<dictionary[i].size(); j++)
	  if (dictionary[i][j] == candidate[j])
	    c++;

	if (c > maximum)
	  {
	    maximum = c;
	    index = i;
	  }
      }

    return index;
  }
};

Medium - grafixMask

400x600 pixelの画像がある。またマスクがあり、マスクは矩形の集合で定義されている。マスクがない領域を調べ、領域の広い順にソートし返す。

アプローチとしては、まず画像を表す配列を準備し、マスクになるピクセルを埋めていきます。次にマスクされていない領域をラベリングしていき、最後に領域の大きさを調べてソートします。

class grafixMask {
public:
  int image[400][600];
  int labelCounter;

  int toInt(string s) {int r = 0; istringstream ss(s); ss >> r; return r;}
  string toStr(int n) {ostringstream ss; ss << n; return ss.str();}

  vector <int> split(const string _s, const string del)
  {
    vector <int> ret;
    string s = _s;

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

    return ret;
  }

  bool inRange(int row, int col)
  {
    if (0 <= row && row < 400 && 0 <= col && col < 600)
      return true;
    return false;
  }

  int drawRectangle(int x1, int y1, int x2, int y2)
  {
    for (int row=x1; row<=x2; row++)
      for (int col=y1; col<=y2; col++)
	image[row][col] = 0;

    return 0;
  }

  int label(int row, int col)
  {
    queue <pair <int, int> > q;
    q.push(make_pair(row, col));

    int xdir[4] = {0, 1, 0, -1};
    int ydir[4] = {-1, 0, 1, 0};

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

	for (int i=0; i<4; i++)
	  if (inRange(current.first+xdir[i], current.second+ydir[i]) && image[current.first+xdir[i]][current.second+ydir[i]] == -1)
	    {
	      image[current.first+xdir[i]][current.second+ydir[i]] = labelCounter;
	      q.push(make_pair(current.first+xdir[i], current.second+ydir[i]));
	    }
      }
    
    labelCounter++;

    return 0;
  }

  vector <int> sortedAreas(vector <string> rectangles)
  {
    memset(image, -1, sizeof(image));
    labelCounter = 1;

    for (int i=0; i<(int)rectangles.size(); i++)
      {
	vector <int> coords = split(rectangles[i], " ");
	drawRectangle(coords[0], coords[1], coords[2], coords[3]);
      }

    for (int row=0; row<400; row++)
      for (int col=0; col<600; col++)
	if (image[row][col] == -1)
	  {
	    image[row][col] = labelCounter;
	    label(row, col);
	  }

    vector <int> ret(labelCounter-1, 0);

    for (int row=0; row<400; row++)
      for (int col=0; col<600; col++)
	if (image[row][col] != 0)
	  ret[image[row][col]-1]++;

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

    return ret;
  }
};

2009-11-03

SRM207 div2 (過去問)

10:17

Easy - TransportCounting

車に乗っていて、直線しかない道路を走っている。道路には何台かバスがいて、全てのバスは自分の車と同じ進行方向。自分の車の初期位置は0で、スピードが与えられる。また各バスの初期位置とスピードが与えられる。time時間経過後に、車は何台のバスを見たか。

時刻を一つ一つ増加させながら、どのバスと出会ったかをカウントするアプローチです。

class TransportCounting {
public:
  int countBuses(int speed, vector <int> positions, vector <int> velocities, int time)
  {
    int ret = 0;
    bool meeted[positions.size()];
    memset(meeted, false, sizeof(meeted));
    int pos = 0;

    for (int i=0; i<positions.size(); i++)
      if (positions[i] <= pos && !meeted[i])
	{
	  ret++;
	  meeted[i] = true;
	}

    for (int i=0; i<time; i++)
      {
	pos += speed;
	for (int j=0; j<positions.size(); j++)
	  {
	    positions[j] += velocities[j];
	    if (positions[j] <= pos && !meeted[j])
	      {
		ret++;
		meeted[j] = true;
	      }
	  }
      }

    return ret;
  }
};

Medium - RegularSeason

バスケットボールのトーナメントで、各チームの勝率と、各ラウンドの試合数が与えられる。チームを勝率順にソートして返す。

問題文の細かい部分がよくわからなかったんですが、exampleをみながらなんとか解きました。まず勝率の計算方法ですが、方法さえわかってしまえば簡単で、各チームの組み合わせごとに、ホームでの勝率*round + アウェイ(英語ではvisitorっていうんですね)での勝率 * roundを計算し、最後に全対戦カードぶん総和するだけです。丸め誤差をさけるために、分子だけを計算し、最後の結果を作る処理で100で割ります。このこともわざわざ問題文に書いてくれていました。次にソートする部分ですが、名前(string)とスコア(double)をそれぞれ昇順、降順にしなければいけないので、単にpairを使ってもできません。そこで構造体と比較のための叙述関数でソートします。最後に四捨五入は、0.5を足して小数点以下を切り捨て(intへキャスト)という常套手段を使いました。個人的には問題文の読解力とソートの仕方がポイントの問題でした。

typedef struct team
{
  string name;
  double score;
};

bool cmp(team a, team b)
{
  if (a.score == b.score)
    return a.name < b.name;
  else
    return a.score > b.score;
}

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;
}

int toInt(string s) {int r = 0; istringstream ss(s); ss >> r; return r;}
string toStr(int n) {ostringstream ss; ss << n; return ss.str();}

class RegularSeason {
public:
  vector <string> finalStandings(vector <string> teams, int rounds)
  {
    vector <team> t;
    vector <vector <string> > steams;
    vector <string> ret;

    for (int i=0; i<teams.size(); i++)
      {
	vector <string> s = splits(teams[i], " ");
	team tt;
	tt.name = s[0];
	tt.score = 0;
	s.erase(s.begin());
	t.push_back(tt);
	steams.push_back(s);
      }

    for (int i=0; i<steams.size(); i++)
      for (int j=0; j<steams[i].size(); j++)
	if (i != j)
	  {
	    t[i].score += toInt(steams[i][j]) * rounds;
	    t[i].score += (100 - toInt(steams[j][i])) * rounds;
	  }

    sort(t.begin(), t.end(), cmp);

    for (int i=0; i<t.size(); i++)
      {
	string s;
	s = t[i].name;
	s += " ";
	double d = t[i].score / 100.0;
	d += 0.5;
	s += toStr((int)d);
	ret.push_back(s);
      }

    return ret;
  }
};

Hard - CaptureThemAll

チェスをプレイしていて、手駒はナイトのみ、相手はルークとクイーンを持っている。特別な魔法"ヘイスト"を使ったので、ナイトは何度でも動けるようになった。ナイトがルークとクイーンの両方をとる、最短ステップを求める。

BFSで解きました。はじめ、単純に全ての空間から探索していたので、ステップ数が大きくなると時間がかかって終わらずシステムテストに落ちました。例えば返り値が10ステップのケースだと、概算で8^10=1,073,741,824通りとなり、多すぎます。(余談ですが、テストでTLEで落ちるかなと思ったんですが、uncought exceptionという例外で落ちました。原因はよくわからないです。)

そこで、"ナイト-ルーク間の最小ステップ"、"ナイト-クイーン間の最小ステップ"、"ルーク-クイーン間の最小ステップ"をそれぞれ別に求め、最後に最小値を返す方法にしました。これで計算量が削減でき、システムテストも通りました。

typedef struct path
{
  int step;
  string pos;
};

class CaptureThemAll {
public:
  bool inRange(string pos)
  {
    if ('a' <= pos[0] && pos[0] <= 'h' && '1' <= pos[1] && pos[1] <= '8')
      return true;
    return false;
  }

  int r(string start, string goal)
  {
    int ret = 0;
    int rdir[8] = {-2, -2, -1, 1, 2, 2, -1, 1};
    int cdir[8] = {-1, 1, 2, 2, -1, 1, -2, -2};
    queue <path> q;
    path s;

    s.step = 0;
    s.pos = start;
    q.push(s);

    while (!q.empty())
      {
	path current = q.front();
	q.pop();

	if (current.pos == goal)
	  {
	    ret = current.step;
	    break;
	  }

	for (int i=0; i<8; i++)
	  {
	    char r = current.pos[0] + rdir[i];
	    char c = current.pos[1] + cdir[i];
	    string s;
	    s = r;
	    s += c;
	    if (inRange(s))
	      {
		path tmp;
		tmp.step = current.step + 1;
		tmp.pos = s;
		q.push(tmp);
	      }
	  }
      }

    return ret;
  }

  int fastKnight(string knight, string rook, string queen)
  {
    int k2r = 0, k2q = 0, r2q = 0;
    k2r = r(knight, rook);
    k2q = r(knight, queen);
    r2q = r(rook, queen);

    return min(k2r + r2q, k2q + r2q);
  }
};