yukicoder No.41 貯金箱の溜息（EASY）

問題はこちら
No.41 貯金箱の溜息（EASY） - yukicoder

111111円に満たない金額は1円玉で払うしか無いので、全体を111111で割ることで問題は次のように読み替えられる
「floor(M/111111)円以下を、1～9円玉を使って払う方法は何通りか」
ということでDP
M≦10^10なので、floor(M/111111)≦90000

int main(){
	int s[90020],i,j;
	long m=1e9+9;
	for(i=0;i<90020;i++)s[i]=1;
	//1円も払わないという選択肢が各1通り
	for(i=1;i<=9;i++){
	//順次i円玉の使用を解禁
		for(j=0;j++<9e4;){
			s[j+i]+=s[j];
			s[i+j]%=m;
		}
	}
	scanf("%d",i);
	while(i--){
		scanf("%ld",&m)
		printf("%d\n",s[m/111111]);
	}
	return 0;
}

配列に初期値1を与えるのはめんどくさいので、iが1の時に余分に1加算するようにしよう
読み飛ばしもうまくやる

i,s[99999];
long m=1e9+9;
main(j){
	for(;i++<9;)for(j=0;j<9e4;s[i+j++]%=m)s[j+i]+=s[j]+(i==1);
	for(;i=~scanf("%ld",&m);j=0)j||printf("%d\n",s[m/111111+1]);
}

初期化をサボったせいでs[0]はずっと0になってしまう
そのせいでindexが1つずれた

1つ目のループ圧縮
初期値の関係でiとjを入れ替え

j,s[99999];
long m=1e9+9;
main(i){
	for(;j<9e4?s[j+i]+=s[j]+!~-i,s[i+j++]%=m:(j=0,i++<9););
	for(;j=~scanf("%ld",&m);i=0)i||printf("%d\n",s[m/111111+1]);
}

2つ目のループ圧縮
処理順序の関係でiのincと評価の順番を変更

j,s[99999];
long m=1e9+9;
main(i){
	for(;9/i?j<9e4?s[j+i]+=s[j]+!~-i,s[i+j++]%=m:(j=0,i++):~scanf("%ld",&m)?j=!j||printf("%d\n",s[m/111111+1]):0;);
}

ここでよく見ると
a?b?c:(j=0,d):e?j=f:0
という形になっているので、頑張れば
j=a?b?c:d:e?f:0
の形に書けそう
そうするとしたらdの部分はi++か++iなので、dpの計算式を
s[j+i]+=s[j]　から　s[j]+=s[j-i]　に書き直すとうまく噛みあう
さらに最初だけjの初期値が0なのでsのindexずれも解消される
fの部分も0にならないように気をつけて書き直す

j,s[99999];
long m=1e9+9;
main(i){for(;j=9/i?j<9e4?s[j]+=s[j-i]+!~-i,s[j]%=m,j+1:++i:~scanf("%ld",&m)?~-j||printf("%d\n",s[m/111111]):0;);}

今までの短いgolf人生で会心の出来
137B

17/01/24追記
iは1以上なので!~-iは1/iと書け1B短縮

j,s[99999];
long m=1e9+9;
main(i){for(;j=9/i?j<9e4?s[j]+=s[j-i]+1/i,s[j]%=m,j+1:++i:~scanf("%ld",&m)?~-j||printf("%d\n",s[m/111111]):0;);}

136B