Hatena::Grouptopcoder

cou929のTopCoder日記

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