Hatena::Grouptopcoder

cou929のTopCoder日記

2009-11-13

SRM430 div2 (過去問)

00:23

Easy - CreateGroups

あなたは塾を経営している.いくつかのクラスがあり,それぞれの参加希望者が与えられる.また全ての授業はminSize以上maxSize以下の人数しか受け入れられない.参加希望者を別のクラスへ何人移動させれば,授業を開講できるか.

面倒くさい問題でした.ごちゃごちゃしちゃっていますが,アルゴリズムは以下です.

  1. 定員オーバーしている人数と,定員を下回っている人数のそれぞれのトータルを出す.
  2. オーバーの人数とアンダーの人数(下回っているクラスの足りない人数)を比べる.
    1. オーバーしている人が多い場合,他のクラスにどれだけ空きがあるか調べる.空きが余っている人より多ければ,オーバーしている人数を返す.そうでなければ不可能なので-1を返す.
    2. アンダーしている人が多い場合,他のクラスから何人まわせるかを調べる.まわせる数が足りていればアンダー人数を,足りていなければ不可能で-1を返す.
class CreateGroups {
public:
  int minChanges(vector <int> groups, int minSize, int maxSize)
  {
    int ret = 0;
    vector <int> flgs(groups.size(), 0);
    vector <int> nums(groups.size(), 0);
    int overs = 0;
    int unders = 0;

    for (int i=0; i<groups.size(); i++)
      {
	if (groups[i] < minSize)
	  unders += minSize - groups[i];
	else if (groups[i] > maxSize)
	  overs += groups[i] - maxSize;
      }

    if (unders == overs)
      ret = overs;
    else if (unders < overs)
      {
	int capacity = 0;
	for (int i=0; i<groups.size(); i++)
	  {
	    if (groups[i] > maxSize)
	      capacity += 0;
	    else if (groups[i] < minSize)
	      capacity += maxSize - minSize;
	    else
	      capacity += maxSize - groups[i];
	  }

	if (capacity < (overs - unders))
	  ret = -1;
	else
	  ret = overs;
      }
    else if (overs < unders)
      {
	int capacity = 0;
	for (int i=0; i<groups.size(); i++)
	  {
	    if (groups[i] > maxSize)
	      capacity += maxSize - minSize;
	    else if (groups[i] < minSize)
	      capacity += 0;
	    else
	      capacity += groups[i] - minSize;
	  }

	if (capacity < (unders - overs))
	  ret = -1;
	else
	  ret = unders;
      }

    return ret;
  }
};

Medium - BitwiseEquations

xとkが与えられるので,次の式を満たすyのうち,小さい方からk番目のyをもとめよ.

x + y = x | y (|はビット演算のor)

たとえばx=10の時を考えると,yは以下のように1, 4, 5, 16, ... という系列になります.

 01010
+    1 => 1
------
  1011

 01010
+  100 => 4
------
  1110

 01010
+  101 => 5
------
  1111 

 01010
+10000 => 16
------
 11011

つまり,xを2進数表現にして,0の部分だけでkの数をカウントしていく,というイメージです.よってアルゴリズムはこうなります.

  1. x, kをそれぞれ2進数で考える.
  2. xの一桁目を調べる.
    1. 1の場合,解(2進数表現)の先頭に0を加える.
    2. 0の場合,解の先頭に,kの一桁目を加える.kを右に一桁シフト
  3. xを左に1桁シフト
  4. 以上をx, yがともに0になるまで繰り返す.

例えば,テストケース2(x=10, y=3)の場合.

  1. x=10の2進数表記は1010, y=3の2進数表記は11
  2. xの一桁目は0.解の先頭にkの一桁目である1を加え,解は現在1(1).kを右にシフトし,k=1(1).xを右にシフトし,x=5(101).
  3. xの一桁目は1.解の先頭に0を加え,解は現在1(01).xを右にシフトし,x=2(10).
  4. xの一桁目は0.解の先頭にkの一桁目である1を加え,解は現在5(101).kを右にシフトし,k=0(0).xを右にシフトし,x=1(1).
  5. xの一桁目は1.解の先頭に0を加え,解は現在5(0101).xを右にシフトし,x=0(0).

よって解は5となります.

実際にはxの一桁目が0かつkの一桁目が1のときにのみ操作をすればいいので(0のビットを先頭に立てても値はかわらないため),以下のコードはそのような実装になっています.

また,以下でコメントしてある解を作る行で,はじめ定数1にLLをつけていなかったため,計算中はint扱いとなり,オーバーフローしてしまい,一度システムテストに落ちてしまいました.

class BitwiseEquations {
public:
  long long kthPlusOrSolution(int x, int k)
  {
    long long ret = 0;
    int n = 0;

    while (x != 0 || k != 0)
      {
	if ((x & 1) == 0)
	  {
	    if ((k & 1) == 1)
	      ret = ret | (1LL << n);    // "LL"をつけ忘れてオーバーフローした
	    k = k >> 1;
	  }
	x = x >> 1;
	n++;
      }

    return ret;
  }
};