082 C - Different Strokes¶

• created: 2022-12-14 wed
• ご意見・ご要望はissue・プルリク用のGitHubまで
• 競技プログラミングのためのF#入門
• GitHub上の対応ディレクトリ
• 公式ページ

解説¶

公式解説通りに素直に実装します.

今回入出力は次のように処理する前提で解説します.

1
2
3

let N = stdin.ReadLine() |> int
let Xa = Array.init N (fun _ -> stdin.ReadLine().Split() |> Array.map int64 |> fun x -> x.[0],x.[1])
solve Xa |> stdout.WriteLine

降順ソートはArray.sortDescendingとArray.sortByDescendingがあり, 今回は後者を使えばよいでしょう.

次は和を取る部分です. 配列はF#流の0はじまりとします. 公式解説では別途b_iの和を取っておくような形になっていました. しかし配列の添字が偶数ならa_iを, 奇数なら-b_iを足すようにすればb_iの和を別途用意する必要はありません.

問題は配列の添字をどう用意するかです. Array.indexedで元の配列Xaを添字づけてから処理する方法もあれば, 添字の配列でArray.foldやArray.sumByを回す方法もあります. ここでは次のようにArray.foldで添字を積む方法を取ります.

1
2
3
4
5

let solve Xa =
  Xa
  |> Array.sortByDescending (fun (a,b) -> a+b)
  |> Array.fold (fun (acc,i) (a,b) -> let c = if i%2=0 then a else -b in (acc+c, i+1)) (0L,0)
  |> fst

Array.foldで持ち回る変数として和のaccだけではなく添字のiも積みます. 添字にあたるiを削るため最後にfstで和だけを取っています.

Array.foldに食わせるラムダでlet c = hoge inを使っています. let inをうまく使うと一行でも見やすく書けて便利です. もちろん二行に分けて書いても構いません.