競技プログラミングのためのF#入門
GitHub上の対応ディレクトリ 公式ページ 要点: アルゴリズムの検討 入出力
| let N = stdin.ReadLine() |> int
let Ia = Array.init N (fun _ -> stdin.ReadLine() |> int64)
solve N Ia |> stdout.WriteLine
|
解説
方針
公式解説とは違い, 次の方針で前から順に計算します.
- 各
i
ごとに自分自身でペアを作れるだけ作る. - 各
i
ごとにあまりは一枚出るか出ないかで, これを次に持ち越す. - 前の
i
であまりがあった場合は, 積み残しとのペアを考えつつ自分自身でペアを作れるだけ作る.
次のfold
で素直に処理できます.
| ((0L,0L), Ia)
||> Array.fold (fun (acc,m) a -> "条件分岐を書く"
|> fst
|
acc
がペアの数を積む変数でm
があまりの有無を表します. 最後に必要なのはペアの数を表すタプルの第一変数だからfst
で切り出します.
fold
内の条件分岐
まずあまりがなかった場合はごく単純に次のように書けます.
| if m=0L then let (q,r) = (a/2L,a%2L) in (acc+q,r)
|
次の二つはあまりがないときの分岐です. まず入力のA_i
が0
の場合はペアを作りようがないためそのまま次に回します.
今度は入力のA_i
が非零の値を持つため, 前からの積み残しの分を考えて計算します.
| 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
が必要です.
まとめ
| 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
|
Previous: 098 C - Palindromic Matrix Next: 100 C - Vacant Seat back to top