読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.314 ケンケンパ

問題はこちら
No.314 ケンケンパ - yukicoder

DP
a:「パで終わった」
b:「ケンが1回で終わった」
c:「ケンが2回で終わった」とする。このとき次の1歩を進むと
aからはbになり、bからはaかcになり、cはaになる。よってこれにより漸化式が立つ。
1歩目はケンでなければならないので、最初の時点ではaであるとしてよい

int main(){
	int a=1,b=0,c=0,n,ta,tb,tc,p=1000000007;
	scanf("%d",&n);
	while(n--){
		ta=a;tb=b;tc=c;
		a=(tb+tc)%p;
		b=ta;
		c=tb;
	}
	printf("%d",((a+b)%p+c)%p);
	return 0;
}

更新部分は、一時変数1つで

t=c;
c=b;
b=a;
a=(t+c)%p;

と書ける。
ところで漸化式により
(a,b,c)→(b+c,a,b)→(a+b,b+c,a)→(a+b+c,a+b,b+c)
と値が更新されていくので、3回余分にやれば出力部分での計算が省略できる

m=1e9+7,a,b,c,t;
main(n){
	for(scanf("%d",&n);3+n--;a=(c+t)%m)t=c,c=b,b=a;
	t=!printf("%d",a);
}

90B