SRM302 div1 easy

とりあえずキューで実装してみたが、2s以内ではできない．

  int countOperations(int N, int M) {
    int flag[M+1];
    memset(flag, -1, sizeof flag);
    queue Q;
    Q.push(N);
    flag[N] = 0;
    while( !Q.empty() ) {
      int n = Q.front(); Q.pop();

      if(n > M) continue;
      for(int i = n/2; i >= 2; i--) {
	if(n % i == 0 && n+i <= M) {
	  if(flag[n+i] == -1) {
	    flag[n+i] = flag[n] + 1;
	    Q.push(n+i);
	  }　//ここが原因か？　もしかすると、if(flag[n+i] == -1)というとこをいじくればいいかも．
	}
      } //end for
    }
    return flag[M];
	  
  }

深さ優先検索でしようとすると、1)で死亡してしまう．

bool DivisorInc::go(int n) {
  if(n == m) {
    return true;
  } else {
    for(int i = n/2; i >= 2; i--) {
      if(n % i == 0 && n+i <=  && flag[i+n] == -1) {
	flag[n+i] = flag[n]+1;
	if(go(n+i)) return true;
      }
    }
  }
  return false;
}

素数を絡めてDPでとくと2)で引っかかる．

  int countOperations(int N, int M) {
    fill(flag, flag+100002, INF);
    flag[N] = 0;
    vector prime = getPrime(M); int sz = prime.size();
 
    for(int i = N; i < M; i++) {
      if(flag[i] != INF) {

	for(int j = 0; j < sz && prime[j]*prime[j] <= i; j++) {
	  int tmp = prime[j];
	  if(i % tmp == 0) {
	    if(i+tmp <= M) {
	      flag[ i+tmp ] = min(flag[i+tmp], flag[i]+1);
	    }
	    if(i+i/tmp <= M) {
	      flag[i + i/tmp ] = min(flag[i + i/tmp], flag[i]+1);
	    }
	  }
	} //end for j

      }
    } //end for i
    return flag[M] == INF ? -1 : flag[M];
  }
};

深く考えずに、順番にやっていくのが正解．

  int countOperations(int N, int M) {
    fill(flag, flag+100002, INF);
    flag[N] = 0;

    for(int i = N; i < M; i++) {
      if(flag[i] != INF) {
	for(int j = 2; j*j <= i; j++) {

	  if(i % j == 0) {
	    if(i+j <= M) {
	      flag[ i+j ] = min(flag[i+j], flag[i]+1);
	    }
	    if(i+i/j <= M) {
	      flag[i + i/j ] = min(flag[i + i/j], flag[i]+1);
	    }
	  }
	} //end for j

      }
    } //end for i
    return flag[M] == INF ? -1 : flag[M];
  }
};
//queueで実装しようとしてもどのみちdpは必要．本質的にはなんの変わりもない．