Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2010-10-09SRM484 Div1

SRM484 Div1 250 RabbitNumber

| 14:30 | SRM484 Div1 250 RabbitNumber - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM484 Div1 250 RabbitNumber - SRM diary(Sigmar) SRM484 Div1 250 RabbitNumber - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→TaroとHanako・・・出た・・・

→全然分からないし・・・

→まあでも10億なら最悪データ埋め込みで解けそうだな。250でその解はないだろうが・・・

→とりあえず考えてみよう

→えーと・・・1000000000を除くと最大9桁の入力なので、、S(x*x)はたかだか9*18桁=162か

→えーと平方数だから最大144・・・

→18桁で足しあわせて144になる数を列挙すると・・・何かすごく多そう・・ダメぽい(←この辺勘違いしすぎでした。9桁で考え

る問題だったのに・・・。もっとちゃんと考えれば良かった)

→・・・

→an*10^n+...+a0*10^0みたいに分解して考えてみよう

→えーと二乗して展開すると・・・係数は・・・

→いかん、訳わからん。250でこんな複雑なはずがない。やめよう。(←もう少し考えれば良かった・・・)

→・・・

→駄目だ・・全然思いつかない。最終手段で行くか・・

→埋め込み用計算開始

→(計算の間500の問題を読む)

→15分後

→計算終わった→サンプル合わない

→ええええええ

→なんでやねん・・・

→あー・・またintがオーバーフローとかか・・→long longに修正して再度計算

→(500の問題を考える)

→15分後

→そろそろ終わったかな

→あれ・・25%しか進んでない

→そういえばPCがすごく重いぞ

→PCが火傷しそうなほど熱い。やばい。冷やそう

→15分後

→85%程度まで計算した状態で時間切れ・・・終わった・・・


チャレンジフェーズ

→lowからhighまでイテレートしてる人は・・・いない

→intのオーバフローは・・・1人いた。撃墜。+50

→終了


終了後

→あー・・よく考えたら入力は9桁で足しあわせて12以下の数なのか

→そうすると、、21C9で30万くらいしかないから余裕なのか(実際には1桁は9以下なのでもう少し少ない)

→というか、18桁で144になる数って10億より多いし、枝刈りしてるのに元より大きくなるとかありえないし勘違い酷すぎ

→埋め込みに頼りすぎだな。。。ちゃんと考えないと


以下、ソースです。

埋め込み版と枝刈り版です。

枝刈りは足し合わせて9*桁数以下という考えに基づいているので12以下列挙より更に枝刈りしたものになってます(あまり意味は

ないですが・・)


埋め込み版

class RabbitNumber {
public:
	ll calcr(ll n) {
		int res=0;
		while(n) {
			res+=n%10;
			n/=10;
		}
		return res;
	}

	int theCount(int low, int high) {
		int res=0;
		int pre[1050]={/*埋め込みデータは長いので省略*/};

		low--;
		int lb=low/1000000;
		int ls=pre[lb];
		for(int i=1; lb*1000000+i<=low; i++) {
			ll ii=lb*1000000+i;
			ll ri=calcr(ii);
			ll rii=calcr(ii*ii);
			if(ri*ri==rii) ls++;
		}

		int hb=high/1000000;
		int hs=pre[hb];
		for(int i=1; hb*1000000+i<=high; i++) {
			ll ii=hb*1000000+i;
			ll ri=calcr(ii);
			ll rii=calcr(ii*ii);
			if(ri*ri==rii) hs++;
		}

		res=hs-ls;

		return res;
	}
};

枝刈り版

static const double EPS = 1e-7;

class RabbitNumber {
public:
	ll calcr(ll n) {
		int res=0;
		while(n) {
			res+=n%10;
			n/=10;
		}
		return res;
	}

	int theCount(int low, int high) {
		int res=0;

		int sum=0;
		int dig=1;
		int thr=(int)(sqrt(dig*2.*9)+EPS);
		for(ll i=1; i<=high; i++) {
			sum=0;
			ll t=i;
			while(t) {
				sum+=t%10;
				t/=10;
			}
			while(sum>thr) {
				ll t=i;
				ll inc=10;
				while(t) {
					if(t%10) break;
					t/=10;
					inc*=10;
				}
				i+=inc-i%inc;
				sum=0;
				t=i;
				dig=0;
				while(t) {
					sum+=t%10;
					t/=10;
					dig++;
				}
				thr=(int)(sqrt(dig*2.*9)+EPS);
			}
			if(i<low) continue;
			if(i>high) break;
			ll r=calcr(i);
			ll r2=calcr(i*i);
			if(r*r==r2) {
				res++;
			}
		}

		return res;
	}
};

SRM484 Div1 550 PuyoPuyo

| 14:30 | SRM484 Div1 550 PuyoPuyo - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM484 Div1 550 PuyoPuyo - SRM diary(Sigmar) SRM484 Div1 550 PuyoPuyo - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→いかにもDP

→うーん・・・両端の状態を覚えながらぷよを追加していくとかかな

→・・・

→駄目だな・・・同じ色が長く連続する場合に同じパターンを複数回数えてしまう

→250のためほとんど考えることもできず終了


終了後

→rngさんの解説を見て解き方を理解した

→自分の考えと照らし合わせながら解釈すると以下のようなことだろうか

(L=4とする)


最初に考えた(解けない)方法


以下のような感じで両端の状態を覚える

 青青○○・・・○○赤赤

同じ色L個を両端にくっつける

 黄黄青青○○・・・○○赤赤黄黄

このようなL個のくっつけ方はL通りくらいあるので適当にDPする


しかし上記の方法だと以下のようなパターンで失敗する


以下に対して

 青青○○・・・○○青青

さらに青をL個くっつける

 青青青○○・・・○○青青青青青

しかしこのパターンは以下のように何通りもの方法で作成できる

  青青青○○・・・○○青 青青青青

 青 青青○○・・・○○青青 青青青

 青青 青○○・・・○○青青青 青青

従って同じものを何度も数えてしまう

なので両端の色と数を全部覚える必要があり計算量が膨大となる


そこで両端の色や数を覚えなくて良い方法を考える

ここでポイントとなるのが同じ色L個が2連続する上記のようなパターンでは、実は必ず両端のどちらかはL個以上同色が連続する

こと

そうすると、全消しできるパターン2つに必ず分解できる

 青青青○○・・・○○青 青青青青

こんな感じ


この考えを応用して、全ての解となるパターンを、これ以上分解できない全消しパターンの組み合わせで表現すると、同じ色L個

を2回以上連続して両端にくっつける必要はないということになる

例えば以下のような感じで分解する(○○・・○○は分解可能なものを含めた全消しパターン)

 青青○○・・・○○青青 赤赤赤赤 黄○○・・○○黄○○・・○○黄黄 黄黄黄黄


分解不可能な全消しパターンは、必ず両端に同じ色が現れる

両端の間は、また分解不可能な全消しパターンの組み合わせとなるので、再帰的な構造となる

ただし、全消しパターンの両端に囲まれた全消しパターンは、以下の制約を受ける

(囲んでいるほうの全消しパターンを上位、囲まれているほうを下位とする)

 ・各下位全消しパターン間のどこかに、上位の両端と同じ色のぷよがL-2個現れる

 ・下位全消しパターンの両端は、上位の両端と異なる色となる


上記に留意してメモ化再帰でコーディングすると以下のようになる。

#かなり考え方が難しいですね。

const int MOD=1000000007;
int memo[502][11][5];

class PuyoPuyo {
public:
	int L;

	int rec(int n, int r, int mul) {
		ll res=0;

		if(n==0) return 1;

		if(memo[n][r][mul]>=0) return memo[n][r][mul];

		for(int i=1; i<=n; i++) {
			for(int j=0; j<=r; j++) {
				ll t;
				if(i>1) t=(ll)rec(i-1, L-2, 3)%MOD;//下位全消しパターンの数え上げ
				else t=1;
				res+=t*rec(n-i, j, mul)%MOD;//残りの上位全消しパターンの数え上げ
				res%=MOD;
			}
		}

		//最上位の全消しパターンは4色あるので4倍、最上位以外の全消しパターンは3色なので3倍する
		res=res*mul%MOD;
		memo[n][r][mul]=res;
		return res;
	}

	int theCount(int L, int N) {
		int res;
		this->L=L;
		int n=N/L;
		if(N%L) return 0;

		memset(memo, -1, sizeof(memo));
		res=rec(n, 0, 4);

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20101009