ルーレットの和

困ってた一つのプログラムが解決したので，あげさせていただきます．

問としては，以下．

1<n<37のそれぞれのnについて，連続するn個の数の和が最大になる場合を求め，ヨーロピアンスタイルでの和がアメリカンスタイルでの和よりも小さくなるnがいくつあるか求めよ．
「プログラマ脳を鍛える数学パズル」　著者：増井敏克

この問題を見て，ルーレットに
アメリカンスタイルとヨーロピアンスタイルがあることを知ったくらいには，無知な状態からのスタート…笑
ちなみに，フレンチルーレットもあるみたい．

でもですね，ルーレットの種類を知ってようがいまいが
プログラムには大して関係ないので，
それは置いておき，この問題の解答を．

public class roulette{
 public static void main (String[] args){
   int eu[] = {0,32,15,19,4,21,2,25,17,34,6,27,13,36,11,30,8,23,10,5,24,16,33,1,20,14,31,9,22,18,29,7,28,12,35,3,26};
   int am[] = {0,28,9,26,30,11,7,20,32,17,5,22,34,15,3,24,36,13,1,00,27,10,25,29,12,8,19,31,18,6,21,33,16,4,23,35,14,2};
   int count = 0;

   for(int n = 2; n < 37; n++){
     if(sum(eu,n) < sum(am,n)){
       count++ ;
     }
   }
   System.out.print(count);
 }

 private static int sum(int rou[] , int n) {
   int ans = 0;
   for(int i = 0; i < n ; i++){
     ans += rou[i];
   }
   int tmp = ans;
   for(int k = 0; k < rou.length ; k++){
     tmp += rou[(k+n) % rou.length];
     tmp -= rou[k] ;
     if(tmp >= ans){
       ans = tmp ;
     }
   }
   return ans;
 }

}

9

今回のこの問題の一番の難しいポイントとしては，

ルーレットが円形であるということでした．

例えば，連続した4つの数の和(n=4)であれば，

それぞれのスタイルの
1~4個目，2~5個目，3~6個目…について
それぞれ和を求めて，その中の最大値を出して，
そのうえでスタイルごとでの比較をすれば良いっていうのが基本方針になると思うのだけれど，
じゃあ配列の最後の方どうする？っていう．

だって，今回のプログラムは配列が基本となっているんだもの．

36，37番目(ヨーロピアンスタイルの最後の目)と1,2番目の和みたいに
円形では連続していても，配列では連続ではないというこのギャップ．

私自分だけの力では無理だったので，増井先生が書かれたrubyの解答に頼りながらも頑張りました…。

一番難しいのがここだと思います．この意味について解説．

int tmp = ans;
   for(int k = 0; k < rou.length ; k++){
     tmp += rou[(k+n) % rou.length];
     tmp -= rou[k] ;
     if(tmp >= ans){
       ans = tmp ;
     }
   }

普通だったら配列の足し算だから，
for文使って回していけば良いのだけど，
それが上手くいくのは配列が最後尾に到着した瞬間まで．

そのあとは，上手く回せない．

そこで，あらかじめ，スタートのn個分の和(Snとする)を計算しておく．

一つずらした和を考えるタイミングでは，
Snにn+1個目の値(anとする)を足し，1個目(a0)の値をひく．

要するに，

S(n+1) = Sn + an - a0

みたいなイメージ．

が，ここで問題．

初っ端はn+1個目の値を足せば良いってわかるけど，
それ一般化しなきゃいけんやん！っていう．

ということで一般化する．
(本当はちゃんと計算した用紙をあげるつもりだったのだけど，写真が重すぎて…笑．ということで，色々面倒くさかったので省略)

そして，このやり方で考えると，配列上で連続しない和を求めるにあたって
うまい具合に作用する．

どういうことかというと，for文で回っているということは
延々と一つずつ数が大きくなっていく．

けれど，私たちは配列の長さを超えた段階で
1番目の値に戻ってほしい．

ってことは，for文で回していったkの値を
配列全体の長さで割ったら，
そのときの余りの値がちょうど1周終わって，2周目突入して何コマ目を表しているのか，捉えることができるじゃないかと．

解答読むと，なんでこんなことも自分で分からなかったのだろうと
色々投げ出したくなるけれど，まあしゃあない．

こういうのを繰り返して成長していくのだと我思ふ．

さ，もう夜も遅いし，寝ます．

自分のためだけの備忘録に，最後まで付き合ってくださった方々ありがとうございます．