問題概要

配列内の等しい要素をマージする問題について、2つの異なるアプローチを解説する。

アプローチ1: 優先度付きキューを使用

優先度付きキューを用いて、値とインデックスを管理する方法。以下の手順で処理を行う:

1. すべての要素を値とインデックスのペアとしてキューに追加
2. キューの先頭から2要素を取り出し、値が等しければ和を計算して再挿入
3. 等しくなければ答えのリストに追加

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
using ll = long long;

struct ElementCompare {
  bool operator()(pair<ll, int> a, pair<ll, int> b) {
    return a.first != b.first ? a.first > b.first : a.second > b.second;
  }
};

struct AnswerCompare {
  bool operator()(pair<ll, int> a, pair<ll, int> b) {
    return a.second > b.second;
  }
};

int main() {
  int n; cin >> n;
  priority_queue<pair<ll, int>, vector<pair<ll, int>>, ElementCompare> pq;
  priority_queue<pair<ll, int>, vector<pair<ll, int>>, AnswerCompare> result;
  
  for(int i=0; i<n; i++) {
    ll val; cin >> val;
    pq.push({val, i});
  }
  
  while(pq.size() > 1) {
    auto [val1, idx1] = pq.top(); pq.pop();
    auto [val2, idx2] = pq.top();
    
    if(val1 == val2) {
      pq.pop();
      pq.push({val1 * 2, idx2});
    } else {
      result.push({val1, idx1});
    }
  }
  
  result.push(pq.top());
  cout << result.size() << "\n";
  
  while(!result.empty()) {
    cout << result.top().first << " ";
    result.pop();
  }
  
  return 0;
}

アプローチ2: 因数分解と分類処理

各要素から2の因数を除去し、分類後に処理する方法:

1. 各数値から2の因数を完全に除去
2. 処理済み数値でソートして分類
3. 各分類ごとにマージ処理を実施

#include<iostream>
#include<algorithm>
#include<bitset>
using namespace std;
using ll = long long;

struct ProcessedElement {
  int original;
  int processed;
  int index;
};

bool compareElements(const ProcessedElement& a, const ProcessedElement& b) {
  if(a.processed != b.processed) return a.processed < b.processed;
  if(a.original != b.original) return a.original < b.original;
  return a.index < b.index;
}

int main() {
  int n; cin >> n;
  vector<ProcessedElement> elements(n);
  bitset<150000> included;
  vector<ll> result(n);
  int count = 0;
  
  for(int i=0; i<n; i++) {
    cin >> elements[i].original;
    elements[i].processed = elements[i].original;
    while(elements[i].processed % 2 == 0) elements[i].processed /= 2;
    elements[i].index = i;
  }
  
  sort(elements.begin(), elements.end(), compareElements);
  
  for(int left=0; left<n; ) {
    int right = left;
    while(right < n && elements[right].processed == elements[left].processed) right++;
    
    vector<int> current, next;
    ll current_val = elements[left].original;
    int pos = left;
    
    while(!current.empty() || pos < right) {
      vector<int> temp;
      while(pos < right && elements[pos].original == current_val) {
        temp.push_back(elements[pos++].index);
      }
      
      int i=0, j=0;
      while(i < current.size() || j < temp.size()) {
        int idx;
        if(i < current.size() && (j == temp.size() || current[i] < temp[j])) {
          idx = current[i++];
        } else {
          idx = temp[j++];
        }
        
        if(i == current.size() && j == temp.size()) {
          included.set(idx);
          result[idx] = current_val;
          count++;
          break;
        }
        
        int next_idx;
        if(i < current.size() && (j == temp.size() || current[i] < temp[j])) {
          next_idx = current[i++];
        } else {
          next_idx = temp[j++];
        }
        next.push_back(next_idx);
      }
      
      current = next;
      next.clear();
      current_val *= 2;
    }
    left = right;
  }
  
  cout << count << "\n";
  for(int i=0; i<n; i++) {
    if(included[i]) cout << result[i] << " ";
  }
  
  return 0;
}

両アプローチの時間計算量はO(n log n)であるが、2番目の方法の方が定数倍が小さい。