A10 - Resort Hotel

入出力

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

方針

ふつうに都度計算していたら凄まじい時間がかかるため, やはりクエリ処理の前の事前計算が重要です. 真ん中を抜いた配列に対する最大値の計算は, 左からLi-1番目までの最大値と, 右からRi+1番目からの最大値を計算すればよいです. 特に左からi番目までの最大値と, 右からi番目までの最大値を比較すればよいため, これを事前に計算しておけば十分です.

この方針さえ立てばあとは素直に実装できます.

解説

命令型的にforを回す計算でも対応できます. ここでは関数プログラミングらしい処理としてscan maxを使います.

1
2
  let La = Array.scan max 0 Aa
  let Ra = Array.scanBack max Aa 0

Laが左からの最大値でRaが右からの最大値です. それぞれ左右の端からはじめるにはscanとscanBackと使えばよいです. 気分としてscanBackはArray.rev >> Array.scanだと思ってください. 上のコードを見ればわかるように初期値0とAaの引数の順番が入れ替わっています. ちなみにscanとscanBackはHaskellだとfoldlとfoldrで, このlとrはleftとrightに由来します.

あとはクエリごとに最大値を比較すれば終わりです.

1
  Ia |> Array.map (fun (l,r) -> max La.[l-1] Ra.[r])

scanとscanBackは初期値0に由来する「余計な項」が入っている点に注意して添字を指定してください. 公式の入力例でLaとRaは次のようになっています.

1
2
Array.scan max 0 Aa |> should equal [|0; 1; 2; 5; 5; 5; 5; 5|]
Array.scanBack max Aa 0 |> should equal [|5; 5; 5; 5; 3; 3; 1; 0|]

scanでは最初に0が, scanBackでは最後に0が入ります. REPLを使うと簡単に確認できます.