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

メモ

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

yukicoder No.478 一般門松列列

問題はこちら
No.478 一般門松列列 - yukicoder

要するに「長さnの数列であって、その長さ3の連続部分列のうち、門松列でないものがちょうどk個であるようなもの」を答えれば良い
サンプル3を眺めると、どうやら「1,3,2,4」を繰り返したものは必ず門松列列になるようだ。これでkが0の場合は解決できた。
これの先頭に1をつけると、最初の「1,1,3」は門松列で無くなるが、それ以降は影響なく門松列なので(先頭に1つ増やした分、末尾を1つ削れば)k=1の場合も解決できる。
同様に先頭に1をk個つけることで一般の場合も解決できる

int main(){
	int n,k,i;
	int a[]={1,3,2,4};
	scanf("%d%d",&n,&k);
	for(i=0;i<k;i++)printf("1 ");
	n-=k;
	for(i=0;i<n;i++)printf("%d ",a[i%4]);
	return 0;
}

「1,3,2,4」を出力する部分だが、これは大小関係さえこうなればよいので、例えばi%4*3%5により達成することが出来る

i%4 i%4*3%5
0 0
1 3
2 1
3 4

余計な変数を使わないよう、nをデクリメントしながらループするという形にする
そうすると「先頭k個を~」という処理はめんどくさいので、「末尾k個を~」と書き換え、以下のようなものができる

n;main(k){for(scanf("%d%d",&n,&k);n--;)printf("%d ",(n>k?n:k)%4*3%5);}

70B