kmjp's blog

競技プログラミング参加記です

TopCoderOpen 2015 Round1A Easy Similars

TCOはRound1はbyeで無条件通過のため不参加。
出てもHardが解けてない可能性が高そうだった。
http://community.topcoder.com/stat?c=problem_statement&pm=13714

問題

2つの整数x,yの類似度f(x,y)とは、x,yで両方で使われている数字の数とする。

整数L,Rが与えられる。L≦a<b≦Rとなる任意の整数対a,bに対しf(a,b)の最大値を求めよ。

解法

Rは最大10^5と大きいため、(a,b)の総当たりは不可。
ただ、整数xに対しそのxで使われている数字の組み合わせは高々2^10通りである。

よってまずLからRの各整数xに対し、使われている数字をbitmaskで表したものmask(x)を求め、同じmask(x)の登場回数を求める。
あとはこのbitmaskを2重ループで処理する。
2種類のbitmask b1,b2に対し:

  • b1==b2の場合、mask(x)=b1となる数値が2個以上あるならbitcount(b1)が解の候補。
  • b1!=b2の場合、mask(x)=b1となる数値x及びmask(y)=b2がそれぞれ1個以上あるならbitcount(b1 and b2)が解の候補。

あとは解の候補の最大値を返せばよい。

class Similars {
	public:
	
	int mask(int v) {
		int mask=0;
		while(v) mask |= 1<<(v%10), v/=10;
		return mask;
	}
	
	int maxsim(int L, int R) {
		int num[1024]={};
		int ma=0,x,y;
		for(;L<=R;L++) num[mask(L)]++;
		FOR(x,1024) FOR(y,1024) {
			if(x==y && num[x]>1) ma=max(ma,__builtin_popcount(x));
			if(x!=y && num[x]>=1 && num[y]>=1 ) ma=max(ma,__builtin_popcount(x&y));
		}
		return ma;
	}
}

まとめ

Div2Easyよりは難しい。
Div2 Medium位の難易度かも。