久しぶりに書くよ！！
最近は問題とコードサイズのランキングをちらっと見て通り過ぎることが多いのですが、この問題を見たとき「縮む！」と直感しました。…が、めちゃくちゃ大変だった（´ω｀）
0008 - Sum of 4 Integers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0008&lang=jp
50 以下の正の整数 n を入力し、0 〜 9 の範囲の整数 a, b, c, d の組で
a + b + c + d = n
を満たすものの組み合わせ数を出力するプログラムを作成して下さい。
例えば、n が 35 のとき、(a, b, c, d) は (8,9,9,9)、(9,8,9,9)、(9,9,8,9)、(9,9,9,8) の 4 通りですので、答えは 4 となります。
深さ優先探索
今回の問題は10^4通りしか組合せがないですし、わざわざこの方法を使わなくても良いですが、最初に思いついた解法なので紹介しておきます。
#include<iostream>
#include<algorithm>
using namespace std;
int ans=0;
int r(int d, int n)
{
if(n<0)return 0;
if(d==0)
{
if(n==0) ++ans;
return 1;
}
for(int i=0;i<=9; ++i)
{
r(d-1,n-i);
}
return 0;
}
main()
{
int n;
for(;cin>>n;cout<<ans<<endl)
{
ans=0;
r(4,n);
}
return 0;
}これを普通に縮めると105Bになります。
a;
r(d,n,i){
for(i=10;d*i--;)r(d-1,n-i);d|n||++a;
}
main(n){
for(;~scanf("%d",&n);a=!printf("%d\n",a))r(4,n);
}
出力部分を
printf("%d\n",r(4,n))
みたいに書いてうまくいく環境もありますが、AOJでは無理っぽいです。
単純な全列挙
4けたの整数0000〜9999について各位の数を素直に足してやるコードだと、とても簡単に書くことができます。
#include<iostream>
using namespace std;
int main()
{
for(int n;cin>>n;)
{
int a=0;
for(int k=0;k<10000;++k)
{
int t=k/1000+k/100%10+k/10%10+k%10;
if(n==t)++a;
}
cout<<a<<endl;
}
return 0;
}これをCで短縮してやると104Bまで縮みます。
a;
main(n,k){
for(;~scanf("%d",&n);a=!printf("%d\n",a))
for(k=1e4;k--;)a+=k/1000+k/100%10+k/10%10+k%10==n;
}
答えを埋め込めないか
「nは50以下の正の整数」という記述がありますが、9+9+9+9=36ですので、37以上のnについてはすべて答えが0になります。実質、36までできちんと数えられれば良いことになりますので、nが0*1から36までの場合について、答えを並べてみます。n=0,1,2,...に対して、答えは
1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 282, 348, 415, 480, 540, 592, 633, 660, 670, 660, 633, 592, 540, 480, 415, 348, 282, 220, 165, 120, 84, 56, 35, 20, 10, 4, 1
のように、n=18の境に対称になっています。実質0から18までを計算するだけで、すべての答えがわかることになります。
しかし、19個もの数を埋め込もうとすれば、コード量は結構増えますので、少し工夫します。隣り合った数の差を取っていくと、
3, 6, 10, 15, 21, 28, 36, 45, 55, 62, 66, 67, 65, 60, 52, 41, 27, 10
のように、1バイトに収まるので、これを文字列とすれば、
a;main(n){for(;~scanf("%d",&n);a=!printf("%d\n",a))for(n=abs(18-n);n<19;)a-="xxxxxxxxxxxxxxxxxx"[n++];}
みたいな形で書くことができます。ただし、改行を表す文字コード'10'が含まれていますから、そのまま文字列にはできません。ですので、-をつけた値で文字列を作る等の工夫は必要です。また、AOJのSubmitフォームでは提出できないので、自分でツールを作るとか、結構な労力が必要でしょう。ちなみに、私はここまで試していませんので、ツールを使ってもうまくいくかは未検証です。なぜかというと、この方法でもせいぜい104B止まりだからです。
じゃあ、最短を目指すには
入力nに対する答えは、頑張れば計算で出すことができます。
nが0から9の範囲では、
(n+1)*(n+2)*(n+3)*1/6
nが10から18の範囲では、
(n+1)*(n+2)*(n+3)*1/6 - (n-9)*(n-8)*(n-7)*2/3
前半の部分は共通していますし、何より変数が1つだけで済みます。というわけで、この方法でやってみましょう。
main(n){
for(;
~scanf("%d",&n);
printf("%d\n",n<0?0:(n+1)*(n+2)*(n+3)/6-(n>9?(n-9)*(n-8)*(n-7)*2/3:0))
)n=n>18?36-n:n;
}
これで115Bと、微妙なサイズではありますが、短縮の余地は大いにあります。まず、括弧（）を可能な限り取り除いていきましょう。
main(n){
for(;
~scanf("%d",&n);
printf("%d\n",n++<0?0:n*~n*~-~n/6+(n>9?(n-=9)*~n*~-n*2/3:0))
)n=n>18?36-n:n;
}
(n-=9)の部分が何とも怪しげですが、AOJの処理系ではうまく動いてくれました。これで105Bです。
n>9の部分にある条件演算子をやめて、この部分の式が必要な場合は1を掛けて、必要ない場合は0を掛ける式に変更します。
main(n){
for(;
~scanf("%d",&n);
printf("%d\n",n++<0?0:n*~n*~-~n/6+n/11*(n-=9)*~n*~-n*2/3)
)n=n>18?36-n:n;
}
これで102B。十分縮んだ気がしますが、もうちょっとだけ改良します。ショートコーディングで多用する条件演算子（3項演算子）
式1 ? 式2 : 式3
は、gccの場合式2を省略することができます。式2を省略すると、省略した部分は式1の値が入るので、上記のコードは式2に当たる0を省略すると、nが負の数の場合にn<0==1が入ります。実際は1ではなく0と表示したいので、式全体を6で割るような形に書き換えて、1/6->0になるようにします。
main(n){
for(;
~scanf("%d",&n);
printf("%d\n",(n++<0?:n*~n*~-~n+n/11*(n-=9)*~n*~-n*4)/6)
)n=n>18?36-n:n;
}
これで101Bになりました。n=n>18?36-n:nの部分をもうちょっと工夫出来れば良いのですが、私は思いつかなかったので、この辺を縮めるアイデアがあれば、さらに短いコードが書けるのではないでしょうか。
*1:説明しやすいので0も入れておきます
