Hatena::Grouptopcoder

cou929のTopCoder日記

2009-11-05

SRM452 div2

00:07

250と500ができて、ratingは1041->1101と増加。今年のsrmはあと3回しかないので、がんばらないと今年中に青になるという目標が厳しくなってきました。

ちなみに問題のwriterはrng_58さんだったそうです。

Easy - EggCartons

整数nが与えられるので、それを8と6の組み合わせで表す。例えば22=8*2+6*1。nを表すのに用いる最小の8と6の個数を返す(先の例なら3)。不可能なら-1。

nが高々100なので、0-100全てについて解を求めました。

class EggCartons {
public:
  int minCartons(int n)
  {
    int ans[101];
    memset(ans, -1, sizeof(ans));

    for (int i=0; i<=12; i++)
      for (int j=0; j<=16; j++)
	{
	  if (8*i + 6*j <= 100)
	    if (ans[8*i + 6*j] == -1)
	      ans[8*i + 6*j] = i+j;
	    else
	      ans[8*i + 6*j] = min(ans[8*i + 6*j], i+j);
	}

    return ans[n];
  }
};

Medium - NotTwo

グリッド上に石を置く。石と石の間のユークリッド距離は2であってはいけない。グリッドの幅と高さが与えられるので、置ける石の最大数を求める。

証明はできてないんですが、最適解では、以下のように2x2の市松模様っぽく石を置くことができます。

**--**--**--**--**--
**--**--**--**--**--
--**--**--**--**--**
--**--**--**--**--**
**--**--**--**--**--
**--**--**--**--**--
--**--**--**--**--**
--**--**--**--**--**

与えられた幅と高さに応じて、このように石が置かれていると仮定し、個数を数える事で解が求まります。

class NotTwo {
public:
  int maxStones(int width, int height)
  {
    int ret = 0;

    for (int i=0; i<width; i++)
      for (int j=0; j<height; j++)
	{
	  int row = i;
	  int col = j;
	  if (row % 2 != 0)
	    row--;
	  if (col % 2 != 0)
	    col--;

	  if (row%4==0 && col%4 == 0 ||
	      row%4 != 0 && col%4 != 0)
	    ret++;
	}

    return ret;
  }
};

Hard - HamiltonPath

問題文は省略。

できませんでした。アルゴリズムは思いついたのですが、実装ができませんでした。以下のようなアルゴリズムを考えました。

  • roadsが有効かチェック。
  • roadsのうち、つながっている道同士をつなげる。例えば、(0, 1) (4, 0)があった場合、(4, 0, 1)とする。
  • 上記処理後のroadsの各道を一つのノードとみなし、経路の数を計算する。これはノード数の階乗となる。
  • 上記の計算結果について、roadsの各道について2方向のパターンがあるので、2^(道の数)を掛ける。

例えばテストケース0の場合、ノードは0-2の三つで、通らなければならないパスは0-1間です。0-1を一つのノードとみなすと、2と(0, 1)の二つのノードとなり、経路は2!=2種類となります。0-1の道は、0->1という方向と1->0という方向の2種類があるので、2! * 2 = 4通りとなり、これが解です。

グラフには不慣れなので、実装に時間がかかり、間に合いませんでした。特に、グラフをどういうデータ構造で表すか。グラフをどう走査し、チェックするかという基本的な部分ができていません。

また、ワーストケースでは50!の計算が発生するので、オーバーフローが起こり、普通に上記の計算をしてから1000000007のmodをとる事はできません。この場合は毎回の乗算ごとにmodを計算するという方法で対処します。例えば、(A*B*C)%X は A%X * B%X * C%X (左から順に計算)という順で計算する事ができます。

challenge

一度もできませんでした。

rating

1041 -> 1101。部屋では2位、div2全体では110位でした。

yutoyutoriyutoyutori2009/11/07 04:12グラフですが、この場合はグラフとしては始端と終端を保持すればいいと思います。つまりint型変数2つでひとつのグラフを表現すれば足ります。
短絡グラフを合成した際に出た中間ノードはブラックリストに登録しておけばいいです(vector<int>)。何故ならば、ブラックリストに登録された中間ノードが尚別の短絡グラフに現われる時、その様な経路を使って全体のノードを一度だけ走査する事はできないからです。なので、0を返します。
1000000007のmodは僕も分かりませんでした。システムテストでは、ベタな階乗計算だとひとつのケースだけエラーが返るみたいです。

cou929cou9292009/11/08 02:58ありがとうございます!大変参考になりました。別エントリとしてポストしました。
http://topcoder.g.hatena.ne.jp/cou929/20091107/1257616436

modの件は、途中経過をlong longで保存する事で、僕の場合はうまくいきました。