結果
| 問題 | No.663 セルオートマトンの逆操作 |
| コンテスト | |
| ユーザー |
 snow4726
|
| 提出日時 | 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 |
ソースコード
/**********************************************************
一次元セルオートマトンルール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;
}