結果
| 問題 |
No.21 平均の差
|
| コンテスト | |
| ユーザー |
 sansaqua
|
| 提出日時 | 2020-10-27 03:56:25 |
| 言語 | Common Lisp (sbcl 2.5.0) |
| 結果 |
AC
|
| 実行時間 | 14 ms / 5,000 ms |
| コード長 | 4,672 bytes |
| コンパイル時間 | 80 ms |
| コンパイル使用メモリ | 48,824 KB |
| 実行使用メモリ | 32,660 KB |
| 最終ジャッジ日時 | 2024-07-21 21:49:45 |
| 合計ジャッジ時間 | 669 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 10 |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 21 JUL 2024 09:49:44 PM): ; file: /home/judge/data/code/Main.lisp ; in: DEFUN MAIN ; (LOOP FOR ; SUM ACROSS SUMS ; FOR ; COUNT ACROSS COUNTS ; MAXIMIZE (/ SUM COUNT) INTO ...) ; --> LET LET LET LET SB-LOOP::WITH-MINIMAX-VALUE LET ; --> SB-LOOP::WITH-MINIMAX-VALUE LET TAGBODY ; --> SB-LOOP::LOOP-ACCUMULATE-MINIMAX-VALUE PROGN WHEN IF OR LET IF > IF ; ==> ; (> #:LOOP-MAXMIN-TEMP-10 MAX) ; ; note: unable to ; open-code FLOAT to RATIONAL comparison ; due to type uncertainty: ; The second argument is a (OR (INTEGER 0 0) SINGLE-FLOAT), not a RATIONAL. ; --> LET LET LET LET SB-LOOP::WITH-MINIMAX-VALUE LET ; --> SB-LOOP::WITH-MINIMAX-VALUE LET TAGBODY ; --> SB-LOOP::LOOP-ACCUMULATE-MINIMAX-VALUE PROGN WHEN IF OR LET IF < IF ; ==> ; (< #:LOOP-MAXMIN-TEMP-12 MIN) ; ; note: unable to ; open-code FLOAT to RATIONAL comparison ; due to type uncertainty: ; The second argument is a (OR (INTEGER 0 0) SINGLE-FLOAT), not a RATIONAL. ; --> LET LET LET LET SB-LOOP::WITH-MINIMAX-VALUE LET ; --> SB-LOOP::WITH-MINIMAX-VALUE LET TAGBODY ; --> SB-LOOP::LOOP-ACCUMULATE-MINIMAX-VALUE PROGN WHEN IF OR LET IF > IF ; ==> ; (> #:LOOP-MAXMIN-TEMP-10 MAX) ; ; note: forced to do GENERIC-> (cost 10) ; unable to do inline float comparison (cost 3) because: ; The second argument is a (OR (INTEGER 0 0) SINGLE-FLOAT), not a SINGLE-FLOAT. ; --> LET LET LET LET SB-LOOP::WITH-MINIMAX-VALUE LET ; --> SB-LOOP::WITH-MINIMAX-VALUE LET TAGBODY ; --> SB-LOOP::LOOP-ACCUMULATE-MINIMAX-VALUE PROGN WHEN IF OR LET IF < IF ; ==> ; (< #:LOOP-MAXMIN-TEMP-12 MIN) ; ; note: forced to do GENERIC-< (cost 10) ; unable to do inline float comparison (cost 3) because: ; The second argument is a (OR (INTEGER 0 0) SINGLE-FLOAT), not a SINGLE-FLOAT. ; (- MAX MIN 1.0e-6) ; ; note: forced to do GENERIC-- (cost 10) ; unable to do inline fixnum arithmetic (cost 2)
ソースコード
(in-package :cl-user)
(eval-when (:compile-toplevel :load-toplevel :execute)
(defparameter *opt*
#+swank '(optimize (speed 3) (safety 2))
#-swank '(optimize (speed 3) (safety 0) (debug 0)))
#+swank (ql:quickload '(:cl-debug-print :fiveam :cp/util) :silent t)
#+swank (use-package :cp/util :cl-user)
#-swank (set-dispatch-macro-character
#\# #\> (lambda (s c p) (declare (ignore c p)) `(values ,(read s nil nil t)))))
#+swank (set-dispatch-macro-character #\# #\> #'cl-debug-print:debug-print-reader)
(macrolet ((def (b)
`(progn (deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))
(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))))
(define-int-types (&rest bits) `(progn ,@(mapcar (lambda (b) `(def ,b)) bits))))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64))
(defconstant +mod+ 1000000007)
(defmacro dbg (&rest forms)
#+swank (if (= (length forms) 1)
`(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
`(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
#-swank (declare (ignore forms)))
(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
(let ((*read-default-float-format* 'double-float))
(prog1 (princ obj stream) (terpri stream))))
;; BEGIN_INSERTED_CONTENTS
(defpackage :cp/modify-macro
(:use :cl)
(:export #:minf #:maxf #:mulf #:divf #:iorf #:xorf #:andf))
(in-package :cp/modify-macro)
(macrolet ((def (name fname)
`(define-modify-macro ,name (new-value) ,fname)))
(def minf min)
(def maxf max)
(def mulf *)
(def divf /)
(def iorf logior)
(def xorf logxor)
(def andf logand))
;; BEGIN_USE_PACKAGE
(eval-when (:compile-toplevel :load-toplevel :execute)
(use-package :cp/modify-macro :cl-user))
(in-package :cl-user)
;;;
;;; Body
;;;
(defun main ()
(declare #.*opt*)
(let* ((n (read))
(k (read))
(nums (coerce (loop repeat n collect (float (read) 1f0))
'(simple-array single-float (*))))
(state (make-array n :element-type 'uint8 :initial-element 0))
(sums (make-array k :element-type 'single-float :initial-element 0f0))
(counts (make-array k :element-type 'uint8 :initial-element 0))
(achievement 0)
(res 0))
(declare (uint4 n k achievement))
(labels ((inc-count (i)
(incf (aref counts i))
(when (= 1 (aref counts i))
(incf achievement)))
(dec-count (i)
(decf (aref counts i))
(when (= 0 (aref counts i))
(decf achievement)))
(update! ()
(unless (find 0 counts)
(loop for sum across sums
for count across counts
maximize (/ sum count) into max
minimize (/ sum count) into min
do (maxf res (ceiling (- max min 1f-6))))))
(dfs (pos)
(when (>= (+ achievement (- n pos)) k)
(if (= pos n)
(update!)
(dotimes (i (min k (+ pos 1)))
(setf (aref state pos) i)
(incf (aref sums i) (aref nums pos))
(inc-count i)
(dfs (+ pos 1))
(decf (aref sums i) (aref nums pos))
(dec-count i))))))
(dfs 0)
(println res))))
#-swank (main)
;;;
;;; Test and benchmark
;;;
#+swank
(progn
(defparameter *lisp-file-pathname* (uiop:current-lisp-file-pathname))
(setq *default-pathname-defaults* (uiop:pathname-directory-pathname *lisp-file-pathname*))
(defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *lisp-file-pathname*))
(defparameter *problem-url* "https://yukicoder.me/problems/no/21"))
#+swank
(defun gen-dat ()
(uiop:with-output-file (out *dat-pathname* :if-exists :supersede)
(format out "9 9~%")
(dotimes (_ 9)
(println (+ 1 (random 1000)) out))))
#+swank
(defun bench (&optional (out (make-broadcast-stream)))
(time (run *dat-pathname* out)))
#-swank
(eval-when (:compile-toplevel)
(when (or (> sb-c::*compiler-warning-count* 0)
sb-c::*undefined-warnings*)
(error "count: ~D, undefined warnings: ~A"
sb-c::*compiler-warning-count*
sb-c::*undefined-warnings*)))
;; To run: (5am:run! :sample)
#+swank
(5am:test :sample
(5am:is
(equal "535
"
(run "5
3
555
20
432
301
21
" nil)))
(5am:is
(equal "651
"
(run "8
4
329
980
656
738
739
542
873
501
" nil))))