Hatena::Grouptopcoder

cou929のTopCoder日記

2009-10-17

SRM450 div2

04:18

ratingは微増+4の1116。500と1000の両方がシステムテストに落ちるという情けない結果でした。

Easy - StrangeComputer

初期状態がすべて0のビットパターンがある。このビットパターンに対して、ある地点と値(1か0)を指定すると、それ以降のビットがすべてその値になる、というオペレーションがある。たとえば0000に対して左から2番目の位置と値1を指定すると、0111というパターンになる。ビットパターンが与えられるので、このオペレーションを何回行えば、このビットパターンが再現できるか求めよ。

左から右へ走査し、パターンが何度変化するかを調べれば良いです。ただし初期状態が0なので、左端が1の場合に対応できるようにしています。

class StrangeComputer {
public:
  int setMemory(string mem)
  {
    int ret = 0;
    char c = '0';

    for (int i=0; i<mem.size(); i++)
      if (mem[i] != c)
	{
	  ret++;
	  c = mem[i];
	}

    return ret;
  }
};

Medium - OrderedNim

nimというゲームの派生である、orderdNimをプレイして、どちらが勝つか。詳細は省略。

各heapの石の数は、1かそれより大きいかだけが問題になります。はじめに1より大きいheapをとることができる人が勝つので、layoutを小さい方からみていき、はじめに1以外の数が入っている地点を調べ、その地点が偶数ならalice、そうでなければbobの勝ちとなります。

アルゴリズムは思いついたんですが、breakを書き忘れるというどうしようもないイージーミスをしてしまい、システムテストに落ちてしまいました。本当に悔やまれます。

class OrderedNim {
public:
  string winner(vector <int> layout)
  {
    int first = layout.size()-1;
    for (int i=0; i<layout.size(); i++)
      if (layout[i] != 1)
	{
	  first = i;
	  break;    // ここのbreakを書き忘れた。
	}

    if (first % 2 == 0)
      return "Alice";
    else
      return "Bob";
  }
};

Hard - EnemyTowers

シミュレーションゲームで、自分と相手のパラメータが与えられ、最短何ターンで勝てるか、あるいは負けるかを求める。詳細は省略。

まず、あるパラメータのもとで相手を倒すには何ターンかかるか、あるいは負けるかを調べる関数getTurn()を作り、あとはmyUnitsをバイナリサーチして解を求めるというアプローチを考えました。システムテストに落ちてしまったんですが、問題点は以下の3つです。

  • バイナリサーチの範囲の変更を失敗していた。これは修正済み
  • バイナリサーチをしている部分で、イテレーションの回数が少なく、十分な解が出ていなかった。こちらも修正済み。
  • numWodT, numStoTのワーストケースでは、getTurn()が遅く、TLEする。

今日は疲れたので、後日最適化を行いたいと思います。また、バイナリサーチはたびたび使う技術なので、もう少し慣れたいです。今回もコードはつたないし、一度間違えてしまいました。何回イテレーションすれば、十分な精度が出るかを見積もる練習も必要です。

以下はまだシステムテストに通らないコードです。

class EnemyTowers {
public:
  int getTurn(int units, int hp, int attack, int numt)
  {
    int ret = 0;

    vector <int> towers(numt, hp);

    while (1)
      {
	int tmp = units;
	for (int i=0; tmp > 0 && i<towers.size(); i++)
	  {
	    if (towers[i] > 0)
	      {
		if (towers[i] >= tmp)
		  {
		    towers[i] -= tmp;
		    tmp = 0;
		  }
		else
		  {
		    tmp -= towers[i];
		    towers[i] = 0;
		  }
	      }
	  }

	int ct = 0;
	for (int i=0; i<towers.size(); i++)
	  if (towers[i] > 0)
	    ct++;

	units -= ct * attack;

	if (units <= 0)
	  break;

	ret++;

	if (towers[towers.size()-1] <= 0)
	  break;
      }

    if (units <= 0)
      ret = -1;

    return ret;
  }

  int attack(int myUnits, int hpT, int attackT, int numWodT, int numStoT)
  {
    int ret = -1;
    int left = 0;
    int mid = myUnits / 2;
    int right = myUnits;

    for (int i=0; i<250; i++)
      {
	int wood = mid;
	int stone = myUnits - wood;

	int resWood = getTurn(wood, hpT, attackT, numWodT);
	int resStone = getTurn(stone, hpT, attackT, numStoT);

	//	cout << mid << " " << resWood << " " << resStone << endl;

	if (resWood == -1 && resStone == -1)
	  return -1;

	if (resWood != -1 && resStone != -1)
	  {
	    if (resWood > resStone)
	      {
		left = mid;
		mid += (right - mid) / 2;
	      }
	    else
	      {
		right = mid;
		mid = (mid - left) / 2;
	      }
	  }
	else
	  {
	    if (resWood == -1)
	      {
		left = mid;
		mid += (right - mid) / 2;
	      }
	    else
	      {
		right = mid;
		mid = (mid - left) / 2;
	      }
	  }

	if (resWood != -1 && resStone != -1)
	  if (ret == -1)
	    ret = max(resWood, resStone);
	  else
	    ret = min(ret, max(resWood, resStone));
      }

    return ret;
  }
};

challenge phese

500点問題で、単に1の数を数えているひとなどがいたので、5人くらいチャレンジ成功しました。

この時点では3問とも解けており、チャレンジも成功していたので、4桁の高得点が出ていて、つかの間ですが意気揚々でした。

system test

500、1000が落ちました。理由は上記の通りです。

rating

プラス4の1116です。


気分的にも上がったり下がったりで疲れました。またすぐ次があるので、div1目指してがんばります。