schemeは関数型言語なので、配列よりも、再帰的に定義されているリストの方が便利です。
そのため、基本的にschemeの本やら解説で、schemeだとこの問題はこんな風に、という例ではたいていリストが使われます。
しかし、リストは配列に比べ、値へのアクセスが遅いです。長さをnとするとO(n)ですね。配列ならO(1)です。（間違っていたらすみません）
その分、削除やら追加などは速いのですが。
よって、動的計画法みたいなのをするときは、リストではなく配列を使いたいところです。
もちろんschemeにも配列にあたるものとして、ベクトルというものが提供されています。
これまで、配列を使うべきな感じの問題は、なんとなくschemeではなくJavaで解いていました。
なんとなくというか、schemeでベクトルの使い方をよく理解していなかったので、避けてきました。
破壊的操作がどうとか、そういうのです。
しかし、とりあえずやってみようということで、今回はschemeのベクトルを使って何かしら問題を解いてみようと思いました。
今回題材にしたのは、AtCoder Beginner Contest 006 D問題です。
動的計画法を使えば解けそうですね。
さっそく実装してみました。
そしてできたコードがこちら。
(define nn (read)) ;読み込んだ数を格納するベクトルを生成 (define Vec (make-vector nn)) ;読み込んだ数をベクトルに入れていく関数 (define (vec-input! count len) (cond ((= count len) 0) (#t (let* ((new (read))) (vector-set! Vec count new) (vec-input! (+ count 1) len))))) (vec-input! 0 (vector-length Vec)) ;動的計画法のために使うベクトルを生成 (define DPvec (make-vector nn)) (vector-set! DPvec 0 1) ;VecとDPvecのcount番目を見ていって、targetよりVec[i]が小さいもののうち、 ;DPvec[i]が最大であるものを返す関数 (define (find-now-max count end target max) (if (= count end) max (if (and (< (vector-ref Vec count) target) (> (vector-ref DPvec count) max)) (find-now-max (+ count 1) end target (vector-ref DPvec count)) (find-now-max (+ count 1) end target max)))) ;DPvecのi番目に、上の関数で求めた値を入れる関数 (define (dp! i) (vector-set! DPvec i (+ (find-now-max 0 i (vector-ref Vec i) 0) 1)) 0) ;dp!を繰り返す関数 (define (dp n) (cond ((= n nn) 0) (#t (dp! n) (dp (+ n 1))))) ;動的計画法を実行 (dp 1) ;(display Vec) ;(display DPvec) ;DPvecの中の最大値を探す関数 (define (answer n max) (if (= n nn) max (if (> (vector-ref DPvec n) max) (answer (+ n 1) (vector-ref DPvec n)) (answer (+ n 1) max)))) ;answerで求まるのは、入力列内の最大増加部分列の長さなので、 ;それをnn(=vector-length Vec)から引けば答えになる。 (display (- nn (answer 0 0))) (newline)
コメントを多めに入れてみたので、特に説明は不要かと思います。
しかし、これで出してみてもTLE・・・。部分点の50点のみでした。
ここで、高橋直大さんの解説スライドを見て、より速い実装、というものをしてみました。
これも動的計画法って呼ぶんでしょうか？
書いてみたのはコチラ。
(define nn (read)) ;読み込んだ数を格納するベクトルを生成 (define Vec (make-vector nn)) ;読み込んだ数をベクトルに入れていく関数 (define (vec-input! count len) (cond ((= count len) 0) (#t (let* ((new (read))) (vector-set! Vec count new) (vec-input! (+ count 1) len))))) (vec-input! 0 nn) ;動的計画法?のために使うベクトルを生成 ;入力の最大が30000なので、それより大きい数で先頭以外埋める。 ;先頭は、解説スライドでは-infとなっていますが、ここでは0にしました ;また、二分探索での便宜上、長さをnn+2としています。 (define DPvec (make-vector (+ nn 2))) (vector-fill! DPvec 32767) (vector-set! DPvec 0 0) ;二分探索のようなもの ;Vecの要素でV[i-1]<target<V[i]となるような ;iを探す関数。Vecが昇順であることを前提としている。 ;また、Vec内にtargetと同じ数値がないことも前提としている。 (define (bi-search hidari migi Vec target) (if (= (- migi hidari) 1) migi (let ((middle (quotient (+ hidari migi) 2))) (if (< (vector-ref Vec middle) target) (bi-search middle migi Vec target) (bi-search hidari middle Vec target))))) ;AtCoderのスライドの最後で解説されている動作の ;一回分を行う関数。 (define (dp! nowlooking) (let* ((nowtarget (vector-ref Vec nowlooking)) (kouho (bi-search 0 (+ nn 1) DPvec nowtarget))) (cond ((< (vector-ref DPvec kouho) nowtarget) 0) (#t (vector-set! DPvec kouho nowtarget) 0)))) ;dp!を繰り返す関数。 (define (dp n) ; (display DPvec)(newline) (cond ((= n nn) 0) (#t (dp! n) (dp (+ n 1))))) ;動作を全部実行 (dp 0) ;DPvecの中で、初期値(先頭以外には32767を入れた)が ;書き換えられている部分のうち、最大の添え字を見つけ ;という関数を作るつもりだったが、bi-serchでOKですね ;最大の添え字に1を足し、それをnnから引いたものが答えです (define ans (+ (- nn (bi-search 0 (+ nn 1) DPvec 30001)) 1)) (display ans) (newline)
お、書けた！
手元で確認をして、提出！
も、またTLE・・・
１つ目の提出で、間に合った中で一番時間かかったサンプル（AtCoderはTLEとなったサンプルにどれくらい時間がかかったか分からないので）が1450msだったのに対して、２つ目の提出ではそれが274msになっていました。
ということは、大分速くなってはいるようなんですが・・・
そして、これをコンパイルするコードに書き直して、なんとかACとなりました。
コンパイルのやり方に関しては、この次の記事で。
いやぁ、時間がかなりかかりました。
関数型言語の書き方は好きなものの、やはりschemeだと遅い場合が多いので、どうしようかという感じですね。
他にAtCoderで使える関数型言語はOcamlとscalaでしょうか。あ、あとHaskell。
しかし、どれも使っている人がいるにはいるんですよね・・・
実際に、AtCoder Regular Contest 024で、提出した人の人数を数えてみると、scalaが4人、Ocamlが2人、Haskellは10人くらい？でschemeが僕のみ、なんですよね(2014/6/6現在)。
せっかくだから、マイナー言語でやる方が、なんというか格好良いですよね・・・
孤高の存在というか。
ちなみに、このARC024で現在提出がない言語は、bash、Visual Basic、pascalです。うーん。
bashとかどうなんでしょうか、コンパイルしてくれないですよね。たまに簡単な問題をbashでスマートに解いている人がいますが、大きくなるとどうなんでしょうか。
ということはVisual Basicかpascalか・・・
Javaが一応書けるには書けるので、格好良さをとるか、便利さをとるか、ということになりますね。
でも、１人だけ皆と違う言語を使って、しかも上位ってのはやはり格好良いですよね。
これに関してはもう少し迷おうと思います。
では、今回は以上です。
