086 D - Coloring Dominoes

入出力

共通の入出力です.

1
2
3
4
let N = stdin.ReadLine() |> int
let S1 = stdin.ReadLine()
let S2 = stdin.ReadLine()
solve N S1 S2 |> stdout.WriteLine

解説1

再帰で素朴に実装します.

補助関数

まずは補助関数を準備します.

1
2
3
  let MOD = 1_000_000_007L
  let (.*) x y = (x*y)%MOD
  let isVertical i = S1.[i]=S2.[i]

MODはまさに余りを取るための数です. .NETでは数値を_で区切って読みやすく書けます. Int32でも問題ないとは思うものの, 念のためLをつけてInt64にします.

let (.*)と括弧をつけると演算子が定義できます. 計算結果を%で処理し忘れないように全てこの演算子で計算します.

あと公式解説でいうX(縦並び)判定用の関数としてisVerticalを用意しました.

再帰関数

まず先頭から確認をはじめます. 縦が一致していたら3をかけて1進め, そうでなければ横の並びと判定して6をかけて2進めます. 最後まで来たら積んできた値を返します. したがって次の処理ではじめればいいでしょう.

1
2
3
4
5
6
7
  let rec frec acc i =
    if i=N then acc
    elif i=0 then if isVertical i then frec (acc.*3L) (i+1) else frec (acc.*6L) (i+2)
    else
      "残りの処理"

  frec 1L 0 // 呼び出し

あとは地道に各iに対して前後を比べて処理します. 公式解説の判定をミスなく実装するだけです.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
  let rec frec acc i =
    if i=N then acc
    elif i=0 then if isVertical i then frec (acc.*3L) (i+1) else frec (acc.*6L) (i+2)
    else
      match isVertical (i-1), isVertical i with
        | true,true   -> frec (acc.*2L) (i+1)
        | false,true  -> frec acc       (i+1)
        | true,false  -> frec (acc.*2L) (i+2)
        | false,false -> frec (acc.*3L) (i+2)
  frec 1L 0

読みづらくも書きにくくもなく, 程々の長さの実装で問題はないでしょう.

解説2

公式解説を参考にHaskell実装を参考に実装します.

方針

大事なのは縦並びか横並びかで, 文字が続くかどうかを判定すればよく, いちいち二つの文字列を比べなくても一つの文字列だけ見れば判定できます. 一つの文字列を見て縦並び・横並びを判定したリストを作っておいて, 前後のペアを順に確認すれば目的の処理が完遂できます.

本質的には変わりませんが, こちらは再帰ではなくfoldで実装します.

補助関数

解説1と同じ補助関数を準備します.

1
2
  let MOD = 1_000_000_007L
  let (.*) x y = (x*y)%MOD

文字列の処理

F#のList.groupと違い, HaskellのData.List.groupは文字列を先頭から見て同じ文字が続く限りグループ化する関数です. 具体的には次のような挙動を取ります.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
#r "nuget: FsUnit"
open FsUnit

    let rec group = function
      | [] -> []
      | x::xs ->
        let ys = List.takeWhile ((=) x) xs
        let zs = List.skipWhile ((=) x) xs
        (x::ys)::group zs
    group (List.ofSeq "Mississippi") |> should equal [['M'];['i'];['s';'s'];['i'];['s';'s'];['i'];['p';'p'];['i']]

ここで定義した再帰関数のgroupがHaskellのData.List.groupのF#実装です. これを使って文字のリストに分割し, 内部の各リストの長さを取れば1のときは縦並び, 2のときは横並びです.

1
  let patterns = S1 |> Seq.toList |> group |> List.map (List.length)

サンプルの実行結果は次の通りです.

1
2
3
4
5
6
#r "nuget: FsUnit"
open FsUnit

let S1 = "RvvttdWI"
S1 |> Seq.toList |> group |> should equal [['R'];['v';'v'];['t';'t'];['d'];['W'];['I']]
S1 |> Seq.toList |> group |> List.map (List.length) |> should equal [1;2;2;1;1;1]

大枠

先程定義したpatternsを処理します. 初項によって初期値は3か6か変わります. 縦か横かは既に判定済みなため, 前後のペアをList.pairwiseで素直に作って順次確認すれば十分です. これをまとめると次のようにfoldが書けます.

1
2
3
  let patterns = S1 |> Seq.toList |> group |> List.map (List.length)
  let hp = List.head patterns
  List.pairwise patterns |> List.fold f (if hp=1 then 3L else 6L)

関数fは解説1と本質的に同じで次のように書けます.

1
2
3
4
5
  let f acc = function
    | (1,1) -> acc.*2L
    | (1,2) -> acc.*2L
    | (2,1) -> acc
    | _     -> acc.*3L

全体をまとめましょう.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
let solve N (S1:string) =
  let MOD = 1_000_000_007L
  let (.*) x y = (x*y)%MOD

  let rec group = function
    | [] -> []
    | x::xs -> let ys = List.takeWhile ((=) x) xs in let zs = List.skipWhile ((=) x) xs in (x::ys)::group zs
  let f acc = function
    | (1,1) -> acc.*2L
    | (1,2) -> acc.*2L
    | (2,1) -> acc
    | _     -> acc.*3L

  let patterns = S1 |> Seq.toList |> group |> List.map (List.length)
  let hp = List.head patterns
  List.pairwise patterns |> List.fold f (if hp=1 then 3L else 6L)

let N = stdin.ReadLine() |> int
let S1 = stdin.ReadLine()
solve N S1 |> stdout.WriteLine