LoginSignup
1
0

More than 3 years have passed since last update.

@dsudo(Daisuke Sudo)

AtCoder 精選過去問 10 問を F# ワンライナー で挑戦

Last updated at Posted at 2020-01-11

前回は AtCoder 精選 10 問に JS ワンライナーで挑戦してみました。今回は同じ問題を F# ワンライナーで挑戦してみたいと思います。一度クリアしてる問題なので翻訳みたいなものですが（汗）今回は F# 固有の部分だけ解説（というかほぼ感想）します。ロジック自体の解説は前回の記事で書いてありますので割愛します。

ルール

  • １行のラムダ関数の組み合わせで構成
  • { } は使わない ※コンピュテーション式が使えない！
  • 全部パイプラインでつなぐ（目指せ！パイプの達人）

テンプレート

なしｗ
F# だと標準入力を一度に全部取れないため，全ての問題に共通な部分を作れませんでした。
（取れました |> 後述）
なので，入力から出力まで全て１行で書きます。
副作用を分離できていないのがちょっと気持ち悪いですが。。

あと，こんな感じでエントリーポイントを書かないといけないのかなと思いましたが・・・

let solution (input : string) = "Hello " + input

[<EntryPoint>]
let main argv =
    stdin.ReadLine() |> solution |> printfn "%s"
    0

以下のような感じでもいけました。（今回はこれでいきます）

stdin.ReadLine() |> fun input -> "Hello " + input |> printfn "%s"

（追記）

あ、、普通にこれで全部取れました💧

stdin.ReadToEnd()

（stdin は System.Console.In のエイリアス）

インデックス

まずはざっと解答一覧を並べてみます。こんな雰囲気です。

// ABC086A - Product
stdin.ReadLine() |> fun x -> x.Split(' ') |> Array.map (int >> (&&&) 1) |> Array.reduce (fun a b -> a &&& b) |> fun x -> (if x = 1 then "Odd" else "Even") |> printfn "%s"

// ABC081A - Placing Marbles
stdin.ReadLine() |> fun x -> x.ToCharArray(0, x.Length) |> Array.map (fun x -> x.ToString() |> int) |> Array.reduce (fun a b -> a + b) |> printfn "%d"

// ABC081B - Shift only
stdin.ReadLine() |> ignore |> fun () -> stdin.ReadLine() |> fun x -> x.Split(' ') |> Array.map int |> Array.reduce (fun a b -> a ||| b) |> fun x -> System.Convert.ToString(x, 2) |> fun x -> x.Length - x.LastIndexOf('1') - 1 |> printfn "%d"

// ABC087B - Coins
(stdin.ReadLine(), stdin.ReadLine(), stdin.ReadLine(), stdin.ReadLine()) |> fun (a, b, c, x) -> (a |> int, b|> int, c|> int, x|> int) |> fun (a, b, c, x) ->  [0..(min a (x / 500))] |> List.map (fun i -> [0..(min b ((x - 500 * i) / 100))] |> List.filter (fun j -> x - 500 * i - 100 * j <= 50 * c) |> fun list -> list.Length ) |> List.sum |> printf "%d"

// ABC083B - Some Sums
stdin.ReadLine() |> fun x -> x.Split(' ') |> Array.map int |> fun x -> (x.[0], x.[1], x.[2]) |> fun (n, a, b) ->  [1..n] |> List.filter (fun ni -> ni.ToString() |> fun x -> x.ToCharArray(0, x.Length) |> Array.map (fun x -> x.ToString() |> int) |> Array.sum |> fun x -> x >= a && x <= b ) |> List.sum |> printfn "%d"

// ABC088B - Card Game for Two
stdin.ReadLine() |> ignore |> fun () -> stdin.ReadLine() |> fun x -> x.Split(' ') |> Array.map int |> Array.sortWith (fun a b -> b - a) |> Array.mapi (fun i x -> (i, x)) |> Array.fold (fun (a, b) (i, x) -> if i % 2 = 0 then (a + x, b) else (a, b + x) ) (0, 0) |> fun (a, b) -> a - b |> printfn "%d"

// ABC085B - Kagami Mochi
stdin.ReadLine() |> int |> fun x -> [1..x] |> List.map (fun _ -> stdin.ReadLine()) |> List.distinct |> List.length |> printfn "%d"

// ABC085C - Otoshidama
stdin.ReadLine() |> fun x -> x.Split(' ') |> Array.map int |> fun x -> (x.[0], x.[1] / 1000) |> fun (n, y) -> [0..(min 2000 (y / 10))] |> List.tryFind (fun i -> (y - n - 9 * i) |> fun x -> if x % 4 = 0 then (x / 4) |> fun j -> (n - i - j) |> fun k -> j >= 0 && k >= 0 else false) |> (fun i -> match i with | Some i -> ((y - n - 9 * i) |> fun x -> (x / 4) |> fun j -> (n - i - j) |> fun k -> sprintf "%d %d %d" i j k) | None -> "-1 -1 -1") |> printfn "%s"

// ABC049C - Daydream
stdin.ReadLine() |> fun input -> ["eraser"; "erase"; "dreamer"; "dream"] |> List.fold (fun acc word -> acc |> List.map (fun (x: string) -> x.Split([| word |], System.StringSplitOptions.None) |> Array.filter (fun x -> not (System.String.IsNullOrEmpty(x))) |> Array.toList) |> List.fold (fun a b -> a @ b) []) [input] |> List.length |> fun x -> (if x = 0 then "YES" else "NO") |> printfn "%s"

// ABC086C - Traveling
stdin.ReadLine() |> int |> fun x -> [1..x] |> List.map (fun _ -> stdin.ReadLine()) |> List.map (fun x -> x.Split(' ') |> Array.map int |> Array.toList) |> List.map (fun x -> (x.[0], x.[1], x.[2])) |> List.fold (fun acc (t2, x2, y2) -> match acc with | Some (t1, x1, y1) -> (if ((t2 &&& 1) = ((x2 + y2) &&& 1)) && ((t2 - t1) >= (abs (x2 - x1) + abs (y2 - y1))) then Some (t2, x2, y2) else None) | None -> None) (Some (0, 0, 0)) |> fun x -> (match x with | Some _ -> "Yes" | None -> "No") |> printfn "%s"

１問目 ABC086A - Product 

stdin.ReadLine()
|> fun x -> x.Split(' ')
|> Array.map (int >> (&&&) 1)
|> Array.reduce (&&&)
|> fun x -> (if x = 1 then "Odd" else "Even")
|> printfn "%s"

JavaScript版

F# だとビットアンドが &&& なんですね。暗黙の型変換はないので，いったん int にしてます。

ちなみに & は match 式で使うみたいです。
参考：シンボルと演算子のリファレンス

あと，改行すると要らないけど，１行で書くときには括弧が必要になる場合があります。if とか match は括弧で囲わないでパイプでつなぐと最後のステート（例えば else の中の処理）にくっつくように推論されてしまいます。

２問目 ABC081A - Placing Marbles 

stdin.ReadLine()
|> fun x -> x.ToCharArray(0, x.Length)
|> Array.map (fun x -> x.ToString() |> int)
|> Array.reduce (fun a b -> a + b)
|> printfn "%d"

JavaScript版

う～ん。。文字列を１文字ずつの配列に変換するのが煩雑な印象です。
C# からのクラスのメソッドとか呼ぶ当たりが洗練されてない感じがしますね。

(追記)
コメントでこちらご提案頂きました！

stdin.ReadLine()
|> Seq.map (string >> int)
|> Seq.sum

おぉ～！断然スッキリしてますね！

String は IEnumerable<char> を実装しているので Seq で操作可能なんですね。

"abc" |> Seq.rev
// seq ['c'; 'b'; 'a']

また，fun a b -> a + b は (+) で置き換え可能なので，fold や reduce で使うと，よりスッキリ書けます。(&&&) や (|||) も同様です。

さらに sumBy（sum と map を組み合わせたもの）を使うとこうなります。

stdin.ReadLine()
|> Seq.sumBy (string >> int)

３問目 ABC081B - Shift only 

stdin.ReadLine()
|> ignore
|> fun () -> stdin.ReadLine()
|> fun x -> x.Split(' ')
|> Array.map int
|> Array.reduce (|||)
|> fun x -> System.Convert.ToString(x, 2)
|> fun x -> x.Length - x.LastIndexOf('1') - 1
|> printfn "%d"

JavaScript版

入力の１行目は要らないので，ignore で捨ててから unit で始まる関数につなぐという無駄なことしてますｗ

結果の変数を取っておいて別のコンテキストで使いたいときにパイプラインでつなぐとスッキリ書けますね。

４問目 ABC087B - Coins 

(stdin.ReadLine(), stdin.ReadLine(), stdin.ReadLine(), stdin.ReadLine())
|> fun (a, b, c, x) -> (a |> int, b|> int, c|> int, x|> int)
|> fun (a, b, c, x) ->
  [0..(min a (x / 500))]
  |> List.sumBy (fun i ->
    [0..(min b ((x - 500 * i) / 100))]
    |> List.filter (fun j -> x - 500 * i - 100 * j <= 50 * c)
    |> List.length
  )
  |> printf "%d"

JavaScript版

入力４行の値が欲しいので，いったんタプルに入れて次に渡してます。

int で割り算すると自動的に切り捨て（floor）られるのを利用しています。
演算によって型が変わらないようになっているのが素晴らしいですね。

５問目 ABC083B - Some Sums 

stdin.ReadLine()
|> fun x -> x.Split(' ')
|> Array.map int
|> fun x -> (x.[0], x.[1], x.[2])
|> fun (n, a, b) -> 
  [1..n]
  |> List.filter (
    fun ni ->
      ni.ToString()
      |> Seq.sumBy (string >> int)
      |> fun x -> x >= a && x <= b
  )
  |> List.sum
  |> printfn "%d"

JavaScript版

分割代入的なことがしたかったので配列からタプルに変換してます。
入力が３つなのは分かっているので問題ありませんが，もし要素数が足りなければ例外がでます。

リストを渡して受け取り側で分割して受け取れないかなと思って以下のようなことしてみたら警告でました。

let f = fun (a :: b :: [c]) -> printfn "%d, %d, %d" a b c
// warning FS0025: Incomplete pattern matches on this expression. For example, the value '[_;_;_;_]' may indicate a case not covered by the pattern(s).

要素が常に３つかどうかコンパイル時には分からないので当然ですね。
パターンマッチしてその他のケースも明示的に扱うようにすれば怒られません。

let f =
  function
  | a :: b :: [c] -> printfn "%d, %d, %d" a b c
  | _ -> ()

でも，１行では書けないので却下ｗ

６問目 ABC088B - Card Game for Two 

stdin.ReadLine()
|> ignore
|> fun () -> stdin.ReadLine()
|> fun x -> x.Split(' ')
|> Array.map int
|> Array.sortWith (fun a b -> b - a)
|> Array.mapi (fun i x -> (i, x))
|> Array.fold (fun (a, b) (i, x) ->
  if i % 2 = 0
  then (a + x, b)
  else (a, b + x)
) (0, 0)
|> fun (a, b) -> a - b
|> printfn "%d"

JavaScript版

JS版では配列にしてたアキュムレーターをタプルにしてます。
（というか，JSでタプルがないから配列で代用してただけですが）

mapi はあるのに foldi はないので，いったん mapi で タプルにしてます。

７問目 ABC085B - Kagami Mochi 

stdin.ReadLine()
|> int
|> fun x -> [1..x]
|> List.map (fun _ -> stdin.ReadLine())
|> List.distinct
|> List.length
|> printfn "%d"

JavaScript版

この問題はJS版とロジックが変わってます。
F# では distinct があったので，こちらを使用するようにしました。

行数が可変なので，１行目の数分だけ ReadLine してます。
はじめて１行目を使いましたｗ

８問目 ABC085C - Otoshidama 

stdin.ReadLine()
|> fun x -> x.Split(' ')
|> Array.map int
|> fun x -> (x.[0], x.[1] / 1000)
|> fun (n, y) ->
  [0..(min 2000 (y / 10))]
  |> List.tryFind (
    fun i ->
      (y - n - 9 * i)
      |> fun x ->
        if x % 4 = 0
        then
          (x / 4)
          |> fun j ->
            (n - i - j)
            |> fun k -> j >= 0 && k >= 0
        else
          false
  )
  |> (
    fun i ->
      match i with
      | Some i -> (
        (y - n - 9 * i)
        |> fun x ->
          (x / 4)
          |> fun j ->
            (n - i - j)
            |> fun k -> sprintf "%d %d %d" i j k
      )
      | None -> "-1 -1 -1"
  )
  |> printfn "%s"

JavaScript版

（関数分割版）
https://atcoder.jp/contests/abs/submissions/9410338

でました！鬼門の Otoshidama 👹

でも，パイプを使うと処理の順と記述の順が一致するので（比較的）分かりやすいかと思います。

前段の関数の変数（引数）が後段の関数でも参照できています。後段の関数を呼び出すところも前段の関数の一部になっているってことですね。どこまでが関数の切れ目なのか分かりづらいですねｗ

tryFind が option を返すので，後段はパターンマッチで場合分けしてます。match が一行で書けるやつで良かったです😅
option でラップされた i が Some にマッチした後では，中の値に変わってます。同じ変数名だけど値を差し替えるのをシャドーイングというようです。他のところでもちょいちょい使っています。

（改良版）

stdin.ReadLine()
|> fun x -> x.Split(' ')
|> Array.map int
|> fun x -> (x.[0], x.[1] / 1000)
|> fun (n, y) ->
  [0..n]
  |> Seq.tryFind (fun a ->
    (y - n - 9 * a) % 4 = 0 &&
       (y - n - 9 * a) >= 0 &&
       n - a - (y - n - 9 * a) / 4 >= 0
  )
  |> fun a ->
    match a with
    | Some a ->
      (y - n - 9 * a) / 4
      |> fun b -> sprintf "%d %d %d" a b (n - a - b)
    | None -> "-1 -1 -1"
|> printfn "%s"

９問目 ABC049C - 白昼夢 / Daydream 

stdin.ReadLine()
|> fun input ->
  ["eraser"; "erase"; "dreamer"; "dream"]
  |> List.fold (
    fun acc word ->
      acc
      |> List.collect (
        fun (x: string) ->
          x.Split([| word |], System.StringSplitOptions.None)
          |> Array.filter (System.String.IsNullOrEmpty >> not)
          |> Array.toList
      )
  ) [input]
  |> List.length
  |> fun x -> (if x = 0 then "YES" else "NO")
  |> printfn "%s"

JavaScript版

なんか JS よりもパフォーマンス悪くなってます。。

Split がこんな記述になるのか～ ダサいですね。たしかに C# だと char はオプションなしでもいいけど，string だと配列でかつオプション指定しないとダメという仕様だったような。。
手元の fsi だと普通にオプションなしで書けるんですが。。バージョンの問題かな？

> "abc".Split "b" ;;
val it : string [] = [|"a"; "c"|]

IsNullOrEmpty も微妙。括弧で囲わないと not に渡せないのは何なんだろう。
→ 結合順序（評価順序）のせい

１０問目 ABC086C - Traveling 

stdin.ReadLine()
|> int
|> fun x -> [1..x]
|> List.map (
  fun _ ->
    stdin.ReadLine().Split(' ')
    |> Array.map int
    |> fun x -> (x.[0], x.[1], x.[2])
)
|> List.fold (
  fun acc (t2, x2, y2) ->
    match acc with
    | Some (t1, x1, y1) ->
      (
        if ((t2 &&& 1) = ((x2 + y2) &&& 1))
          && ((t2 - t1) >= (abs (x2 - x1) + abs (y2 - y1)))
        then Some (t2, x2, y2)
        else None
      )
    | None -> None
) (Some (0, 0, 0))
|> fun x ->
  (
    match x with
    | Some _ -> "Yes"
    | None -> "No"
  )
|> printfn "%s"

JavaScript版

さぁ，いよいよ最後の問題。いままでの集大成的な感じですね。

(Some (0, 0, 0)) のところは括弧で囲わないと適切に結合できません。

アキュムレーター を option にしてパターンマッチするのはなかなか面白いなと感じました。これはもっと応用できそうです。

まとめ

  • F# はインデントが意味を持つ言語ではあるけど，１行でも結構ちゃんと書けます
  • パイプラインは非常に強力で有用です（気に入りました！）
    • それでいうとコンピュテーション式はコンセプトはすごくいいんだけど，構文はいまいち。。
  • 慣れないと括弧つけないといけないところと省略可能なところの見分けが難しい
    • コンパイルエラーとの闘い
  • C# を引きずってるところは，ちょっと洗練されてない感があります
    • 実際プロダクトだと，いい感じに書けるようなラッパーとか用意するんでしょうか
    • 過去のバージョンアップでもちょいちょい追加されてる感じもあります
  • JS と比べてもさほどパフォーマンスが高いようには見えません（書き方にもよると思いますが）

Have a happy programming life 🌄

1
0
5

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0