Hatena::Grouptopcoder

yuyarinのtopcoder記

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

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

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/04/10

Marathon Match 58 IsolatedPrimes

| 00:55

http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14226&pm=10844

HandleScoreRankLast Submission TimeLanguageExample TestsSubmissions
yuyarin23.0016203.26.2010 13:10:23C++42

はじめての MM で SRM と勝手が違って若干戸惑った.

とりあえず素数を最初から舐める方法で実装してみたけど,解が大きい場合に簡単にTLEしてしまう.pi関数と二分探索で解になる素数の位置の当たりをつけて MR 法で素数判定するコードも書いてみたけど,役に立たなかった.

コードサイズを考えると,きっとオフラインで計算したデータを持っておくのかなと思ったけど,何をどう持ってどういうアルゴリズムにするのかを思いつかなくて,年度初めで忙しくなってきて断念.結局最初に書いたコードで submit.

高速化のために若干可読性は落ちているけど,アルゴリズムは多分解説が要らないほど単純なコードだと思う.

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

using namespace std;
typedef unsigned long long ull;
template<class T> inline string tos(T x){ostringstream oss;oss<<x;return oss.str();}

#define N 100000000

// 素数の配列 primes[0]=2, primes[1]=3, ...
ull primes[N]; 
// [primes[i]-a, primes[i]+b] に含まれる素数の個数の配列
unsigned int counts[N]; 

// primes[], counts[] のインデックス
unsigned int n=0;

// インデックス n の探索範囲の下界
unsigned int start=0;

int x, a, b;

class IsolatedPrimes
{
public:

bool isPrime(ull m)
{
	ull max = (ull)sqrt(m+1);
	// 2, 3 は調べなくて良い
	for(unsigned int i=2; i<n && primes[i]<=max; i++)
	{
		if(m%primes[i]==0) return false;
	}
	return true;
}

ull f(ull p)
{
	if(!isPrime(p)) return 0;
	
	n++;
	primes[n] = p;
	counts[n] = 1;
	
	// primes[n]-a より小さい素数はチェックしない
	for(unsigned int i=start; i<n; i++)
	{
		// primes[i] が primes[n]-a 〜 primes[n] に含まれる
		// => counts[n] += 1;
		unsigned int fa = (p <= a + primes[i]);
		counts[n] += fa;
		
		// primes[n] が primes[i] ~ primes[i]+b に含まれる
		// counts[i] += 1;
		unsigned int fb = (p <= b + primes[i]);
		counts[i] += fb;
		
		// primes[i] が primes[n]-a よりも小さくなった
		// => 探索対象から外れた
		if(!(fb|fa))
		{
			// primes[i] 中心の範囲に含まれる素数の個数 counts[i] をチェック
			if(counts[i]<=x && primes[i]>(ull)a) 
			{
				return primes[i];
			}
			// 調べる必要がなくなった
			start = i+1;
		}
	}
	
	return 0;
}

string findPrime(int x_, int a_, int b_)
{
	x = x_; a = a_; b = b_;
	
	primes[0] = 2; primes[1] = 3;
	counts[0] = 2; counts[1] = 2;
	
	n = 1;
	
	ull max = ((1ull<<63)-1-b)/6;
	ull ans = 0;
	
	// 素数は 6*i±1 で表現できる
	for(ull i=1;i<max;i++)
	{
		if((ans=f(6*i-1))>0) return tos(ans);
		if((ans=f(6*i+1))>0) return tos(ans);
	}
	
	return "0";
}
};

int main(int argc, char* argv[])
{
	IsolatedPrimes ip;
	if(argc>=4)
	{
		cout << ip.findPrime(atoi(argv[1]),atoi(argv[2]),atoi(argv[3])) <<endl;
	}
	return 0;
}