結果

問題 No.663 セルオートマトンの逆操作
ユーザー snow4726snow4726
提出日時 2018-03-16 21:20:36
言語 C
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 6,096 bytes
コンパイル時間 328 ms
コンパイル使用メモリ 30,592 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-12-21 14:39:56
合計ジャッジ時間 19,634 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**********************************************************
一次元セルオートマトンルール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;

}
0