Hatena::Grouptopcoder

cou929のTopCoder日記

2009-06-24

SRM443 div2

12:43

さくさく解けて、チャレンジ一勝一敗。ratingは100ほど上がり、緑色になることができました。

Easy - SoccerLeagues

サッカーの総当たり戦の試合結果から、各チームの得点を計算する問題。計算方法は買った場合勝ち点3、ドローの場合は1、負けた場合は0という、現実世界と同様のもの。

これは解くだけの問題でした。チャレンジできそうなポイントも特にないので、次にいきます。

class SoccerLeagues {
public:
  vector <int> points(vector <string> matches)
  {
    vector <int> ret;

    for (int i=0; i<matches.size(); i++)
      {
	int tmp = 0;
	for (int j=0; j<matches.size(); j++)
	  {
	    if (matches[i][j] == 'D')
	      tmp += 1;
	    else if (matches[i][j] == 'W')
	      tmp += 3;

	    if (matches[j][i] == 'D')
	      tmp += 1;
	    else if (matches[j][i] == 'L')
	      tmp += 3;
	  }
	ret.push_back(tmp);
      }
    return ret;
  }
};

Medium - CirclesCountry

2次元座標系上に、始点と終点が与えられている。この座標系上には、最大50個の円がある。始点から終点までを、円との交点の数が最小になるように、線でつなぎ、その交点の数を返す。

始点、終点それぞれについて、その点を覆っている円の数を数え、その合計を返す。ただし、両方の点を含んでいる円は除外。

550点問題だったので警戒していたのですが、さほど難しくはありませんでした。「両方の点を含んでいる円は除外する」という条件のチェックがテストケースに含まれていなかったので、これでチャレンジしようと待ち構えていたんですが、この条件でミスしていたのは、1,2人しかいませんでした。結局チャレンジは1回ミス(手違いによるもの)、1回成功で、+25点でした。ミスが悔やまれます。

class CirclesCountry {
public:
  int leastBorders(vector <int> X, vector <int> Y, vector <int> R, int x1, int y1, int x2, int y2)
  {
    vector <int> powR;
    int ret = 0;

    for (int i=0; i<R.size(); i++)
      powR.push_back(R[i] * R[i]);

    for (int i=0; i<R.size(); i++)
      {
	bool flg1 = false, flg2 = false;
	int x = X[i] - x1;
	int y = Y[i] - y1;
	if (powR[i] > (x*x + y*y))
	  flg1 = true;

	x = X[i] - x2;
	y = Y[i] - y2;
	if (powR[i] > (x*x + y*y))
	  flg2 = true;

	if (!(flg1 && flg2) && !(!flg1 && !flg2))
	  ret++;
      }

    return ret;
  }
};

2009-06-22

SRM323 div2

00:36

Easy - IrreducibleNumber

整数集合Aが与えられる。Aの要素の1つ以上の和で表されない整数をIrreducible numberと呼ぶ。与えられたAのもとで、最小のIrreducible numberを求めよ。

Aの大きさが高々3なので、すべての非Irreducible numberを列挙し、1からインクリメントしながら探索しました。

class IrreducibleNumber {
public:
  int getIrreducible(vector <int> A)
  {
    if (A.size() != 1)
      {
	if (A.size() == 2)
	  A.push_back(0);

	A.push_back(A[0]+A[1]);
	A.push_back(A[0]+A[2]);
	A.push_back(A[1]+A[2]);
	A.push_back(A[0]+A[1]+A[2]);
      }

    int i;
    for (i=1; i<500; i++)
      if (find(A.begin(), A.end(), i) == A.end())
	break;

    return i;
  }
};

Medium - RoadsAndFools

整数集合frontSidesが与えられる。frontSidesの各要素は、frontSides[i]またはlength - frontSides[i]という値をとりうる。frontSidesが昇順となるように、各要素の値を設定する。ただし、解が複数ある場合は"MULTIPLE SOLUTIONS"、解がない場合は"NO SOLUTION"を返す。

まず、昇順に並べる。できなければ"NO SOLUTION"を返す。次にforntSidesの各要素に対して、値をもう一方に変更しても、昇順のオーダーが成り立つかを調べる。成り立った場合、解が複数になるので、"MULTIPLE SOLUTIONS"を返す。

class RoadsAndFools {
public:
  string toStr(int n) {ostringstream ss; ss << n; return ss.str();}

  string determineOrientation(int length, vector <int> frontSides)
  {
    frontSides[0] = min(frontSides[0], length - frontSides[0]);
    for (int i=1; i<frontSides.size(); i++)
      {
	bool ok1 = false, ok2 = false;
	if (frontSides[i-1] < frontSides[i])
	  ok1 = true;
	if (frontSides[i-1] < (length - frontSides[i]))
	  ok2 = true;

	if (ok2)
	  frontSides[i] = length - frontSides[i];

	if (ok1 && ok2)
	  frontSides[i] = min(frontSides[i], length - frontSides[i]);

	if (!ok1 && !ok2)
	  return "NO SOLUTION";
      }

    vector <int> tmp = frontSides;
    tmp.insert(tmp.begin(), -1);
    tmp.push_back(1001);

    for (int i=1; i<tmp.size()-1; i++)
      {
	bool ok1 = false, ok2 = false;
	if (tmp[i-1] < tmp[i] && tmp[i] < tmp[i+1])
	  ok1 = true;
	if (tmp[i-1] < (length - tmp[i]) && (length - tmp[i]) < tmp[i+1])
	  ok2 = true;

	if (ok1 && ok2 && (tmp[i] != length - tmp[i]))
	  return "MULTIPLE SOLUTIONS";
      }

    string ret = "";

    for (int i=0; i<frontSides.size(); i++)
      {
	ret += toStr(frontSides[i]);
	ret += " ";
      }

    ret.erase(ret.end()-1);

    return ret;
  }
};

2009-06-18

SRM426 div2

00:42

Easy - KnockoutTourney

トーナメント戦の組み合わせで、自分とライバルの位置が与えられる。自分とライバルは全勝すると仮定して、2人が対戦するのは何回戦目か。

250点にしては非常に難しい問題でした。方針としては、自分とライバルがぶつかるまで、一回戦ずつ進めていく(参加者を半分にしていく)という方法です。

僕の実装だと非常に長くなってしまったのですが、他の人のコードを見てみると、とてもシンプル(whileの中が4行くらい)でした。自分の位置のインデックスと、ライバルの位置のインデックスのみをどんどん2分の1にしていくという戦略で実装されていました。

class KnockoutTourney {
public:
  int meetRival(int N, int you, int rival)
  {
    vector <int> v(N);
    int ret = 0;

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

    v[--you] = 1;
    v[--rival] = 1;

    while(v.size() > 1)
      {
	ret++;

	bool flg = false;
	for (int i=0; i<v.size()-1; i++)
	  if (v[i] == 1 && v[i+1] == 1 && i % 2 == 0)
	    flg = true;

	if (flg)
	  break;

	vector <int> tmp;
	for (int i=0; i<v.size(); i+=2)
	  {
	    if (v[i] == 1 || ((i + 1) < v.size() && v[i+1] == 1))
	      tmp.push_back(1);
	    else
	      tmp.push_back(0);
	  }

	v.clear();
	v = tmp;
      }
    
    return ret;
  }
};

Medium - ShufflingMachine

カードをシャッフルして配る機会がある。あるプレイヤーにとって、シャッフルの仕方と、シャッフルする前のカードの並び、シャッフル後のデッキのうち、どの位置のカードが自分に配られるかが既知である。シャッフルが行われる回数は、上限値のみがわかっている。プレイヤーは何枚かの欲しいカードがある。プレイヤーが最も多く、欲しいカードを得られるような、最初のデッキの並びを考え、その際の期待値を求めよ。

まず、問題を理解するのに非常に手間取り、一時間くらいかかってしまいました。理解ができてしまったあとは、なんとか解法を考えつくことができました。まず、1からmaxChufflesまで、それぞれの回数シャッフルした際のカードの動きを調べます。カードの動きは既知なのでこれは簡単に求まります。次に、それぞれのシャッフル後のデッキの状態のうち、プレイヤーに配られる位置にあるカードを全て調べ、その出現頻度を調べます。そして頻度が高い方からK個選択します。これを欲しいカードのデッキの初期位置とします。最後に、この初期位置の場合の期待値を計算します。

class ShufflingMachine {
public:
  double stackDeck(vector <int> shuffle, int maxShuffles, vector <int> cardsReceived, int K)
  {
    vector <vector <int> > v;
    vector <int> t;
    vector <pair <int, int> > freq;
    vector <int> initPos;

    for (int i=0; i<shuffle.size(); i++)
      {
	t.push_back(i);
	pair <int, int> t;
	t.first = 0;
	t.second = i;
	freq.push_back(t);
      }

    for (int i=0; i<maxShuffles; i++)
      {
	vector <int> tmp;
	for (int j=0; j<shuffle.size(); j++)
	  tmp.push_back(t[shuffle[j]]);

	v.push_back(tmp);
	t = tmp;
      }

    for (int i=0; i<cardsReceived.size(); i++)
      for (int j=0; j<v.size(); j++)
	freq[v[j][cardsReceived[i]]].first++;

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

    for (int i=0; i<K; i++)
      initPos.push_back(freq[i].second);

    int times = 0;

    for (int i=0; i<v.size(); i++)
      for (int j=0; j<cardsReceived.size(); j++)
	for (int k=0; k<initPos.size(); k++)
	  if (v[i][cardsReceived[j]] == initPos[k])
	    {
	      times++;
	      break;
	    }

    return (double)times / maxShuffles;
  }
};

HeenaHeena2012/07/10 07:49There's nothing like the reelif of finding what you're looking for.

buznuqjgiqibuznuqjgiqi2012/07/10 16:369Ujmvh <a href="http://bgchrdnvpdym.com/">bgchrdnvpdym</a>

bripvlbripvl2012/07/11 21:03uHsbJQ , [url=http://jhcjmhwqsjjh.com/]jhcjmhwqsjjh[/url], [link=http://kjrzktweurvn.com/]kjrzktweurvn[/link], http://dykufbeabimp.com/

ovaiywlspovaiywlsp2012/07/12 12:48ZpKj0w <a href="http://dyuonldrlwpz.com/">dyuonldrlwpz</a>

dfjilezsdfjilezs2012/07/12 18:21IYJBBP , [url=http://nscyjwrnojsl.com/]nscyjwrnojsl[/url], [link=http://rzqdhfqoezvv.com/]rzqdhfqoezvv[/link], http://rpdppxuoljli.com/

2009-06-16

SRM324 div2

20:10

Easy - Alliteration

単語のベクタが与えられる。各単語の先頭の一文字が連続して同じだった場合、Alliterationという。ベクタにはいくつのAlliterationがあるか。

やるだけの問題なんですが、どういうアルゴリズムにしようか悩んでいるうちに、結構時間が経ってしました。結局スコアが180点台になってしまいました。

class Alliteration {
public:
  int count(vector <string> words)
  {
    int ret = 0;
    char c = words[0][0];
    bool flg = false;

    for (int i=1; i<words.size(); i++)
      {
	char cc = words[i][0];
	if (c  == cc || c - 'a' == cc - 'A' || c - 'A' == cc - 'a')
	  flg = true;
	else
	  {
	    if (flg)
	      ret++;
	    flg = false;
	  }
	c = cc;
      }

    if (flg)
      ret++;

    return ret;
  }
};

Medium - PalindromeDecoding

問題文で説明されている方法で、文字列を操作するだけの問題。先ほどとはうってかわって、あまりにも簡単な問題でした。とくにひっかけもなくシステムテストを通っちゃうし。string型の練習問題みたいでした。

class PalindromeDecoding {
public:
  string decode(string code, vector <int> position, vector <int> length)
  {
    for (int i=0; i<position.size(); i++)
      {
	string sub;
	sub = code.substr(position[i], length[i]);
	reverse(sub.begin(), sub.end());
	code.insert(position[i] + length[i], sub);
      }

    return code;
  }
   

};

2009-06-14

SRM442 div2

11:06

250、500点問題ともに比較的簡単でした。よってチャレンジも、僕の部屋では一回もありませんでした。よって当たり前のところをより早く正確にやる必要のある回だったと思います。

Easy - SimpleWordGame

プレイヤーの持つワードの集合と辞書が与えられる。プレイヤーのワードのうち、辞書にあるものの長さの総和を求めよ。ただし、プレイヤーのワードの重複は1回とカウントし、またワードの長さはワードの文字数の自乗とする。

プレイヤーのワードの重複を取り除き、辞書にあるか調べ、長さを計算していきます。そのままやるだけの問題でした。

class SimpleWordGame {
public:
  int points(vector <string> player, vector <string> dictionary)
  {
    set <string> s;
    int ret = 0;

    for (int i=0; i<player.size(); i++)
      s.insert(player[i]);

    for (set <string>::iterator i=s.begin(); i!=s.end(); i++)
      {
	if (find(dictionary.begin(), dictionary.end(), *i) != dictionary.end())
	  {
	    string t = *i;
	    ret += t.size() * t.size();
	  }
      }

    return ret;
  }
};

Medium - Underprimes

整数AからBの範囲にある、underprimeの数を求める。整数Xが、任意個の素数の積で表現でき、かつその素数の数が素数個であった場合、Xはunderprimeであると定義する。

まず昇順の素数の集合を用意する。AからBの範囲の整数Xを一つずつ走査する。Xについて、素数集合を小さい方からループさせながら割っていく。もし最後まで素数のみで割り切れた場合、個数が素数かどうかチェックする。

prime factorizationの計算を、だいたいlog(n)と考えて、計算量がワーストケースで100000 * log(100000)だからなんとかなるかなと実装しました。

class Underprimes {
public:
  bool isPrime(int n)
  {
    if (n < 2)
      return false;

    if (n != 2 && n % 2 == 0)
      return false;

    int s = sqrt(n);

    for (int i=3; i<=s; i++)
      if (n % i == 0)
	return false;

    return true;
  }

  int howMany(int A, int B)
  {
    vector <int> primes;
    int ret = 0;

    for (int i=2; i<=50000; i++)
      if (isPrime(i))
	primes.push_back(i);

    for (int i=A; i<=B; i++)
      {
	int count = 0;
	int t = i;
	while (t != 1)
	  {
	    bool flg = false;
	    for (int j=0; j<primes.size(); j++)
	      if (t % primes[j] == 0)
		{
		  t /= primes[j];
		  count++;
		  flg = true;
		  break;
		}

	    if (!flg)
	      {
		count = 0;
		break;
	      }
	  }

	if (isPrime(count))
	  ret++;
      }

    return ret;
  }
};

Hard - EqualTowers

異なる高さのブロックがいくつか与えられる。ブロックを積み上げて2つのタワーを作りたい。2つのタワーの高さが同じ場合、最大の高さはどれだけになるか。ただし全てのブロックを使い切らなくても良い。また同じ高さのタワーを作れない場合は-1を返す。

brute- forceに解いた場合。最大で3^50個のケースを探索しないといけないため、時間に間に合いません。DPなどを使う必要がありそうですが、慣れてないので時間内に実装できる自信がありませんでした。よって、前者のbrute-forceな方法で、暫定解より悪い場合や、解が上界を超えている場合などに枝狩りして、なんとか計算量をへらせないかなあととりあえず実装してみました。

案の定、この実装では最悪のケースでTLEです。とりあえずDPは早々に慣れておきたいです。

class EqualTowers {
  int ret;
  int opt;
  vector <int> b;
  vector <int> dif;

  int s(int A, int B, int n)
  {
    if (n == b.size())
      {
	if (A != 0 && B != 0 && A == B)
	  ret = max(ret, A);
	return 0;
      }

    if (max(A, B) > opt)
      return 0;

    if (dif[n] != 0 && min(A, B) + dif[n] < max(A, B))
      return 0;

    if (max(A, B) + dif[n]/2 < ret)
      return 0;

    s(A, B, n+1);
    s(A+b[n], B, n+1);
    s(A, B+b[n], n+1);

    return 0;
  }

  int height(vector <int> bricks)
  {
    int sum = 0;
    ret = 0;
    b = bricks;

    dif.push_back(0);

    for (int i=bricks.size()-1; i>0; i--)
      {
	sum += bricks[i];
	dif.push_back(sum);
      }

    reverse(dif.begin(), dif.end());

    sum += bricks[0];
    opt = sum / 2;

    s(0, 0, 0);

    if (ret == 0)
      ret = -1;
    
    return ret;
  }
};

2009-06-11

SRM425 div2

18:39

Easy - InverseFactoring

整数nの約数で、1とn以外のものをproper factorと定義する。proper factorの配列が渡されるので、整数nを求める。

250点にしては、かなり難しい問題でした。僕は一度システムテストに落ち、その後正しい解答にたどり着くまで時間がかかってしまいました。

戦略としては、引数のproper factorのうち、最大のものの倍数を解の候補として、小さい方から調べていきます。各々の解の候補について、proper factorを算出し、それが引数とまったく同じならば正解という方法です。

一応この方法でもできたのですが、他の人は、引数のproper factorのうち、最大値と最小値の積をとるだけという方法で解いていました。editorialに証明が書いてあったのですが、いまいち理解できませんでした。

class InverseFactoring {
public:
  int getTheNumber(vector <int> factors)
  {
    int ret;

    sort(factors.begin(), factors.end());
    int maxi = factors[factors.size()-1];

    for (int t=2; ; t++)
      {
	ret = maxi*t;
	vector <int> props;
	for (int i=2; i*2<=ret; i++)
	  {
	    if (ret % i == 0)
	      props.push_back(i);
	  }

	bool ok = true;
	for (int i=0; i<min(props.size(), factors.size()); i++)
	  if (props.size() != factors.size() || props[i] != factors[i])
	    {
	      ok = false;
	      break;
	    }

	for (int i=0; i<factors.size(); i++)
	  if (factors[i] == ret)
	    {
	      ok = false;
	      break;
	    }

	if (ok)
	  break;
      }

    return ret;
  }
};

Medium - CrazyBot

2次元グリッド上を動くロボットがいる。ロボットは東西南北に1マスずつ進み、それぞれの方向に進む確率が与えられる。ロボットがnステップ進む際、一度も同じマスを通らない確率を求める。

nが14と割と小さいので、シンプルなDFSで実装し、うまくいきました。一度通ったマスがあった場合探索を取りやめると、計算量がかなり削減できます。木の探索も以前に比べれば書けるようになってきたのですが、もっとシンプルに早く書けるようになりたいです。

class CrazyBot {
public:
  map <pair <int, int>, bool> visited;
  int N;
  double ret;
  double ea, we, so, no;

  int s(double p, int walk, pair <int, int> cur)
  {
    if (visited.find(cur) != visited.end())
      return 0;

    if (walk == N)
      {
	ret += p;
	return 0;
      }

    visited[cur] = true;
    pair <int, int> tmp = cur;
    if (ea != 0)
      {
	tmp = cur;
	tmp.first++;
	s(p*ea, walk+1, tmp);
      }

    if (we != 0)
      {
	tmp = cur;
	tmp.first--;
	s(p*we, walk+1, tmp);
      }

    if (so != 0)
      {
	tmp = cur;
	tmp.second--;
	s(p*so, walk+1, tmp);
      }

    if (no != 0)
      {
	tmp = cur;
	tmp.second++;
	s(p*no, walk+1, tmp);
      }

    visited.erase(cur);

    return 0;
  }

  double getProbability(int n, int east, int west, int south, int north)
  {
    N = n;
    ret = 0;
    ea = (double)east/100, we = (double)west/100, so = (double)south/100, no = (double)north/100;

    pair <int, int> start;
    start.first = 0;
    start.second = 0;
    s(1, 0, start);    

    return ret;
  }
};

2009-06-10

SRM325 div2

12:53

Easy - SalaryCalculator

給与の計算方法と目標給与が与えられ、それを達成するには最短何時間働く必要があるかを求める。ほぼ問題文を実装するだけの問題。

class SalaryCalculator {
public:
  double calcHours(int P1, int P2, int salary)
  {
    double ret = 0;
    if (salary <= P1 * 200)
      {
	ret = (double)salary/P1;
      }
    else
      {
	double diff = salary - 200*P1;
	ret = 200 + diff/P2;
      }
    return ret;
  }
};

Medium - RGBStreet

通りに並ぶ家をペイントする。色はRGBの4色。隣り合う家は同じ色にしてはいけない。また各家ごとに、RGBそれぞれの色に塗るコストが与えられる。この条件のもと、最小のコストを求める。

枝が3本(RGB)ずつの木を縦型探索する問題として考えました。計算量を減らすために、暫定解より結果が悪ければ、それ以下の枝の探索を打ち切るようにしました。

class RGBStreet {
public:
  int mini;
  vector <string> houses;

  int s(int _rgb, int n, int cost)
  {
    int rgb[3];

    if (n == houses.size())
      {
	mini = min(mini, cost);
	return 0;
      }

    sscanf(houses[n].c_str(), "%d %d %d", &rgb[0], &rgb[1], &rgb[2]);

    for (int i=0; i<3; i++)
      {
	if (i != _rgb)
	  {
	    int tmp = rgb[i] + cost;
	    if (cost < mini)
	      s(i, n+1, tmp);
	  }
      }
    return 0;
  }

  int estimateCost(vector <string> _h)
  {
    mini = 1000*20;
    houses = _h;

    s(4, 0, 0);

    return mini;
  }
};

2009-06-08

SRM424 div2

16:45

久しぶりのtopCoder過去問練習。先週はなぜか(tcoが原因?)srmのpractice roomがしまっていたので、できませんでした。

Easy - MagicSpell

文字列の中から'A', 'Z'のみをリバースする。特に問題なし。

class MagicSpell {
public:
  string fixTheSpell(string spell)
  {
    string AZ = "";
    for (int i=0; i<spell.size(); i++)
      if (spell[i] == 'A' || spell[i] == 'Z')
	AZ += spell[i];

    reverse(AZ.begin(), AZ.end());

    int j = 0;
    for (int i=0; i<spell.size(); i++)
      if (spell[i] == 'A' || spell[i] == 'Z')
	{
	  spell[i] = AZ[j];
	  j++;
	}

    return spell;
  }
};

Medium - ProductOfDigits

各数値の積がNとなる最小の整数の桁数を返す問題。途中つまったので、editorialをみながら。ポイントはメモ化ですね。

class ProductOfDigits {
public:
  map <int, int> memo;

  int s(int N)
  {
    int res;

    if (N < 10)
      return 1;

    if (memo.find(N) != memo.end())
      return memo[N];

    res = 10000;
    for (int i=2; i<=9; i++)
      if (N % i == 0)
	res = min(res, s(N/i) + 1);

    memo[N] = res;

    return res;
  }

  int smallestNumber(int N)
  {
    int ret = 0;

    ret = s(N);

    return (ret == 10000) ? -1 : ret;
  }
};