Hatena::Grouptopcoder

cou929のTopCoder日記

2009-10-31

SRM387 div2

12:12

Easy - GuessingNextElement

数列が与えられる。数列は必ず等差数列か等比数列のどちらかである。どちらかを判定し、次の要素を返せ。

必ずどちらかの数列になるという制約があるので、Aが等比数列かどうかだけ調べ、違っていれば等差数列と考えることができます。こうして等差・等比を求め、解を計算します。

class GuessingNextElement {
public:
  int guess(vector <int> A)
  {
    int p = A[0];
    int art = A[1] - A[0];
    int geo = A[1] / A[0];
    bool isGeo = true;
    if (A[1] % A[0] != 0)
      isGeo = false;

    if (isGeo)
      {
	int n = p;
	for (int i=1; i<A.size(); i++)
	  {
	    n *= geo;
	    if (n != A[i])
	      {
		isGeo = false;
		break;
	      }
	  }
      }

    if (isGeo)
      return A[A.size()-1]*geo;
    else
      return A[A.size()-1]+art;
  }
};

Medium - MarblesRegroupingEasy

問題文は省略。

最適解には必ずjorker boxがあります。各々のboxについて、それがjorkerであると設定し、以下の方法で必要なステップ数を調べ、最小値を返します。ステップ数はjorkerでないそれぞれのboxについて、

  • 2種類以上のマーブルが入っている場合、全てをjorker boxに移動する。
  • 1種類のマーブルしか入っていない場合、他にもそのようなboxがある場合は、それらを一つにまとめなければならない。層でない場合は、何もしないでいいので、ステップ数は増えない。

はじめ、jorkerの選び方を、一番多くの種類のマーブルが入っているボックスという風に決めていたので、システムテストに落ちてしまいました。

class MarblesRegroupingEasy {
public:
  int minMoves(vector <string> boxes)
  {
    int ret = 100000;

    for (int jorker=0; jorker<boxes.size(); jorker++)
      {
	int tmp = 0;
	bool flg[boxes[0].size()];
	memset(flg, false, sizeof(flg));
	for (int i=0; i<boxes.size(); i++)
	  if (i != jorker)
	    {
	      int counter = 0;
	      int pos = 0;
	      for (int j=0; j<boxes[i].size(); j++)
		if (boxes[i][j] != '0')
		  {
		    counter++;
		    pos = j;
		  }

	      if (counter > 1)
		tmp++;
	      else if (counter == 1)
		{
		  if (!flg[pos])
		    flg[pos] = true;
		  else
		    tmp++;
		}
	    }

	ret = min(tmp, ret);
      }

    return ret;
  }
};