A07 - Event Attendance

入出力

1
2
3
4
let D = stdin.ReadLine() |> int
let N = stdin.ReadLine() |> int
let Ia = Array.init N (fun _ -> stdin.ReadLine().Split() |> Array.map int |> fun x -> x.[0],x.[1])
solve D N Ia |> Array.iter stdout.WriteLine

方針

これも前問A06と同じくどうループを減らすかが問題です. このデータ数で速い言語なら無理を通せるものの, 明らかな無駄は省くべきでもあります. さらにA06と同じくあとの処理を綺麗に書くための前処理もポイントです. もちろん前回と違って今回は各日の出席者数の勘定で, 何日から何日までの指定ではない点も注意が必要です.

結論から言えば入力Iaを使ってi日に何人の出入りがあったかを勘定します.

こう考えて出欠を管理すれば計算できます. 上記のriの処理でi+1を考えているため, 配列で処理する場合は配列外参照の実行時エラーを起こさないように注意しましょう. 特にri = Dがありるため, 途中に出てくる配列の要素数はD+1にしなければいけません. 実際私は提出コードで一回REを出してしまいました. テストケースをきちんと考えれば防げた問題でもあり, テストケース生成の重要性もわかります.

解説

出欠管理

方針で書いた内容を素直に実装します.

1
2
  (Array.create (D+1) 0, Ia)
  ||> Array.fold (fun Xa (l,r) -> Xa.[l-1] <- Xa.[l-1]+1; Xa.[r] <- Xa.[r]-1; Xa)

Array.create (D+1)が重要です. 配列の添字は1-originではなく0-originである点にも注意しましょう.

累積和

これも単純にscanで十分です.

1
2
3
  (Array.create (D+1) 0, Ia)
  ||> Array.fold (fun Xa (l,r) -> Xa.[l-1] <- Xa.[l-1]+1; Xa.[r] <- Xa.[r]-1; Xa)
  |> Array.scan (+) 0

必要な要素の切り出し

今回も初項0が余計です. さらにD+1で配列を生成したため最終項も余計です. スライスで次のように書けばいいでしょう.

1
2
3
4
  (Array.create (D+1) 0, Ia)
  ||> Array.fold (fun Xa (l,r) -> Xa.[l-1] <- Xa.[l-1]+1; Xa.[r] <- Xa.[r]-1; Xa)
  |> Array.scan (+) 0
  |> fun Xa -> Xa.[1..(Xa.Length-2)]

ここも0-originの配列で後ろから二つめを取るにはXa.Length-2であって, Xa.Length-1ではない点に注意します.