Hatena::Grouptopcoder

cou929のTopCoder日記

2009-10-31

SRM387 div2

12:12

Easy - GuessingNextElement

数列が与えられる。数列は必ず等差数列か等比数列のどちらかである。どちらかを判定し、次の要素を返せ。

必ずどちらかの数列になるという制約があるので、Aが等比数列かどうかだけ調べ、違っていれば等差数列と考えることができます。こうして等差・等比を求め、解を計算します。

class GuessingNextElement {
public:
  int guess(vector <int> A)
  {
    int p = A[0];
    int art = A[1] - A[0];
    int geo = A[1] / A[0];
    bool isGeo = true;
    if (A[1] % A[0] != 0)
      isGeo = false;

    if (isGeo)
      {
	int n = p;
	for (int i=1; i<A.size(); i++)
	  {
	    n *= geo;
	    if (n != A[i])
	      {
		isGeo = false;
		break;
	      }
	  }
      }

    if (isGeo)
      return A[A.size()-1]*geo;
    else
      return A[A.size()-1]+art;
  }
};

Medium - MarblesRegroupingEasy

問題文は省略。

最適解には必ずjorker boxがあります。各々のboxについて、それがjorkerであると設定し、以下の方法で必要なステップ数を調べ、最小値を返します。ステップ数はjorkerでないそれぞれのboxについて、

  • 2種類以上のマーブルが入っている場合、全てをjorker boxに移動する。
  • 1種類のマーブルしか入っていない場合、他にもそのようなboxがある場合は、それらを一つにまとめなければならない。層でない場合は、何もしないでいいので、ステップ数は増えない。

はじめ、jorkerの選び方を、一番多くの種類のマーブルが入っているボックスという風に決めていたので、システムテストに落ちてしまいました。

class MarblesRegroupingEasy {
public:
  int minMoves(vector <string> boxes)
  {
    int ret = 100000;

    for (int jorker=0; jorker<boxes.size(); jorker++)
      {
	int tmp = 0;
	bool flg[boxes[0].size()];
	memset(flg, false, sizeof(flg));
	for (int i=0; i<boxes.size(); i++)
	  if (i != jorker)
	    {
	      int counter = 0;
	      int pos = 0;
	      for (int j=0; j<boxes[i].size(); j++)
		if (boxes[i][j] != '0')
		  {
		    counter++;
		    pos = j;
		  }

	      if (counter > 1)
		tmp++;
	      else if (counter == 1)
		{
		  if (!flg[pos])
		    flg[pos] = true;
		  else
		    tmp++;
		}
	    }

	ret = min(tmp, ret);
      }

    return ret;
  }
};

2009-10-22

returnの無い関数の戻り値(C++)

19:01

前回のsrmakhil89さんのeasyの解答が、return文が無いのにテストをパスしており、不可解でした。コードを転載すると、

  int find(int source, int A) {
    int num=source;
    int i=1;
    int flag=0;

    while(flag==0)
      {
    	if(A<source)
    	  {
    	    cout<<source;
    	    flag=1;
          }
    	else
    	  {
    	    num*=10;
    	    source+=num;
    	    i++;
    	  }
      }
  }

この件ついて、rng_58さんがforumにスレッドをたてて下さいました。(ありがとうございます!)

Passed without return? - TopCoder Forums

C++ return statement - TopCoder Forums(関連情報)

コンパイラはあるレジスタに戻り値をセットする。通常はreturn文の値がこのレジスタにセットされるが、returnがない場合はそのレジスタに入っている値が返り値となる。今回の場合、処理系が関数のローカル変数をreturnで使うものと同様のレジスタに保存していたため、結果的に正しく動作した。ということのようです。処理系依存の書き方だし、かなりトリッキーなので、当然ですがこの挙動に依存したコードは書くべきではありません。

これ以上の話はコンパイラの内部や理論の知識がないと難しいので、現段階ではこのくらいのざっくりした理解なんですが、一応なにが起こったかがわかりました。

2009-10-21

SRM451 div2

13:03

ミスが重なり大幅にスコアを落としました。ratingは1041。

Easy - ReverseMagicalSource

問題は省略。

問題文に言われた通りに実装するだけの問題。

class ReverseMagicalSource {
public:
  int find(int source, int A)
  {
    int ret = source;
    int i = 1;

    while (A >= ret)
      ret += source * pow((double)10, i++);

    return ret;
  } 
};

Medium - BoredPhilosophers

textと整数nが与えられるので、1-nについて、textのなかに何種類のn個の連なった単語があるか数える。

これもそのまま実装するだけで、単語を全てベクタに入れて、出現頻度をmapでカウントしています。

コンテスト中は一つミスをしてしまい、システムテストに落ちました。複数単語をつなげる際に、あいだにスペースをいれるのを忘れていました。

class BoredPhilosophers {
public:
  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;
  }

  vector <int> simulate(vector <string> text, int N)
  {
    vector <int> ret;
    string completeText = "";
    for (int i=0; i<text.size(); i++)
      completeText += text[i];

    vector <string> words = splits(completeText, " ");

    for (int i=1; i<=N; i++)
      {
	map <string, int> m;

	for (int j=0; j<words.size()-i+1; j++)
	  {
	    string s = "";

	    for (int k=0; k<i; k++)
	      {
		s += words[j+k];
		s += " ";          // この処理を入れ忘れた
	      }

	    s.erase(s.end()-1);  // この処理を入れ忘れた

	    m[s]++;
	  }

	ret.push_back(m.size());
      }

    return ret;
  }
};

Hard - PizzaDelivery

自分はデリバリーピザ店のオーナーで、配達係の従業員は二人いる。店周辺はグリッドで表現され、各地点の高さや、配達先か否か、などが各セルに入っている。全ての配達先に届ける際短時間を求めよ。できない場合は-1。

問題を、1)全ての配達先への片道の最短時間を計算する、2)届ける順番と割り振りを決める、という2つに分割しました。1)はBFSで探索し、2)も全ての組み合わせを調べています。

以下のコードはコンテスト終了後10分後くらいに完成したものです。システムテストにはまだ通っていません。

class PizzaDelivery {
public:
  vector <string> terrain;
  int X, Y;
  bool inRange(int x, int y)
  {
    if (0 <= x && x < terrain.size() && 0 <= y && y < terrain[0].size())
      return true;
    return false;
  }

  int findRourte(int x, int y)
  {
    int ret = 1000000000;
    bool visited[terrain.size()][terrain[0].size()];
    int dirx[4] = {1, 0, 0, -1};
    int diry[4] = {0, 1, -1, 0};
    queue <pair <int, pair <int, int> > > q;
    memset(visited, false, sizeof(visited));

    q.push(make_pair(0, make_pair(x, y)));

    while (!q.empty())
      {
	pair <int, pair<int, int> > cur = q.front();
	q.pop();
	visited[cur.second.first][cur.second.second] = true;

	for (int i=0; i<4; i++)
	  {
	    int nextx = cur.second.first + dirx[i];
	    int nexty = cur.second.second + diry[i];
	    if (inRange(nextx, nexty) && !visited[nextx][nexty])
	      {
		if (nextx == X && nexty == Y)
		  {
		    ret = min(ret, 2 + cur.first);
		    continue;
		  }
		else if (terrain[cur.second.first][cur.second.second] == '$')
		  {
		    q.push(make_pair(2 + cur.first, make_pair(nextx, nexty)));
		    continue;
		  }
		else if (terrain[nextx][nexty] == '$')
		  {
		    q.push(make_pair(2 + cur.first, make_pair(nextx, nexty)));
		    continue;
		  }
		else
		  {
		    if (abs(terrain[cur.second.first][cur.second.second] - terrain[nextx][nexty]) == 0)
		      q.push(make_pair(1 + cur.first, make_pair(nextx, nexty)));
		    else if (abs(terrain[cur.second.first][cur.second.second] - terrain[nextx][nexty]) == 1)
		      q.push(make_pair(3 + cur.first, make_pair(nextx, nexty)));
		  }
	      }
	  }
      }
    return ret;
  }

  int deliverAll(vector <string> t)
  {
    int ret = 1000000000;
    vector <int> times;
    vector <vector <int> > buildings;
    terrain = t;

    // 各ビルへの経路を調べる
    for (int i=0; i<terrain.size(); i++)
      for (int j=0; j<terrain[i].size(); j++)
	if (terrain[i][j] == 'X')
	  {
	    X = i;
	    Y = j;
	  }
	else if (terrain[i][j] == '$')
	  {
	    vector <int> tmp;
	    tmp.push_back(i);
	    tmp.push_back(j);
	    buildings.push_back(tmp);
	  }

    for (int i=0; i<buildings.size(); i++)
      times.push_back(findRourte(buildings[i][0], buildings[i][1]));

    for (int i=0; i<times.size(); i++)
      if (times[i] == 1000000000)
	return -1;

    // 最短時間の、デリバリーの割り振りと順番を探す
    sort(times.begin(), times.end());

    do {
      int tmp1 = 0;
      int tmp2 = 0;
      int tmp3 = 1000000000;

      for (int i=0; i<times.size(); i++)
	{
	  tmp1 = 0;
	  tmp2 = 0;
	  for (int j=0; j<i+1; j++)
	    if (j == i)
	      tmp1 += times[j];
	    else
	      tmp1 += times[j]*2;

	  for (int j=i+1; j<times.size(); j++)
	    if (j == times.size()-1)
	      tmp2 += times[j];
	    else
	      tmp2 += times[j]*2;

	  tmp3 = min(tmp3, max(tmp1, tmp2));
	}

      ret = min(ret, tmp3);
    } while (next_permutation(times.begin(), times.end()));

    return ret;
  }
};

challenge phase

一人、akhil89というインドの人のチャレンジに失敗しました。

http://www.topcoder.com/stat?c=problem_solution&rm=302573&rd=13905&pm=10674&cr=22756903

コードを転載すると、

  int find(int source, int A) {
    int num=source;
    int i=1;
    int flag=0;

    while(flag==0)
      {
    	if(A<source)
    	  {
    	    cout<<source;
    	    flag=1;}
    	else
    	  {
    	    num*=10;
    	    source+=num;
    	    i++;
    	  }
      }
  }

これが何故returnがないのに動いているのかがわかりません。

また、チャレンジフェイズ修了直前に、上記の500のミスに気がつきました。他にも同様のミスをしている人がいたんですが、チャレンジする時間がありませんでした。

rating

500のfailとチャレンジ失敗により、1115->1041とかなり順位を落としてしまいました。はやくdiv1へ行きたい…

2009-10-20

SRM146 div2

23:17

Easy - YahtzeeScore

整数の数列が与えられる。要素 x 出現頻度の最大値を求めよ。

mapを使いました。特に特筆することはありません。

class YahtzeeScore {
   public:
   int maxPoints(vector <int> toss)
  {
    int ret = 0;
    map <int ,int> m;
    map <int ,int>::iterator mit;

    for (int i=0; i<toss.size(); i++)
      m[toss[i]]++;

    for (mit=m.begin(); mit!=m.end(); mit++)
      ret = max(ret, mit->first * mit->second);

    return ret;
  }
}

Medium - RectangularGrid

グリッドの幅と高さが与えられる。グリッドの中にある長方形の数を求めよ。

サイズが縦横ともに高々1000なので、全ての組み合わせをループして掛け合わせました。

class RectangularGrid {
public:
  long long countRectangles(int width, int height)
  {
    long long ret = 0;

    for (int w=1; w<=width; w++)
      for (int h=1; h<=height; h++)
	if ((width-w) + 1 != (height-h) + 1)
	  ret += w*h;

    return ret;
  }
};

Hard - BridgeCrossing

橋があって、人が何人かいる。それぞれの人の橋を渡りきる時間はばらばらで、入力として与えられる。橋の上は懐中電灯を持って歩かなければ行けない。橋の上は最大2人まで渡れる。2人で渡っているとき、所要時間は遅い方のひとにあわせられる。この条件のもと、全員が橋を渡りきるには最小でどれだけの時間がかかるか。

  • 人数が高々6人
  • 最適解は必ず、行きが2人、帰りが1人になる。(この条件は問題文で与えられている)
  • 最適解では、橋から帰る人は、渡りきった人達の中でもっとも素早い人になる

以上の情報から、全パターンを探索しても十分間に合うと判断し、そのように実装しました。アルゴリズムよりもむしろ実装のほうが大変でした。もっとスマートな書き方にしたいです。

class BridgeCrossing {
public:
  int ret;
  vector <int> times;

  bool isPassed(int person, vector <int> & passed)
  {
    for (int i=0; i<passed.size(); i++)
      if (person == passed[i])
	return true;
    return false;
  }

  int r(vector <int> passed, int score)
  {
    for (int i=0; i<times.size(); i++)
      for (int j=0; j<times.size(); j++)
	if (i != j && !isPassed(i, passed) && !isPassed(j, passed))
	  {
	    vector <int> tmp = passed;
	    tmp.push_back(i);
	    tmp.push_back(j);

	    if (tmp.size() == times.size())
	      {
		ret = min(ret, score + max(times[i], times[j]));
		return 0;
	      }

	    int mini = 1000;
	    int index = -1;
	    for (int k=0; k<tmp.size(); k++)
	      if (mini > times[tmp[k]])
		{
		  mini = times[tmp[k]];
		  index = k;
		}

	    tmp.erase(tmp.begin() + index);
	    r(tmp, score + max(times[i], times[j]) + mini);
	  }

    return 0;
  }

  int minTime(vector <int> t)
  {
    ret = 1000;
    times = t;
    vector <int> emp;

    if (times.size() == 1)
      return times[0];

    r(emp, 0);

    return ret;
  }
};

2009-10-18

SRM450 div2 再チャレンジ

11:33

Hard - EnemyTowers

getTurn()の高速化を行いました。今まではタワー数ぶんの配列を用意して、各要素にはそのタワーの現在のhpをいれ、それを走査しながら計算していたのですが、ここがループの分遅くなっていたので、タワーのhpの総量から直接足し引きするように変更。これであっさりと解決しました。むしろ昨日の実装がけっこうしょうもない方法だったと言えます。

class EnemyTowers {
public:
  int getTurn(int units, int hp, int attack, int numt)
  {
    int ret = 0;
    int total = hp * numt;

    while (units > 0 && total > 0)
      {
	ret++;

	total -= units;
	units -= ceil((double)max(0, total) / hp) * attack;
      }

    if (units <= 0)
      ret = -1;

    return ret;
  }

  int attack(int myUnits, int hpT, int attackT, int numWodT, int numStoT)
  {
    int ret = -1;
    int left = 0;
    int mid = myUnits / 2;
    int right = myUnits;

    for (int i=0; i<500; i++)
      {
	int resWood = getTurn(mid, hpT, attackT, numWodT);
	int resStone = getTurn(myUnits - mid, hpT, attackT, numStoT);

	//	cout << mid << " " << resWood << " " << resStone << endl;

	if (resWood == -1 && resStone == -1)
	  return -1;

	if (resWood != -1 && resStone != -1)
	  {
	    if (resWood > resStone)
	      {
		left = mid;
		mid += (right - mid) / 2;
	      }
	    else
	      {
		right = mid;
		mid = (mid - left) / 2;
	      }
	  }
	else
	  {
	    if (resWood == -1)
	      {
		left = mid;
		mid += (right - mid) / 2;
	      }
	    else
	      {
		right = mid;
		mid = (mid - left) / 2;
	      }
	  }

	if (resWood != -1 && resStone != -1)
	  if (ret == -1)
	    ret = max(resWood, resStone);
	  else
	    ret = min(ret, max(resWood, resStone));
      }

    return ret;
  }
};

2009-10-17

SRM450 div2

04:18

ratingは微増+4の1116。500と1000の両方がシステムテストに落ちるという情けない結果でした。

Easy - StrangeComputer

初期状態がすべて0のビットパターンがある。このビットパターンに対して、ある地点と値(1か0)を指定すると、それ以降のビットがすべてその値になる、というオペレーションがある。たとえば0000に対して左から2番目の位置と値1を指定すると、0111というパターンになる。ビットパターンが与えられるので、このオペレーションを何回行えば、このビットパターンが再現できるか求めよ。

左から右へ走査し、パターンが何度変化するかを調べれば良いです。ただし初期状態が0なので、左端が1の場合に対応できるようにしています。

class StrangeComputer {
public:
  int setMemory(string mem)
  {
    int ret = 0;
    char c = '0';

    for (int i=0; i<mem.size(); i++)
      if (mem[i] != c)
	{
	  ret++;
	  c = mem[i];
	}

    return ret;
  }
};

Medium - OrderedNim

nimというゲームの派生である、orderdNimをプレイして、どちらが勝つか。詳細は省略。

各heapの石の数は、1かそれより大きいかだけが問題になります。はじめに1より大きいheapをとることができる人が勝つので、layoutを小さい方からみていき、はじめに1以外の数が入っている地点を調べ、その地点が偶数ならalice、そうでなければbobの勝ちとなります。

アルゴリズムは思いついたんですが、breakを書き忘れるというどうしようもないイージーミスをしてしまい、システムテストに落ちてしまいました。本当に悔やまれます。

class OrderedNim {
public:
  string winner(vector <int> layout)
  {
    int first = layout.size()-1;
    for (int i=0; i<layout.size(); i++)
      if (layout[i] != 1)
	{
	  first = i;
	  break;    // ここのbreakを書き忘れた。
	}

    if (first % 2 == 0)
      return "Alice";
    else
      return "Bob";
  }
};

Hard - EnemyTowers

シミュレーションゲームで、自分と相手のパラメータが与えられ、最短何ターンで勝てるか、あるいは負けるかを求める。詳細は省略。

まず、あるパラメータのもとで相手を倒すには何ターンかかるか、あるいは負けるかを調べる関数getTurn()を作り、あとはmyUnitsをバイナリサーチして解を求めるというアプローチを考えました。システムテストに落ちてしまったんですが、問題点は以下の3つです。

  • バイナリサーチの範囲の変更を失敗していた。これは修正済み
  • バイナリサーチをしている部分で、イテレーションの回数が少なく、十分な解が出ていなかった。こちらも修正済み。
  • numWodT, numStoTのワーストケースでは、getTurn()が遅く、TLEする。

今日は疲れたので、後日最適化を行いたいと思います。また、バイナリサーチはたびたび使う技術なので、もう少し慣れたいです。今回もコードはつたないし、一度間違えてしまいました。何回イテレーションすれば、十分な精度が出るかを見積もる練習も必要です。

以下はまだシステムテストに通らないコードです。

class EnemyTowers {
public:
  int getTurn(int units, int hp, int attack, int numt)
  {
    int ret = 0;

    vector <int> towers(numt, hp);

    while (1)
      {
	int tmp = units;
	for (int i=0; tmp > 0 && i<towers.size(); i++)
	  {
	    if (towers[i] > 0)
	      {
		if (towers[i] >= tmp)
		  {
		    towers[i] -= tmp;
		    tmp = 0;
		  }
		else
		  {
		    tmp -= towers[i];
		    towers[i] = 0;
		  }
	      }
	  }

	int ct = 0;
	for (int i=0; i<towers.size(); i++)
	  if (towers[i] > 0)
	    ct++;

	units -= ct * attack;

	if (units <= 0)
	  break;

	ret++;

	if (towers[towers.size()-1] <= 0)
	  break;
      }

    if (units <= 0)
      ret = -1;

    return ret;
  }

  int attack(int myUnits, int hpT, int attackT, int numWodT, int numStoT)
  {
    int ret = -1;
    int left = 0;
    int mid = myUnits / 2;
    int right = myUnits;

    for (int i=0; i<250; i++)
      {
	int wood = mid;
	int stone = myUnits - wood;

	int resWood = getTurn(wood, hpT, attackT, numWodT);
	int resStone = getTurn(stone, hpT, attackT, numStoT);

	//	cout << mid << " " << resWood << " " << resStone << endl;

	if (resWood == -1 && resStone == -1)
	  return -1;

	if (resWood != -1 && resStone != -1)
	  {
	    if (resWood > resStone)
	      {
		left = mid;
		mid += (right - mid) / 2;
	      }
	    else
	      {
		right = mid;
		mid = (mid - left) / 2;
	      }
	  }
	else
	  {
	    if (resWood == -1)
	      {
		left = mid;
		mid += (right - mid) / 2;
	      }
	    else
	      {
		right = mid;
		mid = (mid - left) / 2;
	      }
	  }

	if (resWood != -1 && resStone != -1)
	  if (ret == -1)
	    ret = max(resWood, resStone);
	  else
	    ret = min(ret, max(resWood, resStone));
      }

    return ret;
  }
};

challenge phese

500点問題で、単に1の数を数えているひとなどがいたので、5人くらいチャレンジ成功しました。

この時点では3問とも解けており、チャレンジも成功していたので、4桁の高得点が出ていて、つかの間ですが意気揚々でした。

system test

500、1000が落ちました。理由は上記の通りです。

rating

プラス4の1116です。


気分的にも上がったり下がったりで疲れました。またすぐ次があるので、div1目指してがんばります。

2009-10-15

SRM391 div2

23:57

Easy - SnowyWinter

ある道路の雪が積もっている区間が2つのベクタで与えられる。1つ目のベクタは雪が積もっている区間の開始地点の集合。2つ目は終了地点の集合。区間は一部オーバーラップしている可能性がある。雪が積もっている区間の長さを求めよ。

2つのベクタをvector <pair <int, int> >につめ直して、ソートすれば、簡単になります。オーバーラップのチェックは現在の暫定区間内に他の要素の区間が含まれているかどうかで判定し、チェック済の要素を表現するためにフラグの配列を導入しています。

class SnowyWinter {
public:
  int snowyHighwayLength(vector <int> startPoints, vector <int> endPoints)
  {
    int ret = 0;
    int flg[startPoints.size()];
    memset(flg, 0, sizeof(flg));
    vector <pair <int, int> > sorted;

    for (int i=0; i<startPoints.size(); i++)
      sorted.push_back(make_pair(startPoints[i], endPoints[i]));

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

    for (int i=0; i<sorted.size(); i++)
      {
	if (flg[i] == 0)
	  {
	    flg[i] = 1;
	    int under = sorted[i].first;
	    int upper = sorted[i].second;
	    for (int j=i+1; j<sorted.size(); j++)
	      if (flg[j] == 0 && sorted[j].first <= upper)
		{
		  flg[j] = 1;
		  upper = max(upper, sorted[j].second);
		}

	    ret += upper - under;
	  }
      }

    return ret;
  }
};

Medium - IsomorphicWords

ある文字列を別の文字列にmappingできるとき、この2つの文字列はIsomorphicという。mappingとは、ある文字を別の文字に置き換え、文字列の順番がかわっていないような変換方法をいう。たとえばabcaとxylxなど。文字列の集合が与えられるので、何組のIsomorphicがあるか求めよ。

まず、Isomorphicの判定のために、各文字列を次のようにラベル付けします。同じ文字が同じ数字にラベルされ、かつラベルの番号はその文字の文字列中での出現順にします。以下が例です。

  • "abca" -> "0120"
  • "xylx" -> "0120"
  • "ksmlse" -> "012324"

ラベル付け後のベクタを比べれば、Isomorphicかどうかが判定できます。

その後、与えられた集合の中に、同じIsomorphicな文字列がいくつづつあるか調べます。例えばテストケース1なら、"aa"系の文字列が3組、"ab"系の文字列が2組あります。あとはそれぞれについてコンビネーションを計算し、その総和をとればokです。テストケース2の例だと、3C2 + 2C2 = 3 + 1 = 4 となります。

class IsomorphicWords {
public:
  int countPairs(vector <string> words)
  {
    int ret = 0;
    vector <vector <int> > labeled;

    for (int i=0; i<words.size(); i++)
      {
	vector <int> v(words[i].size(), -1);
	int counter = 0;
	for (int j=0; j<words[i].size(); j++)
	  {
	    if (v[j] == -1)
	      {
		v[j] = counter;
		for (int k=j+1; k<words[i].size(); k++)
		  if (v[k] == -1 && words[i][k] == words[i][j])
		    v[k] = counter;
		counter++;
	      }
	  }
	labeled.push_back(v);
      }

    int flg[words.size()];
    vector <int> sames;
    memset(flg, 0, sizeof(flg));

    for (int i=0; i<labeled.size(); i++)
      {
	if (flg[i] == 0)
	  {
	    int counter = 0;
	    flg[i] = 1;
	    for (int j=i+1; j<labeled.size(); j++)
	      if (flg[j] == 0 && labeled[i] == labeled[j])
		{
		  flg[j] = 1;
		  counter++;
		}
	    if (counter > 0)
	      sames.push_back(++counter);
	  }
      }

    for (int i=0; i<sames.size(); i++)
      ret += (sames[i] * (sames[i] - 1)) / 2;

    return ret;
  }
};

Hard - MarbleCollectionGame

格子状のフィールドがあり、各マスにはmarbleが0-9個おいてある。また、'#', 'L', 'U'というマスもあり、それぞれ、立ち入り禁止、左へも進める、上へも進めるという意味を持つ。ロボットは地点(0, 0)からスタートし、ワンステップごとに右が下へ進める。ただし、'L', 'U'のマスでは、それぞれ左、上にも進んでよい。ロボットは現在のマスのmarbleを全て回収し、回収後そのマスのmarble数は0になる。marbleは最大で何個獲得できるか。

フィールドの大きさは最大20x20。全探索の場合をざっくり見積もると(ちょっと自信ないんですが)2^20 = 120万 となるので、これならbruto-forceでも間に合うのかもと考え、はじめの方でぱっと思いついた再帰+メモ化でのアプローチで実装を試みました。

具体的には暫定解で枝狩りをする、深さ優先探索(のつもり)です。20x20のメモを用意しておき、各要素はそのセルでの暫定の最大値(獲得marble数)を保存する。ロボットは再帰的にフィールド上を移動する。もし現在のスコアが暫定スコアより悪ければそのマスからの探索は終了します。

ここまでを実装したのが以下のコードですが、テストケース3だけがまだ通りません。なにか考慮のし忘れか、あるいは問題の理解し間違いがあるのかもしれません。

class MarbleCollectionGame {
public:
  int memo[20][20];
  vector <string> b;

  // x, yが逆になっているので注意
  int r(int x, int y, int score)
  {
    if (b[x][y] == '#')
      return -1;

    int curscore = 0;

    if (b[x][y] != 'L' && b[x][y] != 'U')
      curscore = b[x][y] - '0';

    if (memo[x][y] <= score + curscore)
      {
	memo[x][y] = max(score + curscore, memo[x][y]);

	if (b[x][y] == 'U')                        // 上へ
	  {
	    if (x-1 >= 0 && b[x-1][y] != '#')
	      r(x-1, y, score + curscore);
	  }
	else if (b[x][y] == 'L')                   // 左へ
	  {
	    if (y-1 >= 0 && b[x][y-1] != '#')
	      r(x, y-1, score + curscore);
	  }

	if (x+1 < b.size() && b[x+1][y] != '#' && b[x+1][y] != 'U')     // 下へ
	  r(x+1, y, score + curscore);
	if (y+1 < b[0].size() && b[x][y+1] != '#' && b[x][y+1] != 'L')  // 右へ
	  r(x, y+1, score + curscore);
      }

    return 0;
  }

  int collectMarble(vector <string> board)
  {
    int ret = 0;
    memset(memo, -1, sizeof(memo));
    b = board;

    r(0, 0, 0);

    for (int i=0; i<20; i++)
      for (int j=0; j<20; j++)
	ret = max(ret, memo[i][j]);

    return ret;
  }
};

2009-10-14

SRM395 div2

11:56

Easy - SquareDigitNumbers

記憶が曖昧になってますが、だいぶ前に解いてあった形跡があったので、それを転載。

0, 1, 4, 9からできる整数を昇順で並べ、N番目の数を返す問題。たとえばN=6なら、11 (0, 1, 4, 9, 10, 11)。

整数の数列は、以下のように4周期の規則性があります。この規則性を利用して解いたのだったと思います。

  0   1   4   9
 10  11  14  19
 40  41  44  49
 90  91  94  99
100 101 104 109

nが高々1000なので、数列を1000まで生成してしまうのもありだと思います。

class SquareDigitNumbers {
   public:
   int getNumber(int n)
  {
    unsigned int i;
    int num = n+1;
    int place = 1;
    int digit = 0;
    int mod = 0;
    int ret = 0;

    while (1)
      {
	if (num <= 1)
	  break;

	mod = num % 4;
	if (mod == 0)
	  digit = 9;
	else if (mod == 1)
	  digit = 0;
	else if (mod == 2)
	  digit = 1;
	else if (mod == 3)
	  digit = 4;

	ret += digit * place;

	num = (int)((double)num / 4 + 0.9);
	place *= 10;
      }

    return ret;
   }
};

Medium - StreetWalking

格子状の街にいる。この街の中を縦横方向にwalkTime、斜め方向にsneakTimeで移動できる。現在地が(0, 0)、目的地が(X, Y)で与えられたとき、目的地までの最短時間を求めよ。

典型的なdpの問題なので、せっかくなのでdpで渡航と思ったんですが、X, Yが最大1000000000なので、メモリを使いすぎます。別のアプローチとして、目的地まで行く方法は、

  1. 縦横移動も含め、全てsneakで移動する。
  2. まず行けるところまでsneakで移動し、縦横方向はwalkで移動する。
  3. 全てwalkで移動する

この3種類しかないので、これらを全て計算し、minを返す方法にしました。

class StreetWalking {
public:
  long long minTime(int X, int Y, int walkTime, int sneakTime)
  {
    // all sneak
    long long allSneak = (long long)sneakTime * min(X, Y);
    if (abs(X-Y) % 2 == 0)
      allSneak += (long long)sneakTime * abs(X-Y);
    else
      allSneak += (long long)sneakTime * (abs(X-Y)-1) + walkTime;

    // sneak and walk
    long long sneakAndWalk = (long long)sneakTime * min(X, Y) + (long long)walkTime * abs(X - Y);

    // all walk
    long long allWalk = (long long)walkTime * (X + Y);

    return min(allSneak, min(sneakAndWalk, allWalk));
  }
};

Hard - TriviaGame

あなたはクイズゲームをプレイしている。クイズにはそれぞれ得点があって、正解するとその得点を得て、不正解だと同得点を失う。またtokenNeeded回正解すると、ボーナスが与えられる。得点とボーナスはそれぞれ数列で与えられ、それぞれi番目はi問目の問題の得点/i問目のボーナスに対応している。また問題はこの数列と同じ順番で出題される。あなたはすべての問題の解答を知っているので、得られる得点を最大化せよ。

dpで解きました。問題を順に一問ずつ見ていき、各問題ごとにtokenごとの最大得点を記憶していきます。例えばテストケース0の場合、

  • 一問目は、正解した場合(token, point) = (1, 1)。不正解の場合(0, -1)。この二つを保存。
  • 二問目は、一問目の各結果について、二問目が正解/不正解した場合を計算する。結果は、(2, 3), (1, -1), (1, 1), (0, -3)。ここで、(2, 3), (0, -3)と、token=1の2つについては、pointが最大の(1, 1)の方を保存する。
  • 以降はtokenがtokenNeededに達した場合のボーナス加算などに注意しながら、同様に計算してく。

また最初、tokenNeededが1の場合を考慮し忘れて、システムテストに一度落ちてしまいました。注意力が足りなかったです。

class TriviaGame {
  int MIN;
public:
  int maximumScore(vector <int> points, int tokensNeeded, vector <int> bonuses)
  {
    MIN  = -10000000;
    int ret = MIN;
    int dp[points.size()][tokensNeeded];
    memset(dp, MIN, sizeof(dp));

    if (tokensNeeded == 1)
      {
	dp[0][0] = max(dp[0][0], max(points[0] + bonuses[0], -1 * points[0]));
      }
    else
      {
	dp[0][0] = -1 * points[0];
	dp[0][1] = points[0];
      }

    for (int i=1; i<points.size(); i++)
      {
	for (int j=0; j<tokensNeeded; j++)
	  if (dp[i-1][j] != MIN)
	    {
	      // correct
	      if (j == tokensNeeded-1)
		dp[i][0] = max(dp[i][0], dp[i-1][j] + points[i] + bonuses[i]);
	      else
		dp[i][j+1] = max(dp[i][j+1], dp[i-1][j] + points[i]);

	      // incorrect
	      dp[i][j] = max(dp[i][j], dp[i-1][j] - points[i]);
	    }
      }

    for (int i=0; i<tokensNeeded; i++)
      ret = max(ret, dp[points.size()-1][i]);

    return ret;
  }
};

2009-10-10

SRM392 div2

12:19

Easy - AverageCandyLifetime

1年の各月ごとに、何個のキャンディーを食べたかが与えられる。キャンディーのlifetimeを1月1日からその月までの日数とする(1月なら31, 12月なら365)。lifetimeの平均値を求めよ。

やるだけの問題でした。月の日数はハードコードしました。

class AverageCandyLifetime {
public:
  double getAverage(vector <int> eatenCandies)
  {
    int days[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int lifetime[12];

    int m = 0;
    for (int i=0; i<12; i++)
      {
	m += days[i];
	lifetime[i] = m;
      }

    int totalLifetime = 0;
    int nums = 0;
    for (int i=0; i<eatenCandies.size(); i++)
      {
	totalLifetime += eatenCandies[i] * lifetime[i];
	nums += eatenCandies[i];
      }

    return (double)totalLifetime / nums;
  }
};

Medium - TwoStringMasks

文字列s1, s2が与えられる。それぞれただ一つの*を含んでいる。*の中にはどんな文字列でも入れてよい(空文字列を含む)。s1, s2が同じ文字列になり、かつ*に入れる文字が最小となるような文字列を求める。

あまりスマートでないんですが、こんなアルゴリズムで解きました。

  1. s1, s2を*の前後で分ける。
    • ここで、impossibleを判定。それぞれの前同士、後同士を比べ、どちらか一方がもう一方のスーパーセットになっていなければimpossible。
  2. s1, s2の前後から重複している部分を省く
    • テストケース0の場合は、"*PCO", "OPC*"となる。
  3. s1, s2のどちらが"先"かを調べる。
    • テストケース0の場合は、"OPC*"が先で、"*PCO"が後となる
  4. 両者がどれだけ一致しているかを調べる。
    • テストケース0の場合は、"PC"が一致。
  5. 解答を組み立てる。
    • 前部分 + s1, s2の先の方 + s1, s2の後の方から重複部分を除いたもの + 後部分
    • 上式の真ん中部分について、テストケース0の場合は、先に"OPC"が入り、次に"PCO"から"PC"を取り除いた、"C"が入ります。

教訓としては、"問題から自明な部分、考えなくても良い部分はできるだけ取り除き、考えなくてはいけない部分の複雑さを極力下げる"ということでしょうか。今回の問題で言うと、2番で重複部分を取り除いていることがそれにあたります。複雑さが増すとバグを埋め込む確率が上がり、topcoderのようなタイムアタックのコンテストでは致命的だと思います。

class TwoStringMasks {
public:
  string shortestCommon(string s1, string s2)
  {
    string ret;
    int ast1 = 0, ast2 = 0;
    for (int i=0; i<s1.size(); i++)
      if (s1[i] == '*')
	{
	  ast1 = i;
	  break;
	}
    for (int i=0; i<s2.size(); i++)
      if (s2[i] == '*')
	{
	  ast2 = i;
	  break;
	}

    int lim = min(ast1, ast2);
    for (int i=0; i<lim; i++)
      if (s1[i] != s2[i])
	return "impossible";
    lim = min(s1.size() - ast1 - 1, s2.size() - ast2 - 1);
    for (int i=1; i<=lim; i++)
      if (s1[s1.size() - i] != s2[s2.size() - i])
	return "impossible";

    string head, tail;
    string s, ss;
    int pos = 0;
    if (ast1 < ast2)
      s = s1;
    else
      s = s2;

    if (s1.size() - ast1 - 1 < s2.size() - ast2 - 1)
      {
	ss = s1;
	pos = ast1;
      }
    else
      {
	ss = s2;
	pos = ast2;
      }

    head = s.substr(0, min(ast1, ast2));
    tail = ss.substr(pos+1);

    s1.erase(0, min(ast1, ast2));
    s1.erase(s1.size() - tail.size());
    s2.erase(0, min(ast1, ast2));
    s2.erase(s2.size() - tail.size());

    for (int i=0; i<s1.size(); i++)
      if (s1[i] == '*')
	s1.erase(i, 1);

    for (int i=0; i<s2.size(); i++)
      if (s2[i] == '*')
	s2.erase(i, 1);

    if (ast1 < ast2)
      {
	string tmp = s1;
	s1 = s2;
	s2 = tmp;
      }
      
    int samepos = 0;
    for (int i=1; i<=min(s1.size(), s2.size()); i++)
      {
	string st1, st2;
	st1 = s1.substr(s1.size() - i);
	st2 = s2.substr(0, i);
	if (st1 == st2)
	  samepos = i;
      }

    ret += head;
    ret += s1;
    ret += s2.substr(samepos);
    ret += tail;

    return ret;
  }
};

2009-10-08

SRM248 div2

12:46

Easy - SyllableCounter

文字列が与えられるので、音節がいくつあるか数える。ここでの音節は、文字列の中に含まれる母音のグループの数と定義する。例えば、"FOOBAR"はOOがつながっていて1グループと判定されるので、答えは2になる。

class SyllableCounter {
public:
  bool isVowel(char c)
  {
   string vowel = "AIUEO";

   for (int i=0; i<vowel.size(); i++)
     if (vowel[i] == c)
       return true;

   return false;
  }

  int countSyllables(string word)
  {
    int ret = 0;
    bool inVowelGroup = false;

    for (int i=0; i<word.size(); i++)
      {
	if (isVowel(word[i]))
	  {
	    if (inVowelGroup)
	      continue;
	    else
	      {
		ret++;
		inVowelGroup = true;
	      }
	  }
	else
	  {
	    if (inVowelGroup)
	      inVowelGroup = false;
	  }
      }

    return ret;
  }
};

Medium - WordPattern

与えられた文字列で、こういうパターンを作ったときのことを考える。

Input: HELLO
              O
             OLO
            OLLLO
           OLLELLO
          OLLEHELLO
           OLLELLO
            OLLLO
             OLO
              O

Input: TC
	      C
             CTC
              C  

文字列が与えられるので、その文字列を上記のようなパターンに並べた場合、一文字目(中心)から最後の文字(一番外側)までたどる方法は何通りあるか。ただしパターン上は上下左右にのみ移動できる。

まず、「解は、入力文字列の文字数のみに依存する」ということに気づく必要があります。これは"ABCDE"も"HELLO"も同じ解になるということです。一見、"HELLO"の方はLが2つ続くので解が増えそうな気がしますが、今回は関係しません。僕の場合は、証明はしてないのですが、手計算をすることでこの事実に気がつきました。

次に、この問題は以下のように定式化できます。

f(x) = \begin{cases} 1 &if &n = 1 \\ 4 &if &n = 2 \\ 4 \times 3 + (f(n-1) - 4) \times 2 &if &n \ge 3 \end{cases}

これは、「垂直、水平方向の4文字は3通り、それ以外は2通り存在する」というアイデアに基づいて作りました。例えば、"HELLO"の例で考える場合、

              O
             O#O
            OLLLO
           OLLELLO
          O#LEHEL#O
           OLLELLO
            OLLLO
             O#O
              O

#で示した"L"から"O"へ進むパターンは3通り、それ以外の"L"については2通りになります。そして#で示したLへ至るパターンは4通りしかなく、それ以外のLへ至るパターンは、一文字前の結果から4を引くことで求まります。

class WordPattern {
   public:
   long long countWords(string word)
  {
    if (word.size() == 1)
      return 1;
    else if (word.size() == 2)
      return 4;

    long long ret[word.size()+1];

    ret[1] = 1;
    ret[2] = 4;

    for (int i=3; i<=word.size(); i++)
      ret[i] = 4*3 + (ret[i-1] - 4)*2;

    return ret[word.size()];
  }
};

Hard - BitStrings

BitStrings(1と0からのみ構成される文字列)の集合と、0, 1の個数が与えられる。BitString集合の各要素をつなげて文字列を作る。できた文字列の0, 1の個数が与えられた数値以下のものの中から、使った要素数の最大値を求めよ。

はじめナップザック問題のdpでの解法を応用できないか考えたのですが、うまく思いつきませんでした。editorialを見たところ、brute forceでも解けるようなのですが、練習のためdpで解きました。BitStringのリストを最初から順に調べていき、テーブルを更新していくアプローチです。

class BitStrings {
public:
  int maxStrings(vector <string> list, int numZeroes, int numOnes)
  {
    int ret = 0;
    int dp[numZeroes+1][numOnes+1];
    int tmpdp[numZeroes+1][numOnes+1];
    vector <vector <int> > items;

    memset(dp, 0, sizeof(dp));

    for (unsigned int i=0; i<list.size(); i++)
      {
	vector <int> tmp(2, 0);
	for (unsigned int j=0; j<list[i].size(); j++)
	  if (list[i][j] == '0')
	    tmp[0]++;
	  else
	    tmp[1]++;
	items.push_back(tmp);
      }

    for (unsigned int i=0; i<list.size(); i++)
      {
	memset(tmpdp, 0, sizeof(tmpdp));

	if (items[i][0] <= numZeroes && items[i][1] <= numOnes && dp[items[i][0]][items[i][1]] < 1)
	  tmpdp[items[i][0]][items[i][1]] = 1;

	for (int nz=0; nz<=numZeroes; nz++)
	  for (int no=0; no<=numOnes; no++)
	    if (dp[nz][no] > 0)
	      {
		if (nz + items[i][0] <= numZeroes &&
		    no + items[i][1] <= numOnes &&
		    dp[nz][no] + 1 > dp[nz + items[i][0]][no+items[i][1]])
		  tmpdp[nz + items[i][0]][no + items[i][1]] = dp[nz][no] + 1;
	      }

	for (int j=0; j<=numZeroes; j++)
	  for (int k=0; k<=numOnes; k++)
	    if (tmpdp[j][k] > 0)
	      dp[j][k] = max(tmpdp[j][k], dp[j][k]);
      }

    for (int i=0; i<=numZeroes; i++)
      for (int j=0; j<=numOnes; j++)
	ret = max(dp[i][j], ret);

    return ret;
  }
};

2009-10-06

SRM178 div2

20:06

Easy - SimpleCalculator

四則演算がstring形式で与えられるので、計算してintで返す問題。

作っておいたsplit関数を使う。雑だけど早く解けたしまあいいかということで。

class SimpleCalculator {
public:
  int toInt(string s) {int r = 0; istringstream ss(s); ss >> r; return r;}

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

  int calculate(string input)
  {
    int ret = 0;
    string del;

    for (int i=0; i<input.size(); i++)
      if (input[i] == '+' || input[i] == '-' || input[i] == '*' || input[i] == '/')
	del = input[i];

    vector <int> tmp = split(input, del);

    if (del == "+")
      ret = tmp[0] + tmp[1];
    else if (del == "-")
      ret = tmp[0] - tmp[1];
    else if (del == "*")
      ret = tmp[0] * tmp[1];
    else if (del == "/")
      ret = tmp[0] / tmp[1];

    return ret;
  }
};

Medium - TeXLeX

パターンマッチとかをする問題なんですが、アルゴリズムは簡単なんだけど実装するのが非常にめんどうというタイプのものでした。ちょっと今回はパス。

Hard - BadSubstring

長さ lenngth の文字列(a, b, cの三文字からのみ構成される)のうち、部分文字列"ab"を含まないものは何種類あるか。ただし、空文字列と文字列全体も部分文字列としてカウントする。例えばlength=2だと、(aa, ac, ba, bb, bc, ca, cb, cc)の8種類。

DPで解きました。次のように定式化しました。まず、length=0のとき、解f(0)は1(空文字列)。length=1のとき、解f(1)は3。length=n (n>=2)のときは、f(n) = f(n-2) * 2 + (f(n-1) - f(n-2)) * 3 となります。考え方としては、最後がaで終わる文字列のときは、次はaかcの2種類が続く、そうでないときはabcの3種類が続くというのがアイデアです。length=nの文字列のうち、n-1文字目がaで終わるものの数は、f(n-2)個あります。よってf(n-2)には2を掛け、残り(f(n-1) - f(n-2))のものには3を掛けます。

class BadSubstring {
public:
  long long howMany(int length)
  {
    long long l[length+1];
    l[0] = 1;
    l[1] = 3;

    for (int i=2; i<=length; i++)
      l[i] = l[i-2]*2 + (l[i-1] - l[i-2])*3;

    return l[length];
  }
};

2009-10-05

SRM408 div2 続き

09:13

Easy - TournamentJudging

昨日の続き。赤い玉が青い玉の2倍以上あった場合、プレイヤーは敗北するという規則を導入することで、メモのサイズを2001 x 4001に削減することができます。doubleは8バイトなので、 2001*4001*8/1024/1024 = 61.080940246582 となり、64MBにぎりぎり収まります。これで無事解くことができました。

class MarblesInABag {
public:
  double m[2001][4001]; // modified

  double r(int red, int blue)
  {
    double ret = 0;

    if (red > 2000 || red>blue)  // modified
      return 0;

    if (m[red][blue] != -1)
      return m[red][blue];

    ret += ((double)blue/(red+blue)) * r(red, blue-2);
    if (red >= 1)
      ret += ((double)red/(red+blue)) * r(red-1, blue-1);

    m[red][blue] = ret;

    return ret;
  }

  double getProbability(int redCount, int blueCount)
  {
    for (int i=0; i<2001; i++)
      for (int j=0; j<4001; j++)
	m[i][j] = -1;

    m[0][1] = 1;

    return r(redCount, blueCount);
  }
};

2009-10-04

SRM408 div2

01:28

Easy - TournamentJudging

同じ長さの数列 rawScores と conversionFactor が与えられるので、 rawScores[i]/conversionFactor[i] (小数点以下は四捨五入)の総和を求めよ。

四捨五入はその数値に0.5を加え、小数点以下を切り捨てることで実現できます。

class TournamentJudging {
public:
  int getPoints(vector <int> rawScores, vector <int> conversionFactor)
  {
    int ret = 0;

    for (int i=0; i<rawScores.size(); i++)
      {
	double d = (double)rawScores[i]/conversionFactor[i];
	ret += (int)(d+0.5);
      }

    return ret;
  }
};

Medium - OlympicCandles

毎日キャンドルに灯をともす。灯をともすキャンドルの数は、1日目は1本、2日目は2本、...、n日目はn本。キャンドルの灯は毎日消すが、一度つけるごとに長さが1減る。キャンドルの長さを表す数列 candles が与えられるので、これらのキャンドルで何日間上記の作業をできるか求める。

できるだけ長いキャンドルから灯をつけていくという、greedyっぽいアルゴリズムで大丈夫です。

class OlympicCandles {
  int getArriveCandleNum(vector <int> candles)
  {
    int ret = 0;

    for (int i=0; i<candles.size(); i++)
      if (candles[i] > 0)
	ret++;

    return ret;
  }

public:
  int numberOfNights(vector <int> candles)
  {
    int ret = 0;

    while (getArriveCandleNum(candles) >= ret+1)
      {
	ret++;

	sort(candles.rbegin(), candles.rend());

	for (int i=0; i<ret; i++)
	  candles[i]--;
      }

    return ret;
  }
};

Hard - MarblesInABag

袋に赤と青の玉が入っており、そこから玉を取り出すゲームをする。自分は赤と青の玉全体から同確率で玉を引き、相手は必ず青い玉を引く。最後に袋から取り出される玉が青ならば自分が勝ち、そう出なければ相手の勝ち。ゲームは自分が先攻ではじまる。赤青両方の玉の個数が与えられた場合、自分が勝つ確率を求める。

メモ化再帰でのアプローチを試みたんですが、一部のテストケースで落ちてしまいます。bad_allocの例外が出ているので、メモに使っているmapが巨大になり、メモリが確保できなくなったのではないかと予想しています。またそれ以前に、ローカルで試したところ時間がかかっているので、メモリがもっとあってもTLEになると思います。別のアプローチを考える必要があるようです。

ちなみに、再帰関数は毎回青をとった場合、赤をとった場合それぞれについて計算しています。メモは最初double memo[4001][4001]という配列を使おうとしましたが、大きすぎて使えなかったのでmapにしています。しかしこれでも結局メモリの上限(確か64M)に達してしまうようです。

一応エラーメッセージもはっておきます。

terminate called after throwing an instance of 'std::bad_alloc'
what():  St9bad_alloc
class MarblesInABag {
public:
  map <pair <int, int>, double>m;

  double r(int red, int blue)
  {
    double ret = 0;

    if (red>blue)
      return 0;

    if (m.find(make_pair(red, blue)) != m.end())
      return m[make_pair(red, blue)];

    ret += ((double)blue/(red+blue)) * r(red, blue-2);
    if (red >= 1)
      ret += ((double)red/(red+blue)) * r(red-1, blue-1);

    m[make_pair(red, blue)] = ret;

    return ret;
  }

  double getProbability(int redCount, int blueCount)
  {
    m[make_pair(0, 1)] = 1;

    return r(redCount, blueCount);
  }
};


SRM156 div2

12:35

Hard - WordParts

originalとcompoundの二つの文字列が与えられる。compoundをいくつかのサブ文字列に分割し、かつ全てのサブ文字列がoriginalのprefixかsuffixになるようにしたい。分割に仕方の最小を求める。

Editorialを見ながら再帰+メモ化で解きました。ポイントは最初にprefixとsuffixを全部詰め込んだ辞書を作ることと、compound文字列の位置だけを持ち回す再帰関数を使う点だと思います。

あと、なぜかローカルのテストでテストケース6だけが、返り値14となって落ちていました。サーバでは正常に意図した値を返しています。テストのコードはTZTesterが自動生成したものそのままです。原因がまだわからず、これで時間を取られました。

class WordParts {
public:
  string comp;
  vector <string> dic;
  int m[100];

  int r(int pos)
  {
    int & ret = m[pos];

    if (m[pos] != -1)
      return m[pos];

    if (pos == comp.size())
      return 0;

    ret = 10000;

    for (int i=0; i<dic.size(); i++)
      if (comp.substr(pos, dic[i].size()) == dic[i])
	ret = min(ret, 1 + r(pos+dic[i].size()));

    return ret;
  }

  int partCount(string original, string compound)
  {
    int ret = 0;
    comp = compound;
    memset(m, -1, sizeof(m));

    for (int i=0; i<original.size(); i++)
      {
	if (i != 0)
	  dic.push_back(original.substr(0, i));
	dic.push_back(original.substr(i));
      }
 
    ret = r(0);

    if (ret > 1000)
      ret = -1;

    return ret;
  }
};

2009-10-01

2003 TCCC Round 4

17:46

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

Easy - ChessMetric

サイズ可変のチェスのボードを考える。Kingknightという特別な駒があり、以下のようにキングとナイトの動きができる。

   .......
   ..L.L..
   .LXXXL.
   ..XKX..
   .LXXXL.
   ..L.L..
   .......

スタート、ゴール地点と整数nが与えられるので、ちょうどn回でスタートからゴールへ行く行き方は何通りか求めよ。

チェスボードと同じサイズの配列を用意し、各要素はそのマスへ移動できる方法が何通りあるかを記録するようにする。n=1から順に繰り返すことで求めることができる。

class ChessMetric {
public:
  bool isInRange(int x, int y, int size)
  {
    bool ret = false;

    if (0 <= x && x < size && 0 <= y && y < size)
      ret = true;

    return ret;
  }

  long long howMany(int size, vector <int> start, vector <int> end, int numMoves)
  {
    long long board[size][size];
    long long tmpboard[size][size];
    memset(board, 0, sizeof(board));
    memset(tmpboard, 0, sizeof(tmpboard));
    int dirx[16] = {-1, 1, -2, -1, 0, 1, 2, -1, 1, -2, -1, 0, 1, 2, -1, 1};
    int diry[16] = {-2, -2, -1, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 1, 2, 2};
    board[start[0]][start[1]] = 1;

    for (int cmove=0; cmove<numMoves; cmove++)
      {
	memset(tmpboard, 0, sizeof(tmpboard));
	for (int x=0; x<size; x++)
	  for (int y=0; y<size; y++)
	    if (board[x][y] != 0)
	      {
		for (int i=0; i<16; i++)
		  {
		    int curx = x + dirx[i];
		    int cury = y + diry[i];
		    if (isInRange(curx, cury, size))
		      tmpboard[curx][cury] += board[x][y];
		  }
	      }

	for (int x=0; x<size; x++)
	  for (int y=0; y<size; y++)
	    board[x][y] = tmpboard[x][y];
      }

    return board[end[0]][end[1]];
  }
};