F# での出力

F# contest

Codeforces 22 Problem C を F# で書いたら TLE 食らいまくったので対処法メモ。

この問題は出力が最大で 10^5 行 (800KB) くらいになるので，出力のところで気をつけないと時間が足りない模様。最初は一行ごとに printfn してたのですが，それだと苦しいようなので StringBuilder を使ってみました。

81190 Jun 30, 2010 6:50:25 PM kozima C - System Administrator F# Accepted 270 ms 20512 KB
81187 Jun 30, 2010 6:28:55 PM kozima C - System Administrator F# Time limit exceeded on test 21 2000 ms 6264 KB

上限 2s で TLE していたのが 270 ms になったそうです。思った以上に差が出ました。正確に何が 270 ms だったのかはよくわかりませんけど。

TLE したコード (81187)

let solve n m v =
  for i = 1 to n do if (i <> v) then (stdout.Write(v); stdout.Write(" "); stdout.WriteLine(i))
  let u = if v = 1 then 2 else 1 in
  let rec loop a b c =
    if c = 0 then ()
    else
      let ok = a <> u && b <> u && a <> v && b <> v in
      let c' = if ok then c-1 else c in
        (if ok then printfn "%d %d" a b);
        if b < n then loop a (b+1) c' else loop (a+1) (a+2) c'
  in loop 1 2 (m - n + 1)

let [n; m; v] = stdin.ReadLine().Split([|' '|]) |> Array.toList |> List.map int in
  if m < n-1 || (n < 10000 && 1 + (n-1) * (n-2) / 2 < m) then
    stdout.WriteLine("-1")
  else solve n m v

solve の中の stdout.Write, stdout.WriteLine, printfn でたくさん出力します。(毎回 flush してる？)

どうでもいいけど for の最後に done; を書くの忘れてますね。F# はインデントを見て適当に処理してくれるみたいです。

通ったコード (81190)

もともと出力していたところを StringBuilder への append で置き換えて，最後にまとめて書き出すようにした。

open System.Text

let solve n m v =
  let sb = StringBuilder() in
  let output a b = ignore <| sb.AppendFormat("{0} {1}\n", a, b) in
    for i = 1 to n do if (i <> v) then output i v;
    let u = if v = 1 then 2 else 1 in
    let rec loop a b c =
      if c = 0 then ()
      else
        let ok = a <> u && b <> u && a <> v && b <> v in
        let c' = if ok then c-1 else c in
          (if ok then output a b);
          if b < n then loop a (b+1) c' else loop (a+1) (a+2) c'
    in loop 1 2 (m - n + 1); stdout.Write(sb.ToString())

let [n; m; v] = stdin.ReadLine().Split([|' '|]) |> Array.toList |> List.map int in
  if m < n-1 || (n < 10000 && 1 + (n-1) * (n-2) / 2 < m) then
    stdout.WriteLine("-1")
  else solve n m v

まとめ

  • 出力が多いときは StringBuilder を使うといいかも
  • StringBuilder は System.Text namespace にいる
  • AppendFormat の第一引数は {0}, {1} とかで残りの引数を参照するらしい
  • ToString() で中身を取り出す
  • 今回は使ってないけど Insert とか Replace とかメソッドがたくさんあって，わりといろいろできるらしい