yukicoder No.305 鍵(2)

問題はこちら
No.305 鍵(2) - yukicoder

writer解と同じ発想
ある桁の数字を変えた時、当たり数が大きくなれば新しい方が当たり、小さくなれば古い方が当たり。これを繰り返して上の桁から順に調べていく

char s[]="0000000000";
n,k,i;
main(){
	puts(s);
	fflush(0);
	scanf("%d%*s",&n);
	for(;k<10;){
		puts(s);
		fflush(0);
		scanf("%d%*s",&k);
		if(k!=n){
			k>n?n=k:s[i]--;
			i++;
			continue;
		}
		s[i]++;
	}
}

scanfが2つあるのでこれを1つにまとめる
また、読み込みはgets+atoiでできる

char s[]="0000000000";
n,k;
main(i){
	for(n=i=-1;k<10;k>n?n=k:s[i]--,i++)
		for(;puts(s),fflush(0),k=atoi(gets(&k)),k==n;s[i]++);
}

ループ圧縮
また、kを1増やすことでnの初期化は不要(-2B+2B)、iの符号を逆にすることでiの初期化は不要(-4B+2B)

for(n=i=-1;k<10;k>n?n=k:s[i]--,i++)for(;puts(s),fflush(0),k=atoi(gets(&k)),k==n;s[i]++);
for(n=i=-1;puts(s),fflush(0),k=atoi(gets(&k)),k-n?k>n?n=k:s[i]--,i++,k<10:s[i]++;);
for(;puts(s),fflush(0),k=atoi(gets(&k))+1,k-n?k>n?n=k:s[-i]--,i--,k<11:s[-i]++;);

というかそもそもポインタを使えばiそのものが不要。1B短縮

char s[]="0000000000",*p=s-1;
k;
main(n){
	for(;puts(s),fflush(0),k=atoi(gets(&k))+2,k-n?k>n?n=k:--*p,p++,k<12:++*p;);
}

115B

文字列を使わずに数のまま扱うのも考えたが、初期化がうまく噛み合わないなどして120Bとなった

long s,k,i;
main(n){
	for(;printf("%010ld\n",s),fflush(0),k=atoi(gets(&k))+2,k-n?k>n?n=k:(s-=i),i=i*10?:1,k<12:(s+=i,1););
}

2017/09/13追記
atoi(gets())+2としていたところを~atoi(gets())とすることで1B短縮
putsをfflushの引数に押し込んで自明に1B短縮

char s[]="0000000000",*p=s-1;
k;
main(n){
	for(;fflush(!puts(s)),k=~atoi(gets(&k)),k-n?k<n?n=k:--*p,p++,k+11:++*p;);
}

113B

yukicoder No.557 点対称

問題はこちら
No.557 点対称 - yukicoder

回文と同様、上半分を決めると下半分は自動的に決まる
・n=1のとき
1,8の2通り
・nが偶数のとき
上位n/2桁を決めると、下位は自動的に決まる
先頭の位に使えるのは1,6,8,9の4通り
それ以外は0,1,6,8,9の5通り
よって4*5^(n/2-1)
・nが3以上の奇数のとき
上位(n+1)/2桁を決めると、下位は自動的に決まる
先頭の位に使えるのは1,6,8,9の4通り
真ん中の位に使えるのは0,1,8の3通り
それ以外は0,1,6,8,9の5通り
よって4*3*5^((n+1)/2-2)

冪剰余は繰り返し二乗法により求める

#define ll long long
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n%2?x=x*a%m:0,a=a*a%m;return x;}

ll n,m=1e9+7,ans;
main(){
	scanf("%ld",&n);
	if(n==1)ans=2;
	else if(n%2==0)ans=4*pom(5,n/2-1,m)%m;
	else ans=12*pom(5,(n+1)/2-2,m)%m;
	printf("%d",ans);
}

整数除算は切り捨てられることから、5の指数部分はn/2-1とまとめられる
繰り返し二乗法の実装をぎゅっとするなどして（c.f.yukicoder No.117 組み合わせの数 - メモ）

long x,n;
m=1e9+7;
p(a,i){x=i?p(1L*a*a%m,i/2),i%2?x*a%m:x:1;}
main(){
	scanf("%ld",&n);
	p(5,(n/2-1)%~-m);//フェルマーの小定理
	printf("%d",n>1?(n%2*8+4)*x%m:2);
}

133B

yukicoder No.554 recurrence formula

問題はこちら
No.554 recurrence formula - yukicoder

とする
このとき
よりとなりの漸化式が得られる
でありなので、これにより計算できる

long s[100100];
n,ans,m=1e9+7;
main(){
	scanf("%d",&n);
	if(n==1)ans=1;
	else{
		s[1]=1;
		for(int i=2;i<=n;i++)s[i]=(i*s[i-1]+s[i-2])%m;
		ans=(s[n]-s[n-2]+m)%m;
	}
	printf("%d",ans);
}

s[n]は三項間漸化式で得られ、a[n]はs[n]とs[n-2]で得られるので、これはs[n],s[n-1],s[n-2]の3状態のDPといえる
これをa[n],s[n-1],s[n-2]の3状態だと思えば、要するに「a[n]、n-1までの奇数項目の和、n-1までの偶数項目の和」ということ

long esum,osum,an;
n,m=1e9+7;
main(){
	scanf("%d",&n);
	an=1;
	for(int i=2;i<=n;i++){
		if(i%2==1){
			esum=(esum+an)%m;
			an=i*esum%m;
		}else{
			osum=(osum+an)%m;
			an=i*osum%m;
		}
	}
	printf("%d",an);
}

これをひとまず縮める

long t[2];
i,n,m=1e9+7;
main(a){
	scanf("%d",&n);
	for(i=2;i<=n;i++){
		t[i%2]=(t[i%2]+an)%m;
		a=t[i%2]*i%m;
	}
	printf("%d",a);
}

tは毎回剰余をとらなくても大丈夫。その場合でもt*iの計算は64bit整数の範囲に収まるので剰余は各回1回だけ取れば良い

long t[2];
i,n,m=1e9+7;
main(a){
	for(i=scanf("%d",&n);n/++i;)a=(t[i%2]+=a)*i%m;
	printf("%d",a);
}

92B

yukicoder No.552 十分簡単な星1の問題

問題はこちら
No.552 十分簡単な星1の問題 - yukicoder

値が大きいので文字列として読み込む。
0のときはそのまま出力し、それ以外のときは末尾に0をつける

char s[99];
main(){
	gets(s);
	if(strcmp(s,"0")==0)puts("0");
	else printf("%s0",s);
}

20文字くらいならint型に読み込んでもどうにかなりそう

n;main(){printf(n-48?"%s0":"0",gets(&n));}

nをmainの引数にするとREとなる
42B

yukicoder No.548 国士無双

問題はこちら
No.548 国士無双 - yukicoder

「a～mのうち、いずれか1種を2つ、残りの12種を1つ含む」というのは「a～mのうち、13種いずれもを1つ以上含み、これら以外を含まない」と同値
よって、与えられた13文字にa～mを加えたものが条件をみたすかをチェックする

s,f;
main(){
	for(int i=0;i<13;i++)s|=1<<(getchar()-'a');
	for(int i=0;i<13;i++)if((s|1<<i)==0x1FFF){
		printf("%c\n",'a'+i);
		f++;
	}
	if(f==0)puts("Impossible");
}

まとめやすくするためにちょっといじる

s,f;
main(i){
	for(;i<14;i++)s|=1<<getchar()-97;
	for(;i<27;i++)(s|1<<i-14)-8191||printf("%c\n",f=83+i);
	f||puts("Impossible");
}

まとめる

s,f;
main(i){
	for(;i<27;(s|1<<i++-14)-8191||printf("%c\n",f=82+i))s|=(i<14)<<getchar()-97;
	f||puts("Impossible");
}

ふと思ってiの増減を逆にしたら2B縮んだ

s,f;main(i){for(;i<27;(s|1<<i++-14)-8191||printf("%c\n",f=96+i))s|=(i<14)<<getchar()-97;f||puts("Impossible");}
s,i=26,f;main(){for(;i;(s|1<<i)-8191||printf("%c\n",f=109-i))s|=--i/13<<109-getchar();f||puts("Impossible");}
//iをmainの引数に入れられない+1B
//8191との一致チェック-3B
//入出力時の定数+2B
//入力時の括弧省略-2B

ということで

s,i=26,f;
main(){
	for(;i;(s|1<<i)-8191||printf("%c\n",f=109-i))s|=--i/13<<109-getchar();
	f||puts("Impossible");
}

108B