将棋とプログラミング

将棋の学習記録とプログラミングの創作記録

yukicoder No.663 セルオートマトンの逆操作 (未完)

No.663 セルオートマトンの逆操作 - yukicoder

セルオートマトンの逆操作という問題に挑戦しました。詳しくはリンク先を参照。

結果は解けませんでした。このコードを提出してもテストケースは通りません。

再帰関数使って解こうと思ったんだけどプログラムの実行時間が掛かり過ぎて
制限時間内に実行を終える事が出来ず、タイムオーバーとなってしまいました。

プログラムのコード的には合ってると思うんだけどどうしても解けない。
いつもこういう問題が解けない気がするなぁ。

何か良い解決策無いんだろうか。

/**********************************************************
一次元セルオートマトンルール110を1段目に適用した結果である2段目が
与えられるのであり得る1段目の種類数を出力するプログラム
入力:列数N、2段目のi列目の数値0か1
出力:2段目を生成できる1段目の種類数を10^9+7で割った余り
**********************************************************/
#include<stdio.h>
#include<stdlib.h>

/* グローバル変数 */
int* first; /* 1段目の数列*/
int* second;    /* 2段目の数列 */
int n;  /* 列数N */

long long int saiki(int);  /* 1段目の数列の種類数を求める再帰関数 */
int ismatch(int, int, int, int, int, int, int);
/* 一次元セルオートマトンルールの上段の値の列毎の比較と一次元セルオートマトンの上段の値を仮定して決める関数 */

int main(){

    int i;  /* カウンタ */
    long long int count;  /* 1段目の数列の種類数 */

    scanf("%d",&n); /* 列数Nの入力 */

    first = (int*)calloc(n,sizeof(int));    /* 1段目の数列の領域確保 */
    second = (int*)calloc(n,sizeof(int));   /* 2段目の数列の領域確保 */

    for(i=0; i<n; i++){
        scanf("%d",second+i);   /* 2段目のi列目の数値の入力 */
    }

    count = saiki(0);    /* 再帰関数によって1段目の数列の種類数を求める */

    printf("%lld\n",count%1000000007);  /* 出力 */

    return 0;

}

/**********************************************************
1段目の数列の種類数を求める再帰関数
引数:現在の列
返戻値:1段目の数列の種類数
**********************************************************/
long long int saiki(int stage){

    long long int count = 0;  /* 1段目の数列の種類数 */
    int num1,num2,num3;   /* 一次元セルオートマトンの上段の3つを指定する数列の列数番号 */

    if( stage < n ){    /* 現在の列がn列目以下の時 */
        if( stage == 0 ){
            num1 = n - 1;   /* 1列目は一次元セルオートマトンの上段の左の列数はn列目 */
        }else{
            num1 = stage - 1;   /* 1列目以外は現在の列-1が一次元セルオートマトンの上段の左の列数 */
        }

        if( stage == n - 1 ){
            num3 = 0;   /* n列目は一次元セルオートマトンの上段の右の列数は1列目 */
        }else{
            num3 = stage + 1;   /* n列目以外は現在の列+1が一次元セルオートマトンの上段の右の列数 */
        }

        num2 = stage;   /* 一次元セルオートマトンの上段の真ん中の値の列数は現在の列 */
    }

    if( stage == n ){   /* 現在の列がn+1列目の時はその数列は1段目の数列と見なされる */
        count++;    /* 1段目の数列の種類数をカウント*/
    }else{  /* 探索中 */
        if( second[stage] == 0 ){   /* 2段目の現在の列の数値が0の場合 */
            if( ismatch(stage,num1,num2,num3,0,0,0) == 1 ) count += saiki(stage+1); /* 一次元セルオートマトンの上段が0,0,0の場合の比較、再帰 */
            if( ismatch(stage,num1,num2,num3,1,0,0) == 1 ) count += saiki(stage+1); /* 一次元セルオートマトンの上段が1,0,0の場合の比較、再帰 */
            if( ismatch(stage,num1,num2,num3,1,1,1) == 1 ) count += saiki(stage+1); /* 一次元セルオートマトンの上段が1,1,1の場合の比較、再帰 */
        }else{  /* 2段目の現在の列の数値が1の場合 */
            if( ismatch(stage,num1,num2,num3,0,0,1) == 1 ) count += saiki(stage+1); /* 一次元セルオートマトンの上段が0,0,1の場合の比較、再帰 */
            if( ismatch(stage,num1,num2,num3,0,1,0) == 1 ) count += saiki(stage+1); /* 一次元セルオートマトンの上段が0,1,0の場合の比較、再帰 */
            if( ismatch(stage,num1,num2,num3,0,1,1) == 1 ) count += saiki(stage+1); /* 一次元セルオートマトンの上段が0,1,1の場合の比較、再帰 */
            if( ismatch(stage,num1,num2,num3,1,0,1) == 1 ) count += saiki(stage+1); /* 一次元セルオートマトンの上段が1,0,1の場合の比較、再帰 */
            if( ismatch(stage,num1,num2,num3,1,1,0) == 1 ) count += saiki(stage+1); /* 一次元セルオートマトンの上段が1,1,0の場合の比較、再帰 */
        }
    }

    return count;
}

/************************************************************************
一次元セルオートマトンルールの上段の値の列毎の比較と
一次元セルオートマトンの上段の値を仮定して決める関数
引数:現在の列数、一つ前の列、現在の列、一つ後の列、一次元セルオートマトンの値3つ
返戻値:一次元セルオートマトンの上段の値の列毎の比較を行い全て等しいか否か
************************************************************************/
int ismatch(int stage, int num1, int num2, int num3, int i1, int i2, int i3){

    int flag = 0;   /* 一次元セルオートマトンの上段の値の列毎の比較に使うフラグ */

    if( stage >= n - 2 ){   /* 2段目の現在の列がn-1かn列目の時 */
        /* 一次元セルオートマトンの上段の値の列毎の比較 */
        if( first[num1] == i1 && first[num2] == i2 && first[num3] == i3 ) flag = 1;
    }else if( stage != 0 ){ /* 2段目の現在の列が1列目以外の時 */
        /* 一次元セルオートマトンの上段の値の列毎の比較 */
        if( first[num1] == i1 && first[num2] == i2 ){
            flag = 1;
            first[num3] = i3;   /* 次の列の一次元セルオートマトンの上段の値を仮定する */
        }
    }else{  /* 2段目の現在の列が1列目の時 */
        /* 一次元セルオートマトンの上段の値3つ全てを仮定する */
        first[num1] = i1;
        first[num2] = i2;
        first[num3] = i3;
        flag = 1;   /* 1列目の時は無条件で判定OKとする */
    }

    return flag;

}