Codeforces #312 Div2 D: Amr and Chemistry

めんどくさい解き方をしてしまった。

問題はこちら。

問題

n個の値からなる数列aを与えられる。aの各要素に対して
1. 2をかける
2. 2で割る（小数点切り捨て）
の操作を行い、すべての要素を等しくする。必要な操作の最低回数はいくらか。

解法

各要素に対して作りえる値とそのときの操作回数を全探索していく。
a[i]の最大値mは10⁵で操作後の最大値がこれを超えることはないため、2をかける操作は10⁵に到達したらやめる。また2で割って1余るとき、割ったあとに2をかけると元の値と変わるので2で割ったあとには2をかけていく。また前の操作で2をかけた値を2で割る必要はない（2で割った余りが0だから）。
ある要素に対するrecの呼び出し回数はlog(m)²以下でO(n(log(m))²)となりこれで間に合う。
各要素が到達可能な値のうち、操作回数の総和がもっとも小さいものが答えとなる。

const int NMAX = 100005;
const int AMAX = 100005;
int n;
int a[NMAX], need[AMAX], cnt[AMAX];

void rec(int m, int step, bool up, int rem) {
  if (m >= AMAX) return;
  need[m] += step;
  cnt[m]++;
  if (up)
    rec(2 * m, step + 1, true, 0);
  else {
    if (rem == 1) rec(2 * m, step + 1, true, 0);
    if (m > 1)    rec(m / 2, step + 1, false, m % 2);
  }
}

int main(void) {
  cin >> n;
  rep(i, n) cin >> a[i];

  rep(i, n) rec(a[i], 0, false, 1);

  int ans = NMAX * 200;
  rep(i, AMAX) {
    if (cnt[i] == n)
      ans = min(ans, need[i]);
  }

  cout << ans << endl;

  return 0;
}

まとめ

2進数の共通prefixを取るほうがだいぶ楽そう。