結果
問題 |
No.633 バスの運賃
|
ユーザー |
![]() |
提出日時 | 2025-08-13 00:43:43 |
言語 | Scheme (Gauche-0.9.15) |
結果 |
AC
|
実行時間 | 120 ms / 2,000 ms |
コード長 | 8,082 bytes |
コンパイル時間 | 69 ms |
コンパイル使用メモリ | 7,588 KB |
実行使用メモリ | 24,576 KB |
最終ジャッジ日時 | 2025-08-13 00:43:51 |
合計ジャッジ時間 | 2,316 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 9 |
ソースコード
(use srfi.13) ; string (use srfi.42) ; list-ec (use srfi.197) ; chain (use scheme.list) (use scheme.vector) (use data.queue) (use gauche.dictionary) (use gauche.generator) (use gauche.sequence) (use util.match) (define input read-line) (define (read-words) (string-split (input) " ")) (define (ii) (string->number (input))) (define (li) (map string->number (read-words))) (define-method prn* ((coll <collection>)) (for-each-with-index (^(i x) (when (> i 0) (display " ")) (display x)) coll) (newline)) (define (prn . args) (prn* args)) (define (prn-yn b) (prn (if b "Yes" "No"))) (define-syntax ->/prn (syntax-rules () ((_ x fns ...) (-> x fns ... prn)))) (define-syntax let/g (syntax-rules () ((_ var body ...) (generate (lambda (var) body ...))))) (define-method reverse ((s <string>)) (string-reverse s)) (define-method reverse ((vs <vector>)) (rlet1 res (vector-copy vs) (vector-reverse! res))) (define ord char->integer) (define chr integer->char) (define int string->number) (define str x->string) (define-method min ((xs <collection>)) (fold min (~ xs 0) xs)) (define-method max ((xs <collection>)) (fold max (~ xs 0) xs)) (define (minmax . xs) (values->list (apply min&max xs))) (define-method minmax ((xs <collection>)) (values->list (apply min&max xs))) (define (sum xs) (fold + 0 xs)) (define (divmod a b) (values->list (div-and-mod a b))) (define (ceildiv a b) (div (+ a (1- b)) b)) (define (1+ n) (+ n 1)) (define (1- n) (- n 1)) (define (!= a b) (not (= a b))) (define (midpoint a b) (div (+ a b) 2)) (define pow (case-lambda ((a b) (expt a b)) ((a b m) (expt-mod a b m)))) (define sq square) (define isqrt exact-integer-sqrt) (define pos? positive?) (define neg? negative?) (define == equal?) (define (cmp< a b) (< (compare a b) 0)) (define (cmp> a b) (> (compare a b) 0)) (define (cmp= a b) (= (compare a b) 0)) (define ++ string-append) (define all every) (define any-ec any?-ec) (define all-ec every?-ec) (define concat concatenate) (define foldl fold-left) (define (pairwise xs) (zip xs (cdr xs))) (define (comb n k) (if (or (< k 0) (> k n)) 0 (let loop ((i 0) (x 1)) (if (= i k) x (loop (1+ i) (div (* x (- n i)) (1+ i))))))) (define-method frequencies ((xs <collection>)) (let1 ht (make-hash-table equal-comparator) (for-each (^x (hash-table-update! ht x 1+ 0)) xs) (new ht))) ;; '(a b c) -> op(op(op(init, a), b), c) (define (scanl op init xs) (define (f a b) (let1 t (op b a) (values t t))) (map-accum f init xs)) ;; '(a b c) -> op(a, op(b, op(c, init))) (define (scanr op init xs) (define (f a b) (let1 t (op a b) (values t t))) (reverse (map-accum f init (reverse xs)))) (define zip* (apply$ zip)) (define string* (apply$ string)) (define-macro (input! vars . body) (define (group xs) (if (null? xs) '() (let1 x (car xs) (cond ((keyword? x) ; (:i VAR) (assume (and (pair? (cdr xs)) (symbol? (cadr xs)))) (cons (list x (cadr xs)) (group (cddr xs)))) ((symbol? x) ; default :i (cons (list :i x) (group (cdr xs)))) ((pair? x) (cons (group x) (group (cdr xs)))) (else (error "parse error: " xs)))))) (define (gen-receive binds body) (let* ((ss (gensym)) (vars (map cadr binds)) (vals (map-with-index (^(i x) (ecase x ((:i) `(int (list-ref ,ss ,i))) ((:i-1) `(- (int (list-ref ,ss ,i)) 1)) ((:s) `(list-ref ,ss ,i)))) (map car binds)))) `(receive ,vars (let1 ,ss (read-words) (values ,@vals)) ,body))) (define (gen-receive-list kind var body) (let* ((val (ecase kind ((:i) `(map int (read-words))) ((:i-1) `(map (^x (- (int x) 1)) (read-words))) ((:s) `(read-words))))) `(receive (,var) (values ,val) ,body))) (define (gen-receive1 kind var body) (let* ((val (ecase kind ((:i) `(int (input))) ((:i-1) `(- (int (input)) 1)) ((:s) `(input))))) `(receive (,var) (values ,val) ,body))) (define (gen binds body) (if (null? binds) body (let1 bind (car binds) (if (keyword? (car bind)) ; (:i vAR) (gen-receive1 (car bind) (cadr bind) (gen (cdr binds) body)) (match-let1 (x . more) bind (if (null? more) (gen-receive-list (car x) (cadr x) (gen (cdr binds) body)) (gen-receive bind (gen (cdr binds) body)))))))) (let ((binds (group vars))) (gen binds `(begin ,@body)))) (define-macro (! self quoted-name . args) (let ((name (cadr quoted-name))) `(,name ,self ,@args))) (define-macro (d/ . args) (let ((ss (map (^x `(list (quote ,x) ,x)) args))) `(pprint (list ,@ss)))) (define mlet match-let) (define mlet* match-let*) (define mlet1 match-let1) (define-macro (mfn pat . body) (let ((args (gensym))) `(lambda ,args (mlet1 ,pat ,args ,@body)))) (define-macro (mfn1 pat . body) (let ((arg (gensym))) `(lambda (,arg) (mlet1 ,pat ,arg ,@body)))) (define-method len ((coll <collection>)) (size-of coll)) (define (digits n) (map digit->integer (str n))) (define (digits->int ds) (fold-left (^(a b) (+ (* 10 a) b)) 0 ds)) (define (-> x . fns) (call-with-values (^() (values x)) (apply compose (reverse fns)))) (define (rep n thunk) (list-ec (: _ n) (thunk))) (define (memoize fn) (let1 cache (make-hash-table 'equal?) (lambda args (if (hash-table-exists? cache args) (hash-table-get cache args) (rlet1 val (apply fn args) (hash-table-put! cache args val)))))) (define (accumulate xs) (list->vector (scan-left + 0 xs))) (define (accum xs) (let ((vs (accumulate xs))) (case-lambda ((l r) ; [l, r] (- (~ vs r) (if (> l 0) (~ vs (1- l)) 0))) ((r) ; [0, r] (~ vs r))))) (define (string->set s) (list->set eqv-comparator (string->list s))) (define (difference xs ys) (let ((excludes (list->set equal-comparator ys))) (filter (^x (not (set-contains? excludes x))) xs))) (define (uniq xs) (let1 ht (make-hash-table 'equal?) (for-each (^x (hash-table-put! ht x #t)) xs) (hash-table-keys ht))) (define-macro (define-interface class . clauses) (let ((self (gensym)) (kind (gensym)) (args (gensym))) (define (gen-clause kind spec) (let1 sym (string->symbol (keyword->string kind)) `((,sym) ,spec))) `(define-method new ((,self ,class)) (lambda (,kind . ,args) (apply (case ,kind ,@(map (^x (gen-clause (car x) (cadr x))) (slices clauses 2))) ,self ,args))))) (define-interface <hash-table> :get hash-table-get :put! hash-table-put! :update! hash-table-update! :push! hash-table-push! :keys hash-table-keys :values hash-table-values :items hash-table->alist :contains? hash-table-contains? :map hash-table-map) (define (make-dict) (new (make-hash-table equal-comparator))) (define (alist->dict alist) (new (alist->hash-table alist equal-comparator))) (input! (N) (let* ((A (rep (1- N) ii)) (stops (rep N li))) (->/prn (let loop ((a A) (stops stops) (p 0) (cost 0)) (if (null? a) cost (mlet1 (b c) (car stops) (let1 np (+ p c (- b)) (loop (cdr a) (cdr stops) np (+ cost (* np (car a)))))))))))