SRM517 Div1 Easy(250), Div2 Medium(500) CompositeSmash

TopCoder

CompositeSmash

動的計画法。場合分けして解く方法もあるらしいけど、コンテスト中にミス無く書ける自信が無い……。

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

vector<int> memo;
int target;

bool f( int n )
{
    if ( n==target )
        return true;
    if ( memo[n]>=0 )
        return memo[n]!=0;

    bool ans = true;
    bool prime = true;

    for ( int i=2; i*i<=n; i++ )
    if ( n%i==0 )
    {
        prime = false;
        if ( !f(i) && !f(n/i) )
            ans = false;
    }
    if ( prime )
        ans = false;

    memo[n] = ans?1:0;
    return ans;
}

class CompositeSmash{public:
string thePossible( int N, int target )
{
    memo = vector<int>(N+1,-1);
    ::target = target;

    return f(N) ? "Yes" : "No";
}};