CODE FESTIVAL 2015 決勝【B問題】※TLE ※再帰関数

一番最近のコードフェスティバルのB問題

問題文

ボードゲームにはダイス（サイコロ）を使うゲームが少なくありません。そこで、ダイスについての問題を出したいと思います。

問題： 6 面ダイスを N 個振るとき、ダイスの目の和として出る確率が最も高い値は何か？そのような値が複数ある場合は、そのうち最も小さい値を答えよ。

問題文を読んだ瞬間、再帰関数使って余裕やなと考えて、出力結果があっていたので提出、すると結果は初めて出てきたTLE(Time Limit Exceeded)と返ってきた。どうやら、プログラムの制限時間2秒をオーバーしてしまい、再帰関数では、時間がかかりすぎるようなので非再帰の関数を明日以降考えていきたいと思う。一応以下、ソースコード。コードフェスティバルの提出用のプログラムをそのまま、コピペしたのでインデントは一切行われていない。

1. #include <stdio.h>
2.  
3. int a[6*256];
4.  
5. void dice_total(int N, int total){
6. if(N == 0){ //最後
7. a[total]++;
8. return ;
9. }
10.  
11. int k;
12. for(k = 1; k <= 6; k++){
13. total++;
14. dice_total(N-1, total);
15. }
16. }
17.  
18. int main(void){
19. int k, n, N;
20. scanf("%d", &N);
21.  
22. for(k = 0; k < 6*N; k++){
23. a[k] = 0;
24. }
25.  
26. dice_total(N, 0);
27.  
28. int i = 0;
29. for(k = 0; k <= 6*N; k++){
30.  
31. // printf("a[%d] = %d\n", k, a[k]); //デバッグ用
32.  
33. if(a[k] > i)
34. i = a[k];
35. }
36.  
37. for(k = 0; k <= 6*N; k++){
38. if(a[k] == i){
39. printf("%d\n", k);
40. break;
41. }
42. }
43.  
44. return 0;
45. }

それはそうと、ネットにソースコードをあげることが増えてきたので

そろそろD-Wコードを読んだ方が良いかもしれない。