AtCoder Regular Contest 022 B問題をschemeで - プログラミングを上達させたい

最近、AtCoderの時間に何かしら用事があって、２回連続で参加できていません。
出来れば、毎週やりたいのに・・・
やはり、良いにしろ悪いにしろ、自分の実力を示す結果が出てくる、ってのはモチベーションを高めてくれます。
今週末もキツそうなのですが、なんとか参加したいものです。
最近、毎週コンテストが開催されていますね。本当にすごいです。

さて、そんな感じなので一番最近参加したのはAtCoder Regular Contest #023です。
１問しか解けませんでした。2問目の問題文を読み間違え？、3問目にとりかかりました。
そしてJavaでコードを書いて提出したのですが、

WA・・・
その時のコードが以下のものです。

import java.util.*;
import java.math.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
 
		int daynum = sc.nextInt();
 
		int[] nikkiArray;
		nikkiArray = new int[daynum];
 
		for(int i = 0; i < daynum; i++){
			nikkiArray[i] = sc.nextInt();
		}
 
		int[] howArray;
		howArray = new int[daynum];
		int[] maxArray;
		maxArray = new int[daynum];
		int[] minArray;
		minArray = new int[daynum];
 
		int checked = 0;
		int lengthcount = 0;
		boolean unknown = false;
		int nowmin = 0;
		long answer = 1;
		int count = 0;
 
		for(int i = 0; i < daynum; i++){
			if(nikkiArray[i] > 0 && unknown){
				howArray[checked] = count;
				count = 0;
				maxArray[checked] = nikkiArray[i];
				minArray[checked] = nowmin;
				nowmin = nikkiArray[i];
				checked++;
				unknown = false;
			}else if(nikkiArray[i] > 0){
				nowmin = nikkiArray[i];
			}else{
				count++;
				unknown = true;
			}
		}
 
		long howup;
		long bunbo;
		long bunsi;
		long up;
 
		for(int i = 0; i < checked; i++){
			if(maxArray[i] == minArray[i]){continue;}
			howup = maxArray[i] - minArray[i] + howArray[i];
			bunsi = 1;
			bunbo = 1;
			up = 1;
 
			for(int j = 0; j < howArray[i]; j++){
 
				bunbo *= howup;
				bunsi *= up;
				up++;
				howup--;
 
			}
			answer *= (bunbo / bunsi);
			answer = answer % 1000000007;
		}
 
 
		System.out.println(answer);
	}
}

長いですね。
しかし、まったくダメだったわけではなく、半分以上はACで、ところどころWAという感じ。
学生時代に情報学やプログラミングの勉強をほとんどしなかった僕が少ない知識で必死に考えた結果、これはあの、longの幅に収まらなくなって別の数になっちゃう？、オーバーフローというやつではないかと思いました。

この解き方では、まず、読めなくなっているひとかたまりの情報を順に取得していきます。
取得するのは、読めない部分の直前の数、直後の数、その幅、です。
たとえば、
2 3 -1 -1 5 6 -1 -1 -1 7 -1 7
という入力があるとすると、読めない塊は３つあり、それらの情報は、
1つ目=直前3、直後5、幅2
2つ目=直前6、直後7、幅3
3つ目=直前7、直後7、幅1
といった具合です。
そして、それぞれに対して、何通りあり得るか場合の数を計算し、最後にかけあわせるといったやり方です。
あり得る場合の数は、

	for(int i = 0; i < checked; i++){
		if(maxArray[i] == minArray[i]){continue;}
		howup = maxArray[i] - minArray[i] + howArray[i];
		bunsi = 1;
		bunbo = 1;
		up = 1;
 
		for(int j = 0; j < howArray[i]; j++){
 
			bunbo *= howup;
			bunsi *= up;
			up++;
			howup--; 
		}
		answer *= (bunbo / bunsi);
		answer = answer % 1000000007;
	}

で計算しています。i番目の塊の、直前の数がminArray[i]、直後の数がmaxArrray[i]、幅がhowArray[i]です(確か)。
これは、高校の組み合わせの知識が必要です。
余談ですが、僕は高校のときにどうしてもHとPが好きになれず、全部Cで解いていました。まぁ今回は素直にHを使ったのですが。

これだと変数bunbo、bunsiに入る数は非常に大きくなることがあります。
またそのために用意されている「1,000,000,007 (素数)で割った余りで」という要件についても、bunbuとbunsiを計算して割ったあとで適用するため、それじゃ遅いよ、といった感じなんでしょうね。

対応策として、
1,BigIntegerというものを使ってみる
2,なんか余りを求めるところをこまめに、うまいことやる
のどちらかかなぁと思ったのですが、前者は使ったことないし、そもそもそれで収まるんかも分からんし、後者はさっぱり思いつかないので、諦めかけました(というか、諦めた瞬間あたりでタイムアップでした)。

そこでふと、schemeはBigNumがどうの、みたいな話を思い出しました。
1000!を求めても、ちゃんと出力してくれる頼れるナイスガイです。
こんな感じ↓

ようこそ DrRacket, バージョン 6.0 [3m].
言語: R5RS; memory limit: 128 MB.
> (fact 1000)
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
>

よし、schemeで解こう、と思い、上のJavaと同じアルゴリズムで解いてみました。
そして、提出して少し直して、を繰り返して、3回目でAC。
書き始めてから10分くらい、と、Javaで書こうとしてかかった時間の半分以下で出来ました。
提出したコードはコチラ↓。

(define day (read))
(define big 1000000007)
 
(define (read-input-list n)
  (if (= n 0) '() (let* ((ele (read))) (cons ele (read-input-list (- n 1))))))
 
(define nikki (read-input-list day))
 
 
;list = how,max,min
(define (makelist numlist min count unknown list)
  (cond ((null? numlist) list)
        ((and (> (car numlist) 0) unknown)
         (makelist (cdr numlist) (car numlist) 0 #f (cons (cons count (cons (car numlist) (cons min '()))) list)))
        ((> (car numlist) 0) (makelist (cdr numlist) (car numlist) 0 unknown list))
        (#t (makelist (cdr numlist) min (+ count 1) #t list))))
 
;list = how,max,min
(define (howcount list)
  (let ((num (- (car (cdr list)) (car (cdr (cdr list)))))
        (len (car list)))
    (modulo (/ (pp (+ num len) len) (fact len)) big)))
 
(define (ppp kakeru count answer)
  (if (= count 0) answer
      (ppp (- kakeru 1) (- count 1) (* kakeru answer))))
(define (pp kakeru count) (ppp kakeru count 1))
 
(define (fact2 n answer)
  (if (= n 0) answer
      (fact2 (- n 1) (* n answer))))
(define (fact n) (fact2 n 1))
          
(define (answer list ans)
  (if (null? list) ans
      (answer (cdr list) (modulo (* ans (howcount (car list))) big))))
 
(display (answer (makelist nikki 0 0 #f '()) 1))
(newline)

後から見直す際にはやはりJavaより読みにくい気がしますね。

というわけで、schemeとJavaしか出来ず、そしてなんとなくschemeの方が好きな僕が、今まで苦しんできた「schemeで解くメリットってなんなんや」という問いに１つ答えが出ました。
おっきい数が出てくるとき。
です。

これからも、こういう場合があればサッとschemeを使います。
以上です。