099 B - Simplified mahjong

入出力

1
2
3
let N = stdin.ReadLine() |> int
let Ia = Array.init N (fun _ -> stdin.ReadLine() |> int64)
solve N Ia |> stdout.WriteLine

解説

方針

公式解説とは違い, 次の方針で前から順に計算します.

次のfoldで素直に処理できます.

1
2
3
  ((0L,0L), Ia)
  ||> Array.fold (fun (acc,m) a -> "条件分岐を書く"
  |> fst

accがペアの数を積む変数でmがあまりの有無を表します. 最後に必要なのはペアの数を表すタプルの第一変数だからfstで切り出します.

fold内の条件分岐

まずあまりがなかった場合はごく単純に次のように書けます.

1
    if m=0L then let (q,r) = (a/2L,a%2L) in (acc+q,r)

次の二つはあまりがないときの分岐です. まず入力のA_iが0の場合はペアを作りようがないためそのまま次に回します.

1
    elif a=0L then (acc,0L)

今度は入力のA_iが非零の値を持つため, 前からの積み残しの分を考えて計算します.

1
    else let (q,r) = ((a-1L)/2L, (a-1L)%2L) in (acc+q+1L,r))

積み残しと一つペアを作るため, 次に積み回すための商とあまりのq,rはa-1から計算します. さらにa-1で計算した以上ペアがもう一つできているためペアのカウントはacc+q+1で+1が必要です.

まとめ

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
let solve N Ia =
  ((0L,0L), Ia)
  ||> Array.fold (fun (acc,m) a ->
    if m=0L then let (q,r) = (a/2L,a%2L) in (acc+q,r)
    elif a=0L then (acc,0L)
    else let (q,r) = ((a-1L)/2L, (a-1L)%2L) in (acc+q+1L,r))
  |> fst

let N = stdin.ReadLine() |> int
let Ia = Array.init N (fun _ -> stdin.ReadLine() |> int64)
solve N Ia |> stdout.WriteLine