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位の難易度かも。