A08 - Two Dimensional Sum¶

• created: 2022-12-27 tue
• ご意見・ご要望はissue・プルリク用のGitHubまで
• 競技プログラミングのためのF#入門
• GitHub上の対応ディレクトリ
• 公式ページ
• 要点: アルゴリズム, ループを減らす

入出力¶

1
2
3
4
5

let H,W = stdin.ReadLine().Split() |> Array.map int |> (fun x -> x.[0],x.[1])
let Xa = Array.init H (fun _ -> stdin.ReadLine().Split() |> Array.map int)
let Q = stdin.ReadLine() |> int
let Qa = Array.init Q (fun _ -> stdin.ReadLine().Split() |> Array.map int |> fun x -> x.[0],x.[1],x.[2],x.[3])
solve H W Xa Q Qa |> Array.iter stdout.WriteLine

方針¶

これもやはり典型的な処理です. 結論から言うと, 予め問題中の添字でいう(1,1)から(i,j)までの総和を取って配列Sa.[i,j]にためます. 求める部分長方形領域に対しては余計な要素を削って処理します. 部分総和を取る部分でO(HW), 質問のQa全体をチェックする部分でO(Q)だから十分間に合います.

方針さえはっきりすれば, 実装で問題になるのは最後の余計な要素を削る部分の添字の指定ミス程度でしょう.

解説¶

総和の配列を計算¶

計算の仕方はいろいろあります. C/C++/Rustのコードを参考にして, 例えば次のような破壊的な書き方をしてもいいでしょう.

1
2
3
4
5
6

  let Sa =
    let sa = Array2D.create (H+1) (W+1) 0
    let Ia = [| for i in 0..H-1 do for j in 0..W-1 do (i,j) |]
    Ia |> Array.iter (fun (i,j) -> sa.[i+1,j+1] <- sa.[i+1,j]+Xa.[i].[j])
    Ia |> Array.iter (fun (i,j) -> sa.[i+1,j+1] <- sa.[i+1,j+1]+sa.[i,j+1])
    sa

これはSaの計算の内部で破壊的なコードが閉じているため, 関数プログラミング的な実装とみなして構いません.

しかしここまでと同じくscanを使うともっとすっきり書けます. 「横を足してから縦に足す」素直な計算が次のように書けます.

1
2
3
4

  let Sa =
    Xa
    |> Array.map (Array.scan (+) 0)
    |> Array.scan (Array.map2 (+)) (Array.create (W+1) 0)

はじめのXa |> Array.map (Array.scan (+) 0)が横を足しているのはわかりやすいでしょうから, 問題は縦に足す部分です. 公式の入力例に即してどう計算しているか追いかけます. 説明の便宜のため次のように書き換えます.

1
2
3

  let Sa =
    let Ya = Xa |> Array.map (Array.scan (+) 0)
    Array.scan (Array.map2 (+)) (Array.create (W+1) 0) Ya

まずYaから書きます.

1
2
3
4
5
6
7
8

let Ya = Xa |> Array.map (Array.scan (+) 0)

val it: int array array =
  [|[|0; 2; 2; 2; 7; 8|];
    [|0; 1; 1; 4; 4; 4|];
    [|0; 0; 8; 13; 13; 15|];
    [|0; 4; 5; 5; 5; 11|];
    [|0; 0; 9; 11; 18; 18|]|]

これに対して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

  Qa |> Array.map (fun (a,b,c,d) -> Sa.[c].[d] - Sa.[c].[b-1] - Sa.[a-1].[d] + Sa.[a-1].[b-1])

わかりにくければ図を描いて確認してください.