A06 - How Many Guests?

入出力

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

方針

都度入場者数を計算していたら間に合わないため先に計算します. あとの処理を綺麗に書くための計算法もポイントです.

解説

i日目までの入場者数の計算

累積的な計算が必要です. もちろんAiから素直に計算すれば問題ありません. 例えば次のように書けます.

1
2
3
4
let Na0 = Array.create N 0
for i in 0..N-1 do
  if i=0 then Na0.[i] <- Aa.[i]
  else Na0.[i] <- Aa.[i]+Na0.[i-1]

forで破壊的に書きました. もう少し関数型らしく書きたければ次のようにfoldで書けます.

1
2
3
4
5
let Na0 =
  (Array.zeroCreate N, [|0..N-1|])
  ||> Array.fold (fun Na0 i ->
    if i=0 then Na0.[i] <- Aa.[i]; Na0
    else Na0.[i] <- Aa.[i]+Na0.[i-1]; Na0)

ここでNa0.[i] <- Aa.[i]などはunitを返すだけで配列を返さないため, 明示的に配列Na0を返す必要があります.

少し余談を挟みます. ちなみにfoldの内部で破壊的な計算をしています. しかしこれはfoldの外部には漏れません. 関数プログラミングでもパフォーマンスを求める場合は破壊的な処理を使いますし, 破壊的な操作はできる限り外に漏れないようにします. いまは必ずしもパフォーマンスを求める場面ではないものの, F#の配列に対する仕様によって破壊的な処理が便利な部分です. Haskellでは明示的にモナド環境下で作業するように強制されます.

さて, これを使って計算しても構いません. ただ後の処理がやや面倒になるため, 次のようにscanを使って累積和を計算しましょう.

1
  let Na = (0,Aa) ||> Array.scan (+)

これと先のNa0が何が違うかは実行するとわかります. 問題で出てきた入力例で確認しましょう.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#r "nuget: FsUnit"
open FsUnit

let N,Q,Aa,Ia = 10,5,[|8;6;9;1;2;1;10;100;1000;10000|],[|(2,3);(1,4);(3,9);(6,8);(1,10)|]

(Array.zeroCreate N, [|0..N-1|])
||> Array.fold (fun Na0 i ->
  if i=0 then Na0.[i] <- Aa.[i]; Na0
  else Na0.[i] <- Aa.[i]+Na0.[i-1]; Na0)
|> should equal [|8; 14; 23; 24; 26; 27; 37; 137; 1137; 11137|]

(0,Aa) ||> Array.scan (+) |> should equal [|0; 8; 14; 23; 24; 26; 27; 37; 137; 1137; 11137|]

後者は先頭に0がはさまっています. (0,Aa)とした0です. 今回はこれを使いますが, もし先頭の0がほしくない場合は例えば次のように書くといいでしょう.

1
2
(Array.head Aa, Array.tail Aa) ||> Array.scan (+)
|> should equal [|8; 14; 23; 24; 26; 27; 37; 137; 1137; 11137|]

クエリへの対応

先のNaを使えば素直に計算できます.

1
2
  let Na = (0,Aa) ||> Array.scan (+)
  Ia |> Array.map (fun (l,r) -> Na.[r]-Na.[l-1])

ここでのポイントはNa.[r] - Na.[l-1]です. Liには1が来る場合もあり, この場合はRi日目までの全ての入場者を計算する必要があります. 特にNa.[l-1]の減算なしでNa.[r]だけを返す必要があって条件分岐が入ります. さらに条件分岐で適切な対処をしなければ, Na.[l-1]はl-1 = -1に対する配列外参照の実行時エラーまで起こり得ます. これが先のscanでの初項0の意義です.

コードがわかりにくくなるためわざわざ書きませんが, scanによる初項0がなくてももちろん正しいコードは書けます.