Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/09/28

SRM 483 Bribes

| 00:55

http://www.topcoder.com/stat?c=problem_solution&rm=305892&rd=14236&pm=11037&cr=22851423

問題

選挙において投票者に最小限の賄賂を渡して勝つようにする.n 人の投票者がいて,それぞれ影響度 influence と抵抗度 resistance が存在する.i 番目の人に賄賂を渡すと,j 番目の人の抵抗度が influence[i]/2^|i-j| だけ減る.全員の抵抗度が 0 以下になれば賄賂は成功する.賄賂が成功する渡し方のうち,賄賂を渡す人数が最小になる人数を返す.できなければ失敗として -1 を返す.

アプローチ

一見すると O(n*2^n) な複数ナップサック問題のように見えるが,影響度の値が 500 以下,つまり 2^9 より小さいので両隣 8 人目まで考慮すればいいことが分かる.これで 2^n の部分が 2^17 の定数で押さえられるので O(n).で解くことができる(定数項はそれなりに大きいので注意).

両隣 8 人を含めた計 17 人への賄賂を 17-bit で表現することができる.DP の問題の分割は投票者の人数で行うことができる.つまり0人,1人,と増やしていく.i 人目の抵抗度を 0 にするには i-8 人目から i+8 人目までの影響度を考慮すればいい.抵抗度を 0 にできるパターンの中から最も賄賂を渡す人数が少ないパターンを記録している. i+1 人目を計算するには i 人目のビットパターンのうち上位 16-bit だけ分かればよいので,配列に保存するのは 16-bit 分で良いことが分かる. n 人目まで繰り返していき,最小の値(人数)を選ぶ.

配列のサイズが大きいので int では allocate できない.short を使う.

ソースコード

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

#include <cmath>

using namespace std;

#define sz(a) int((a).size())
#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)

short dp[51][1<<16];

int minBribes(vector <int> influence, vector <int> resistance)
{
	int n = sz(influence);
	int INF = 100;
	
	Rep(i,n+1) Rep(j,1<<16)
		dp[i][j] = i ? INF : __builtin_popcount(j);
	
	Rep(i,n) Rep(mask,1<<17)
	{
		int sum = 0;
		for(int j=i-8,k=0; j<=i+8; j++,k++)
			if((mask&(1<<k)) && 0<=j&&j<n)
				sum += influence[j]>>abs(j-i);
		if(sum>=resistance[i])
			dp[i+1][mask>>1] = min(
				(int)dp[i+1][mask>>1],
				(int)dp[i][mask%(1<<16)]+mask/(1<<16)
			);
	}
	int r = INF;
	Rep(j,1<<16)
		r = min(r,(int)dp[n][j]);
	
	return r>n ? -1 : r;
}

ttvijfyomttvijfyom2011/02/27 18:44XXnJye <a href="http://idnbvnetymog.com/">idnbvnetymog</a>, [url=http://ftuabcqbiduw.com/]ftuabcqbiduw[/url], [link=http://gwxepxsaficy.com/]gwxepxsaficy[/link], http://judtzquinqwh.com/

2010/05/24

Google Code Jam 2010 Round 1A B. Make it Smooth

| 16:01

http://code.google.com/codejam/contest/dashboard?c=544101#s=p1

解き方がわからなかった問題に再チャレンジ.

問題

最長 100 個の [0,255] の値(文字)が入った配列(文字列)が与えられる.隣り合う要素の差が M 以内であればこの文字列は smooth であるという.文字列に対して削除,置換,挿入の3操作が可能である.削除のコストは D で与えられ,置換のコストは置換前後の数値の差で定義される.挿入のコストは1要素につき I で与えられる.

このとき与えられた文字列を smooth にするために必要なコストの最小値を求める.

アプローチ

与えられた文字列に対してレーベンシュタイン距離の最小となるような文字列を作る操作を求める問題と等価である.

当たり前だけど,各文字を適当に固定して分岐して行く方法だと 255^100 以上の計算量になる.

と考えて実はこれやっぱりまさに典型的に DP で解けるのではないかと気付く.

(100 文字 + 頭 1)×(255 値)の配列 dp[101][256] を用意して,コストを代入して行く. dp[i][j] には i-1 番目の文字が j で i 番目の文字を決める直前のコストを代入する.

dp[0][j] は 0 で,他は十分大きな値にする(*1).INT_MAX を使ってしまうとコストを足したときに簡単に integer overflow を起こすので適度に大きくする.

前の文字 v[i-1] が j に決まったときに v[i] をある値 k に決めるコストを求めていき,k に決めた操作の中でコストが一番小さいものを取る.

これを繰り返して最後に N 文字目のコストで一番小さいものをとる(*2).

削除

v[i] を削除したときの累積コストは dp[i][j]+D である(*3).

変更

v[i] を文字 k に変更したときの累積コストは dp[i][j]+abs(v[i]-k) である(*4).ただし変更は M 以内に収まるような場合のみを行う.

挿入

j → k をつなぐ挿入を行うコストは I*((abs(k-j)-1)/M+1) である.

ここで気をつけなくてはいけないのが,v[i] の前,つまり v[i-1]=j → v[i]=k について挿入操作を行うのではなく,v[i] の後に行うということである.v[i]=j の後に,最後の文字が k になるように挿入を行うと, v[i+1] はあたかも v[i]=k に見える.

ポイントはこの挿入の操作は削除,変更を行ってコストを決めた後の v[i] に対して行うということである.

これを考慮しないと,値の変更・削除を行ってからその間に挿入を行う方がコストが安いケースに対応出来ない.

ここでハマった.

なので累積コストは dp[i][j]+I*((abs(k-j)-1)/M+1) ではなく dp[i+1][j]+I*((abs(k-j)-1)/M+1) とし,削除と挿入の後にコストの改善を行わなくてはならない.

ソースコード

以上のことをまとめるとこういうコードになる.

  • 挿入のところの if(k!=j) が必要ないので削除(2010/05/27 10:07)
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>

using namespace std;

typedef vector<int> VI;

#define Rep(i,n) for(int i=0;i<(n);++i)
#define MN(a,b) a = min(a,b)

// 128 >= 100 chars + 1
// 256 = (0..255)
int dp[128][256];

int solve(int D, int I, int M, int N, VI &v)
{
	// initialization (*1)
	Rep(i,N+1) Rep(j,256) dp[i][j] = 10000000;
	Rep(j,256) dp[0][j] = 0;
	
	Rep(i,N)
	{
		//delete v[i] (*3)
		Rep(j,256)
			MN(dp[i+1][j], dp[i][j]+D);

		// modify v[i]=j to k (*4)
		Rep(j,256)
			Rep(k,256)
				if(abs(j-k)<=M)
					MN(dp[i+1][k], dp[i][j]+abs(v[i]-k));

		// insert chars after v[i] = j
		// the last inserted char is k (*5)
		if(M>0)
			Rep(j,256)
				Rep(k,256)
					MN(dp[i+1][k], dp[i+1][j]+I*((abs(j-k)-1)/M+1));
	}
	
	// (*2)
	int r = INT_MAX;
	Rep(j,256)
		MN(r,dp[N][j]);
	
	return r;
}

int main(int argc, char* argv[])
{
	int T;
	cin >> T;
	
	Rep(t,T)
	{
		int D, I, M, N;
		cin >> D >> I >> M >> N;
		VI v(N);
		Rep(n,N)
			cin >> v[n];
		int r = solve(D, I, M, N, v);
		cout << "Case #" << t+1 << ": " << r << endl;
	}
	
	return 0;
}

忍者最終号忍者最終号2010/05/24 14:291を数えないようにした方がもっと早くなりそうだ.

yuyarinyuyarin2010/05/27 10:16あ,本当ですね.
そのようにしてみました.

2010/05/23

Google Code Jam 2010 Round 1B C. Your Rank is Pure

| 04:38

http://code.google.com/codejam/contest/dashboard?c=635101#s=p2&a=0

問題

正数の集合 S の中においてある数 n が pure である条件がある.n が S の中で r 番目の数であるとき n のランクは r であると言う.n のランクが r1 であり,数 r1 のランクが r2 であり,,,としていき最後に 1 にたどり着けば n は pure であると言う.

与えられた n について, S = {x|x∈[2,n]} の部分集合 S' において n が pure であるような S' の作り方の個数を求める.

結果

small は correct だったけど提出するコードを間違えた.

large は答えを出したけど,提出がギリギリで駄目だったけど,admin に問い合せろとエラーが出た.

なので問い合わせ中.

→提出は + 0.674 秒遅かったらしい.そう計測された以上 reject とのこと.正しいソースコードの再アップロードと,エラーの理由はスルーされた.

large-practice では正解を出せていた.

アプローチ

数字 n がランク r として出現するときの場合の数を求める.

DP でも解けるけど DP にせずに再帰とキャッシュ(*1)を使った.

r〜n の間に m 個(m∈[0,r-2]) の数字が入る場合(*2)の数は Combination(n-r-1,m) で(*3),1〜r の間に数字が入る場合の数は数字 r がランク r-m-1 で現れる場合の数なのでこの関数の再帰で求められる.これらを掛け合せたものが,数字 n がランク r として出現するときの場合の数である(*4).

この関数を入力 n に対して,数字 n がランク r∈[1,n] として出現するときの場合の数の合計を計算してあげれば良い(*5).

Combination を求める部分で Integer Overflow を起こしそうな気配なので,gmpxx にお世話になった.

ソースコード

提出コードから掲載コードへの変更点

  • キャッシュ部分をマクロ化.
  • include 順序の整列,改行の追加削除等,表示を見やすくするもの
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <iostream>

// using The GNU Multiple Precision Arithmetic Library
// http://gmplib.org/
// compile with -lgmpxx -lgmp
#include <gmpxx.h>

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())

#define make_cache(...) map< __VA_ARGS__ > cache;\
map< __VA_ARGS__ >::iterator cache_it;
#define cache_hit(query_) (cache_it=cache.find(query_))!=cache.end()
#define check_cache(query_) if(cache_hit(query_)) return (*cache_it).second;
#define store_cache(key_,value_) cache.insert(mp(key_,value_))

make_cache(pair<int,int>,mpz_class)

mpz_class func(int n, int r)
{
	if(r==1) return 1;
	
	// *1
	check_cache(mp(n,r));
	
	int N = n-r-1;
	int M = r-2;
	mpz_class ans = 0;
	
	// *2
	for(int m=0; m<=M; m++)
	{
		if(N<m) continue;
		mpz_class p=1;
		// Combination(N,m) *3
		for(int j=0; j<=m-1; j++)
			p *= (N-j);
		for(int j=2; j<=m; j++)
			p /= j;
		// *4
		ans += p*func(r, M-m+1);
	}
	
	// *1
	store_cache(mp(n,r),ans);
	
	return ans;
}

int solve(int n)
{
	mpz_class ans = 0;
	// *5
	for(int i=1; i<n; i++)
		ans += func(n, i);
	ans %= 100003;
	return ans.get_si();
}

int main(int argc, char* argv[])
{
	uint T;
	cin >> T;
	
	for(uint t=0;t<T;t++)
	{
		uint n;
		cin >> n;
		cout << "Case #" << t+1 << ": " << solve(n) << endl;
	}
	
	return 0;
}

AndiAndi2011/07/22 15:08Thanks alot - your answer solved all my problems after several days srtuglging

ymztwdpymztwdp2011/07/26 00:50iMKSlH , [url=http://vxqonjgohmzr.com/]vxqonjgohmzr[/url], [link=http://bdghiksyjeoz.com/]bdghiksyjeoz[/link], http://fqpjpgeffbmu.com/

EgwoloEgwolo2013/02/16 23:19Thanks for contributing. It's helepd me understand the issues.

zzokgazzokga2013/02/19 14:25gNeh7s <a href="http://jdxldqxslfbx.com/">jdxldqxslfbx</a>

ealpalshhtealpalshht2013/02/19 14:25ftpxVI <a href="http://cpdedlynamuf.com/">cpdedlynamuf</a>

2010/05/18

TopCoder Open 2010 Algorithm Qualification Round 2 HandlesSpelling

| 19:40

http://www.topcoder.com/stat?c=problem_statement&pm=10864&rd=14277

System Test: Passed

長い文字列(parts)を,短い文字列(badges)で覆っていったとき(同じbadgeを何度でも使える),覆った部分が繋がる最長の長さ A と,覆えなかった文字の数 B について, A^2 - B の最大値を求める問題.

Div 1, Div 2 を通して 1000 pt. の問題が自力で解けたのは初めて.TopCoderDP の問題を解いたのも初めてだと思う.それにしてもこの問題は DP の問題でもかなり難易度が高いと思う.

赤コーダーのコードを読んでみたけどさっぱりわからない...けど配列の数を見たりすると,僕のはなんとなく効率が悪いアルゴリズムのようだ.

解説を入れてみたので長くなるので表示省略↓


parts は最大 50 文字が最大 20 要素なので 1000 文字.badges は最大 50 文字が最大 50 要素なので,総当たりだと最大 2^50 の計算量.

なのでお決まりの DP で解く.

ひとまず parts を全部つなげた文字列 s を考えるとして,分割方法としては s の長さを短くするのと,badges の数を減らすのが考えられるが,文字列マッチのDP問題では前者の方法が一般的?

なので覆うべき s を先頭 0 文字から順に増やしていくことにする.

記録する値を考える.DP では縮小した問題の結果を利用できなくてはいけないので A^2 - B をそのまま記録してはいけない.s[0..i] で最大を取ったパターンを継承したものが s[0..i+m] で最大を取るとは限らないからだ.

0123456789
ABCDEFGHIJ (s)
ABC        (badges[0])
  CD       (badges[1])
    EFGHIJ (badges[2])

この例を考えたときに s[0..3] の最大のパターンは badges[0] だけを使った時の 3^2 -1 = 8 である.s[0..9] は s[0..3] + s[4..9] で badges[2] がちょうど s[4..9] にマッチするので,badges[2] を加えれば s[0..9] の時の最大のパターンが求まると思うが,badges[1] は badges[2] と繋がるので,こちらを選択した方が良い結果になる.

では,なるべく次に繋がるように選んでいけばよいのか? s[0..3] までを見たときに badges[0] ではなく次に繋がりそうな badges[1] を選ぶことにしよう.実は s が s[3] までしかなかったという場合に失敗するのは明らかであるし,以下のような場合でも失敗する.

0123456789
ABCDEFGHIJ (s)
ABC        (badges[0])
  CD       (badges[1])
     FGHIJ (badges[2])

また,次のようなケースを考えると s[0..5] までは badges[0] を取った方がいいけど,s[0..9] まで拡大すると badges[2] が選択可能になるので badges[1] を選択したパターンを予め考慮に入れていないと正しい答えが出せない.

また,s[0..3] で badges[1] と badges[3] を取っていれば,連続する長さが 1 でも覆えない文字の数は減らせるが,後でそれを変更できなければ badges[2] が選択可能になっても badges[3] と衝突して選択できなくなるので,連続する長さが短くて,たくさん覆えないパターンも生き残らせる必要がある.

0123456789
ABCDEFGHIJ (s)
ABCDEF     (badges[0])
 B         (badges[1])
  CDEFGHIJ (badges[2])
   D       (badges[3])

同じ最大長を持っていて,次に繋がる可能性があるパターンが2つあったときにどうするかが問題になる.次に繋がる可能性が「長い」パターンを選んでしまうと次のようなケースで失敗する.多く覆っているパターンを選択すると,次の例で badges[3] が無いパターンで失敗する.

0123456789
ABCDEFGHIJKLMN.... (s)
ABCDEFGH           (badges[0])
         J         (badges[1])
  CDEFGHIJ         (badges[2])
           L...    (badges[3])

なので次に繋がる可能性が長いパターンと,多くを覆っているパターンの両方を選択できるようにする.

次に繋がる可能性が一番長いというわけでもなく,一番多く覆っているというわけでもないパターンは,絶対に最良のケースには成り得ないのでこれで十分である.なぜなら badge が続く場合は,A^2 が効いて繋がる可能性が一番長いものの方が有利になるし,続いた上で可能性が一番長いものですら最長にならない場合は,多く覆っている方が有利になるし, badge が後に続かない場合は,一番多く覆っている方が有利である.

まとめると

  • これまでに連続した長さが長い方がいい
  • 同じ長さが連続しているなら,たくさん覆っている方がいい
  • 連続する長さが短くてたくさん覆えなくても最終的に選択される可能性がある
  • 次に繋がる可能性は残しておく必要がある
  • 次に繋がる可能性がある場合は,これまでに一番多く覆っているパターンと,これから一番長く続きそうなパターンを残しておく

これを踏まえると,

  1. これまでに連続している長さによって記録する場所を分けた方がいい
  2. 次に繋がる可能性があるかどうかで記録する場所を分けた方がいい
  3. 次に繋がる可能性がある場合は多く覆っているパターンを選んだ記録と,長く続きそうなパターンを選んだ記録を残す

1. によって A^2 -B のうちパラメータ A は分離されるので B に関する値だけ,つまり覆っていない文字の数を記録していけばよい.この配列を uncoverd という名前にする.

#define LIM 1024
int uncoverd[LIM][LIM][3];
// uncoverd[i][j][k]

i は s を 0..i に縮小する場合を考えるインデックスである.i=0〜1000 なので大きさは 1024 で十分である.

j はこれまでに連続している長さによって記録をわけるためのインデックスである.j 文字連続して覆えている場合は uncoverd[i][j] に記録する.

k は配列の種類を表すインデックスである.

  1. 次に繋がる可能性がない場合 (k=0)
  2. 次に繋がる可能性があり,多く覆っているパターンを選ぶ場合 (k=1)
  3. 次に繋がる可能性があり,長く続きそうなパターンを選ぶ場合 (k=2)

はそれぞれ別の配列を用意してもいいが,処理が共通するのでループで回す方が簡潔に書けるため,このようにした.

こうすれば j^2 - uncoverd[s.length()][j][k] が最大になるものを最後に計算すれば答えが出る.

uncoverd[0][0][k] は 0 で初期化できる.対象が 0 文字なので覆っていない文字の数は必ず 0 である.他は大きな値で初期化する.覆えていない文字数なので最大値は 1000 である.よって 1024 で初期化することにする.

さて,覆うべき文字が後ろに一文字増えたときには

  1. 覆えない文字が1文字増える
  2. その文字から覆いが始まる badge がある
  3. その文字で覆いが終わる badge がある

ということが起きる.3 に関しては,終わるのであれば始まりがあるので 2 の時に処理してしまえばいい.このときある (i,j,k) について,覆い終わりなのか,覆い終わりであれば覆いが何文字つづいているのか,という情報が必要になる.k=0 の時は定義上覆い終わりには成り得ないのでこれを抜き int tail[LIM][LIM][2]; という配列を用意して,何文字続いて覆い終わったのかを記録する.これは 0 ですべて初期化できる.

int tail[LIM][LIM][2];
// tail[i][j][k-1]
// k-1=0 が uncoverd の k=1 に対応する

ここまで準備できればあとは簡単である.

http://www.yuyarin.net/screenshot/20100518010601.png

↑デバッグ中,System Test にあるテストケースについての uncoverd[i][j][0] の一部.

uncoverd[i+1][j][0] は uncoverd[i][j][k]+1 (k=0,1,2) のうち最小のものになる.これは覆うべき文字が 1 つ増えたときに覆わない選択を記録するものである.

次に,ある (i,j,k) について i から覆い始まる badge がみつかった時の処理である.その badge の長さを m とすると,この badge を選択したときに,連続して覆うことができる最長の長さは,tail[i][j][k-1] + m と j の大きい方となる.tail[i][j][k-1] + m は新しい badge を選んだときに,最長の長さが増える場合,j は増えない場合を意味する.これを x とする.k==0 のときは tail[i][j][k-1] を加えてはいけない.

int c = m + (k?tail[i][j][k-1]:0);
int x = max(j, c);

この badge を選択すると m 個後に x 文字連続して覆えている uncoverd[i+m][x][k] と tail[i+m][x][k-1] が影響を受ける.覆えていない文字は増えないので uncoverd[i+m][x][k] は uncoverd[i][x][k] と同じになる.tail[i+m][x][k-1] は tail[i][j][k-1] + m = c になる.

多く覆っているパターンを選ぶ場合(k==1)は

// 覆っている数が多くなる
if((uncoverd[i+m][x][1]>uncoverd[i][j][k])
// 同じだったら長く続きそうな方
|| (uncoverd[i+m][x][1]==uncoverd[i][j][k]&&tail[i+m][x][0]<c))
{
	uncoverd[i+m][x][1] = uncoverd[i][j][k];
	tail[i+m][x][0] = c;
}

長く続きそうなパターンを選ぶ場合(k==2)は

// 長く続く
if((tail[i+m][x][1]<c)
// 同じだったら多く覆えている方
||(tail[i+m][x][1]==c&&uncoverd[i+m][x][2]>uncoverd[i][j][k]))
{
	uncoverd[i+m][x][2] = uncoverd[i][j][k];
	tail[i+m][x][1] = c;
}

以上を纏めるとこのようになる

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <climits>

#define sz(Z) ((int)Z.size())

using namespace std;

#define LIM 1024

int uncoverd[LIM][LIM][3];
int tail[LIM][LIM][2];
bool match[LIM][50];

class HandlesSpelling
{
public:

int spellIt(vector <string> parts, vector <string> badges)
{
	string s = "";
	for(int i=0;i<sz(parts);i++) s += parts[i];
	
	int n = sz(badges);
	int l = sz(s);
	
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<l; j++)
			match[j][i] = false;
		size_t idx = -1;
		while((idx=s.find(badges[i], idx+1))!=string::npos)
			match[idx][i] = true;
	}
	
	for(int i=0; i<LIM; i++) for(int j=0; j<LIM; j++)
	{
			uncoverd[i][j][0] = uncoverd[i][j][1] = uncoverd[i][j][2] = LIM;
			tail[i][j][0] = tail[i][j][1] = 0;
	}
	
	uncoverd[0][0][0] = uncoverd[0][0][1] = uncoverd[0][0][2] = 0;
	
	for(int i=0; i<l; i++) for(int j=0; j<l; j++) for(int k=0; k<3; k++)
	{
		if(uncoverd[i][j][k]>=LIM) continue;
		
		if(uncoverd[i+1][j][0]>uncoverd[i][j][k]+1)
			uncoverd[i+1][j][0] = uncoverd[i][j][k]+1;
		
		for(int b=0; b<n; b++)
		{
			if(!match[i][b]) continue;
		
			int m = sz(badges[b]);
			int c = m + (k?tail[i][j][k-1]:0);
			int x = max(j, c);
			if((uncoverd[i+m][x][1]>uncoverd[i][j][k])
			|| (uncoverd[i+m][x][1]==uncoverd[i][j][k]&&tail[i+m][x][0]<c))
			{
				uncoverd[i+m][x][1] = uncoverd[i][j][k];
				tail[i+m][x][0] = c;
			}
			if((tail[i+m][x][1]<c)
			||(tail[i+m][x][1]==c&&uncoverd[i+m][x][2]>uncoverd[i][j][k]))
			{
				uncoverd[i+m][x][2] = uncoverd[i][j][k];
				tail[i+m][x][1] = c;
			}
		}
	}
	
	int r = -LIM;
	for(int j=0; j<LIM+1; j++) for(int k=0; k<3; k++)
		if(uncoverd[l][j][k]<LIM)
			if(r<j*j-uncoverd[l][j][k])
				r = j*j-uncoverd[l][j][k];
	return r;
}

LucindaLucinda2011/08/30 17:11That's way more celevr than I was expecting. Thanks!

qcsfbdcrznfqcsfbdcrznf2011/09/01 01:16MuL60l <a href="http://ldwctdptemza.com/">ldwctdptemza</a>

uzzdbpogphuzzdbpogph2011/09/02 21:19Ek7mGB , [url=http://xuvqzogutnji.com/]xuvqzogutnji[/url], [link=http://mtfcrzsqbevx.com/]mtfcrzsqbevx[/link], http://yidsymtdxulp.com/

sjsczxrsjsczxr2011/09/03 18:32v2hpOA <a href="http://bwurazrpzmzh.com/">bwurazrpzmzh</a>

jhwvoumajhwvouma2011/09/04 01:44LhXMUP , [url=http://rjqsugidoqec.com/]rjqsugidoqec[/url], [link=http://gukwrezfgzuo.com/]gukwrezfgzuo[/link], http://zesuvabbctky.com/

2010/03/20

SRM 464 ColorfulStrings

| 21:19

http://www.topcoder.com/stat?c=problem_statement&pm=10724&rd=14149

Sample Case: passed

System Test: passed

問題の条件から

  • 2桁以上の数字では0と1が入ってはいけない
  • 同じ数字は2回現れない

ということがわかるので 2<=n<=8 で考えればいいことがわかるので,ひとまず枝刈りをせずに 2,3,4,5,6,7,8,9 を辞書順で生成していき colorful かチェックする.結果的に枝刈りをしなくても実行速度は十分であった.

数字は整数の配列 num[] で各桁を表現する.

辞書順の生成は再帰を使う (rec()).ある数字が使われたかを ap[] で記録しておき,使われていない数字を小さい方から num[pos] に入れていく.pos を 1 増やして再帰する.長さが桁数に達したら colorful かチェックを行う (colorful()).

colorful のチェックではそれまでの数字の積を記録 (mr[]) しておけば,ループを1重減らすことができる.

積のデータベースには set を利用している.insert() は既に要素があったときに .second で false が返されるので,既に積が出現している=colorful ではない場合を挿入と同時に判定できる.

あんまりスマートなコードだとは思わないけど,理解はしやすいと思う.

上位のコードはもっとシンプルだけどまだ解読出来ていない...

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <set>

using namespace std;
inline int toi(string s){int v; istringstream iss(s);iss>>v;return v;}
template<class T> inline string tos(T x){ostringstream oss;oss<<x;return oss.str();}

class ColorfulStrings
{
public:

bool colorful(int n, int* num)
{
	// the results of mul
	int mr[] = {1,1,1,1,1,1,1,1,1,1,};
	
	set<int> m;
	
	for(int len=1; len<=n; ++len)
	{
		for(int idx=0; idx<=n-len; ++idx)
		{
			mr[idx] *= num[idx+len-1];
			if(!m.insert(mr[idx]).second)
				return false;
		}
	}
	
	return true;
}

bool rec(int n, int k, int* num, int* ap, int pos, int &cnt)
{
	if(pos==n)
	{
		if(colorful(n, num)) cnt++;
		if(cnt==k) return true;
		return false;
	}
	
	for(int i=2; i<10; ++i)
	{
		if(ap[i]) continue;
		num[pos] = i;
		ap[i] = 1;
		if(rec(n, k, num, ap, pos+1, cnt)) return true;
		ap[i] = 0;
	}
	return false;
}

string getKth(int n, int k)
{
	if(n>8) return "";
	if(n==1) return (k>10) ? "" : tos(k-1);
	
	string s = "";
	int num[8];
	int ap[] = {0,0,0,0,0,0,0,0,0,0};
	int cnt = 0;
	
	if(rec(n, k, num, ap, 0, cnt))
	{
		for(int i=0; i<n; ++i) s += num[i]+'0';
	}
	return s;
}
	
	
};

ElenaElena2013/02/17 05:39That addresses several of my concerns acutlaly.

sdxtpjsdxtpj2013/02/18 07:467hgOED , [url=http://vkhpudkqbafn.com/]vkhpudkqbafn[/url], [link=http://ibikxlgbdgkx.com/]ibikxlgbdgkx[/link], http://trdttgtbmydr.com/

beidpbknybeidpbkny2013/02/19 14:45wqJCeV <a href="http://pkzbvtmxkrzw.com/">pkzbvtmxkrzw</a>

hcaepwobinzhcaepwobinz2013/02/19 20:07MApC6d , [url=http://desrxojmthft.com/]desrxojmthft[/url], [link=http://qcvljhvzomoh.com/]qcvljhvzomoh[/link], http://socvhhjtbmkl.com/