084 C - Shopping Street

三つの実装

まずはユーザー解説にあったビットマスクを使った実装を紹介します. しかし執筆時点でビットマスクに慣れていないためにいま一つ腑に落ちず, Haskell実装を参考にビットマスクではな真偽値の形で全パターンを作る実装を確認しました. この実装は簡潔な割に見通しもよいコードで何をどうすればいいかようやく見えました. そこでさらにHaskell実装を参考にパターン網羅部分をビットマスクに書き換える処理を実装しました.

ビットマスクに慣れていなければ解説2の実装を読むといいでしょう. 最後に解説3でビットマスク化したときの実装を載せています.

解説1: ビットマスクを使う方法

解説する実装はどちらかと言えば関数型らしい実装にしています. しかしfor文による処理の方がわかりやすいかもしれません. 本質的に全く同じ処理をしているため, 読みやすい方で実装を確認してください.

入力

F_{ijk}のj,kは指示の上で曜日と午前午後でわかれています. しかしこれは時間指定用パラメーターが10個あると思って処理した方が便利です. 特にループ用に[|0..9|]の意図を明確にする変数としてjkNum = 10-1を用意します.

さらに次のように入力を取得して変数に束縛します.

1
2
3
4
5
6
let solve N (Fa:int[][]) (Pa:int[][]) = "処理"

let N = stdin.ReadLine() |> int
let Fa = Array.init N (fun _ -> stdin.ReadLine().Split() |> Array.map int)
let Pa = Array.init N (fun _ -> stdin.ReadLine().Split() |> Array.map int)
solve N Fa Pa |> stdout.WriteLine

全体構成

全パターンを総なめして最大値を取ります. 以下のコードでは0はじまりで配列を作っているため, 総パターン数にあたるtotalは2^10-1とします. 最大値を取るため, たたみ込むループとみなせ, 大枠は次のfoldです.

1
2
3
4
  let total = (1 <<< 10) - 1
  let jkNum = 10-1
  (-System.Int32.MinValue, [|0..total|])
  ||> Array.fold (fun acc i -> "何かの処理")

ループはビットマスクで回します.

各パターンのチェック

foldの内部を考えます. 各開店パターンごとに店が両方営業しているか調べ, 両方開いていれば利益を計算します. 特に開店している時間帯の個数をcとして積みます. c=0は一つも開店しない除外パターンだから最大値は更新しません. それ以外の場合は利益を計算して最大値候補を比較して更新します.

店iとお姉ちゃんが両方開店している時間帯の個数に対する配列をCaとすれば, fold内部は次のように書けます.

1
2
3
4
5
6
7
  let total = (1 <<< 10) - 1
  let jkNum = 10-1
  (-System.Int32.MinValue, [|0..total|])
  ||> Array.fold (fun acc n ->
    let (c, Ca) = "適当に計算"
    if c=0 then acc
    else let p = (0, [|0..N-1|]) ||> Array.fold (fun acc jk -> acc + Pa.[jk].[Ca.[jk]]) in max acc p)

最後のelse let p = ...は問題文での利益計算そのままです. あとは店ごとに両方開店している時間帯の個数を数えれば終わりです.

開店時間帯の個数計算

F_{ijk}に関する処理です. 店舗数はNで開店時間帯の総和を求めたいため, Caは0埋めしたArray.zeroCreate Nで初期化し, 時間指定の10個のループを回します.

1
2
3
4
5
6
  ||> Array.fold (fun acc n ->
    let (c, Ca) =
      ((0, Array.zeroCreate N), [|0..jkNum|])
      ||> Array.fold "適当な関数"
    if c=0 then acc
    else let p = (0, [|0..N-1|]) ||> Array.fold (fun acc jk -> acc + Pa.[jk].[Ca.[jk]]) in max acc p)

いま見たいのはfun acc n -> hogeの部分であるため, 以下そこだけ抜き出しましょう.

1
2
3
    let (c, Ca) =
      ((0, Array.zeroCreate N), [|0..jkNum|])
      ||> Array.fold "適当な関数"

foldで積み回す変数は(c, Ca)として, ループの変数はjkにします.

1
2
3
    let (c, Ca) =
      ((0, Array.zeroCreate N), [|0..jkNum|])
      ||> Array.fold (fun (c, Ca) jk -> "処理")

次にビットマスクに関する変数nを処理します. 基本はn >>> jkで, 開店状況を取るためにさらに&&& 1をかませます. 該当時間帯で開店していればlet bit = n >>> jk &&& 1が立つため, bit = 1なら開店状況を更新します. もちろん開店している店の個数に関するcも同時に更新する必要があります. まとめると次のように書けます.

1
2
3
4
      ((0, Array.zeroCreate N), [|0..jkNum|])
      ||> Array.fold (fun (c, Ca) jk ->
        let bit = n >>> jk &&& 1
        (c+bit, if bit=0 then Ca else Ca |> Array.mapi (fun i t -> t+Fa.[i].[jk])))

最後のタプルを作る部分が一行にまとめると読みづらいなら適当に書き換えるといいでしょう.

1
2
3
4
5
6
7
8
      ((0, Array.zeroCreate N), [|0..jkNum|])
      ||> Array.fold (fun (c, Ca) jk ->
        let bit = n >>> jk &&& 1

        if bit = 0 then (c+bit, Ca)
        else
          let Ca1 = Ca |> Array.mapi (fun i t -> t+Fa.[i].[jk])
          (c+bit, Ca1))

補足: ビット演算

私自身, この記事の執筆時点で全くビット演算に慣れていません. どういう計算になっているか確認したければ次のコードを実行して出力を見るといいでしょう.

1
2
3
4
let n = 5
let Ni = 1 <<< n - 1
let Nj = n - 1
[| for i in 0..Ni do for j in 0..Nj do (i, j, i>>>j, i>>>j &&& 1)|] |> Array.iter (printfn "%A")

解説2: ビットマスクの代わりに全開店状態の真偽値を生成して確認する

ビットマスクに慣れていないため, 比較用に真偽値で開店状態を全て生成する実装も試してみました. Haskellを参考にしています.

1024通りの真偽値を生成

F#でのリスト版replicateMを実装して, Oaとして開店状態の真偽値を表す配列を生成しました.

1
2
3
4
  let replicateM n xs =
    let k m acc = List.collect (fun y -> List.collect (fun ys -> [y::ys]) acc) m
    List.foldBack k (List.replicate n xs) [[]]
  let Oa = replicateM 10 [false;true] |> List.toArray |> Array.map (List.toArray)

Faを真偽値に変換

さらにHaskell実装と同じくFaを0,1から真偽値に変換します.

1
  let Ga = Fa |> Array.map (Array.map ((=) 1))

処理の大枠のfoldの構成

解説1と同じくfoldでたたみ込めばよいため, 大枠は次のように書けます.

1
2
  (System.Int32.MinValue, Oa)
  ||> Array.fold (fun acc opn -> "利益計算して最大値を更新")

foldの内部

opnは[|false; false; false; true; true; false; false; false; true; false|];のような1024通りの開店状況のうちの一つです. まず一つはお店が開いていなければならないため, 少なくとも一つはtrueが必要です. 特に次のような分岐処理が入ります.

1
2
3
  (System.Int32.MinValue, Oa)
  ||> Array.fold (fun acc opn ->
    if Array.exists id opn then max acc "利益計算" else acc)

利益計算

あとは利益計算処理を書けば終わりです. この準備のもとでF_{ijk}から開店状況(開店店舗数)を取得し, 利益を計算する関数calを作りましょう.

上記のGaと入力のPaの各行ごとにopnと比較して計算すればよく, 特にこれらの各行がきちんと対応しているため, Array.map2で同時に各行を取得しつつ処理した結果の総和を取れば問題文のP_{1,c_1}+P_{2,c_2}+...+P_{N,c_N}が計算できます. 特に利益計算は(Ga, Pa) ||> Array.map2 (cal opn) |> Array.sumとして, cal関数を作れば十分です.

cal関数の構成

最後にcal関数の構成を考えます. まずGa(Fa)の各行gとopnで渡した開店状況を比較して開店個数を取ります. 真偽値に変換しているためArray.map2で次のように書けます.

1
Array.map2 (&) opn g

これでフラグが立っている店舗数を計算すればよく, Array.sumByを使えば次のように計算できます.

1
Array.map2 (&) opn g |> Array.sumBy (fun b -> if b then 1 else 0)

これで開店店舗数nがわかったため, あとはPaの各行pに対して開店店舗数にあたるp.[n]を取れば終わりです. 特にArray.getを使えばパイプラインで次のように流せます.

1
  let cal opn g p = Array.map2 (&) opn g |> Array.sumBy (fun b -> if b then 1 else 0) |> Array.get p

最後に処理をまとめると次のように書けます.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
let solve N (Fa:int[][]) (Pa:int[][]) =
  let replicateM n xs =
    let k m acc = List.collect (fun y -> List.collect (fun ys -> [y::ys]) acc) m
    List.foldBack k (List.replicate n xs) [[]]
  let Oa = replicateM 10 [false;true] |> List.toArray |> Array.map (List.toArray)
  let Ga = Fa |> Array.map (Array.map ((=) 1))

  let cal opn g p = Array.map2 (&) opn g |> Array.sumBy (fun b -> if b then 1 else 0) |> Array.get p
  (System.Int32.MinValue, Oa)
  ||> Array.fold (fun acc opn ->
    if Array.exists id opn then max acc ((Ga, Pa) ||> Array.map2 (cal opn) |> Array.sum) else acc)

参考

replicateMやfilterMなどいくつかのアクションに対して, F#のリスト版の実装をReference.fsxに収録しています.

解説3: 解説2の実装のビットマスク化

まず実装は次の通りです.

1
2
3
4
5
6
7
let solve N (Fa:int[][]) (Pa:int[][]) =
  let cal opn f p = (0,opn,f) |||> Array.fold2 (fun acc o b -> if o=b && o=1 then acc+1 else acc) |> Array.get p
  (-System.Int32.MinValue, [|0..1023|])
  ||> Array.fold (fun acc n ->
    let opn = [|0..9|] |> Array.map (fun jk -> n>>>jk &&& 1)
    if Array.exists (fun i -> i=1) opn then max acc ((Fa,Pa) ||> Array.map2 (cal opn) |> Array.sum)
    else acc)

calが少し書き換わります. map2 >> sumByではなくfold2で一気に和を計算しています. さらに真偽値ではなく0,1のままで処理を進めているため, map2 (&)の部分でo=b && o=1のような書き方が必要です.

あとのポイントはビットマスクからのopnの手動生成です. 私はこれでようやくビットマスクで何をやっているか理解できました. 私の感覚では解説1の実装より簡潔になった上に意味も把握しやすくなりました. ようやくすっきり理解できてとてもいい気分です.