A09 - Winter in ALGO Kingdom

入出力

1
2
3
let H,W,N = stdin.ReadLine().Split() |> Array.map int |> (fun x -> x.[0],x.[1],x.[2])
let Ia = Array.init N (fun _ -> stdin.ReadLine().Split() |> Array.map int |> fun x -> x.[0],x.[1],x.[2],x.[3])
solve H W N Ia |> Array.iter (Array.map string >> String.concat " " >> stdout.WriteLine)

方針

これもやはり典型的な処理です. 二次元になって積み方にもう一捻り必要になっただけでA07と本質的に同じです. 方針さえはっきりすれば, 実装で問題になるのは最後の余計な要素を削る部分の添字の指定ミス程度でしょう. 正しい実装を導くために入力例をうまく使うと便利です.

解説

方針にも書いたように基本はA07と本質的に同じです. ここでは大幅に解説を省略します.

結論から言えば入力の二次元配列への積み方は次の通りです.

1
2
3
4
5
6
7
  (Array.init (H+1) (fun _ -> Array.create (W+1) 0), Ia)
  ||> Array.fold (fun Xa (a,b,c,d) ->
    Xa.[a-1].[b-1] <- Xa.[a-1].[b-1]+1;
    Xa.[a-1].[d] <- Xa.[a-1].[d]-1;
    Xa.[c].[b-1] <- Xa.[c].[b-1]-1;
    Xa.[c].[d] <- Xa.[c].[d]+1;
    Xa)

(a-1,d)と(c,b-1)に-1を追加し, (c,d)に+1を追加するのがポイントです. (a-1,b-1)で立てた追加フラグを削除するのがこの二つの指定です. 余計なマイナスを削るためにさらに(c,d)に+1を追加します. これで必要な領域にだけ+1できます.

あとは横に足してから縦を足します.

1
2
3
4
5
6
7
8
9
  (Array.init (H+1) (fun _ -> Array.create (W+1) 0), Ia)
  ||> Array.fold (fun Xa (a,b,c,d) ->
    Xa.[a-1].[b-1] <- Xa.[a-1].[b-1]+1;
    Xa.[a-1].[d] <- Xa.[a-1].[d]-1;
    Xa.[c].[b-1] <- Xa.[c].[b-1]-1;
    Xa.[c].[d] <- Xa.[c].[d]+1;
    Xa)
  |> Array.map (Array.scan (+) 0)
  |> Array.scan (Array.map2 (+)) (Array.create (W+2) 0)

これはscan (+) 0の影響で二つついた余計な項を次のようなスライスで落とします.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
  (Array.init (H+1) (fun _ -> Array.create (W+1) 0), Ia)
  ||> Array.fold (fun Xa (a,b,c,d) ->
    Xa.[a-1].[b-1] <- Xa.[a-1].[b-1]+1;
    Xa.[a-1].[d] <- Xa.[a-1].[d]-1;
    Xa.[c].[b-1] <- Xa.[c].[b-1]-1;
    Xa.[c].[d] <- Xa.[c].[d]+1;
    Xa)
  |> Array.map (Array.scan (+) 0)
  |> Array.scan (Array.map2 (+)) (Array.create (W+2) 0)
  |> fun Xa -> Xa.[1..H] |> Array.map (fun Ra -> Ra.[1..W])