プログラミングを上達させたい

プログラミングの勉強を始めた、情報学専攻の大学院生です。モチベーション維持のため、ブログに勉強したことを書いていきます。→就職。IT全然関係ない仕事をしています

schemeの配列(ベクトル)を使って問題を解く

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・・・

1つ目の提出で、間に合った中で一番時間かかったサンプル(AtCoderはTLEとなったサンプルにどれくらい時間がかかったか分からないので)が1450msだったのに対して、2つ目の提出ではそれが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が一応書けるには書けるので、格好良さをとるか、便利さをとるか、ということになりますね。
でも、1人だけ皆と違う言語を使って、しかも上位ってのはやはり格好良いですよね。
これに関してはもう少し迷おうと思います。

では、今回は以上です。

広告を非表示にする