SRM 517 250pt: CompositeSmash

問題概要

整数N(<10^5)が与えられる。整数は二つの整数の積に再帰的に分解される。途中でtargetという値が必ず現れるかどうか判定する問題。

考えたこと

• Nが大したことないし普通に愚直に探索で間に合いそう。
• 書けた。メモ化も付けることができるけど、最大ケースだと思われるのが余裕で間に合ってるし、今日のセットはmediumが600で250早解きになる可能性が高いのでさっさと出す。
• 一応いろんなケース試して余裕で間に合っていたので再提出はしなかった。無事AC。
• 最近強く意識している、「基本は全探索」、「間に合うなら最もシンプルに書くべし」というのが生きた問題だった。easyが早解きできるようになるとレートは安定する。

本番で通ったコード

計算量よく分かんない。最大ケースは(65536, 2)だと思われる。

#include <string>
#include <vector>
using namespace std;

struct CompositeSmash {

	string thePossible(int N, int target) {
		return solve(N, target) ? "Yes": "No";
	}

	bool solve(int N, int target){
		if(N==target){
			return true;
		}

		vector<int> fs;
		for(int i=2; i*i<=N; i++){
			if(N%i == 0){
				fs.push_back(i);
			}
		}

		if(fs.empty()){
			return false;
		}

		for(int i=0; i<(int)fs.size(); i++){
			if( !(solve(N/fs[i], target) || solve(fs[i], target) ) ){
				return false;
			}
		}

		return true;
	}

};