ABC038をOCamlで解いてみました。

なんでOCaml?

fetburner.hatenablog.com

ここを見ていただければよくわかると思うのですが、OCamlは関数型言語でありながら副作用もimperativeスタイルも使える非常にバランスの取れた実践的な言語です。関数型の記述の簡明さと破壊的代入などの副作用をきちんとマネジできるパワーがとても良い具合に混ざっていてこの手のコンテストの言語としてはうってつけのように思います。

正直筆者がアホなのでStateモナドとかを駆使してHaskellで書くのとかきついわ、なんでワーシャルフロイド書くのにモナド引っ張りまわさないかんのとか、やっぱりこの手のコンテストは手に馴染む言語で書くのが一番だなという感じです。JavaのStreamは関数の部分適用が素直に書けなくてハゲろという気持ちになってOCamlに戻ることになりました。アイムホーム!

なんかAtCoderみてるとOCamlの参加者少なすぎる気がします。もっと流行れ!

問題と回答と解説

http://abc038.contest.atcoder.jp/data/abc/038/editorial.pdf

ここに乗ってます。

A問題

文字列が与えられる。末尾がTならYES, じゃないならNOを出力する。

これは流石にやるだけですね。scanfいらない気もします。

let solve str = match str with
    x when x.[String.length x - 1] = 'T' -> "YES"
  | _ -> "NO"
    
let () =
  let rec read () =
    try let ans = (Scanf.scanf "%s\n" solve) in
        Printf.printf "%s\n" ans;
        read ()
    with End_of_file ->
         ()
  in
  read ()
;;

B問題

2つの整数のタプル(H,W)が2つ与えられます。 H同士一緒かHとWが一緒かW同士一緒ならYES,じゃないならNO

与えられた条件をそのまま書きます。

let solve h1 w1 h2 w2 = h1 = h2 || h1 = w2 || w1 = h2 || w1 = w2
    
let () =
  let rec read () =
    try let ans = (Scanf.scanf "%d %d\n%d %d\n" solve) in
        Printf.printf "%s\n" (if ans then "YES" else "NO");
        read ()
    with End_of_file ->
         ()
  in
  read ()
;;

C問題

数列が与えられて単調増加な部分列のインデックスの組を答える問題。例えば[1, 1, 2, 3, 3, 4 ]だと[1, 2, 3]と[3, 4]が単調増加とみなされるほか[1]のように一つだけの要素も全て単調増加とみなされます。つまり、この場合 [1], [1], [2], [3], [3], [4], [1, 2], [1, 2, 3], [2, 3], [3, 4]が単調増加列とみなされ、答えは10です。最初私が書いたのはこんなコード。

let read_list_of_int () =
  let rec read_list_of_int_inner lst =
    try let ans = (Scanf.scanf "%d " (fun x->x)) in
        read_list_of_int_inner (ans::lst)
    with End_of_file ->
      List.rev lst
  in
  read_list_of_int_inner []
 
let rec solve_a_line hd line res = match line with
    [] -> res
  | h::r -> if h > hd then solve_a_line h r (res+1) else res
                         
let rec solve = function
    [] -> 0
  | hd::rest -> (solve_a_line hd rest 1) + solve rest
    
let () =
  let _ = read_int() in
  let list = read_list_of_int () in
  let ans = solve list in
  Printf.printf "%d\n" ans
;;

これは素直にl, r (lが始点のインデックス、rが終点のインデックス)の総当りをするために、各l(1<=l<=N, where Nは最後の数字のインデックス, 1-オリジン)についてrをすべてまわすという方法。nの2乗のオーダです。これで部分点。

ところが少し考えればわかるようにあるlについてr=kで単調増加じゃなくなった時、それ以上いくらrを増やしてもr>kで単調増加に再びなることはありません。その上、例えばl=1、r=1でrを順番に増やしていってr=3までで単調増加、r=4が単調増加じゃなくなった時、当然(1,3)が答えに含まれるわけですが、(2,3), (3,3)も答えに含まれます。なので、lを増やしたりrを増やしたりを交互に繰り返すことでlとrは配列の各要素を1回ずつ舐めます。つまり、オーダnで探索できます。しゃくとり法ですね。

もっとぶっちゃけ言うと、for文をまわすひつようもなくて、仮に単調増加が破綻するインデックスのリストさえあれば、例えば[1, 2, 3, 3, 4, 1]なら[1, 2, 3]で6要素、[3, 4]の3要素、末尾の[1]の1要素が条件をみたします。破綻するインデックス同士の距離を2乗して2で割った三角形の面積を順々に足しあわせていけばよいということがわかります。下のコードのmensekiという変数はまさにそれを表しています。forward_to関数はその単調増加が破綻するインデックスを線形探索で求めているだけです。

f:id:euphonictechnologies:20160905215355p:plain

こんな感じに!

let read_list_of_int () =
  let rec read_list_of_int_inner lst =
    try let ans = (Scanf.scanf "%d " (fun x->x)) in
        read_list_of_int_inner (ans::lst)
    with End_of_file ->
      List.rev lst
  in
  read_list_of_int_inner []

let rec forward_to arr offset =
  if offset = (Array.length arr) - 1 then offset+1 else if arr.(offset+1) > arr.(offset) then forward_to arr (offset+1) else offset+1
                         
let rec solve arr from =
  if (Array.length arr) - 1 < from then 0 else
    let ft = (forward_to arr (from)) in
    let width = ft - from in
    let menseki = (width * (width+1) / 2) in
    menseki + solve arr ft

let () =
  let _ = read_int() in
  let arr = Array.of_list (read_list_of_int ()) in
  let ans = solve arr 0 in
  Printf.printf "%d\n" ans
;;

これで満点が取れました。

D問題

高さと幅(h, w)のペア(箱という)が複数与えられます。B1:(h1, w1), B2:(h2, w2)についてh1>h2 and w1>w2のとき、B2はB1に入れられるといいます(B1はB2を包み込むことができる)。次々と箱のなかに箱を入れて行く時、入れ子の数を最大化した時の個数を答えます。

部分点解法は総当りをメモ化する解法です。すべての箱について入れられるかをメモ化していきます。

let rec max_list = function
  | [] -> 0
  | h :: t -> max h (max_list t)
                  
let pack list =
  let table = Hashtbl.create 10000 in
  let rec pack_inner this =
    try let found = Hashtbl.find table this in
        found
    with Not_found ->
      let h, i = this in
      let ans = max_list @@ List.map (fun (j, k) -> if h > j && i > k then (pack_inner (j,k) + 1) else 0 ) list in
      Hashtbl.add table this ans;
      ans
  in
  pack_inner (99999,99999)

let () =
  let rec read lst =
    try let ans = (Scanf.scanf "%d %d\n" (fun a b -> (a,b)) ) in
        read (ans::lst)
    with End_of_file ->
      let list = List.rev lst in
      let ans = pack list in
      Printf.printf "%d\n" (ans)
  in
  let _ = read_int() in
  read []
;;

Hashtblを使って素直にメモ化しました。max_listはHaskellでいうmaximumです。これはfoldを使って書くのがかっこいいと思うのですが、再帰で書きました。ダサいですね。

ある箱について、すべての箱について考えます。その箱が入れられないなら探索しません。入れられるならpack_inner関数で再帰します。結果が出たらそれをメモ化します。これを再帰的にやっていくと答えが求まります。

これで頭のなかに思い浮かぶのはDAGです。矢印の始点は入れられる、終点を入れる側としたグラフです。最高に巨大な箱と最小の箱を用意してこの最大の箱と最小の箱を結ぶ最長経路が問われています。この箱の問題はDAG上の最長経路を求める問題ということがわかります。最長経路問題はNPです。なので残念ですが貪欲法とかそういううまいのはできません。

ところで、高さが全部違うと仮定してその昇順に並べて幅だけを考えると幅だけからなるリストの最長増加部分列(LIS)を求める問題であるという見方ができます。それならDPできます！

高さが同じものがある場合でも、同じ高さのもの同士は入れられないので、同じ高さのところだけ幅を降順に並べてその部分が全く増加列を作らないようにすることができます。

最長部分増加列を求めるアルゴリズムはAOJのサイトに詳しい説明があります。

最長増加部分列 | 動的計画法 | Aizu Online Judge

この中ではSetではなく配列で処理をしています。この配列を1−オリジンとして1番目の要素は1つだけの要素からLISを構成した時の末尾です。2番めは2つ、3番めは3つ、という感じです。当然この配列は昇順に並ぶのでSetでも変わりません。Setなら実装がヒープなのでLISアルゴリズムの途中で入れ替えたり拡張したりする操作が…(多分)n log nで、できるはず(実装見てないので自信ないです)。

let comp_boxes x y =
  match x, y with
    (a,_), (t,_) when a <> t -> compare a t
  | (_,b), (_,u) -> compare u b

module IntSet = Set.Make(struct type t = int let compare = compare end)
             
let lis list =
  let splitGE element set =
    let l, present, r = IntSet.split element set in
    if present then l, present, IntSet.add element r
    else l, present, r in
  let lis_inner set element =
    let _, present, r = splitGE element set in
    if IntSet.is_empty r then IntSet.add element set else
      if present then set
      else (IntSet.remove (IntSet.min_elt r) set) |> IntSet.add element
  in
  IntSet.cardinal @@ List.fold_left lis_inner IntSet.empty (List.map snd (List.sort comp_boxes list))

let () =
  let rec read lst =
    try let ans = (Scanf.scanf "%d %d\n" (fun a b -> (a,b)) ) in
        read (ans::lst)
    with End_of_file ->
      let list = List.rev lst in
      let ans = lis list in
      Printf.printf "%d\n" (ans)
  in
  let _ = read_int() in
  read []
;;

こんな感じにしてみました。fold_leftで綺麗に書いてみました。どうでしょうか。

まとめ

ホントOCamlって最高だわ。まじで。
プロコンでOCamlって意外とありなので是非どうぞ。

euphonictechnologies’s diary

Haskell超初心者の日記です。OCamlが好きです。

AtCoder Beginner Contest 038 in OCaml

なんでOCaml?

問題と回答と解説

A問題

B問題

C問題

D問題

まとめ