結果

問題 No.265 数学のテスト
ユーザー trigotttrigott
提出日時 2015-08-08 07:03:50
言語 OCaml
(5.1.0)
結果
AC  
実行時間 159 ms / 2,000 ms
コード長 5,226 bytes
コンパイル時間 502 ms
コンパイル使用メモリ 22,912 KB
実行使用メモリ 30,752 KB
最終ジャッジ日時 2024-10-08 23:36:24
合計ジャッジ時間 2,305 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 159 ms
30,752 KB
testcase_01 AC 138 ms
19,836 KB
testcase_02 AC 50 ms
6,656 KB
testcase_03 AC 35 ms
6,272 KB
testcase_04 AC 36 ms
6,144 KB
testcase_05 AC 41 ms
6,272 KB
testcase_06 AC 35 ms
6,272 KB
testcase_07 AC 40 ms
6,272 KB
testcase_08 AC 50 ms
6,528 KB
testcase_09 AC 32 ms
6,144 KB
testcase_10 AC 34 ms
6,144 KB
testcase_11 AC 39 ms
6,272 KB
testcase_12 AC 3 ms
5,248 KB
testcase_13 AC 14 ms
5,760 KB
testcase_14 AC 10 ms
5,632 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 7 ms
5,504 KB
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 2 ms
5,248 KB
testcase_19 AC 2 ms
5,248 KB
testcase_20 AC 3 ms
5,248 KB
testcase_21 AC 2 ms
5,248 KB
testcase_22 AC 12 ms
5,632 KB
testcase_23 AC 2 ms
5,248 KB
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 20 ms
5,888 KB
testcase_26 AC 2 ms
5,248 KB
testcase_27 AC 2 ms
5,248 KB
testcase_28 AC 5 ms
5,632 KB
testcase_29 AC 2 ms
5,248 KB
testcase_30 AC 5 ms
5,376 KB
testcase_31 AC 2 ms
5,248 KB
testcase_32 AC 2 ms
5,248 KB
testcase_33 AC 2 ms
5,248 KB
testcase_34 AC 2 ms
5,248 KB
testcase_35 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
File "Main.ml", line 199, characters 6-7:
199 |   let n = read_int () in
            ^
Warning 26 [unused-var]: unused variable n.

ソースコード

diff # 

(* mParser *)

type state = { buf: string; idx: int }

type 'a reply =
  | Failed
  | Ok of 'a * state

type 'a t = state -> 'a reply

let parse_string p str = p { buf = str; idx = 0 }

let return x s = Ok (x, s)

let zero _ = Failed

let bind p f s =
  match p s with
  | Failed      -> Failed
  | Ok (r1, s1) -> f r1 s1

let (>>=) = bind

let (<|>) p1 p2 s =
  match p1 s with
  | Failed -> p2 s
  | other  -> other

let choice ps = List.fold_left (<|>) zero ps

(* many parses zero or more occurences of p *)
let rec many p s =
  match p s with
  | Failed -> Ok ([], s)
  | Ok (r, s') ->
    begin
      match many p s' with
      | Failed -> Failed
      | Ok (rs, s'') -> Ok (r :: rs, s'')
    end

let sep_by1 p sep =
  p >>= fun x ->
  many (sep >>= fun _ -> p >>= fun x -> return x) >>= fun xs ->
  return (x :: xs)

let (<|>$) p x = p <|> return x

let opt x p = p <|>$ x

let regexp rx s =
  if Str.string_match rx s.buf s.idx
  then
    let matched = Str.matched_string s.buf in
    Ok (matched, { s with idx = s.idx + String.length matched })
  else
    Failed

let spaces = regexp (Str.regexp " *")

let string str = regexp (Str.regexp str)
let symbol str = string str >>= fun s -> spaces >>= fun _ -> return s

let integer =
  regexp (Str.regexp "[1-9][0-9]*") >>= fun i ->
  return (int_of_string i)

type assoc =
  | Assoc_none
  | Assoc_left
  | Assoc_right

type 'a operator =
  | Infix   of ('a -> 'a -> 'a) t * assoc
  | Prefix  of ('a -> 'a) t
  | Postfix of ('a -> 'a) t

let expression operators term =

  let make_parser term ops =

    let split_op (rassoc, lassoc, nassoc, prefix, postfix) op =
      match op with
      | Infix (p, assoc) ->
        ( match assoc with
          | Assoc_none  -> (rassoc, lassoc, p :: nassoc, prefix, postfix)
          | Assoc_left  -> (rassoc, p :: lassoc, nassoc, prefix, postfix)
          | Assoc_right -> (p :: rassoc, lassoc, nassoc, prefix, postfix) )
      | Prefix p ->
        (rassoc, lassoc, nassoc, p :: prefix, postfix)
      | Postfix p ->
        (rassoc, lassoc, nassoc, prefix, p :: postfix) in

    let (rassoc, lassoc, nassoc, prefix, postfix) =
      List.fold_left split_op ([], [], [], [], []) ops in

    let rassoc_op  = choice rassoc
    and lassoc_op  = choice lassoc
    and nassoc_op  = choice nassoc
    and prefix_op  = choice prefix
    and postfix_op = choice postfix in

    let prefix_p  = opt (fun x -> x) prefix_op
    and postfix_p = opt (fun x -> x) postfix_op in

    let term_p =
      prefix_p  >>= fun pre ->
      term      >>= fun x ->
      postfix_p >>= fun post ->
      return (post (pre x)) in

    let rec rassoc_p x =
      rassoc_op                           >>= fun f ->
      (term_p >>= (fun z -> rassoc_p' z)) >>= fun y ->
      return (f x y)
    and rassoc_p' x = opt x (rassoc_p x) in

    let rec lassoc_p x =
      lassoc_op >>= fun f ->
      term_p    >>= fun y ->
      lassoc_p' (f x y)
    and lassoc_p' x = opt x (lassoc_p x) in

    let nassoc_p x =
      nassoc_op >>= fun f ->
      term_p    >>= fun y ->
      return (f x y)
    in

    term_p >>= fun x -> (rassoc_p x <|> lassoc_p x <|> nassoc_p x <|>$ x)

  in List.fold_left make_parser term operators

(* ------------------------------------ mParser ------------------------------------ *)

type expr =
  | Var
  | Add of expr * expr
  | Mul of expr * expr
  | Const of int
  | Deriv of expr

let add x y = Add (x, y)
let mul x y = Mul (x, y)

let operators =
  [ [ Infix (symbol "*" >>= (fun _ -> return mul), Assoc_left) ]
  ; [ Infix (symbol "+" >>= (fun _ -> return add), Assoc_left) ]
  ]

let deriv p =
  string "d{" >>= fun _ ->
  p           >>= fun x ->
  string "}"  >>= fun _ ->
  return (Deriv x)

let const s = (integer >>= fun x -> return (Const x)) s

let var s = (string "x" >>= fun _ -> return Var) s

let rec term s = ((deriv expr <|> const <|> var) >>= fun x -> return x) s
and expr s = expression operators term s

type poly = (int * int) list

let rec add_poly p1 p2 =
  match p1, p2 with
  | [], _ -> p2
  | _, [] -> p1
  | (d1, c1) :: p1', (d2, c2) :: p2' ->
    if d1 = d2
    then (d1, c1 + c2) :: add_poly p1' p2'
    else if d1 > d2
    then (d2, c2) :: add_poly p1 p2'
    else (d1, c1) :: add_poly p1' p2

let mul_mono_with_mono (d1, c1) (d2, c2) = (d1 + d2, c1 * c2)
let mul_poly_with_mono p m = List.map (mul_mono_with_mono m) p
let rec mul_poly p1 p2 =
  match p1 with
  | [] -> []
  | m :: rest -> add_poly (mul_poly_with_mono p2 m) (mul_poly p2 rest)

let rec normalize = function
  | Var -> [(1, 1)]
  | Add (d1, d2) -> add_poly (normalize d1) (normalize d2)
  | Mul (d1, d2) -> mul_poly (normalize d1) (normalize d2)
  | Const x -> [(0, x)]
  | Deriv d -> derivate (normalize d)
    
and derivate = function
  | [] -> []
  | p ->
    List.map (fun (deg, coeff) -> (deg - 1, coeff * deg)) p
    |> List.filter (fun (d, _) -> d >= 0)

let _ =
  let n = read_int () in
  let depth = read_int () in
  let s = read_line () in
  match parse_string expr s with
  | Failed -> failwith "parse error"
  | Ok (res, _) ->
    let d = normalize res in
    for i = 0 to depth do
      try
        Printf.printf "%d " (List.assoc i d)
      with
        Not_found -> Printf.printf "0 "
    done;
    print_endline ""
0