Hatena::Grouptopcoder

cou929のTopCoder日記

2009-05-29

SRM423 div2

16:10

Easy - TheSimpleGame

n x n の盤上で、全ての駒を4角のどこかに移動させるには、最短で何手かかるか。駒の移動は一手で上下左右に1マス移動できる。

与えられたそれぞれの駒の初期位置から、4角すべてにかかる手数を調べ、その中から最小値を選択していきます。

class TheSimpleGame {
public:
  int count(int n, vector <int> x, vector <int> y)
  {
    int ret = 0;
    int corners[4][2] = {{1, 1}, {1, n}, {n, 1}, {n, n}};

    for (int i=0; i<x.size(); i++)
      {
	int t = n*n;
	for (int j=0; j<4; j++)
	  {
	    int tmp = abs(corners[j][0] - x[i]);
	    tmp += abs(corners[j][1] - y[i]);
	    t = min(t, tmp);
	  }
	ret += t;
      }

    return ret;
  }
};

Medium - TheTower

上の問題と同様の条件(ただし盤の広さが無限)を考える。N個の駒の初期位置が与えられた場合、1からN個の駒が同じ位置に集まる際に必要な最短の手数を、それぞれ求める。

わからなかったので、editorialを参考に解きました。ポイントは全ての2駒間の距離を調べ、昇順にソートするところです。ソートの結果を1つずつ足していくことで、その駒を起点とした0からNまでの最小の手数を求められます。

class TheTower {
public:
  vector <int> count(vector <int> x, vector <int> y)
  {
    vector <int> ret;

    for (int i=0; i<x.size(); i++)
      ret.push_back(1000000000);

    for (int i=0; i<x.size(); i++)
      for (int j=0; j<y.size(); j++)
	{
	  vector <int> dists;
	  for (int k=0; k<x.size(); k++)
	    dists.push_back(abs(x[i] - x[k]) + abs(y[j] - y[k]));

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

	  int sum = 0;
	  for (int k=0; k<x.size(); k++)
	    {
	      sum += dists[k];
	      ret[k] = min(ret[k], sum);
	    }
	}

    return ret;
  }
};

2009-05-28

SRM441 div2

16:18

始まる前に少し寝ておこうと思い、仮眠をとったのですが、開始時間を20分くらい寝過ごしてしまいました。でもトラブルがあり開始が遅れたらしく、寝過ごしの影響が少なくなりラッキーでした。

頭が回っていなくて、250点問題は時間がかかってしまいました。500点問題はチャレンジ成功されました。最終的にはスコアが10点くらいアップしました。

Easy - DifferentStrings

文字列A, Bの間の、異なる文字の個数を求める問題。

Aを1文字ずつスライドさせながらBと比較し、異なっている文字数を求め、それぞれの結果の中から最小値を返します。

class DifferentStrings {
public:
  int minimize(string A, string B)
  {
    int ret = 1000000;

    for (int i=0; i<=B.size() - A.size(); i++)
      {
	int len = 0;
	for (int j=0; j<A.size(); j++)
	  {
	    if (A[j] != B[i+j])
	      len++;
	  }
	ret = min(len, ret);
      }

    return ret;
  }
};

Medium - PaperAndPaintEasy

紙を折り畳んでいき、その一部を切り抜く(色を塗る)。その後紙を広げたときに、切り抜かれていない部分の面積を求める。

まず紙を折り畳み、必要なセルに色を塗ります。色を塗ったそれぞれのセルについて、広げたときに何倍の個数になるかを計算していきます。考慮すべき点は、

  • xfoldがwidthの半分を超えているかどうか。
  • x1, x2, xfoldの位置関係に応じて、3通りに場合分け。
    • xfold <= x1 の場合
    • x1 < xfold < x2 の場合
    • xfold <= x2 の場合
  • 値のオーバーフロー。かけ算するときはlong longにキャストする。

加えて、僕が最初に組んだ解法は、色を塗ったセルを1つずつ調べていいました。しかしこの方法では大きな値でTLEしてしまします。チャレンジされたのもこれが原因だったと思います。

class PaperAndPaintEasy {
public:
  long long computeArea(int width, int height, int xfold, int cnt, int x1, int y1, int x2, int y2)
  {
    long long color = 0;

    if (xfold > width/2)
      xfold = width - xfold;

    if (xfold <= x1)
      {
	color += ((long long)x2 - x1) * (cnt + 1);
      }
    else if (x2 <= xfold)
      {
	color += ((long long)x2 - x1) * (cnt + 1) * 2;
      }
    else
      {
	color += ((long long)xfold - x1) * (cnt + 1) * 2;
	color += ((long long)x2 - xfold) * (cnt + 1);
      }

    color *= (y2 - y1);

    return (long long)width * (long long)height - color;
  }
};

2009-05-27

SRM326 div2

10:02

Easy - AdditionCycles

たとえば26という整数の場合、2+6=8, 6 and 8 -> 68, 6+8=14, 8 and 4 -> 84, 8+4 = 12, 4 and 2 -> 42, 4+2=6, 2 and 6 -> 26 という具合に、このような計算を繰り返すともとの値にもどってくる。何回のイテレーションでもとの値にもどるか。

単純にもとの値に戻るまで繰り返しました。

class AdditionCycles {
public:
  int cycleLength(int n)
  {
    int ret = 0;
    int cur = n;

    while (++ret)
      {
	int tmp = cur/10 + cur%10;
	cur = cur%10 * 10 + tmp%10;
	if (cur == n)
	  break;
      }

    return ret;
  }
};

Medium - PositiveID

ベクトルが何本か与えられるので、2つのベクトル間の類似度を"同じ要素の個数"と定義し、最大の類似度を返す。

ベクトルが高々50、要素数が高々25なので、全探索しても問題なく時間内に終わります。引数からベクトルを生成する部分は、以前作ったsplitという関数をコピペすることで時間短縮できました。同一ベクトル内に同じ要素がある場合({aaa, bbb, aaa, ccc}など)を考慮して、setを使ったのですが、システムテストのテストケースをちらっと見たところでは、そんなケースはなかったので、setでなく普通にvectorでもよかったかもしれません。また今回は要素の探索にfind()を使ったので問題なかったのですが、ある要素が別の要素のサブセットになっている場合("blond"と"blondie"など)を特に意識していなかったので、もしfind()の部分を自分で実装していたとしたら、ここで引っかかっていたかもしれません。

class PositiveID {
public:
  set <string> split(const string _s, const string del)
  {
    set <string> ret;
    string s = _s;

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

    return ret;
  }

  int maximumFacts(vector <string> suspects)
  {
    int ret = 0;
    vector <set <string> > sus;

    for (int i=0; i<suspects.size(); i++)
      sus.push_back(split(suspects[i], ","));

    for (int i=0; i<sus.size(); i++)
      for (int j=0; j<sus.size(); j++)
	if (i != j)
	  {
	    int c = 0;
	    for (set <string>::iterator it=sus[i].begin(); it!=sus[i].end(); it++)
	      {

		if (sus[j].find(*it) != sus[j].end())
		  c++;
	      }
	    ret = max(c, ret);
	  }

    return ret;
  }
};

2009-05-26

SRM327 div2

12:45

Easy - FunnyFence

文字列中のシーケンス(|-|-というふうに|と-が交互に現れる)の最大長を返す問題。問題ありませんでした。

class FunnyFence {
public:
  int getLength(string s)
  {
    int ret = 0;
    for (int i=0; i<s.size(); i++)
      {
	bool preIsHifun = false;;
	if (s[i] == '-')
	  preIsHifun = true;

	int j = i + 1;
	int len = 1;

	while ((preIsHifun && s[j] == '|') || (!preIsHifun && s[j] == '-'))
	  {
	    preIsHifun = !preIsHifun;
	    len++;
	    j++;
	  }

	ret = max(ret, len);
      }
    return ret;
  }
};


Medium - IQTest

IQテストによくある、数列が与えられて次にくる数字は何?という問題を解く。数列の要素(全部でN個)をk1 ~ kNとすると、数列はkn = Kn-1 * p + qと定式化できる。ただしpとqは整数とする。

すべてのpとqの候補を探索し、条件にマッチするものを探すというbruto-forceなやり方で解きました。しかし、探索の範囲を適当に決めていたため、システムテストで一度落ちました。この点を最初にしっかり検討しておく必要がありました。

class IQTest {
public:
  string toStr(int n) {ostringstream ss; ss << n; return ss.str();}
  string nextNumber(vector <int> previous)
  {
    vector <pair <int, int> > sols;

    if (previous.size() == 1)
      return "AMBIGUITY";

    for (int i=-1000; i<=1000; i++)
      for (int j=-20000; j<=20000; j++)
	if (previous[0] * i + j == previous[1])
	  {
	    pair <int, int> tmp(i, j);
	    sols.push_back(tmp);
	  }

    for (int i=1; i<previous.size()-1; i++)
      for (int j=0; j<sols.size(); j++)
	if (previous[i] * sols[j].first + sols[j].second != previous[i+1])
	  {
	    sols.erase(sols.begin() + j);
	    j--;
	  }

    set <int> next;
    for (int i=0; i<sols.size(); i++)
      next.insert( previous[previous.size()-1] * sols[i].first + sols[i].second);

    if (sols.size() == 0)
      return "BUG";

    if (next.size() > 1)
      return "AMBIGUITY";

    return toStr(*next.begin());
  }
};

SRM422 div2

12:36

Easy - MultiNumber

ある整数を2つのパートにわけ(1234を12と34など)、左右それぞれの数字を掛け合わせる(1*2と3*4など)。左右の計算結果が等しければ"YES"、異なれば"NO"を返す。

全ての組み合わせについて調べるという方法で、そのまま実装しました。

class MultiNumber {
public:
  string toStr(int n) {ostringstream ss; ss << n; return ss.str();}
  string check(int number)
  {
    string ret = "NO";
    string n = toStr(number);

    for (int i=1; i<n.size(); i++)
      {
	int productL = 1, productR = 1;

	for (int j=0; j<i; j++)
	  productL *= n[j] - '0';

	for (int j=i; j<n.size(); j++)
	  productR *= n[j] - '0';

	if (productL == productR)
	  {
	    ret = "YES";
	    break;
	  }
      }

    return ret;
  }
};

Medium - PrimeSoccer

AとBの2チームがある。それぞれ18回得点のチャンスがあり、2チームそれぞれ一回ごとに得点できる確率が与えられる。少なくとも1チームが、素数得点をあげる確率を求める。

18以下の正の整数のみ扱えばいいので、両チームとも非素数得点をとる確率を計算し、1からマイナスすればokです。

 1 - \sum_{i \in S} _{18}C_{i} \times ProbOfTeamA \times (1 - ProbOfTeamA) \times \sum_{i \in S} _{18}C_{i} \times ProbOfTeamB \times (1 - ProbOfTeamB)

tex記法を使ってみました。Sは18以下の非素数です。

class PrimeSoccer {
public:
  double combination(int n, int r)
  {
    int i, j;
    double result[r+1], tmp[r+1];

    for (i=0; i<=r; i++)
      {
	result[i] = 0;
	tmp[i] = 0;
      }

    result[0] = 1;

    for (i=1; i<=n; i++)
      {
	tmp[0] = 1;

	for (j=1; j<=r; j++)
	  tmp[j] = result[j-1] + result[j];

	for (j=0; j<=r; j++)
	  result[j] = tmp[j];
      }

    return result[r];
  }

  double getProbability(int skillOfTeamA, int skillOfTeamB)
  {
    int notPrimes[12] = {0, 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18};
    double probA = 0, probB = 0;
    double skillA = (double)skillOfTeamA / 100, skillB = (double)skillOfTeamB / 100;

    for (int i=0; i<12; i++)
      {
	probA += combination(18, notPrimes[i]) * pow(skillA, notPrimes[i]) * pow(1 - skillA, 18 - notPrimes[i]);
	probB += combination(18, notPrimes[i]) * pow(skillB, notPrimes[i]) * pow(1 - skillB, 18 - notPrimes[i]);
      }

    return 1 - probA * probB;
  }
};

2009-05-20

SRM329 div2

11:42

Easy - VowelEncryptor

文字列の中から母音を取り除く。ただし、母音のみの文字列の場合は、取り除かない。

問題の条件さえ間違わなければ大丈夫です。

class VowelEncryptor {
public:
  vector <string> encrypt(vector <string> text)
  {
    vector <string> ret;

    for (int i=0; i<text.size(); i++)
      {
	string s;

	for (int j=0; j<text[i].size(); j++)
	  if (text[i][j] != 'a' && text[i][j] != 'i' && text[i][j] != 'u' && text[i][j] != 'e' && text[i][j] != 'o')
	    s += text[i][j];

	if (s.empty())
	  s = text[i];

	ret.push_back(s);
      }

    return ret;
  }
};

Medium - RailroadSeatNumeration

列車の座席の表示方法を統一する問題。

「引数は同じ方式(domesticsかinternationals)での表記である」という条件が抜けていたため、一度システムテストに落ちてしまいました。それがちゃんとできていれば、500点の割には簡単だったと思います。

class RailroadSeatNumeration {
public:
  string toStr(int n) {ostringstream ss; ss << n; return ss.str();}
  
  string getInternational(vector <int> tickets)
  {
    string ret;
    vector <int> domestics;
    vector <int> internationals;
    int intSeat[] = {1, 3, 4, 6};

    for (int i=0; i<tickets.size(); i++)
      {
	if (tickets[i] <= 36)
	  {
	    int t = (double)tickets[i] / 4 + 0.9;
	    t = t*10 + intSeat[(tickets[i] - 1) % 4];
	    domestics.push_back(t);
	  }

	if (tickets[i] / 10 <= 9 && tickets[i] > 9)
	  if (tickets[i] % 10 == 1 || tickets[i] % 10 == 3 || tickets[i] % 10 == 4 || tickets[i] % 10 == 6)
	    internationals.push_back(tickets[i]);
      }

    if (domestics.size() != tickets.size() && internationals.size() != tickets.size())
      return "BAD DATA";
    else if (domestics.size() == tickets.size() && internationals.size() == tickets.size())
      return "AMBIGUOUS";

    if (domestics.size() == tickets.size())
      for (int i=0; i<domestics.size(); i++)
	ret += toStr(domestics[i]) + " ";

    if (internationals.size() == tickets.size())
      for (int i=0; i<internationals.size(); i++)
	ret += toStr(internationals[i]) + " ";

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

    return ret;
  }
};

SRM328 div2

11:42

Easy - MarbleNecklace

与えられた文字列が循環しているリストだとする。例えばABC, BCA, CABは同一。また、逆順も同一(CBA, BAC, ACB)。この中で最も辞書順がはやいものを返す。

そのままの方法でやりました。

class MarbleNecklace {
public:
  string normalize(string necklace)
  {
    vector <string> ret;

    for (int i=0; i<necklace.size(); i++)
      {
	string s;
	s = necklace.substr(i);
	s += necklace.substr(0, i);
	ret.push_back(s);
      }

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

    for (int i=0; i<necklace.size(); i++)
      {
	string s;
	s = necklace.substr(i);
	s += necklace.substr(0, i);
	ret.push_back(s);
      }

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

    return ret[0];
  }
};

Medium - LightsCube

N*N*Nのキューブがある。最初、1以上のキューブのライトがついている。ライトがついているキューブに隣接しているキューブは、同じ色のライトがつく。最初についているライトの座標が与えられる。最終的に、何色のライトが何個ついているかを返す。

毎回ライトを伝播させていき、最終的に何個ついているかを数えるというストレートな方法で解きました。ミスなくできたのですが、時間がかかってしまいました。本番では間に合わなかった。

class LightsCube {
public:
  int N;
  int l[40][40][40];
  int tmp[40][40][40];

  bool inRange(int n)
  {
    if (0 <= n && n < N)
      return true;
    return false;
  }

  int ltotmp()
  {
    for (int x=0; x<N; x++)
      for (int y=0; y<N; y++)
	for (int z=0; z<N; z++)
	  tmp[x][y][z] = l[x][y][z];
    return 0;
  }

  int tmptol()
  {
    for (int x=0; x<N; x++)
      for (int y=0; y<N; y++)
	for (int z=0; z<N; z++)
	  l[x][y][z] = tmp[x][y][z];
    return 0;
  }

  vector <int> around(int _x, int _y, int _z)
  {
    map <int, int> m;
    vector <int> ret;
    char dir[2] = {-1, 1};

    for (int i=0; i<2; i++)
      {
	int x = _x + dir[i];
	int y = _y;
	int z = _z;

	if (inRange(x) && inRange(y) && inRange(z))
	  if (l[x][y][z] != -1)
	    m[l[x][y][z]]++;
      }

    for (int i=0; i<2; i++)
      {
	int x = _x;
	int y = _y + dir[i];
	int z = _z;

	if (inRange(x) && inRange(y) && inRange(z))
	  if (l[x][y][z] != -1)
	    m[l[x][y][z]]++;
      }

    for (int i=0; i<2; i++)
      {
	int x = _x;
	int y = _y;
	int z = _z + dir[i];

	if (inRange(x) && inRange(y) && inRange(z))
	  if (l[x][y][z] != -1)
	    m[l[x][y][z]]++;
      }

    for (map <int, int>::iterator i=m.begin(); i!=m.end(); i++)
      ret.push_back(i->first);

    return ret;
  }

  vector <int> count(int _N, vector <string> lights)
  {
    vector <int> ret;
    map <int, int> m;
    memset(l, -1, sizeof(l));
    N = _N;

    for (int i=0; i<lights.size(); i++)
      {
	int x, y ,z;
	sscanf(lights[i].c_str(), "%d %d %d", &x, &y, &z);
	l[x][y][z] = i;
      }

    while (1)
      {
	bool found = false;
	ltotmp();

	for (int x=0; x<N; x++)
	  for (int y=0; y<N; y++)
	    for (int z=0; z<N; z++)
	      if (l[x][y][z] == -1)
		{
		  found = true;
		  vector <int> res = around(x, y, z);
		  if (res.empty())
		    continue;

		  sort(res.begin(), res.end());
		  tmp[x][y][z] = res[0];
		}

	if (!found)
	  break;

	tmptol();
      }

    for (int x=0; x<N; x++)
      for (int y=0; y<N; y++)
	for (int z=0; z<N; z++)
	  m[l[x][y][z]]++;

    for (int i=0; i<lights.size(); i++)
      ret.push_back(m[i]);

    return ret;
  }
};

2009-05-16

SRM421 div2

09:43

Easy - GymTraining

ジムでトレーニングを胃している。トレーニング回数のノルマが与えられる。また、ある回数トレーニングして、pulseがたまると、トレーニングを休まなければならない。ノルマを達成するために最低限必要な時間を求める。

250にしては、少し時間がかかってしまいました。特に、pulseの上限値は超えてはならず、下限値は超えても良いという条件を勘違いしていたため、時間を取られました。

class GymTraining {
public:
  int trainingTime(int needToTrain, int minPulse, int maxPulse, int trainChange, int restChange)
  {
    int pulse = maxPulse - minPulse;
    int now = 0;
    int ret = 0;
    int trained = 0;

    if (pulse < trainChange)
      return -1;

    while (trained < needToTrain)
      {
	ret++;
	if (now + trainChange <= pulse)
	  {
	    now += trainChange;
	    trained++;
	  }
	else
	  {
	    now = min(now - restChange, 0);
	  }
      }
    return ret;
  }
};

Medium - EquilibriumPoints

物体の位置と質量のセットが与えられる。全てのEquilibrium Pointの位置を求めよ。

連立方程式を解く方法がわからず、Editorialを見ながら解きました。連立方程式の解は、バイナリサーチで見つけるそうです。なるほど、この手法は今後も応用する機会がありそうです。また、バイナリサーチのチュートリアルも良い記事でした。あとで練習問題にチャレンジします。

class EquilibriumPoints {
public:
  vector <int> x;
  vector <int> m;

  double calc(double d)
  {
    double ret = 0;

    for (int i=0; i<x.size(); i++)
      {
	if (x[i] < d)
	  ret -= m[i] / (d - x[i]) / (d - x[i]);
	else
	  ret += m[i] / (x[i] - d) / (x[i] - d);
      }

    return ret;
  }

  double bs(int left, int right)
  {
    double d = 0, l = left, r = right;
    int i = 0;

    while (i++ < 500)
      {
	d = (l + r) / 2.0;
	double res = calc(d);

	if (res == 0)
	  break;
	else if (res < 0)
	  l = d;
	else if (0 < res)
	  r = d;
      }

    return d;
  }

  vector <double> getPoints(vector <int> _x, vector <int> _m)
  {
    x = _x;
    m = _m;
    vector <double> ret;

    for (int i=0; i<x.size()-1; i++)
      ret.push_back(bs(x[i], x[i+1]));

    return ret;
  }
};

Hard - FloorIndicator

一部が壊れているかもしれないインジケータがある。表示している可能性のある数字の平均を求める。

時間がかかりましたが、一応実装はできました。まず各数値について、可能性のある数字を調べていきます。その後、全ての組み合わせを再帰的に調べていき、平均を求めます。

class FloorIndicator {
public:
  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();}
  double averageFloor(int N, vector <string> indicator)
  {
    vector <string> nums;
    string s = "###...#.###.###.#.#.###.###.###.###.###";
    nums.push_back(s);
    s = "#.#...#...#...#.#.#.#...#.....#.#.#.#.#";
    nums.push_back(s);
    s = "#.#...#.###.###.###.###.###...#.###.###";
    nums.push_back(s);
    s = "#.#...#.#.....#...#...#.#.#...#.#.#...#";
    nums.push_back(s);
    s = "###...#.###.###...#.###.###...#.###.###";
    nums.push_back(s);

    vector <vector <int> > vals;

    for (int i=0; i<N; i++)
      {
	bool candidates[10];
	memset(candidates, true, sizeof(candidates));

	for (int j=0; j<10; j++)
	  for (int col=0; col<5; col++)
	    for (int row=0; row<3; row++)
	      if (indicator[col][row + i*4] == '#' && nums[col][row + j*4] == '.')
		candidates[j] = false;

	vector <int> t;
	for (int k=0; k<10; k++)
	  if (candidates[k])
	    t.push_back(k);

	if (t.empty())
	  return -1;
	
	vals.push_back(t);
      }

    double nume = 0;
    double deno = 0;
    queue <string> q;
    for (int i=0; i<vals[0].size(); i++)
      q.push(toStr(vals[0][i]));

    while (!q.empty())
      {
    	string cur = q.front();
    	q.pop();

    	if (cur.size() == N)
    	  {
    	    nume += (double)toInt(cur);
    	    deno += 1.0;
    	    continue;
    	  }

    	for (int i=0; i<vals[cur.size()].size(); i++)
    	  q.push(cur + toStr(vals[cur.size()][i]));
      }

    return nume / deno;
  }
};

しかしこの解法では、大きな値の際にTLEでした。Editorialによると、各桁ごとに平均を計算し、足し込んでいくという方法が紹介されていました。これには関心しました。

class FloorIndicator {
public:
  double averageFloor(int N, vector <string> indicator)
  {
    string nums[] = {"###...#.###.###.#.#.###.###.###.###.###",
		     "#.#...#...#...#.#.#.#...#.....#.#.#.#.#",
		     "#.#...#.###.###.###.###.###...#.###.###",
		     "#.#...#.#.....#...#...#.#.#...#.#.#...#",
		     "###...#.###.###...#.###.###...#.###.###"};

    double ret = 0;

    for (int i=0; i<N; i++)
      {
	bool candidates[10];
	memset(candidates, true, sizeof(candidates));

	for (int j=0; j<10; j++)
	  for (int col=0; col<5; col++)
	    for (int row=0; row<3; row++)
	      if (indicator[col][row + i*4] == '#' && nums[col][row + j*4] == '.')
		candidates[j] = false;

	int sum = 0;
	int total = 0;
	for (int k=0; k<10; k++)
	  if (candidates[k])
	    {
	      sum += k;
	      total++;
	    }

	if (total == 0)
	  return -1;

	ret = ret * 10 + (double)sum / total;
      }

    return ret;
  }
};

2009-05-15

SRM420 div2

23:38

Hard - PrettyPrintingProduct

Permutation(A, B)を表示する問題。出力は、"12345...67891 * 10^3"のようなフォーマットで行う。

とりあえず、string型で乗算を行う関数を実装して、パーミュテーションを計算し、整形して出力するという方法でいってみましたが、やはり大きな数字になるとTLEです。

Editorialをみてみると、正解者が5人でした。難しい問題のようです。詳しい解説は次回見ていきます。

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

  string plus(string a, string b)
  {
    string ret;

    int i = 0;
    int up = 0;

    while (i < a.size() || i < b.size())
      {
	int ai = (i < a.size()) ? a[a.size() - 1 - i] - '0' : 0;
	int bi = (i < b.size()) ? b[b.size() - 1 - i] - '0' : 0;
	int sum = ai + bi + up;

	ret += sum % 10 + '0';
	up = sum / 10;

	i++;
      }

    if (up)
      ret += '1';

    reverse(ret.begin(), ret.end());
    return ret;
  }

  string mul(string a, string b)
  {
    string ret = "0";
    vector <string> muls;

    for (int i=0; i<b.size(); i++)
      {
	string tmp;
	int cur = b[b.size() - 1 - i] - '0';
	for (int j=0; j<i; j++)
	  tmp += "0";

	int up = 0;
	for (int j=0; j<a.size(); j++)
	  {
	    int n = a[a.size() - 1 - j] - '0';
	    n *= cur;
	    n += up;
	    up = n / 10;
	    tmp += n % 10 + '0';
	  }
	if (up)
	  tmp += up + '0';
	reverse(tmp.begin(), tmp.end());
	muls.push_back(tmp);
      }

    for (int i=0; i<muls.size(); i++)
      ret = plus(ret, muls[i]);

    return ret;
  }

  string prettyPrint(int A, int B)
  {
    string ret;
    string m = "1";

    for (int i=A; i<=B; i++)
      m = mul(m, toStr(i));

    int zeros = 0;
    for (int i=0;; i++)
      if (m[m.size() - 1 - i] == '0')
	zeros++;
      else
	break;

    m.erase(m.end()-zeros, m.end());

    if (m.size() > 10)
      {
	ret += m.substr(0, 5);
	ret += "...";
	ret += m.substr(m.size()-5, 5);
      }
    else
      {
	ret += m;
      }

    ret += " * 10^";
    ret += toStr(zeros);

    return ret;
  }
};

2009-05-14

SRM330 div2

11:22

Easy - Sortness

sortnessを計算する問題。ソートされた後の位置との差が大きいほどsortnessは大きくなる。問題文通りに実装すれば解ける。

class Sortness {
public:
  double getSortness(vector <int> a)
  {
    double ret = 0;
    for (int i=0; i<a.size(); i++)
      {
	int sortness = 0;
	for (int j=0; j<a.size(); j++)
	  {
	    if (j < i)
	      if (a[j] > a[i])
		sortness++;

	    if (j == i)
	      continue;

	    if (i < j)
	      if (a[i] > a[j])
		sortness++;
	  }
	ret += sortness;
      }

    return ret / (double)a.size();
  }
};

Medium - Arrows

文字列に含まれる矢印の最大長を返す問題。450点問題だったので、とても簡単だった。

class Arrows {
public:
  string s;
  int getArrowLength(int pos, int dir)
  {
    int ret = 1;

    if (dir == 0)
      {
	for (int i=pos+1; i<s.size(); i++)
	  {
	    if (s[i] == '<' || s[i] == '>')
	      break;

	    if (s[i] == s[pos+1])
	      ret++;
	    else
	      break;
	  }
      } 
    else if (dir == 1)
      {
	for (int i=pos-1; i>=0; i--)
	  {
	    if (s[i] == '<' || s[i] == '>')
	      break;

	    if (s[i] == s[pos-1])
	      ret++;
	    else
	      break;
	  }
      }

    return ret;
  }

  int longestArrow(string _s)
  {
    s = _s;
    int ret = -1;
    for (int i=0; i<s.size(); i++)
      if (s[i] == '<')
	ret = max(ret, getArrowLength(i, 0));
      else if (s[i] == '>')
	ret = max(ret, getArrowLength(i, 1));

    return ret;
  }
};

Hard - NextPalindromicNumber

引数以上の数で、回文となっている数を返す問題。

とりあえずナイーブなアルゴリズムを実装しました。引数をインクリメントしていき、回文になっているかを判定するというものです。しかし、大きな数ではあきらかにTLEになってしまいます。あとで考えるかも。

class NextPalindromicNumber {
public:
  bool isPal(string s)
  {
    if (s.size() == 1)
      return true;

    for (int i=0; i<s.size()/2; i++)
      if (s[i] != s[s.size() - 1 - i])
	return false;

    return true;
  }

  string plusone(string s)
  {
    bool up = true;
    for (int i=1; i<=s.size(); i++)
      {
	if (s[s.size()-i] != '9')
	  {
	    int c = s[s.size()-i] - '0';
	    s[s.size()-i] = c + 1 + '0';
	    up = false;
	    break;
	  }
	else
	  s[s.size()-i] = '0';
      }

    if (up)
      s.insert(s.begin(), '1');

    return s;
  }

  string getNext(string n)
  {
    while (1)
      {
	n = plusone(n);
	if (isPal(n))
	  break;
      }

    return n;
  }
};

2009-05-13

SRM331 div2

13:54

Easy - SantaGifts

サンタがプレゼントを、子供たちにどのように配るかという問題。STLの練習問題といったところです。

class SantaGifts {
public:
  vector <string> distribute(vector <string> gifts, int N)
  {
    vector <string> ret(N);

    int limit = min((int)gifts.size(), N*4);
    for (int i=0; i<limit; i++)
      ret[i % N] += gifts[i] + " ";

    for (int i=0; i<N; i++)
      if (ret[i][ret[i].size()-1] == ' ')
	ret[i].erase(ret[i].end()-1);

    return ret;
  }
};

Medium - CarolsSinging

こちらもクリスマスにちなんだ問題。全員が歌えるように、クリスマスキャロルを選曲します。

全ての組み合わせを考えても、高々2^10となるので、brute-forceな戦略がよさそうです。再帰を使ってdfsを実装し、解きました。

class CarolsSinging {
public:
  vector <string> lyrics;
  int ret;

  bool check(vector <int> v)
  {
    bool sang[lyrics.size()];
    memset(sang, false, sizeof(sang));

    for (int i=0; i<lyrics.size(); i++)
      for (int j=0; j<v.size(); j++)
	if (v[j] == 1 && lyrics[i][j] == 'Y')
	  sang[i] = true;

    for (int i=0; i<lyrics.size(); i++)
      if (!sang[i])
	return false;

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

    ret = min(ret, tmp);

    return true;
  }

  int dfs(int c, vector <int> & v)
  {
    if (c == lyrics[0].size())
      {
	check(v);
	return 0;
      }

    c++;
    v.push_back(0);
    dfs(c, v);
    v.erase(v.end()-1);

    v.push_back(1);
    dfs(c, v);
    v.erase(v.end()-1);

    return 0;
  }

  int choose(vector <string> _lyrics)
  {
    lyrics = _lyrics;
    ret = lyrics.size();
    vector <int> tmp;

    int b = 1 << 3;

    dfs(0, tmp);

    return ret;
  }

その後他の人のコードを見ていると、組み合わせの生成にビットをうまく使っている解法が多く使われていました。このテクニックにはかなり感動しました。この問題では、各キャロルを歌うか歌わないか、その全ての組み合わせが必要です。言い換えると、各要素が0と1をとる数列の、全てのパターンがわかればいいわけです。よって、0から目的のビット数までを順に調べていけば、目的が達成できることになります。例えば、キャロルが3曲の場合、000, 001, 010, 011, 100, 101, 110, 111が得られます。

class CarolsSinging {
public:
  int choose(vector <string> lyrics)
  {
    int ret = lyrics.size();

    for (int i=0; i<(1 << lyrics[0].size()); i++)
      {
	bool sang[lyrics.size()];
	memset(sang, false, sizeof(sang));

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

	bool ok = true;
	for (int j=0; j<lyrics.size(); j++)
	  if (!sang[j])
	    ok = false;

	if (ok)
	  ret = min(ret, __builtin_popcount(i));
      }

    return ret;
  }
};

チュートリアルにビットに関する記事があったので、あとで読んでみたいと思います。

A bit of fun: fun with bits

2009-05-12

SRM440 div2

23:38

Easyはなぜか解法が思いつかず、解けなかった。Mediumは時間が足りず、こちらも解けなかった。結果レーティングがまた100くらい落ちた。

Easy - IncredibleMachineEasy

重力加速度を求める問題。落ち着いて数式を展開すれば解けるはずだが、計算途中で加速度の項の分子と分母を間違えていて、解けなかった。

class IncredibleMachineEasy {
public:
  double gravitationalAcceleration(vector <int> height, int T)
  {
    double d = 0;
    for (int i=0; i<height.size(); i++)
      d += sqrt(height[i] * 2);

    return  d*d / (double)(T*T);
  }
};

Medium - MazeWanderingEasy

ひらめき系ではなく、愚直に組めば解ける問題。次に進む座標と、現在までに何回decisionがあったかを保存しながら、再帰的に探索すればできる。Easyでねばりすぎた & 解いてる途中でNHKの集金が来たため、時間が足りず間に合わなかった。

同じ部屋のシステムテストで落ちていた人は、以下の理由で落ちていた。

  • 現在の座標の周囲をしらべる際、値の範囲(0以上maze.size()以下など)を考慮していない。
  • 次に進めるセルがない場合を考慮していない。

また、問題文が無駄に長く、苦労しました。クラシック音楽のくだりはいらないと思います。

class MazeWanderingEasy {
public:
  int decisions(vector <string> maze)
  {
    bool visited[maze.size()][maze[0].size()];
    memset(visited, false, sizeof(visited));
    queue <vector <int> > q;
    vector <int> start;
    int ret;
    int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    for (int i=0; i<maze.size(); i++)
      for (int j=0; j<maze[0].size(); j++)
	if (maze[i][j] == 'M')
	  {
	    start.push_back(i);
	    start.push_back(j);
	  }

    start.push_back(0);
    q.push(start);

    while (!q.empty())
      {
	vector <int> here;
	here = q.front();
	q.pop();

	int x = here[0];
	int y = here[1];

	if (maze[x][y] == '*')
	  {
	    ret = here[2];
	    break;
	  }

	visited[x][y] = true;

	int c = 0;
	int d = 0;

	for (int i=0; i<4; i++)
	  {
	    int cx = x + dir[i][0];
	    int cy = y + dir[i][1];
	    if (0 <= cx && cx < maze.size() && 0 <= cy && cy < maze[0].size())
	      if (!visited[cx][cy] && (maze[cx][cy] == '.' || maze[cx][cy] == '*'))
		c++;
	  }

	if (c > 1)
	  d = 1;
	if (c >= 1)
	  {
	    for (int i=0; i<4; i++)
	      {
		int cx = x + dir[i][0];
		int cy = y + dir[i][1];
		if (0 <= cx && cx < maze.size() && 0 <= cy && cy < maze[0].size())
		  if (!visited[cx][cy] && (maze[cx][cy] == '.' || maze[cx][cy] == '*'))
		    {
		      vector <int> tmp;
		      tmp.push_back(cx);
		      tmp.push_back(cy);
		      tmp.push_back(here[2] + d);
		      q.push(tmp);
		    }
	      }
	  }
      }

    return ret;
  }
   

};

Hard - WickedTeacher

本番中はopenしなかった。あとで見てみるも、解けなかった。ある整数A(非常に大きな値)が別の整数Kの倍数かどうかを判定する方法がわからなかった。editorial待ち。

2009-05-11

SRM332 div2

00:04

Easy - TextStatistics

文字列中の単語文字長の平均値を計算する。単語の定義は以下の通り。

  • [a-zA-Z]から成る
  • [0-9,.!?-]で区切られる

250点問題のわりには、注意を要する問題でした。時間がかかった上に、システムテストに一度落ちてしまいました。原因は、文字列の最初が[a-zA-Z]出ない場合を考慮していなかったこと。よって戦略を、単語のベクタを作るものに変更しました。変更前の戦略は、文字列を走査し、アルファベットならば文字長をカウント、非アルファベットならば単語数をカウントするというものです。

class TextStatistics {
public:
  double averageLength(string text)
  {
    int word = 0;
    int len = 0;
    string w;
    vector <string> words;

    text += " ";

    for (int i=0; i<text.size(); i++)
      {
	if (('A' <= text[i] && text[i] <= 'Z') || ('a' <= text[i] && text[i] <= 'z'))
	  w += text[i];
	else
	  {
	    if (!w.empty())
	      {
		words.push_back(w);
		w.clear();
	      }
	  }
      }
      
    for (int i=0; i<words.size(); i++)
      {
	word++;
	len += words[i].size();
      }

    if (word == 0)
      word = 1;

    return (double)len / (double)word;
  }
};

Medium - CreatePairs

整数の集合が与えられる。集合内の各整数の最大の総和をもとめる。ただし、任意の2つの整数を選んで積をとってもよい。

考慮すべきポイントが多く、抜けが出てテストで落ちそうだと感じたため、まずは全ての可能性について計算する戦略でいこうとしました。しかし、集合から任意の数のペアを作るアルゴリズムが、時間内には思いつきそうにありませんでした。よって、brute-forceな戦略はあきらめ、ヒューリスティックにせめることにしました。

以下のポイントを考慮すればできます。

  • 集合を、0, 1, 負数, 1以外の正数の4つにわける
  • 1以外の正の整数の集合について、降順にソートし、大きい方から2つずつ積を取り、足していく。あまった要素は積を取らずに足し込む。
  • 負数について、昇順にソートし、小さい方から2つずつ積を取り、足していく。余った要素は、もし0があれば、0と積を取る。なければ結果から引く。
  • 1はそのまま結果に足す。
  • 0は上記の負数の相殺のみに用いる。

負数同士をかけてプラスにする部分がぬけており、システムテストに一度落ちてしまいました。

class CreatePairs {
public:
  int maximalSum(vector <int> data)
  {
    int ret = 0;
    int zeros = 0;
    int ones = 0;
    vector <int> negative;
    vector <int> positive;

    for (int i=0; i<data.size(); i++)
      if (data[i] == 0)
	zeros++;
      else if (data[i] == 1)
	ones++;
      else if (data[i] > 1)
	positive.push_back(data[i]);
      else
	negative.push_back(data[i]);

    sort(negative.begin(), negative.end());
    sort(positive.rbegin(), positive.rend());

    for (int i=0; i<positive.size(); i++)
      {
	if (i+1 < positive.size())
	  {
	    ret += positive[i] * positive[i+1];
	    i++;
	  }
	else
	  ret += positive[i];
      }

    for (int i=0; i<negative.size(); i++)
      {
	if (i+1 < negative.size())
	  {
	    ret += negative[i] * negative[i+1];
	    i++;
	  }
	else
	  {
	    if (zeros > 0)
	      zeros--;
	    else
	      ret += negative[i];
	  }
      }

    ret += ones;

    return ret;
  }
};

SRM333 div2

15:48

Easy - ChessboardPattern

チェスボードのパターンを生成する問題。もっとコンパクトに書ける気がします。

class ChessboardPattern {
public:
  vector <string> makeChessboard(int rows, int columns)
  {
    vector <string> ret;
    char pat[] = {'.', 'X'};

    for (int i=0; i<rows; i++)
      {
	string tmp;
	int s = 0;
	if (i % 2 != 0)
	  s = 1;
	for (int j=0; j<columns; j++)
	  {
	    tmp.push_back(pat[s]);
	    s = (s + 1) % 2;
	  }
	ret.push_back(tmp);
      }

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

    return ret;
  }
};

Medium - BirthNumbersValidator

stringを渡され、正しいフォーマットかをチェックする問題。正しいフォーマットは次の条件を満たす。

  • はじめの2文字は、生年月日の西暦の下2桁
  • つぎの2文字は生年月日の月。女性は+50
  • 次の2文字は生年月日の日。
  • 全体は11で割り切れる数値になっている。

上記の条件を単純にチェックしていく戦略で大丈夫でした。注意点の一点目として、10桁の数字はintだと桁あふれする可能性があるので、long longなどを使う必要があります。ただしこの点はテストケースでチェックされるので、あまり問題ではないでしょう。二点目として、うるう年を考慮する必要があります。

コードが汚いです。

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

  vector <string> validate(vector <string> test)
  {
    vector <string> ret;

    int d[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    vector <int> days(d, d+12);

    for (int i=0; i<test.size(); i++)
      {
	long long all = toLong(test[i]);
	int year = toInt(test[i].substr(0, 2));
	int month = toInt(test[i].substr(2, 2));
	int day = toInt(test[i].substr(4, 2));

	if (year >= 7)
	  year += 1900;
	else
	  year += 2000;

	if (!((0 < month && month < 13) || (50 < month && month < 63)))
	  {
	    ret.push_back("NO");
	    continue;
	  }

	if (month > 50)
	  month -= 50;

	int limit = days[month-1];
	if (month == 2 && (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)))
	  limit++;

	if (!(0 < day && day <= limit))
	  {
	    ret.push_back("NO");
	    continue;
	  }

	if (all % 11 != 0)
	  {
	    ret.push_back("NO");
	    continue;
	  }

	ret.push_back("YES");
      }

    return ret;
  }  
};

SRM334 div2

12:09

Easy - SupermarketDiscount

商品のディスカウントと、最適な買い方の問題。今回のケースは状況がかなり限定されていて簡単ですが、もっと制約の少ない問題だと難しくなりそうです。

  int minAmount(vector <int> goods)
  {
    int com = 0;
    int ret = 0;

    for (int i=0; i<goods.size(); i++)
      {
	if (goods[i] >= 50)
	  ret += goods[i] - 10;
	else
	  com += goods[i];
      }

    ret += com;

    if (com >= 50)
      ret -= 10;      

    return ret;
  }

Medium - KnightTour

チェスの盤上でナイトを動かす。ナイトが、全ての盤上を通り、かつ最終到達地点から初期位置にまで戻ることができる道筋がある。この道筋のことを"re-entrant"という。ナイトの動きの軌跡が与えられるので、この軌跡が"re-entrant"かどうか判定せよという問題。

こちらの問題も、引数が必ず36要素のベクターになっている(ナイトが移動し終えた)という制約があるため、すんなり解けました。(1)ナイトがセルを重複して通過していないか。(2)ナイトの動きがおかしくないか。この2点だけチェックすればできます。

class KnightTour {
public:
  vector <string> cells;

  bool visitAllCell(void)
  {
    map <string, int> cellCount;
    bool ret = true;

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

    if (cellCount.size() != 36)
      ret = false;

    return ret;
  }

  bool correctMove(string from, string to)
  {
    bool ret = false;
    int col = abs(from[0] - to[0]);
    int row = abs(from[1] - to[1]);

    if ((col == 2 && row == 1) || (col == 1 && row == 2))
      ret = true;

    return ret;
  }

  string checkTour(vector <string> _cells)
  {
    cells = _cells;

    if (!visitAllCell())
      return "Invalid";

    for (int i=0; i<cells.size()-1; i++)
      if (!correctMove(cells[i], cells[i+1]))
	return "Invalid";

    if (!correctMove(cells[cells.size()-1], cells[0]))
      return "Invalid";

    return "Valid";
  }
}

Hard - ExtendedHappyNumbers

ナイーブなアルゴリズムだと、割とすぐ書けるが、そのままだとTLEになるというたぐいの問題でした。途中の計算結果を保存しておくことで、計算量を削減できるみたいです。

とりあえず、最初に書いたナイーブなほうをはります。あとで改良するかも。

class ExtendedHappyNumbers {
public:
  long long pow(int a, int b)
  {
    long long ret = 1;
    for (int i=0; i<b; i++)
      ret *= a;

    return ret;
  }

  long long S(int n, int k)
  {
    long long ret = 0;

    while (n)
      {
	ret += pow(n % 10, k);
	n /= 10;
      }

    return ret;
  }

  long long getHappyNumber(int N, int K)
  {
    set <int> dupulicateChecker;

    dupulicateChecker.insert(N);

    while (1)
      {
	long long cur = S(N, K);
	if (dupulicateChecker.find(cur) != dupulicateChecker.end())
	  break;

	dupulicateChecker.insert(cur);
	N = cur;
      }

    return *dupulicateChecker.begin();
  }

  long long calcTheSum(int A, int B, int K)
  {
    long long ret = 0;

    for (int i=A; i<=B; i++) 
      ret += getHappyNumber(i, K);
   
    return ret;
  }
}

2009-05-10

SRM335 div2(過去問)

18:15

Easy - Palindromize

回文をつくる問題。文字列の末尾に一文字ずつ追加していき、その度に回文になっているかを判定する戦略でできました。

  bool isPalindrome(string s)
  {
    for (int i=0; i<s.size()/2; i++)
      if (s[i] != s[s.size() - 1 - i])
	return false;

    return true;
  }

  string minAdds(string s)
  {
    string ret;

    for (int i=0; i<s.size(); i++)
      {
	string sub = s.substr(0, i);
	reverse(sub.begin(), sub.end());
	if (isPalindrome(s + sub))
	  {
	    ret = s + sub;
	    break;
	  }
      }

    return ret;
  }

Medium - Multifactorial

Multifactorialという値を計算する。Multifactorial(n, k)はすべて正の n - X*k の積。ただしXは正の整数。

doubleでMultifactorialを計算しながら、オーバーフローを検出するという戦略で解きました。ただ、解説記事によると、この解法は正確さの点でトリッキーだそうです。よくわからないのですが、浮動小数点の誤差の関係でしょうか。いまいちよく理解できていません。

  string toStr(long long n) {ostringstream ss; ss << n; return ss.str();}

  double fac(int n, int k)
  {
    double ret = n;

    while (k < n)
      {
	n = n-k;
	ret *= n;
	if (ret > 1000000000000000000.0)
	  return -1;
      }

    return ret;
  }

  string calcMultiFact(int n, int k)
  {
    string ret;

    double f = fac(n, k);

    if (f == -1)
      return "overflow";

    ret = toStr((long long)f);

    return ret;
  }

SRM336 div2(過去問)

11:59

Easy - VowelLatin

引数の母音と子音を分離する問題。特に問題なし。

  string translate(string word)
  {
    string vow;
    string nvow;
    for (int i=0; i<word.size(); i++)
      {
	if (word[i] == 'a' ||
	    word[i] == 'i' ||
	    word[i] == 'u' ||
	    word[i] == 'e' ||
	    word[i] == 'o' ||
	    word[i] == 'A' ||
	    word[i] == 'I' ||
	    word[i] == 'U' ||
	    word[i] == 'E' ||
	    word[i] == 'O' )
	  vow += word[i];
	else
	  nvow += word[i];
      }
    return nvow + vow;
  }

Medium - ServiceNames

引数をパース、整形する問題。戻り値をアルファベット順にソートする必要があったのですが、それを忘れていてシステムテストに一度落ちてしまいました。

  // stringを文字列delで分離し、ベクタで返す関数
  vector <string> split(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 <string> makeList(vector <string> services)
  {
    vector <string> ret;
    map <string, vector <string> > m;

    // 引数をパースし、結果をmapにつめていく
    for (int i=0; i<services.size(); i++)
      {
	vector <string> elems = split(services[i], " ");

        // elems[0]がKindOfInput、elems[1]以降がservice names
	for (int j=1; j<elems.size(); j++)
	  m[elems[j]].push_back(elems[0]);
      }

    // 出力をつくる
    for (map <string, vector<string> >::iterator i=m.begin(); i!=m.end(); i++)
      {	
        // service namesをアルファベット順にソートする
	sort(i->second.begin(), i->second.end());

        // service namesを", "区切りで並べる
	string tmp = i->second[0];
	for (int j=1; j<i->second.size(); j++)
	  tmp += ", " + i->second[j];

        // KindOfInputとservice namesをつなぐ
	ret.push_back(i->first + " ==> " + tmp);
      }

    return ret;
  }

2009-05-08

SRM338 div2(過去問)

15:21

Easy - BinaryIncrementation

'0'と'1'のみから成る文字列が与えられる。これは2進数を表現している。この数に1を足し、同様のフォーマットで返す。

問題文の通りに実装しました。他には、引数を数値に変換し、1を足し、また文字列に戻すという方法もあると思います。

  string plusOne(string x)
  {
    string ret = "0";
    ret += x;

    int cur = ret.size() - 1;
    while (cur >= 0)
      {
	if (ret[cur] == '0')
	  {
	    ret[cur] = '1';
	    break;
	  }
	else
	  {
	    ret[cur] = '0';
	    cur--;
	  }
      }

    if (ret[0] == '0')
      ret.erase(0, 1);

    return ret;
  }

SRM339 div2(過去問)

09:58

Easy - BettingStrategy

問題文が長く、細かいところをきちんと読まなかったせいで、システムテストに落ちました。betを途中で打ち切るタイミングを勘違いしていました。

  int finalSum(int initSum, string outcome)
  {
    int ret = initSum;
    int bet = 1;

    for (int i=0; i<outcome.size(); i++)
      {
	if (outcome[i] == 'W')
	  {
	    ret += bet;
	    bet = 1;
	  }
	else
	  {
	    ret -= bet;
	    bet *= 2;
	    if (ret - bet < 0)
	      break;
	  }
      }
    return ret;
  }

Medium - ProblemsToSolve

通し番号付きの問題集が与えられる。問題は順番に解くか、1つとばしに解くことができる。また0問目は必ず解かなければいけない。intのベクタpleasantnessと整数varietyが与えられる。pleasantnessは各問題の満足度?である。順に問題を解いていき、既に解いた問題の最大と最小の満足度の差がvariety以上であれば、問題集をやめてよい。そうでなければ、全問解く必要がある。解くべき最小の問題数を求めよ。

戦略:pleasantnessから2つの要素を選び、その差がvariety以上ならば、必要な問題数を計算し、保存する。この操作を全ての組み合わせに対して行う。最小値を返す。

簡単そうに思えたのですが、意外に難しかったです。submit->system testを何度か繰り返してしまいました。特に、最初に見つかった解が最適ではないケースが、テストケースに含まれていなかったので、ここでつまずきました。

  int getProbNum(int r, int l)
  {
    int ret = 0;

    // rとlの間にある、解くべき問題数
    ret += 2;
    ret += (l - r - 1) / 2;

    // 0とrの間にある、解くべき問題数
    if (r != 0)
      {
	ret++;
	ret += (r - 1) / 2;
      }

    return ret;
  }

  int minNumber(vector <int> pleasantness, int variety)
  {
    int ret = pleasantness.size();

    for (int i=1; i<pleasantness.size(); i++)
      {
	bool found = false;
	for (int j=0; j<i; j++)
	  {
	    if (abs(pleasantness[i] - pleasantness[j]) >= variety)
	      {
		ret = min(getProbNum(j, i), ret);
		found = true;
	      }
	  }
	if (found)
	  break;
      }

    return ret;
  }

2009-05-07

SRM340 div2(過去問)

23:06

Easy - CssPropertyConverter

"-"と小文字のアルファベットから成る文字列が与えられる。"-"を消去し、直後の文字を大文字にする(camel記法にする)という問題。

以前作ったsplitという関数を使ってみました。

  vector <string> split(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;
  }

  string getCamelized(string cssPropertyName)
  {
    string ret;
    vector <string> s = split(cssPropertyName, "-");
    for (int i=1; i<s.size(); i++)
      s[i][0] = s[i][0] - 'a' + 'A';
    for (int i=0; i<s.size(); i++)
      ret += s[i];
    return ret;
  }

SRM341 div2(過去問)

18:33

Easy - ChangingString

2つの文字間の距離を、文字の差の絶対値と定義する。2つの同じ長さの文字列の距離を、同じインデックスの文字の距離の総和とする。("abc"と"cba"の場合4)。K個の文字を変更した場合の、文字列間の最小距離を計算する問題。

戦略:2つの文字列の各文字の距離をそれぞれ計算し、降順に並べる。距離が大きいものからK個、距離を0にする。もし距離が0だった場合、距離を1にする。


  int distance(string A, string B, int K)
  {
    vector <int> gap;
    int ret = 0;

    for (int i=0; i<A.size(); i++)
      gap.push_back(abs(A[i] - B[i]));

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

    for (int i=0; i<K; i++)
      if (gap[i] == 0)
	gap[i] = 1;
      else
	gap[i] = 0;

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

    return ret;
  }

Medium - KLastNonZeroDigits

引数Nの階乗を計算する。値の右側に0があれば削除する(202000の場合202となる)。位の低い方からK文字を返すという問題。

階乗を計算し、0を除き、部分文字列を返すという、ストレートな方法で問題ありませんでした。

  string getKDigits(int N, int K)
  {
    double d = 1;
    char c[30];
    string str;
    string ret;

    for (int i=1; i<=N; i++)
      d *= i;

    sprintf(c, "%.0f", d);
    str = c;

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

    while (str[0] == '0')
      str.erase(0, 1);

    if (K <= str.size())
      for (int i=0; i<K; i++)
	ret += str[i];
    else
      ret = str;

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

    return ret;
  }

SRM420 div2(過去問)

16:46

Easy - DeckRearranging

文字列を並び替える問題。stringのメソッドの使い方がわかれば、すぐに解ける問題でした。

  string rearrange(string deck, vector <int> above)
  {
    string ret;

    for (int i=0; i<deck.size(); i++)
      ret.insert(above[i], deck.substr(i, 1));

    return ret;
  }

Medium - YearProgressbar

日付と時刻が与えられ、その年のうち何%が経過したかを計算する問題。

戦略は、一年間のトータルの時間と、与えられた時刻までの経過時間の両方を分に変換し、パーセンテージを計算するという方法です。ストレートに考えました。

うるう年の判定法も問題文中に明記されていたため、素早く実装するのみの問題でした。しかし、細かいミスなどで結構時間がとれれてしまいました。

  double percentage(string currentDate)
  {
    // 月ごとの経過日数
    map <string, int> month;
    month["January"] = 0;
    month["February"] = 31;
    month["March"] = 59;
    month["April"] = 90;
    month["May"] = 120;
    month["June"] = 151;
    month["July"] = 181;
    month["August"] = 212;
    month["September"] = 243;
    month["October"] = 273;
    month["November"] = 304;
    month["December"] = 334;

    char monc[10];
    string mon;
    int day;
    int year;
    int hour;
    int min;

    // 引数を読み込む
    sscanf(currentDate.c_str(), "%s %02d, %d %02d:%02d", monc, &day, &year, &hour, &min);
    mon = monc;

    // うるう年の判定
    bool isLeap = false;
    if (year % 400 == 0 || year % 4 == 0 && year % 100 != 0)
      isLeap = true;

    double md = 0, my = 0;

    // 一年間の分を計算
    if (isLeap)
      my = 366 * 24 * 60;
    else
      my = 365 * 24 * 60;

    // うるう年で3月以降の場合一日増やす
    if (isLeap && (mon != "January" && mon != "February"))
      day++;

    // その日付までの経過日数が欲しいので、デクリメントする
    day--;

    // 現在時刻の分を計算
    md += month[mon] * 24 * 60;
    md += day * 24 * 60;
    md += hour * 60;
    md += min;

    return (md / my) * 100;
  }

2009-05-04

SRM342 div2(過去問)

02:57

Easy - DegreesToRadians

degreeをradianに変換する問題。計算式が問題文に書かれているので、ほんとうにやるだけの問題。

  double convertToRadians(int degrees, int minutes, int seconds)
  {
    double pi = 3.141592653589793;
    double min = (double)minutes + (double)seconds / 60.0;
    double deg = min / 60.0 + (double)degrees;
    return deg * pi / 180.0;
  }

Medium - TagalogDictionary

tagalog語という言語の単語順を用いて、単語をソートする問題。

意外とストレートに解くことができた。tagalogのアルファベットをうまく変換するところがポイントだと思う。また、pairのソートは、第一要素で比較。第一要素が同じだった場合、第二要素で比較という風に行われる。便利。

解説ページに色々面白そうなことが書いてあったので、後で読んでみよう。

  vector <string> dic;
  TagalogDictionary(void)
  {
    dic.push_back("a");
    dic.push_back("b");
    dic.push_back("k");
    dic.push_back("d");
    dic.push_back("e");
    dic.push_back("g");
    dic.push_back("h");
    dic.push_back("i");
    dic.push_back("l");
    dic.push_back("m");
    dic.push_back("n");
    dic.push_back("ng");
    dic.push_back("o");
    dic.push_back("p");
    dic.push_back("r");
    dic.push_back("s");
    dic.push_back("t");
    dic.push_back("u");
    dic.push_back("w");
    dic.push_back("y");
  }

  int toVar(string s)
  {
    int ret = 0;
    for (int i=0; i<dic.size(); i++)
      if (s == dic[i])
	ret = i;

    return ret;
  }

  char toChar(int n)
  {
    return 'a' + n;
  }

  vector <string> sortWords(vector <string> words)
  {
    vector <string> ret;
    vector <pair<string, int> > v;

    for (int i=0; i<words.size(); i++)
      {
	string enc = "";
	for (int j=0; j<words[i].size(); j++)
	  {
	    string tmp = "";
	    if (j < words[i].size()-1 && words[i][j] == 'n' && words[i][j+1] == 'g')
	      {
		tmp = "ng";
		j++;
	      }
	    else
	      tmp = words[i][j];

	    enc += toChar(toVar(tmp));
	  }
	pair <string, int> t(enc, i);
	v.push_back(t);
      }

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

    for (int i=0; i<v.size(); i++)
      ret.push_back(words[v[i].second]);

    return ret;
  }

SRM343 div2(過去問)

02:00

Easy - PersistentNumber

Persistent Number という数に関する問題。Persistent Numberの数学的意味は無視して、アルゴリズムの側面からのみ考えると、ただやるだけの簡単な問題でした。

  string toStr(int n) {ostringstream ss; ss << n; return ss.str();}

  int getPersistence(int n)
  {
    int ret = 0;
    int d = n;

    while (d > 9)
      {
	string s = toStr(d);
	int tmp = 1;
	for (int i=0; i<s.size(); i++)
	  tmp *= s[i] - '0';
	d = tmp;
	ret++;
      }
    return ret;
  }

Medium - CDPlayer

CDプレイヤーのランダム再生を考える。数曲再生し、きちんとランダム再生されているかをしらべる問題。

特にひねることなく、ストレートに攻めれば解ける問題でした。

  bool ok(string s)
  {
    map <char, int> m;
    map <char, int>::iterator it;
    for (int i=0; i<s.size(); i++)
      m[s[i]]++;

    for (it=m.begin(); it!=m.end(); it++)
      if (it->second > 1)
	return false;

    return true;
  }

  int isRandom(vector <string> songlist, int n)
  {
    string s = "";

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

    for (int i=0; i<n; i++)
      {
	string sub = s.substr(0, i);
	if (!ok(sub))
	  continue;

	int pos = i;
	bool notFound = false;
	while (pos < s.size())
	  {
	    sub = s.substr(pos, n);
	    if (!ok(sub))
	      {
		notFound = true;
		break;
	      }
	    pos += n;
	  }
	if (!notFound)
	  return i;
      }

    return -1;
  }

SRM344 div2(過去問)

19:06

Easy - Chessboard

チェスボードの記法を変換する問題。少し時間がかかったが、特に問題はなかった。

  string toStr(int n) {ostringstream ss; ss << n; return ss.str();}

  string changeNotation(string cell)
  {
    string ret = "";

    if ('0' <= cell[0] && cell[0] <= '9')
      {
	int c;
	sscanf(cell.c_str(), "%d", &c);
	int n = (double)c / 8 + 0.9;
	int a = c % 8;
	if (a == 0)
	  a = 8;
	a--;

	ret += 'a' + a;
	ret += '0' + n;
      }
    else
      {
	char c;
	int n;
	sscanf(cell.c_str(), "%c%d", &c, &n);
	int r = (c - 'a' + 1) + 8 * (n - 1);
	ret = toStr(r);
      }
    return ret;
  }

Medium - SimpleRotationDecoder

暗号をデコードする問題。この問題では、アルゴリズム的な難しさよりも、落ち着いて、正確に、素早くコーディングする力が求められているようだった。解くことはできたけど、本番だったら焦っていて間に合わなかったかもしれない。

一応、僕のとった戦略は、全ての可能なパスワードをしらみつぶしに調べるというものです。全ての可能なパスワードは26*26*26通りなので、実行時間は問題ないと考えました。

  int toVar(char c)
  {
    int ret = 0;
    if (c != ' ')
      ret = c - 'a' + 1;
      
    return ret;
  }

  char toChar(int d)
  {
    char ret = ' ';
    if (d > 0)
      ret = 'a' + d - 1;
      
    return ret;
  }

  vector <string> getWords(string s)
  {
    size_t pos;
    vector <string> ret;

    while (!s.empty())
      {
	pos = s.find(' ');
	if (pos == string::npos)
	  {
	    ret.push_back(s.substr(0));
	    s.erase(0);
	  }
	else
	  {
	    ret.push_back(s.substr(0, pos));
	    s.erase(0, pos+1);
	  }
      }
    return ret;
  }

  bool isValid(string s)
  {
    vector <string> words;
    char vow[5] = {'a', 'i', 'u', 'e', 'o'};

    if (s[0] == ' ' || s[s.size()-1] == ' ')
      return false;

    words = getWords(s);

    for (int i=0; i<words.size(); i++)
      {
	if (words[i].size() < 2 || 8 < words[i].size())
	  return false;

	bool ok = false;
	for (int j=0; j<5; j++)
	  if (words[i].find(vow[j]) != string::npos)
	    {
	      ok = true;
	      break;
	    }

	if (!ok)
	  return false;
      }

    return true;
  }

  string decode(string cipherText)
  {
    string ret = "";
    string pass = "";

    for (int a=0; a<26; a++)
      for (int b=0; b<26; b++)
	for (int c=0; c<26; c++)
	  {
	    pass = "";
	    pass += 'a' + a;
	    pass += 'a' + b;
	    pass += 'a' + c;

	    string tmp = "";
	    for (int i=0; i<cipherText.size(); i++)
	      tmp += toChar((27 + toVar(cipherText[i]) - toVar(pass[i%3])) % 27);

	    if (isValid(tmp))
	      {
		ret = tmp;
		break;
	      }
	  }

    return ret;
  }

SRM345 div2(過去問)

19:06

Easy - Trekking

特に問題はなかった。

  int findCamps(string trail, vector <string> plans)
  {
    int mini = 100;

    for (int i=0; i<plans.size(); i++)
      {
	bool ok = true;
	int c = 0;
	for (int j=0; j<trail.size(); j++)
	  {
	    if (plans[i][j] == 'C')
	      {
		c++;
		if (trail[j] == '^') 
		  {
		    ok = false;
		    break;
		  }
	      }
	  }
	if (ok)
	  mini = min(mini, c);
      }

    if (mini == 100)
      mini = -1;

    return mini;
  }

Medium - Pathfinding

2次元座標系の上で、原点から目標地点(x, y)への最短距離を求める問題。ただし、yが奇数の地点では、xが正の方向へ。逆にyが偶数の地点では、xが負の方向へしか進むことができない。同様に、xが奇数ならyは負、xが偶数ならyは正の方向へしか進めない。

一見簡単そうだったが、やってみると非常に難しい問題でした。まず考えたのは、全ての場合について、最短経路がどうなるか手で計算するという方法です。x, yの正負と奇偶より16通り + x, yのいずれかが0かつそれぞれの奇偶より8通り + x, yの両方が0という1通りで、全部で25通りの場合があります。このそれぞれについて調べます。abs(x)+abs(y)の最短のケースか、それに2か4を足すケースのいずれかになります。他の人のコードを見てみたところ、この戦略で解いている人がほとんどでした。

解説記事によると、25通りのケースは15通りまで減らすことができるそうです。理由は、xとyの対称性らしいのですが、ここはうまく理解できませんでした。また他のアプローチとして、ある範囲内の全ての経路をbfsで探索する方法。ゴールと現在地とのユークリッド距離が最小になるよう、一歩ずつ進んでいく方法が紹介されていました。そこで練習のため、bfsのアプローチを実装してみました。

かなり時間がかかってしまったのですが、なんとかできたと思います。しかし、入力が大きくなると、uncaught exceptionという例外が発生し、システムテストに落ちてしまいます。ローカルだと少し時間がかかっているようなのですが、解は出ています。疲れたので、原因究明は保留とします。

class Pathfinding {
public:
  set <pair<int, int> > visited;
  queue <pair <pair<int, int>, int> > q;
  int lx, ux, ly, uy;
  pair <int, int> goal;

  int bfs(int a, int b)
  {
    pair <pair <int, int>, int> cur;
    pair <int, int> t(a, b);
    pair <pair <int, int>, int> s(t, 0);
    q.push(s);
    visited.insert(t);

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

	if (cur.first == goal)
	  break;
	
	pair <int, int> tmp;
	if (cur.first.second % 2 == 0)
	  {
	    tmp.first = cur.first.first+1;
	    tmp.second = cur.first.second;
	  }
	else
	  {
	    tmp.first = cur.first.first-1;
	    tmp.second = cur.first.second;
	  }

	if (lx <= tmp.first && tmp.first <= ux && ly <= tmp.second && tmp.second <= uy && visited.find(tmp) == visited.end())
	  {
	    visited.insert(tmp);
	    pair<pair<int, int>, int> t(tmp, cur.second+1);
	    q.push(t);
	  }

	if (cur.first.first % 2 == 0)
	  {
	    tmp.first = cur.first.first;
	    tmp.second = cur.first.second+1;
	  }
	else
	  {
	    tmp.first = cur.first.first;
	    tmp.second = cur.first.second-1;
	  }

	if (lx <= tmp.first && tmp.first <= ux && ly <= tmp.second && tmp.second <= uy && visited.find(tmp) == visited.end())
	  {
	    visited.insert(tmp);
	    pair<pair<int, int>, int> t(tmp, cur.second+1);
	    q.push(t);
	  }
      }

    return cur.second;
  }

  int getDirections(int x, int y)
  {
    goal.first = x;
    goal.second = y;

    if (x > 0)
      {
	ux = x + 2;
	lx = -2;
      }
    else if (x < 0)
      {
	ux = 2;
	lx = x - 2;
      }
    else
      {
	ux = x + 2;
	lx = x - 2;
      }

    if (y > 0)
      {
	uy = y + 2;
	ly = -2;
      }
    else if (y < 0)
      {
	uy = 2;
	ly = y - 2;
      }
    else
      {
	uy = y + 2;
	ly = y - 2;
      }

    return bfs(0, 0);
  }
};

2009-05-03SRM346 div2(過去問)

Easy - DiamondHunt

'<'と'>'から成る文字列が与えられる。文字列から'<>'(ダイアモンド)を探す。見つかったダイアモンドは文字列から取り除かれる。その際、新しいダイアモンドができる場合もある。文字列に含まれるダイアモンドの数を返す。例えば、'<<>>'の場合2を返す。

文字列からダイアモンドを一つ探し、見つかればそれを取り除く。この作業をダイアモンドがなくなるまで繰り返す、という単純な戦略で実装しました。findやeraseを使うと簡単に実装できます。

  int countDiamonds(string mine)
  {
    int ret = 0;
    size_t pos;

    while (1)
      {
	pos = mine.find("<>");
	if (pos == string::npos)
	  break;
	mine.erase(pos, 2);
	ret++;
      }
    return ret;
  }

Medium - CommonMultiples

整数のセットと、上限値、下限値が与えられる。[下限値, 上限値]の範囲の整数で、整数セット中の全ての整数の倍数となっているものの数を返す。

最も単純な戦略は、[下限値, 上限値]の各整数について、整数セットの各値で割り切れるかをチェックするというもの。しかし、これでは最大 2*10^9*50 回操作があるので、明らかに時間がかかる。よって、整数セットの全ての値の最小公倍数を求め、その最小公倍数の倍数の中から、条件を満たすものの数を数えるという戦略で行いました。

  int gcd(int _a, int _b)
  {
    int a = max(_a, _b);
    int b = min(_a, _b);

    while (b)
      {
	int tmp = a % b;
	a = b;
	b = tmp;
      }

    return a;
  }

  double lcm(int _a, int _b)
  {
    int a = max(_a, _b);
    int b = min(_a, _b);

    return (double)a / gcd(a, b) * b;
  }


  int countCommMult(vector <int> a, int lower, int upper)
  {
    int ret = 0;

    double l = a[0];
    for (int i=1; i<a.size(); i++)
      {
	l = lcm(max((int)l, (int)a[i]), min((int)l, (int)a[i]));
	if (l > 2000000000)
	  return 0;
      }

    if (upper < l)
      return 0;

    ret = upper / l;

    if (l < lower)
      ret -= (int)((lower-1) / l);

    return ret;
  }

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

2009-05-01

SRM439 div2

19:27

Easyをよくわからないミスによって落とし、Mediumが解けなかったため0点。スコアが100点ぐらい落ちました。

Easy - SquareOfDigits

各要素に0-9の整数が格納された2次元配列から、各頂点が同じ数字となっている最大の正方形の面積を返すという問題。

入力のサイズが小さいので、ストレートに実装すればできそうです。が、配列全体ではなく、配列の半分しか走査しないアルゴリズムにしてしまい、システムテストで落ちました。意味不明なミスだ。まじで悔しい。

同じ部屋のシステムテストに落ちた人のコードを見てみると、正方形じゃなくて長方形を探していて、落ちている人が何人かいました。チャレンジのチャンスだったのに、なんで気づかなかったんだろう。悔いが残る。

  int getMax(vector <string> data)
  {
    int i, j, k;
    int ret = 1;

    for (i=0; i<data.size()-1; i++)
      for (j=0; j<data[i].size()-1; j++)
	for (k=j+1; k<data[i].size(); k++)
	  if (data[i][j] == data[i][k])
	    {
	      int l = k-j;
	      if ((l+1)*(l+1) > ret)
		if (i+l < data.size() && j+l < data[i].size() && data[i+l][j] == data[i][j] && data[i+l][j+l] == data[i][j])
		  ret = (l+1)*(l+1);
	    }

    return ret;
  }

Medium - PouringWater

できなかった。この問題のボトルが、2進数と同じ構造を持っているということに気づくことができれば、解けたと思います。そうするとこの問題は、2進数で表現したときに立っているビットの数がKである、N以上の最小の値を探すという問題に変換できます。また、新しく買えるボトルの数に制限がないので、返り値が-1になることはありません。

cafelierさんの日記を参考にさせていただきました。

  int countBit(int N)
  {
    int n = N;
    int counter = 0;

    while (n)
      {
	if (n & 1)
	  counter++;
	n = n >> 1;
      }

    return counter;
  }

  int getMinBottles(int N, int K)
  {
    for (int i=0;;i++)
      {
	if (countBit(N+i) <= K)
	  return i;
      }

    return -1;
  }

SRM349 div2(過去問)

07:18

Easy - DocumentSearch

文字列をサーチする系統の問題。

この手の問題は、ループの境界を間違えやすいです。それぞれのループの開始・終了条件や、イテレータへの加減算には特に注意。逆にチャレンジのチャンスにもなる。

僕は今回、一致するフレーズがあるかどうかを自前で書いたのですが、関数(findとかsubstr)を積極的に使った方が、早いし安全ですね。

  int nonIntersecting(vector <string> doc, string search)
  {
    int i, j, k;
    int ret = 0;
    string s = "";

    for (i=0; i<doc.size(); i++)
      s += doc[i];

    for (i=0; i<s.size(); i++)
      {
	if (s[i] == search[0])
	  {
	    bool found = true;
	    for (k=1; k<search.size(); k++)
	      {
		if (s[i+k] != search[k])
		  {
		    found = false;
		    break;
		  }
	      }

	    if (i+search.size() > s.size())
	      found = false;

	    if (found)
	      {
		ret++;
		i += k-1;
	      }
	  }
      }

    return ret;
  }