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

メモ

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

yukicoder No.360 増加門松列

問題はこちら
No.360 増加門松列 - yukicoder

Cにはnext_permutationはないので場合分けして考察
7箇所の位置を順にa~gとすると、各門松が(左端<右端)であるという条件から
a<c<e<g
b<d<f
が必要とわかり、各部分列が門松列になる条件をあわせて

b<d<f     a<c<e<g
^ ^ ^       ^ ^ ^
a<c<e<g     b<d<f

のどちらかを満たすことが必要十分と分かる。
この不等式を睨むと
「同じものが3個あったらだめ」
「最大値/最小値が2つあったらだめ」
「4種以下しか数がなければだめ」
という事がとりあえずわかる。
この3つの必要条件を満たすものは(与えられた竹の長さを適当に圧縮して1~7で表すと)
1234567
123456+(2,3,4,5)
12345+(23,34,24)
の8つあり、その中で1234524以外は元の不等式を満たすことが確かめられる

135  124  1235 1234 1235
2467 2356  346  456  456

123  1234 1??  1234
2345  345 2345  ??5  (1234524だけはどちらも満たせない)

ということで、与えられたD[i]をソートして、上の7パターンのいずれかになっていることをチェックすれば良い
1234567
1223456
1233456
1234456
1234556
1223345
1233445
のどのパターンかをそれぞれ調べても良いが、条件式を少しずつまとめていくことで、以下のようなまあまあ短い条件にまとめられる

a[9],i,s;
int c(int*x,int*y){return *x-*y;}
int main(){
	for(i=0;i<7;i++)scanf("%d",a+i);
	qsort(a,7,4,c);
	if(a[0]!=a[1]&&a[5]!=a[6]&&((a[1]!=a[2]&&a[3]!=a[4])||(a[2]!=a[3]&&a[4]!=a[5])))puts("YES");
	else puts("NO");
	return 0;
}

a[i]とa[i+1]が等しいか否かをbitで保存すれば良さそう

a[9],i,s,z;
c(int*x,int*y){z=*x-*y;}
main(){
	for(;~scanf("%d",a+i++););
	for(qsort(a,7,4,c);--i;s+=a[i-1]==a[i])s*=2;
	s=!puts(s&33||s&10&&s&20?"NO":"YES");
}

for文をぐぐっと圧縮して

for(i=0;~scanf("%d",a+i++););for(qsort(a,7,4,c);--i;s+=a[i-1]==a[i])s*=2;
//↓for文圧縮
for(i=7;~scanf("%d",a)?qsort(a,7,4,c),1:--i?s+=s+(a[i-1]==a[i]),1:0;);
//毎回ソートし、D[i]が正であることを利用して、読み込み先をa[0]に固定した
//↓ソートしてあるのでa[i-1]==a[i]⇔a[i-1]≧a[i]であることを利用して
for(i=7;~scanf("%d",a)?qsort(a,7,4,c),1:--i?s+=s+a[i-1]/a[i],1:0;);
//↓よく考えたら--iの位置は動かせる
for(i=6;~scanf("%d",a)?qsort(a,7,4,c),1:(s+=s+a[i-1]/a[i],--i););
//というかじゃあカッコの外でよくない?
for(i=13;!~scanf("%d",a)?s+=s+a[i-1]/a[i]:qsort(a,7,4,c),--i;);

まとめると

a[9],i=13,s,z;
c(int*x,int*y){z=*x-*y;}
main(){
	for(;!~scanf("%d",a)?s+=s+a[i-1]/a[i]:qsort(a,7,4,c),--i;);
	s=!puts(s&33||s&10&&s&20?"NO":"YES");
}

142B

16/06/17追記
iがカッコの外でいいなら、それ以外の部分はfor文の空いてるところに動かせるじゃん

a[9],i=14,z,s;
c(int*x,int*y){z=*x-*y;}
main(){
	for(;--i;!~scanf("%d",a)?s+=s+a[i-1]/a[i]:qsort(a,7,4,c));
	s=!puts(s&33||s&10&&s&20?"NO":"YES");
}

141B