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