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

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

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

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

追記の追記：

@no_maddojjjjjj 確かにモナドにはなるんですが、それよりもF#のパイプライン演算子を意識して書きました。OCamlにも4.01.0からPervasivesに入ったのでお勧めです。
— ろんだ (@fetburner) 2013, 12月 13

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

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

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

追記：

@no_maddojjjjjj それ do 言うてたら F#者に刺されるで
— 星のキャミバ様 (@camloeba) 2013, 12月 13

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

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

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

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

問題文

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

高橋くんのレートが C の時に、レート R の競技プログラマーの講座動画を見ると、高橋くんのレートは (C+R)⁄2 に変化します。
高橋くんは、講座動画を合計で K 個まで好きな順番で見ることができますが、同じ競技プログラマーの講座動画は一度までしか見ることができません。
講座動画を配信している N 人のレートが与えられた時、高橋くんが講座動画を見ることによって達成できるレートの最大値を求めるプログラムを書いてください。
ただし、高橋くんの初期レートは 0 です。
入力
入力は以下の形式で標準入力から与えられる。
N K
R1 R2 ... RN
1 行目には、講座動画の数を表す整数 N (1≦N≦100) と高橋くんが見ることのできる動画の数を表す整数 K (1≦K≦N) がスペース区切りで与えられる。

2 行目には、講座動画を配信している競技プログラマーのレートを表す整数 Ri (1≦Ri≦4,000) がスペース区切りで与えられる。

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

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

Submission #123064 - AtCoder Beginner Contest #003 | AtCoder

Submission #123064

ソースコード

let rec parse str =

let ls =ref [] in

let pool =ref in

let len =String.length str in

for i =0 to len -1do

if str.[ i ]=' '

then begin

ls :=(String.concat ""!pool) :: !ls;

pool :=

end

else begin

let s =Char.escaped str.[ i ]in

pool :=!pool @[ s ]

end

done;

(String.concat "" !pool) :: !ls

let take n list =

let rec take' n list =

if n = 0 then

else match list with

| -> failwith "take"

| h :: t -> h :: take' (n-1) t

in take' n list

let rec drop n list =

if n = 0 then list

else drop (n-1) (List.tl list)

let max i j =

if i > j then i else j

let rec get_score list ori n c cnt =

if n = 0

then c

else

match list with

| h :: ->

let ori = take cnt ori in

get_score ori ori (n-1) ( (c +. h) /. 2.) 0

| h :: t ->

let new_ori = (take cnt ori) @ (drop (cnt+1) ori) in

max

(get_score new_ori new_ori (n-1) ( (c +. h) /. 2.) 0)

(get_score t ori n c (cnt+1))

| _ -> failwith ""

let main () =

let (n,k) = Scanf.scanf "%d %d" (fun i j -> (i,j)) in

let rate_str = read_line () in

let rate_list = List.map float_of_string (parse rate_str) in

let score = get_score rate_list rate_list k 0.0 0 in

print_float score;

print_endline ""

let _ = main ()

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

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

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

f:id:no_maddojp:20131213075625j:plain

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

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

Submission #122467 - AtCoder Beginner Contest #003 | AtCoder

Submission #122467

ソースコード

let id x = x

let (|>) x f = f x

let (n, k)=Scanf.scanf "%d %d\n"(fun n k ->(n, k))

let repeat f =

    let rec loop acc =function

    |0->List.rev acc

    | n -> loop (f ():: acc)(n -1) in

    loop

let r = repeat (fun ()->Scanf.scanf "%d " id) n

let rec take n =function

    | ->

    | hd :: tl ->

    if n =0then

    else hd :: take (n -1) tl

let ()=

    r

      |>List.sort compare

        |>List.rev

      |> take k

      |>List.rev

      |>List.map float_of_int

      |>List.fold_left (fun c r ->(c +. r)/.2.)0.

      |>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

ソースコード

let id x = x
let repeat f =
let rec loop acc =function
| 0->List.rev acc
| n -> loop (f ():: acc)(n -1) in
loop
let take n list =
let rec take' n list =
if n = 0 then
else match list with
| -> failwith "take"
| h :: t -> h :: take'(n-1) t
in take' n list
let rec drop n list =
if n = 0 then list
else drop (n-1) (List.tl list)
let main () =
let (n,k) = Scanf.scanf "%d %d\n" (fun i j -> (i, j)) in
let rate_list = repeat (fun () -> Scanf.scanf "%d " id) n in
let rate_list = List.map float_of_int rate_list in
let sorted = List.fast_sort (fun i j -> int_of_float (i -. j)) rate_list in
let ans_list = drop (n-k) sorted in
let score = List.fold_left (fun c x -> (c +. x) /. 2.) 0. ans_list in
Printf.printf "%f\n" score
let _ = main ()

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

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

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

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

type t (* void *)

ソフトウエアのこととか

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

問題文

入力

Submission #123064

ソースコード

Submission #122467

ソースコード

ソースコード