保存されている過去のバージョンの一覧

2014年04月05日18時32分51秒

TopCoder SRM615 DIV1 EASY - AmebaDiv1

Source

TopCoder SRM615 DIV1 EASY (250pt)
Problem Statement

問題概要

$N$ 要素の正整数の数列 $\{A_k\}_{k=0}^{N-1}$ が与えられる．
正整数 $x$ を選んで次の操作を行う．
$x$ が $A_0$ と等しければ$x$ を $2$ 倍し，
$x$ が $A_1$ と等しければ$x$ を $2$ 倍し，…，
$x$ が $A_{N-1}$ と等しければ$x$ を $2$ 倍する．
$x$ の初期値を自由に選んで良い時，最終的な $x$ の値としてとりえない正整数は何個あるかを求める問題．

解法

数列 $\{A_k\}$ に含まれない整数は素通りするので，数列に含まれる整数のみを考えれば良い．
以下の解答では，それぞれのステップで，$x$ が各 $A_k$ となり得るかどうかをDPした．
愚直に実装して $O(N^3)$，工夫すれば $O(N^2)$ ぐらいにもできる．
もっと簡潔な方法は，$x$ の初期値としてどの $\{A_k\}$ の要素を取っても，最終結果として得られない $\{A_k\}$ の要素が作れないので，$x$ の初期値として $A_k$ を全部試してみる方法などがある．

C++によるスパゲッティなソースコード

// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

class AmebaDiv1 {
public:
int count(vector <int> X) {
  int i, j, k, n;
  int dp[210], nx[210];
  set<int> S;

  n = X.size();
  rep(i,n) dp[i] = 1;

  rep(k,n){
    rep(i,n) nx[i] = 0;
    rep(i,n) if(dp[i]){
      if(X[k]!=X[i]){ nx[i] = 1; continue; }
      rep(j,n) if(2*X[i] == X[j]) nx[j] = 1;
    }
    rep(i,n) dp[i] = nx[i];
  }

  rep(i,n) if(dp[i]==0) S.insert(X[i]);
  return S.size();
}

}

Current time: 2024年04月19日14時31分40秒
Last modified: 2014年04月05日18時32分51秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM615 SRM_Div1_Easy
トップページに戻る

Logged in as: unknown user (not login)

ログイン：