競技プログラミングのためのF#入門
1 2 3 4 5 |
|
ふつうに都度計算していたら凄まじい時間がかかるため, やはりクエリ処理の前の事前計算が重要です. 真ん中を抜いた配列に対する最大値の計算は, 左からLi-1
番目までの最大値と, 右からRi+1
番目からの最大値を計算すればよいです. 特に左からi
番目までの最大値と, 右からi
番目までの最大値を比較すればよいため, これを事前に計算しておけば十分です.
この方針さえ立てばあとは素直に実装できます.
命令型的にfor
を回す計算でも対応できます. ここでは関数プログラミングらしい処理としてscan max
を使います.
1 2 |
|
La
が左からの最大値でRa
が右からの最大値です. それぞれ左右の端からはじめるにはscan
とscanBack
と使えばよいです. 気分としてscanBack
はArray.rev >> Array.scan
だと思ってください. 上のコードを見ればわかるように初期値0
とAa
の引数の順番が入れ替わっています. ちなみにscan
とscanBack
はHaskellだとfoldl
とfoldr
で, このl
とr
はleft
とright
に由来します.
あとはクエリごとに最大値を比較すれば終わりです.
1 |
|
scan
とscanBack
は初期値0
に由来する「余計な項」が入っている点に注意して添字を指定してください. 公式の入力例でLa
とRa
は次のようになっています.
1 2 |
|
scan
では最初に0
が, scanBack
では最後に0
が入ります. REPLを使うと簡単に確認できます.