会津大学オンラインジャッジ 問8

Sum of 4 Integers

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0008
ｎが与えられるのでa+b+c+dで何通りの方法でｎが作れるか答える問題。
0<=a,b,c,d<=9


解法
Ｊａｖａといふものを一つ初めて見よふと思ひておもむろにエクリープスなるものをダウソロードし右も左もわからぬまま気の赴くままにＡＯＪの問題などをといてみゆ。

計算量は19*19+10*10となかりしけるが、Ｊａｖａ言語事体の重さの前には全く意味がないといふことに気付く。


C++で書き直してみたら計算量27*4回になった。
ちなみにこの問題数式で書き表してもよいが数式を具体的に計算する計算量はもう少し小さくなるはず。
多分。


import java.util.Scanner;

class Main{
static final Scanner stdin=new Scanner(System.in);
//javaの手習い

public static void main(String[] args){
int[] memo=new int[37];
int[] memo2=new int[37];
for(int i=0;i<37;i++){
memo[i]=0;
memo2[i]=0;
}
for(int a=0;a<10;a++)
for(int b=0;b<10;b++)
memo[a+b]++;
for(int u1=0;u1<=18;u1++){
for(int u2=0;u2<=18;u2++){
memo2[u1+u2]+=memo[u1]*memo[u2];
}
}

while(stdin.hasNext()){
int n=stdin.nextInt();
if(n<0||n>36){
System.out.println(0);
}else{
System.out.println(memo2[n]);
}
}
}
}



ｃ++版

#include<stdio.h>

int main(){
int dp[37]={1,0},n,a;
for(int i=0;i<4;i++){
int sum=0,p=0,old=0;
for(int s=18;s>=-8;s--){
if(s>=9){
sum+=dp[s];
}else{
sum=sum-old+(s>=0?dp[s]:0);
}
old= s>9?0:dp[s+9];
dp[s+9]=sum;
p=(p+1)%10;
}
}
while(scanf("%d",&n)!=EOF){
if(n>36||n<0)a=0;
else a=dp[n>18?36-n:n];
printf("%d\n",a);
}
}