Hatena::Grouptopcoder

cou929のTopCoder日記

2009-04-30

SRM419 div2(過去問)

23:28

Easy - ColumnDiagramPerimeter

グラフの周囲長を求める問題。特に難しいポイントはなし。

  int getPerimiter(vector <int> a)
  {
    int i;
    int ret = 0;

    ret = a.size() * 2;

    a.insert(a.begin(), 0);
    a.push_back(0);

    for (i=0; i<a.size()-1; i++) {
      ret += abs(a[i] - a[i+1]);
    }

    return ret;
  }

Medium - Undo

テキストエディタの一機能を実装している。2種類のコマンドがある。ひとつはtype s。文字sをテキストの末尾に追加するコマンド。もうひとつはundo n。時間nの時点まで処理を戻す。それぞれのコマンドには実行した時点の時間が記録されている。コマンドとそれを実行した時刻を入力とし、最終的なテキストを出力するという問題。

ポイントは再帰的に現れるundo命令をどう処理するかというところでしょう。僕がはじめにたてた戦略は、まずerase sという命令を導入。erase sはsをテキスト末尾から消去するという命令。そして、命令セットの先頭から走査し、undoだった場合は、undoが有効な時間だけ前に戻り、type sはerase sへ変換。逆にerase sはtype sへ変換していきます。こうすることで、最終的にはすべての命令がtypeとeraseのみになります。最後に命令を最初から順に処理し、出力のテキストを生成します。例えば、

commands = {"type a", "type b", "undo 2", "undo 2"}
time = {1, 2, 3, 4}

の場合、最終的な命令セットは、

{"type a", "type b", "erase a", "erase b", "type a", "type b", "erase b"}

となります。

しかし、この戦略だと実装がけっこう複雑になり、時間内には間に合いませんでした。

ほかの人のコードを見たところ、次の戦略をとっている人が多かったです。まず、命令セットを順に走査し、それぞれの時刻でのテキストの状態をvector <string>形式などで保存しておく。もしundo命令にさしかかったら、その時間だけ以前の状態へ戻すというものです。確かにこれならシンプルなので、実装も比較的容易です。

  string getText(vector <string> commands, vector <int> time)
  {
    int i;
    vector <string> V(100);
    string ret = "";

    for (i=0; i<commands.size(); i++)
      {
	if (commands[i][0] == 't')
	  {
	    V[i] = ret;
	    ret += commands[i][5];
	  }
	else
	  {
	    V[i] = ret;

	    int u;
	    sscanf(commands[i].c_str(), "undo %d", &u);

	    for (int j=i-1; j>=0; j--)
	      {
		if (time[i] - time[j] <= u)
		  {
		    ret = V[j];
		  }
		else
		  break;
	      }
	  }
      }

    return ret;
  }

SRM352 div2(過去問)

10:45

Easy - AttendanceShort

特に難しいことはない問題。一カ所、75%未満のところを75%以下と間違えていたため、少しタイムロスになってしまった。

  vector <string> shortList(vector <string> names, vector <string> attendance)
  {
    int i, j;
    vector <string> ret;

    for (i=0; i<names.size(); i++) {
      map <char, int> m;
      for (j=0; j<attendance[i].size(); j++)
	m[attendance[i][j]]++;

      if ((double)m['P'] / (attendance[i].size() - m['M']) < 0.75)
	ret.push_back(names[i]);
    }

    return ret;
  }

SRM351 div2(過去問)

06:50

Medium - CoinExchange

あなたはRPGをプレイしている。ゲームの世界には、ゴールド、シルバー、ブロンズの3種類の通貨がある。銀行ではそれぞれの通貨を以下のルールで交換できる。

  • 1枚のゴールドを9枚のシルバーと交換
  • 11枚のシルバーを1枚のゴールドと交換
  • 1枚シルバーを9枚のブロンズと交換
  • 11枚のブロンズを枚のブロンズと交換

あなたは現在G1枚のゴールド、S1枚のシルバー、B1枚のブロンズを持っている。今あなたはには欲しい装備がある。装備の値段はG2, S2, B2である。銀行で最低何回交換すれば、その装備を買えるか。何回交換しても無理な場合は-1を返す。

できませんでした。僕が考えた戦略は、それぞれの通貨の余剰・不足分をだし、それら全てを正負を保存したままブロンズ通貨に交換、それぞれにかかった交換回数の差を返すというものです。素直な戦略だと条件が多く複雑になる気がしたので、全てをブロンズ通貨に交換した方がシンプルになるのではないかと考えたためです。しかし、上位への交換と下位への交換が9枚/11枚という風に非対称なので、この方法ではできません。

解答と解説をみたところ、素直な戦略で解いていました。

  1. ゴールドが足りなければ、シルバーの余剰からとってくる。シルバーの余剰がなければ、ブロンズの余剰からとってくる。
  2. シルバーが足りなければ、ゴールドの余剰からとってくる。ゴールドの余剰がなければ、ブロンズの余剰からとってくる。
  3. ブロンズが足りなければ、シルバーの余剰からとってくる。シルバーの余剰がなければ、ゴールドの余剰からとってくる。

個人的なポイントは、2段階の交換が必要な場合の処理です(例えばゴールドとブロンズなど)。1度にすべて交換してしまうのではなく、1回のループで1回交換とすると、コードがシンプルになります。例えばブロンズをゴールドに交換する場合、最初のループでブロンズを11枚マイナスし、シルバーを1枚増やす。これを11回繰り返し、その後のループでシルバーを11枚マイナスし、ゴールドを1増やすという具合です。

  int countExchanges(int G1, int S1, int B1, int G2, int S2, int B2)
  {
    int ret = 0;

    while (G1 < G2) {
      if (S1 >= 11) {
	S1 -= 11;
	G1++;
	ret++;	
      }
      else if (B1 >= 11) {
	B1 -= 11;
	S1++;
	ret++;
      }
      else
	return -1;
    }

    while (S1 < S2) {
      if (G1 > G2) {
	G1--;
	S1 += 9;
	ret++;	
      }
      else if (B1 >= 11) {
	B1 -= 11;
	S1++;
	ret++;
      }
      else
	return -1;
    }

    while (B1 < B2) {
      if (G1 > G2) {
	G1--;
	S1 += 9;
	ret++;	
      }
      else if (S1 > S2) {
	S1--;
	B1 += 9;
	ret++;
      }
      else
	return -1;
    }
    return ret;
  }

Easy - RoomNumber

部屋のドアにルームナンバーを取り付ける。店には0-9までの10個入りで、数字のプレートのセットが売っている。自分の部屋番号(roomNumber という引数で与えられる)を表すのには何セット必要か。ただし6と9は、逆さまにすることで、お互い代用できる。

戦略:roomNumber中の各数字の頻度をカウント、最も頻度が高いものを返す。6と9の場合は、6と9の頻度を足して2で割る。その際小数点以下は繰り上げする必要がある。例えば、6が1、9が2という頻度だった場合、(1+2)/2=1.5。この場合、実際には2セット必要なので、1.5を繰り上げして2という数字が欲しい。

この繰り上げの部分を最初このように実装しましたが、

// c はmapで、c[n]にはnの頻度を格納
int ret = (c[6] + c[9]) / 2 + 0.9;

これでは"(c[6] + c[9]) / 2"の部分はint型で計算されるので、小数点以下が切り捨てられ、うまくいかない。よって、

int ret = (c[6] + c[9]) / 2.0 + 0.9;

// または

int ret = (c[6] + c[9] + 1) / 2;

とする必要がある。

この繰り上げの部分はテストケースでカバーされていなかったので、もしかしたらチャレンジのチャンスがあったかもしれない。

class RoomNumber {
public:
  int numberOfSets(int roomNumber)
  {
    int i;
    map <int, int> c;
    map <int, int>::iterator it;
    int ret = 0;

    while (roomNumber)
      {
	int n;
	n = roomNumber % 10;
	roomNumber /= 10;

	c[n]++;
      }

    for (it=c.begin(); it!=c.end(); it++)
      {
	int n = 0;
	if (it->first == 6 || it->first == 9)
	  n = (c[6] + c[9]) / 2.0 + 0.9;
	else
	  n = it->second;
	if (ret < n)
	  ret = n;
      }

    return ret;
  }
};

2009-04-29

SRM350 div2 (過去問)

11:00

Medium - SumsOfPerfectPowers

n = a^m + b^k (ただし各変数は非負、m, kは2以上) を満たすnを sum of two perfect powers と定義する。2つのint型の引数lowerBound, upperBound間の整数のうち、sum of two perfect powersとなる値の数を返す。lowerBound, upperBoundは1から5000000までの範囲。

最初に全てのsum of two perfect powersのリストを作り、求める値がそこにあるかを調べる戦略でいくことに。リストはsetで実装しました。

  int howMany(int lowerBound, int upperBound)
  {
    int i;
    set <int> p;
    set <int> pp;
    set <int>::iterator si;
    set <int>::iterator sj;
    int ret = 0;

    for (i=0; i*i<=upperBound; i++)
      {
	if (i <= 1)
	  p.insert(i);
	else
	  {
	    long long n = i*i;
	    while (n <= upperBound)
	      {
		p.insert(n);
		n *= i;
	      }
	  }
      }

    for (si=p.begin(); si!=p.end(); si++)
       for (sj=si; sj!=p.end(); sj++)
          if (*si + *sj <= upperBound)
	     pp.insert(*si + *sj);

    for (i=lowerBound; i<=upperBound; i++)
       if (pp.find(i) != pp.end())
	  ret++;

    return ret;
  }

しかしこのままでは、lowerBoundが1、upperBoundが5000000というワーストケースではTLEでした。最後のfind()で調べてカウントしている部分が重いので、boolの配列にフラグを立てる方法に代えました。


  int howMany(int lowerBound, int upperBound)
  {
    int i;
    set <int> p;
    set <int>::iterator si;
    set <int>::iterator sj;
    int ret = 0;

    bool used[5000001];
    memset(used, false, sizeof(used));

    for (i=0; i*i<=upperBound; i++)
      {
	if (i <= 1)
	  p.insert(i);
	else
	  {
	    long long n = i*i;
	    while (n <= upperBound)
	      {
		p.insert(n);
		n *= i;
	      }
	  }
      }

    for (si=p.begin(); si!=p.end(); si++)
      for (sj=si; sj!=p.end(); sj++)
	if (*si + *sj <= upperBound)
	  used[*si + *sj] = true;

    for (i=lowerBound; i<=upperBound; i++)
      ret += used[i];

    return ret;
  }

この変更で大丈夫でした。ワーストケースでも実行時間は約100msでした。

1~5000000の場合、答えは149070。よって上記のfind()を使うアルゴリズムだと、ほとんどの場合find()はリストの最後まで探索することになります。よって、約 4850000^2 というオーダーの計算量になるということだと思います。これは時間がかかるはずです。

Easy - DistanceBetweenStrings

文字間の距離を、(n1 - n2)^2、ただしn1は文字列aでの文字nの頻度、n2は文字列bでの文字nの頻度と定義する。文字列a, b, lettersetが与えられたとき、letterset内の各文字の距離の総和を返すという問題。

この問題ポイントは文字の頻度を数える部分だけだなと思い、そこの部分はmapで実装。テストケースも全て通り、サブミットするも、システムテストで落ちました。原因は大文字と小文字を区別しないという条件を忘れていたからでした。うっかりしてたと思いつつ、tolower()を追加し、無事システムテストも通りました。ただ、今回のテストケースでは、大文字小文字を区別"する"アルゴリズムでも正しい答えがでちゃうところがいやらしいなあと思いました。

  int getDistance(string a, string b, string letterSet)
  {
    int i;
    map <char, int> am;
    map <char, int> bm;
    int ret = 0;

    for (i=0; i<a.size(); i++)
      am[tolower(a[i])]++;

    for (i=0; i<b.size(); i++)
      bm[tolower(b[i])]++;

    for (i=0; i<letterSet.size(); i++)
      ret += (am[letterSet[i]] - bm[letterSet[i]])*(am[letterSet[i]] - bm[letterSet[i]]);

    return ret;
  }

2009-04-25

SRM418 div2 (過去問)

15:10

Level one - Towers

ターン性シミュレーションゲームみたいな問題。敵味方のhp、攻撃力や数が与えられて、何ターンで敵を倒せるか、倒せなければ-1を返すというもの。特に難しいところはなかった。

Level two - TwoLotteryGames

lottery gameというゲームで勝つ確率を求める問題。ルールは、プレイヤーと胴元はそれぞれ、1~nの整数の中から別々のm個を選択する。k個以上一致する数字を選んでいたら、プレイヤーの勝利というもの。問題では、n, m, kの値が与えられ、プレイヤーが勝利する確率を返す。

定式化さえできれば問題なく解けるなと思いましたが、定式化がうまくできない。しばらく悩んだ末、解説と解答をみました。

プレイヤー視点で考える。胴元が選んだm個の整数と、ちょうどi個一致している確率は、(胴元が選んだm個の数字からi個選択する組み合わせ) * (胴元が選んでいないn-m個の数字からm-i個の数字を選択する組み合わせ) / (n個の数字からm個選択する組み合わせ) と考えることができる。よって、binom(m, i) * binom(n-m, m-i) / binom(n, m) となる。あとはiをkからnまで計算すればok。

そりゃそうだよなあ。そんなに難しくないよなあという解答でした。k個以上の全ての組み合わせをいっぺんに求めようとしたのが敗因でした。うーん。このくらいさっとできるようにならなきゃなあ。

これとは別に、もう一つ解答方針が示されていました。nの範囲が1から高々8までなので、すべてのとりうる組み合わせを列挙し、条件に合う組み合わせの数を数えるという方法です。brute-forceな考え方ですね。計算量はだいたいO(n!)なので、間に合うということ。なるほど。

この方針だと、全ての場合を生成する部分が難しいところだと思うので、その部分のみ実装してみました。まず、それぞれの組み合わせは、ベクターのベクター(vector <vector <int> >)で表現することにしました。計算はcombinationsというクラスが行います。calc()という関数にnとmの値を渡すと、r()という関数を再帰的に呼び出し、結果を保存していきます。print()という関数で結果を表示します。ループでやろうとしたのですがうまく思いつかなかったので、再帰で実装しました。以下は、1から5の数字の中から、3個選ぶ組み合わせを求めています。

// srm418.cpp

#include <vector>
#include <iostream>

using namespace std;

class combinations {
private:
  vector <vector <int> > result;
  int n;
  int m;
public:
  combinations(){};
  int calc(int _n, int _m);
  void r(int l, int r, vector <int> v);
  int print();
};

void combinations::r(int l, int r, vector <int> v)
{
  for (int i=l; i<=r; i++)
    {
      v.push_back(i);

      if (r == n)
	result.push_back(v);
      else
	this->r(i+1, r+1, v);

      v.pop_back();
    }
}

int combinations::calc(int _n, int _m)
{
  n = _n;
  m = _m;
  vector <int> tmp;
  r(1, n-m+1, tmp);

  return 0;
}

int combinations::print()
{
  for (int i=0; i<result.size(); i++)
    {
      for (int j=0; j<result[i].size(); j++)
	cout << result[i][j] << " ";
      cout << endl;
    }

  return 0;
}

int main(void) 
{
  combinations *c = new combinations;

  c->calc(5, 3);  // n = 5, m = 3 を計算
  c->print();     // 結果を表示

  return 0;
}

実行結果は以下の通り、うまくいったようです。

% g++ -Wall srm418.cpp && ./a.out
srm418.cpp: In member function 'int combinations::print()':
srm418.cpp:45: warning: comparison between signed and unsigned integer expressions
srm418.cpp:47: warning: comparison between signed and unsigned integer expressions
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

2009-04-19

SRM438 div2

03:35

Level one - UnluckyNumbers

20分くらいかかってしまった。チャレンジを成功させまくっている人がいて、さらにシステムテストでもほとんどの人が落ちたので、結局解けたのは部屋で二人だけ。落ち着いてチャレンジをがんばればよかった。

失敗していた人たちは、境界条件をうまく処理できていなかったみたい。特に、LuckyNumberとnがn<LuckyNumbarと連続していた場合({3,6}, 5など)に間違っているものが多かった。


Level two - FeudaliasBattle

こちらは解けてる人が少なくて(250点問題に時間をとられすぎたのかな)、さらにシステムテストで落ちまくり。僕も落ちた。結局部屋で通ったのは一人だけという状況。

原因はintのオーバーフローでした。下のように、xy座標系の2点間の距離を求める必要があったのですが、

double getdistance(int x1, int y1, int x2, int y2)
{
  return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

x1, x2, y1, y2 はそれぞれ、最大1000000の値をとる可能性があるので、1000000^2で桁あふれします。なので、自乗しているところをdoubleでキャストしてあげる必要があります。

double getdistance(int x1, int y1, int x2, int y2)
{
  return sqrt((double)(x1-x2)*(double)(x1-x2) + (double)(y1-y2)*(double)(y1-y2));
}

ちなみに、intは4バイトだとすると、プラスマイナス約20億くらいまで格納できます。doubleの範囲は、

2.225074 10-308 < double の絶対値 < 1.797693 10+308

です。この上/下限値は <float.h> の DBL_MIN, DBL_MAX というマクロに定義されています。


TopCoder部@はてなに参加

09:40

TopCoder部

topcoderでぐぐっていたらたまたま発見したので、参加してみました。よろしくお願いします。

みてみると皆さんdiv1で活躍されている方が多く、恐縮しました。僕はまったりdiv2の日記をつけていこうかと思います。今年の目標青色になること。

JasonWeidoJasonWeido2017/01/25 04:21печать блокнотов с логотипом http://wkrolik.com.ua