プログラマー-四段高音

プログラマー-四段高音
コカソはテストボックスが打たれることがあるので、デバッグが不便です.
この問題は基本的にdfs+剪断問題である.
nが与えられた場合、その数値が問題で与えられた条件を満たす場合、nを生成できる状況がどれだけあるかを調べることができる.
問題は*+...などの文字列で、*は乗算3演算、+は加算1演算です.
*の後には2つの+演算があり、*は**++、*+*++などの形式で連続的に与えることができます.
1から*に遭遇すると3を掛け、+に遭遇すると1を掛ける.
例えば、**++は13を表す.
41を表すのは2つのケースがあります:**++*++、*+*+++.
解決策は以下の通り.

最初にk個*で表される範囲の最大値は、k−1個*で表される範囲の最大値よりも常に大きく、k+1個*で表される範囲の最大値よりも小さい.すなわち,nが与えられると,k値がどれだけあるかがすぐに分かる.

kが3の場合、****++++は最高値、*++*+++は最高値となる.

nを表す文字列の最後の2つは常に++である.

上記の条件でdfsを回し、nが与えられたときにn−2からdfsを実行し、+が何回発生したか、*が何回発生したかを確認し、同時に剪断を実行する.
dfsを迂回する概念はnの値に基づいて逆方向に演算を追加する方式である.
すなわち、3を掛けると除法3になり、1を加えるとマイナス1になる.
たとえば、13を作成するには、
13 -> 12 -> 11 -> 10 -> 9 -> 8 ... -> 1
13 -> 12 -> 4 -> 3 -> 2 -> 1
13 -> 12 -> 4 -> 3 -> 1
等順で演算できるはずです.
このとき、*が3回発生したnであれば、+個の数は常に6未満でなければならず、*個の数は3未満でなければならない.
また、+の個数は*の個数の2倍を超えてはならず、nは常に1より大きくなければならない.
上記の条件に従って枝打ちを行い、条件に合致した場合にのみ、1の正解を増やすことができます.
コードは以下の通りです.

#include <cstdio>

int answer;

void dfs(int high, int cur, int p, int m)
{
    if(cur < 3)
        return;
    if(m > high) 
        return;
    if(p > (high << 1))
        return;
    if((m << 1) > p)
        return;
    
    if(cur == 3 && ((m + 1) << 1) == p) {
        answer++;
        return;
    }
    
    if(cur % 3 == 0)
        dfs(high, cur / 3, p, m + 1);
    dfs(high, cur - 1, p + 1, m);
}
int solution(int n) {
    if(n % 2 == 0)
        return 0;
    
    int high_note[20] = { 1 };
    int tmp = -2;
    for(int i=1;i<20;i++) {
        high_note[i] = high_note[i - 1] * 3 - tmp;
        tmp += 4;
    }
    int high = 19;
    for(int i=1;i<20;i++) 
        if(n < high_note[i]) {
            high = i - 1;
            break;
        }

    answer = 0;
    dfs(high, n - 2, 2, 0);
    
    return answer;
}