読者です 読者をやめる 読者になる 読者になる

type t (* void *)

関数型言語や英語学習の事とか。

OCaml: Atcoderで自分のコードを悔い改めた

えー、12/12の9時からAtcoder beginner contest #003が開催されました。

自分はそれにちょっと色々あって出遅れる形で参加したのですが、C問題をやってるときに色々詰まって終わった後に他の人の回答を見たら素晴らしく読みやすくて反省する次第でありました。そのことを書いてみたいと思います。

-------------------------------------------------------------------------------------

追記の追記:

書かれた方僕がフォローしている方でした、気付かずすいません。

パイプライン演算子というものがあるのですね。

-------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------

追記:

 do記法については理解せずに書いている部分があります。

さらっと流してもらえると助かります。。。

-------------------------------------------------------------------------------------

 

 

そう、問題はC問題なのです。C問題、僕は時間内に正解出来なかったのです。

問題文

AtCoder社では、優秀な競技プログラマーの講座動画を N 個配信しています。
初心者競技プログラマーの高橋くんは、AtCoder社が配信している動画を見て修練しようとしています。
高橋くんの実力はレートという実数値で表され、レートが高いほど実力が高いことを表します。

高橋くんのレートが C の時に、レート R の競技プログラマーの講座動画を見ると、高橋くんのレートは (C+R)⁄2 に変化します。
高橋くんは、講座動画を合計で K 個まで好きな順番で見ることができますが、同じ競技プログラマーの講座動画は一度までしか見ることができません。
講座動画を配信している N 人のレートが与えられた時、高橋くんが講座動画を見ることによって達成できるレートの最大値を求めるプログラムを書いてください。
ただし、高橋くんの初期レートは 0 です。

入力

入力は以下の形式で標準入力から与えられる。
N K
R1 R2 ... RN
  1. 1 行目には、講座動画の数を表す整数 N (1≦N≦100) と高橋くんが見ることのできる動画の数を表す整数 K (1≦KN) がスペース区切りで与えられる。
  2. 2 行目には、講座動画を配信している競技プログラマーのレートを表す整数 Ri (1≦Ri≦4,000) がスペース区切りで与えられる。

C: AtCoderプログラミング講座 - AtCoder Beginner Contest #003 | AtCoder

 

僕のクソみたいな回答を見てみましょう。

Submission #123064 - AtCoder Beginner Contest #003 | AtCoder

Submission #123064

ソースコード

  1. let rec parse str =
  2.     let ls =ref [in
  3.     let pool =ref  in
  4.     let len =String.length str in
  5.     for i =0 to len -1do
  6.     if str.[ ]=' '
  7.     then begin
  8.         ls :=(String.concat ""!pool:: !ls;
  9.         pool := 
  10.     end
  11.     else begin
  12.         let s =Char.escaped str.[ ]in
  13.         pool :=!pool @]
  14.   end
  15.   done;
  16.   (String.concat "" !pool:: !ls
  17.  
  18. let take n list =
  19.     let rec take' n list =
  20.     if n = 0 then
  21.     else match list with
  22.       | -> failwith "take"
  23.       | h :: t -> h :: take' (n-1) t
  24.     in take' n list
  25.  
  26. let rec drop n list =
  27.     if n = 0 then list
  28.     else drop (n-1) (List.tl list)
  29.  
  30. let max i j =
  31.     if i > j then i else j
  32.  
  33. let rec get_score list ori n c cnt =
  34.     if n = 0
  35.     then c
  36.     else
  37.     match list with
  38.     | h :: ->
  39.         let ori = take cnt ori in
  40.         get_score ori ori (n-1) ( (c +. h) /. 2.) 0
  41.     | h :: t ->
  42.         let new_ori = (take cnt ori) @ (drop (cnt+1) ori) in
  43.         max
  44.             (get_score new_ori new_ori (n-1) (  (c +. h) /. 2.) 0)
  45.             (get_score t ori n c (cnt+1))
  46.       | _ -> failwith ""
  47. let main () =
  48.     let (n,k) = Scanf.scanf "%d %d" (fun i j -> (i,j)) in
  49.     let rate_str = read_line () in
  50.     let rate_list = List.map float_of_string (parse rate_str) in
  51.     let score = get_score rate_list rate_list k 0.0 0 in
  52.     print_float score;
  53.     print_endline ""
  54.  
  55. let _ = main ()

これ、通ってないんですよね。ランタイムエラーで弾かれてる。

それ以外にも色々ダメな部分があります。列挙してみると、

  • ランタイムエラーで弾かれてる。原因は読み込みの部分。
  • でもって、それに気づかなかった。なぜなら普通に./a.outを呼び出して手で標準入力にデータを入力してたら動いたから。cat problem | ./a.out みたいにテストしてたら絶対に気づいた。
  • 回答を導くアルゴリズムがクソ。簡単にどういうふうに選べばいいのかわかるのにわざわざ全通り試して最も良い回答を選んでる。リソースの無駄。後述するがfoldの形で結果が計算できることに気づいてない。
  • OCamlでsplitを使おうと思ったのだけど、標準ライブラリではないStrモジュールの中に含まれており使えなかったから自分でスペースで区切られた文字列をパースするための関数を書いてる。クソ。もっと良い方法があったし内部の性能がだいぶ悪い。

f:id:no_maddojp:20131213075625j:plain

 

B問題までは25分で解いてる。あと1時間半使っても出来なかったわけですか…。

 

コンテストが終わった後に他の人の回答を見てみました。OCamlで回答してる人は僕の他にもう一人しかいなかったのですが、それを見て愕然としました。

Submission #122467 - AtCoder Beginner Contest #003 | AtCoder

Submission #122467

ソースコード

  1. let id x = x
  2. let (|>) x f = f x
  3. let (n, k)=Scanf.scanf "%d %d\n"(fun n k ->(n, k))
  4.  
  5. let repeat f =
  6.     let rec loop acc =function
  7.     |0->List.rev acc
  8.     | n -> loop (f ():: acc)(n -1in
  9.       loop
  10.  
  11. let r = repeat (fun ()->Scanf.scanf "%d " id) n
  12.  
  13. let rec take n =function
  14.     ->
  15.     | hd :: tl ->
  16.       if n =0then
  17.       else hd :: take (n -1) tl
  18.  
  19. let ()=
  20.     r
  21.         |>List.sort compare
  22.         |>List.rev
  23.         |> take k
  24.         |>List.rev
  25.         |>List.map float_of_int
  26.         |>List.fold_left (fun c r ->(c +. r)/.2.)0.
  27.         |>Printf.printf "%f\n"

 まず綺麗で読みやすいなぁと思ったのが最初の印象。で、中身を見てみると非情に分かりやすい。パーサーなんて書いてない、普通にScanfを繰り返し用いて入力からデータを取得してる。

で、最後のlet ()以下が読みやすい。そういえばReal World OCamlにもこういうふうに書かれてたコードがあったような…。

ここで回答を求める手順がfoldであることに気づく。

自分のレートがCで、レートがRの人の動画を見ると(C + R) / 2にレートが変化するわけだから、

f:id:no_maddojp:20131213081204p:plain

みたいにどんどん変わっていくわけですよね、

これまんま畳み込みじゃないか!!!

 

私は大層反省しましたと。

コンテスト終了後、自分でこれを参考に書きなおしたもの。

Submission #123335 - AtCoder Beginner Contest #003 | AtCoder

Submission #123335

ソースコード

  1. let id x = x
  2.  
  3. let repeat f =
  4.     let rec loop acc =function
  5.         0->List.rev acc
  6.         | n -> loop (f ():: acc)(n -1in
  7.         loop
  8.  
  9. let take n list =
  10.     let rec take' n list =
  11.     if n = 0 then
  12.     else match list with
  13.     | -> failwith "take"
  14.     | h :: t -> h :: take'(n-1) t
  15.     in take' n list
  16.  
  17. let rec drop n list =
  18.     if n = 0 then list
  19.     else drop (n-1) (List.tl list)
  20.  
  21. let main () =
  22.     let (n,k) = Scanf.scanf "%d %d\n" (fun i j -> (i, j)) in
  23.     let rate_list = repeat (fun () -> Scanf.scanf "%d " id) n in
  24.     let rate_list = List.map float_of_int rate_list in
  25.     let sorted = List.fast_sort (fun i j -> int_of_float (i -. j)) rate_list in
  26.     let ans_list = drop (n-k) sorted in
  27.     let score = List.fold_left (fun c x -> (c +. x) /. 2.) 0. ans_list in
  28.     Printf.printf "%f\n" score
  29.  
  30. let _ = main ()

 

自分的には十分これで読みやすくなったと思う。

微妙にShadowingしてるのと名前の付け方が怪しいけども。

でもなぁ、うーん。なにしてるかは圧倒的に上の回答者の方のほうが分かりやすいよなぁ…。

慣れていくしか無いのでしょう。つらぽよ…。