Schemeの環境構築(vim)＆Gaucheのツリーマップを使った

AtCoderProblemsのBoot camp for BeginnersをSchemeで解いていっています。
多種多様な問題があるし、解き進めているのが可視化されてモチベーションも上がるし。このサイトよすぎませんか？少し自分の税金が投入されても全然いいくらいです。

さて、その中で「数の探索、追加、削除をO(log_n)で行いたい」という問題がありました。こちらです。
atcoder.jp
そういう問題になるとJava〜といつもはしていたのですが、たまたまGaucheでTree-mapというデータ構造があるのを見つけました。
ツリーマップ (Gauche ユーザリファレンス)
これがあればできるじゃん、ということでコーディングしようとしたのですが、僕が使っているDrRacketという開発環境では、Gaucheが使えなさそうで・・・
※AtCoderのScheme処理系はGauche

また、最近自分のvim操作の遅さで仕事でも少しうまくいかなかったこともあり、
・vimでScheme(@Gauche)を書けるように
・数の探索、追加、削除をO(log_n)で行うようなコードを作成
してみることにしました。

vim環境の構築

色んなサイトを見て、追加したり削除したりして、 ~/.vimrc は最終的にこうなりました。

filetype plugin indent on
set autoindent
set smartindent
autocmd FileType scheme setlocal autoindent
autocmd FileType scheme inoremap <buffer> <Tab> <C-o>==
syntax enable

こうすると、自動インデントも不満なく＆予約語の色も変わり＆対応するカッコもわかりやすいです。

ツリーのやつ

GaucheのTree-mapをうまく使って、
・数の追加がO(log_n)
・数の削除がO(log_n)
・数の有無の検索がO(log_n)
・最大値、最小値の検索がO(log_n)
でできるデータ構造を作ります。
Tree-mapはkey-valueをkey使って色々便利にできるものです。よって、
key->数
value->key(=数)の個数
として、1個以上あるものは数-個数が、ないものは数-0としてでなくそもそも保持しない、という形のデータ構造を作ります。

;treemapのkey-valueをvalue-countだと思って制御する
(define (tree-add! tr value)
  (if (tree-map-exists? tr value)
      (let ((count (tree-map-get tr value)))
        (tree-map-put! tr value (+ count 1)))
      (tree-map-put! tr value 1)))
;delete対象はtreeにある前提
(define (tree-delete! tr value)
  (let ((count (tree-map-get tr value)))
    (if (= count 1)
        (tree-map-delete! tr value)
        (tree-map-put! tr value (- count 1)))))
 
(define (tree-max tr)
  (car (tree-map-max tr)))
(define (tree-min tr)
  (car (tree-map-min tr)))
(define (tree-clear! tr) (tree-map-clear! tr))

できました。そして、これを使ってアルゴリズムを書き提出→無事ACでした。全体はこんな感じに。

;treemapのkey-valueをvalue-countだと思って制御する
(define (tree-add! tr value)
  (if (tree-map-exists? tr value)
      (let ((count (tree-map-get tr value)))
        (tree-map-put! tr value (+ count 1)))
      (tree-map-put! tr value 1)))
;delete対象はtreeにある前提
(define (tree-delete! tr value)
  (let ((count (tree-map-get tr value)))
    (if (= count 1)
        (tree-map-delete! tr value)
        (tree-map-put! tr value (- count 1)))))
 
(define (tree-max tr)
  (car (tree-map-max tr)))
(define (tree-min tr)
  (car (tree-map-min tr)))
(define (tree-clear! tr) (tree-map-clear! tr))
 
(define N (read))
(define M (read))
(define Tree (make-tree-map))
(define (read-as-treeN n)
  (if (= n 0) "input-OK "
      (let ((ele (read)))
        (begin
          (tree-add! Tree ele)
          (read-as-treeN (- n 1))))))
(read-as-treeN N)
 
(define (tree-sum)
  (define (sub sum)
    (if (tree-map-empty? Tree) sum
        (let ((maxval (tree-max Tree)))
          (begin
            (tree-delete! Tree maxval)
            (sub (+ sum maxval))))))
  (sub 0))
 
(define (waribiki! counter)
  (if (= counter 0) 0
      (let ((maxval (tree-max Tree)))
        (begin
          (tree-delete! Tree maxval)
          (tree-add! Tree (quotient maxval 2))
          (waribiki! (- counter 1))))))
 
(waribiki! M)
(display (tree-sum))
(newline)

これでGauche特有の関数なども使えるようになった。せっかく買ったこれを読み進めていきたいところ。

頑張る国、ガンバルディア