SRM 519 Div2 Hard BinaryCards

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11552&rd=14544
カードが複数枚あり、2^0, 2^1, 2^3, ...というように各々に２のべき乗のいずれかが書かれている。このカードを表にすることでそのカードを使用するということをあらわす。自然数A、B（Aい<= B）が与えられ、Aを表すカードの状態から、カードを裏表にすることでAに２のべき乗数を足し引きしていく処理を繰り返して最終的にBを表す状態にしたい。ただしB < 2^k （つまりBより大きいカード）となるようなカードを表にすることは許されないとする。この処理中で現れうる最大の数を求めよ。

やりかた

まず2進数に書き直してみて2つの2進数のビット数が異なるときと同じ時に分けて考えてみる。また便宜上A-> Bという操作ではなく、Bに加減を行なってAにするという処理として考える。
異なるときは

6         110
16     10000

このようになっているとき、16に(111)2 = 8を足して(10111)2 = 23（これが最大値）にしてから(10001)2 = 17を引いて(110)2 = 6にすることができる。一般化すると、Aの最上位ビット以下の位置にあるBのビットをすべて1にした数がとりうる最大の値となる。

ここまでくればビット数が同じ時も一緒だとわかる。AとBのビットが先頭から数えて初めて異なる部分より前を省いてしまえば（10001、10100なら先頭の10を省いて001、100にする）上の議論と同じになる。結局はAとBの先頭から数えてビットが初めて異なる位置より以降のBのビットをすべて立てた値が最大値になる。

以下ソース。

class BinaryCards {
public:
  string i2s(ll a){
    string s;
    while(a){
      s += (a % 2) + '0';
      a /= 2;
    }
    return s;
  }
  ll s2i(string s){
    ll ret = 0;
    for(int i = 0; i < (int)s.length(); i++)
      ret += (s[i] - '0') * (1LL << i);
    return ret;
  }
  long long largestNumber(long long A, long long B) {
    string sa = i2s(A);
    string sb = i2s(B);
    sa += string(sb.length() - sa.length(), '0');
    for(int i = (int)sa.length() - 1; i >= 0; i--) 
	if(sa[i] != sb[i]) {
	  for(int j = i; j >= 0; j--) sb[j] = '1';
	  break;
	}
      return s2i(sb);
  }
};

時間はかかったができた。
にしても本当にペース落ちてるなあ。