TopCoder/SRM596_IncrementAndDoubling - Wiki2D

TopCoder SRM 596 Div 1 Easy : IncrementAndDoubling

問題概要

N個の要素からなる、0で初期化された配列がある。
この配列に対して、以下の2つの操作を行うことができる。

• 配列の任意の1つの要素に対して1を足す。
• 配列の全ての要素を2倍する。

引数として、N個の[0,1000]の整数からなる配列が与えられる。
最小何回の操作で、引数の配列と等しくすることができるか答えよ。

解法1

貪欲に解く。
0の配列の状態からスタートするのではなく、逆からスタートして計算する。
つまり、引数で与えられた配列の形からスタートして、0の配列にできる、最小のステップ数を求めると考える。

こう考えれば、ある配列の状態から、以下の2つの操作で一意に遷移しつつ、0の配列を目指すことができる。

• 奇数の値が配列の中に一つでも入っている場合
  • 奇数になっている値全てから1を引く
  • 1を引いた回数の分をコストに足す
• 全ての値が偶数の場合
  • 2で割れるので、全ての値を2で割る
  • コストに1足す

解法2

まず、[0,1000]の各数について、次のように動的計画法(DP)を使って最小コストを求めておく。

dp[number (1000)][doub (10)] =
  numberにするために、2倍操作をdoub回行ったときの、
  インクリメント操作の最小回

2倍の操作は、高々9回だけ行えばいい。10回以上行うと1000を超えるから。

次に、配列について考える。
配列の各値において、2倍操作の回数は全て共通で変わらないはずである。
そのため、2倍操作の回数だけループで決めてやって、先程のdp配列を利用してコストを足し合わせればよい。

プログラム1（解法1ver.）

class IncrementAndDoubling {
public:
 
bool finished(const vector<int> v){
  for(int i = 0; i < v.size(); i++){
    if(v[i] != 0) return false;
  }
  return true;
}
 
int getMin(vector <int> desiredArray) {
  int res = 0;
 
  while(!finished(desiredArray)){
    bool doubleFlg = true;
    for(int i = 0; i < desiredArray.size(); i++){
      if(desiredArray[i] % 2 != 0){
        desiredArray[i]--;
        res++;
        doubleFlg = false;
      }
    }
 
    if(!doubleFlg) continue;
 
    res++;
    for(int i = 0; i < desiredArray.size(); i++){
      desiredArray[i] /= 2;
    }
  }
 
  return res;
}
};

プログラム2（解法2ver.）

int dp[1002][12];
 
class IncrementAndDoubling {
public:
int getMin(vector <int> desiredArray) {
  int n = desiredArray.size();
 
  for(int j = 0; j < 1002; j++){
    for(int k = 0; k < 12; k++){
      dp[j][k] = INT_MAX;
    }
  }
 
  dp[0][0] = 0;
 
  for(int j = 0; j < 1000; j++){
    for(int k = 0; k <= 10; k++){
      if(dp[j][k] == INT_MAX) continue;
 
      dp[j + 1][k] = min(dp[j + 1][k], dp[j][k] + 1);
      if(j * 2 > 1000) continue;
      dp[j * 2][k + 1] = min(dp[j * 2][k + 1], dp[j][k]);
    }
  }
 
  int res = INT_MAX;
 
  for(int i = 0; i <= 10; i++){
    int sum = i;
 
    for(int j = 0; j < n; j++){
      if(dp[desiredArray[j]][i] == INT_MAX){
        sum = INT_MAX;
        break;
      }
      sum += dp[desiredArray[j]][i];
    }
 
    res = min(res, sum);
  }
 
  return res;
}
};