競技プログラミングのためのF#入門
1 2 3 4 5 |
|
これもやはり典型的な処理です. 結論から言うと, 予め問題中の添字でいう(1,1)
から(i,j)
までの総和を取って配列Sa.[i,j]
にためます. 求める部分長方形領域に対しては余計な要素を削って処理します. 部分総和を取る部分でO(HW)
, 質問のQa
全体をチェックする部分でO(Q)
だから十分間に合います.
方針さえはっきりすれば, 実装で問題になるのは最後の余計な要素を削る部分の添字の指定ミス程度でしょう.
計算の仕方はいろいろあります. C/C++/Rustのコードを参考にして, 例えば次のような破壊的な書き方をしてもいいでしょう.
1 2 3 4 5 6 |
|
これはSa
の計算の内部で破壊的なコードが閉じているため, 関数プログラミング的な実装とみなして構いません.
しかしここまでと同じくscan
を使うともっとすっきり書けます. 「横を足してから縦に足す」素直な計算が次のように書けます.
1 2 3 4 |
|
はじめのXa |> Array.map (Array.scan (+) 0)
が横を足しているのはわかりやすいでしょうから, 問題は縦に足す部分です. 公式の入力例に即してどう計算しているか追いかけます. 説明の便宜のため次のように書き換えます.
1 2 3 |
|
まずYa
から書きます.
1 2 3 4 5 6 7 8 |
|
これに対してscan
の処理を追いかけましょう.
Array.create (W+1) 0 = [|0; 0; 0; 0; 0; 0|]
Ya
の一行目: [|0; 2; 2; 2; 7; 8|]
map2 (+)
で足す: [|0; 2; 2; 2; 7; 8|]
scan
として積み足しつつ次の入力に回すscan
の前段: [|0; 2; 2; 2; 7; 8|]
Ya
の二行目: [|0; 1; 1; 4; 4; 4|]
map2 (+)
で足す: [|0; 3; 3; 6; 11; 12|]
scan
として積み足しつつ次の入力に回すscan
の前段: [|0; 3; 3; 6; 11; 12|]
Ya
の三行目: [|0; 0; 8; 13; 13; 15|]
map2 (+)
で足す: [|0; 3; 11; 19; 24; 27|]
scan
として積み足しつつ次の入力に回すscan
の前段: [|0; 3; 11; 19; 24; 27|]
Ya
の四行目: [|0; 4; 5; 5; 5; 11|]
map2 (+)
で足す: [|0; 7; 16; 24; 29; 38|]
scan
として積み足しつつ次の入力に回すscan
の前段: [|0; 7; 16; 24; 29; 38|]
Ya
の五行目: [|0; 0; 9; 11; 18; 18|]
map2 (+)
で足す: [|0; 7; 25; 35; 47; 56|]
scan
として積み足しつつ終了これで縦の和も計算できました.
先のscan
二発で一行・一列が追加されています. それを前提にすると次のように書けます.
1 |
|
わかりにくければ図を描いて確認してください.
Previous: A07 - Event Attendance Next: A09 - Winter in ALGO Kingdom back to top