racketにハマって以降、AtCoder競プロ典型 90 問を簡単なものからracketで解いてます。
atcoder.jp
ちなみにracketにハマったときの記事はこちら。
frfrfrfr.hatenablog.com
racketのモジュール使って簡単に書けました!みたいなのがあるといいなぁと思いながらも、標準出力や2次元配列すら書きにくいracket・・・
解き方を考え、思いついたら「racket + 使うアルゴリズム」とかで調べていると、この12問目で解答に使う"Union-Find木"については
(require data/union-find)
で簡単に使えることがわかりました!
今回はその使い方について書いていきます。
そもそもUnion-Find木について
ざっくり言うと、各要素それぞれがいろんなグループに所属しているようなデータ構造です。要素1、2はグループ1、要素3〜6はグループ2、のように。また、各要素は1つのグループにしか所属していません(初期は、各要素は自分のみが所属しているグループに所属している、という状態)。
そしてこのデータ構造では、要素がN個あるとき、
・要素aが所属しているグループと要素bが所属しているグループを併合する(同じグループとする)
・要素aが所属しているグループと要素bが所属しているグループが同じかどうかを判定する
がどちらも O(log n)で計算できる、というものです。合ってます?
モジュール"data/union-find"について
ドキュメントはこちら。
docs.racket-lang.org
使い方はこんな感じですね(Dr.Racketの対話モードで確認)。
> (require data/union-find) > (define a (uf-new 'uf1)) > (define b (uf-new 'uf2)) > (uf-find a) 'uf1 > (uf-find b) 'uf2 > (uf-same-set? a b) #f > (uf-union! a b) > (uf-same-set? a b) #t > (uf-find a) 'uf1 > (uf-find b) 'uf1
こんな感じで、uf-new + 引数 で、その引数を代表要素とするsetが生まれ、uf-union!が合併したらその両方の代表要素のうちどちらかが合併後の代表要素として使われる、という仕組みです。
ただ、これだとa、bみたいにいちいち名前つけないかんのか、どうしよ・・・
と困っていたのですが、配列に入れると名前を付けなくともうまく管理できそうです。
> (define UFvector (make-vector 2 0)) > (display UFvector) #(0 0) > (vector-set! UFvector 0 (uf-new 0)) > (vector-set! UFvector 1 (uf-new 1)) > (display UFvector) #(#<uf-set: 0> #<uf-set: 1>) > (uf-find (vector-ref UFvector 0)) 0 > (uf-find (vector-ref UFvector 1)) 1 > (uf-union! (vector-ref UFvector 0) (vector-ref UFvector 1)) > (uf-find (vector-ref UFvector 0)) 0 > (uf-find (vector-ref UFvector 1)) 0
というわけで、この問題を解いたコードを書いて終わりにします。
https://atcoder.jp/contests/typical90/tasks/typical90_l
query1という関数の行数が結構多くなってしまったのですが、ゼロから書く記述量でいくと結構少なめになったと思います。
#lang racket (require data/union-find) (define (break) (display "")) (define H (read)) (define W (read)) (define Q (read)) (define UFtree (make-vector (* H W) 0)) ;i行j列は(i-1)*W+(j-1)に格納 (define (index-ref i j) (+ (* (- i 1) W) (- j 1))) (define (query1) (let* ((r (read)) (c (read)) (index (index-ref r c))) (if (number? (vector-ref UFtree index)) (let ((above (index-ref (- r 1) c)) (below (index-ref (+ r 1) c)) (left (index-ref r (- c 1))) (right (index-ref r (+ c 1)))) (begin (vector-set! UFtree index (uf-new index)) (if (and (<= 0 above (- (* H W) 1)) (uf-set? (vector-ref UFtree above))) (uf-union! (vector-ref UFtree index) (vector-ref UFtree above)) (break)) (if (and (<= 0 below (- (* H W) 1)) (uf-set? (vector-ref UFtree below))) (uf-union! (vector-ref UFtree index) (vector-ref UFtree below)) (break)) (if (and (< 1 c) (uf-set? (vector-ref UFtree left))) (uf-union! (vector-ref UFtree index) (vector-ref UFtree left)) (break)) (if (and (< c W) (uf-set? (vector-ref UFtree right))) (uf-union! (vector-ref UFtree index) (vector-ref UFtree right)) (break)))) (break)))) (define (query2) (let* ((r1 (read)) (c1 (read)) (r2 (read)) (c2 (read)) (index1 (index-ref r1 c1)) (index2 (index-ref r2 c2))) (begin (let ((uf1 (vector-ref UFtree index1)) (uf2 (vector-ref UFtree index2))) (display (if (and (uf-set? uf1) (uf-set? uf2) (= (uf-find uf1) (uf-find uf2))) "Yes" "No")) (newline))))) (define (solve q) (define (sub i) (if (>= i q) (break) (let* ((querynum (read))) (begin (if (= querynum 1) (query1) (query2)) (sub (+ i 1)))))) (sub 0)) (solve Q)