yukicoder No.533 Mysterious Stairs

問題はこちら
No.533 Mysterious Stairs - yukicoder

初期値にちょっと気をつける必要があるがDPやるだけ。
dp[昇った段数合計][直前に段数]=場合の数

dp[1000010][4];n;
mod=1000000007;
main(){
	dp[1][1]=1;
	dp[2][2]=1;
	dp[3][1]=dp[3][2]=dp[3][3]=1;
	scanf("%d",&n);
	for(int i=4;i<=n;i++){
		dp[i][1]=(dp[i-1][2]+dp[i-1][3])%mod;
		dp[i][2]=(dp[i-2][1]+dp[i-2][3])%mod;
		dp[i][3]=(dp[i-3][1]+dp[i-3][2])%mod;
	}
	printf("%d",(dp[n][1]+dp[n][2]+dp[n][3])%mod);
}

実際には3段前までの情報があればいいので、直前の9状態から次の3状態を生成するDP。
ということは何かいい感じの漸化式ができるのでは……と思いながらOEISを見たらビンゴ
A155822 - OEIS
次の2つの漸化式が書いてあった

引き算が入っているとmodをとる時にこまるのと、単純に式が短い方が嬉しいので後者を採用した
代入が多いのでmain再帰で書いたけど、初期値を与えるもっと簡単な方法はないのだろうか……

n;M=1e9+7;main(a,b,c,d,e,f){~scanf("%d",&n)?main(1,1,3,3,4,8):--n?main(b,c,d,e,f,(0L+d+c+b+a+a)%M):printf("%d",a);}

115B

2017/07/29追記
自明な2B

n;M=1e9+7;main(a,b,c,d,e,f){~scanf("%d",&n)?main(1,1,3,3,4,8):--n?main(b,c,d,e,f,(2L*a+b+c+d)%M):printf("%d",a);}

113B

yukicoder No.538 N.G.S.

問題はこちら
No.538 N.G.S. - yukicoder

数学するだけ

連立方程式

を解き

を得る。求める答えはであるからこれに代入して

となる。
は最大10^5なので2乗すると32bitの範囲に収まらないことに注意する

long a,b,c;
main(){
	scanf("%ld%ld%ld",&a,&b,&c);
	printf("%ld",(c*c+b*b-b*c-a*c)/(b-a));
}

式をぐっと睨むと(c*c+b*b-b*c-a*c)/(b-a)をc+(b-c)*(b-c)/(b-a)と書き換えられることがわかる（自力では気づけず）

long b,c;
main(a){
	scanf("%d%ld%ld",&a,&b,&c);
	printf("%ld",c+(b-c)*(b-c)/(b-a));
}

79B

yukicoder No.544 Delete 7

問題はこちら
No.544 Delete 7 - yukicoder

Cで文字列処理をするのはつらいので数値として扱う。
下の位から順に見ていって、7であるようなところは6と1に分解する。それ以外はそのまま。
例えば72727なら62626+10101にする

int s,n,i;
main(){
	scanf("%d",&n);
	for(i=1;i<n;i*=10)if(n/i%10==7)s+=i;
	printf("%d %d",n-s,s);
}

もうほとんど縮めるところもないけれど、ぎゅっとして

s,n;
main(i){
	for(scanf("%d",&n);n/i;i*=10)s+=n/i%10-7?0:i;
	printf("%d %d",n-s,s);
}

80B

yukicoder No.543 命題

問題はこちら
No.543 命題 - yukicoder

問題文をよく読むと、入力「a b」に対しては「b a」を出力すれば良いことがわかる

main(){
	char a,b;
	scanf("%c %c",&a,&b);
	printf("%c %c",b,a);
}

1行まるごとひっくり返せばよい
頭から読んでお尻から出力→main再帰

main(i){read(0,&i,1);i&8||main()+putchar(i);}

45B

2017/08/13追記
普通にやったほうが短かった

main(i){gets(&i);printf("%c %c",i>>16,i);}

42B

数値のまま文字列処理するのも考えたけど流石にそれは長かった

main(i){gets(&i);i=i%255*65537-2080800-i;puts(&i);}
main(i){gets(&i);i+=(i%65537-8192)*65535;puts(&i);}

yukicoder No.542 １円玉と５円玉

問題はこちら
No.542 １円玉と５円玉 - yukicoder

5*b+4円以下の範囲については1円玉を5枚以上使うことなく作れるので、その範囲については2重ループ
それ以上は5円玉を全て使った上で1円玉で調整する

main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<=b;i++)for(int j=0;j<=4&&j<=a;j++){
		if(i==0&&j==0)continue;
		printf("%d\n",5*i+j);
	}
	for(int j=5;j<=a;j++)printf("%d\n",5*b+j);
}

まあそんなことしなくても、金額ごとに作れるかチェックすれば単純なループで書ける
作れる金額の最大は5*b+a円。これ以下の範囲については、i%5>aとなるようなi円は作れず、それ以外はすべて作れる。

i;main(a,b){for(scanf("%d%d",&a,&b);i++<5*b+a;i%5>a||printf("%d\n",i));}

72B