SRM 480 Div2 Hard SignalIntelligence

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11059&rd=14159

vector int numbersが与えられ、ここからある文字列を作る。numbers[i]を文字列に組み込むとは、文字列の2のべき乗番目から連続してnumbers[i]個の1を組み込むという行為になる。こうやってすべての数字を組み込んだ時にできる最短の文字列の長さを求めよ。ただし、すべてのi、j（i != j）について文字列中のnumbers[i]の部分の1とnumbers[j]の部分の1は連続してはならない。

やりかた

Editorialを参考にしました。

ある数字を組み込むには区切りのその数字より大きい最小の２のべき乗数が必要になる（区切りの0も含んでいる）。ただし文字列に最後に組み込む数字は、その次の数字がもうないために、次の2のべき乗まで0をつなげる必要がない。そのため、最後の数字については変則的である。実を言うと最後の数字を考えない場合に、数字を昇順に組み込むときに最短になる。

並び順がi < j（num[i] > num[j]）であるときに数字num[i]とnum[j]の現れる順を反対にするようが短くなりうる。少し実験すればわかる。

以下ソース。

static const ll INF = (1LL << 62) + 100;

class SignalIntelligence {
public:
  long long encrypt(vector <int> numbers) {
    long long result = 1LL << 62;
    int N = numbers.size();
    for(int i = 0; i < N; i++){
      vector<int> num;
      for(int j = 0; j < N; j++) if(i != j) num.push_back(numbers[j]);
      sort(ALL(num));
      
      int prev = 0;
      int idx = 0;
      for(int j = 0; ; j++){
	if(idx == (int)num.size()) break;
	if((1LL << j) - (1LL << prev) - 1 >= num[idx]){
	  idx++;
	  prev = j;
	}
      }
      result = min(result, (1LL << prev) + numbers[i] - 1);
    }
    return result;
  }
};

間違ってたらどなたか教えてください。