075 D - Face Produces Unhappiness¶

解説¶

考え方としてはユーザー解説の方がわかりやすいでしょう. 引用します.

で、これらを考えていくと、回転させるのは、ある同一方向を向いている塊を回転させれば良さそうということになる。やっと400点レベルにまで落ちてきた。方向が一致している区間を縮約するとLRLRLRやRLRLRLになっているはず。例えばLRLRLRの最初のRを回転させるとLLLRLRでLRLRとなり、方向が一致していない箇所が2つ減る。なので、LかRのどちらかを貪欲に回転させて、方向不一致の区間を減らしていったときの幸福人数が答え。幸福人数はN-(LかRのグループ数)となる。各グループで1つは幸福でないため。

あとはこれをどうコードに落とし込むかにかかっています.

最大値を計算する部分に集中します.

元からの幸福度を計算する. これは前後の向きが一致しているか, 各位置の前後のペアの文字を調べて確認すればよい.
部分列をうまく回転させると回転させた両端の2だけ幸福度が上がる. 特に最大2*Kだけ幸福度が上がる.

この和を取れば幸福度最大の状況の幸福度が計算できるはずです. ただしLLLLLRRRRRの例のような真の最大幸福度が実現される場合, 問題の制約によって端の人の幸福度の処理が必要で, この処理を忘れてはいけません.

実装1¶

F#の文字列は文字列のモジュールもある一方で文字のシーケンス(Seq)です. 文字列のモジュールにほしい処理がなくても, シーケンスの関数を拝借して処理できます. 実際Seq.pairwiseで前後ペアのシーケンスが取れるため, これで元の幸福度計算用の処理を進めればいいでしょう. 例えば次のような結果が得られます.

#r "nuget: FsUnit"
open FsUnit

"LRLR" |> Seq.pairwise |> should equal (seq [('L', 'R'); ('R', 'L'); ('L', 'R')])

前後ペアを取った結果のシーケンスから幸福度を計算するには, シーケンスのたたみ込みで和を取ればよく, 典型的にはSeq.foldで計算できます. ここではSeq.sumByを紹介します.

1	`let s = S \|> Seq.pairwise \|> Seq.sumBy (fun (a,b) -> if a=b then 1 else 0)`

これが処理の本体で, あとは次の通りです.

let solve N K S =
  let s = S |> Seq.pairwise |> Seq.sumBy (fun (a,b) -> if a=b then 1 else 0)
  min (s+2*K) (N-1)

let N,K = stdin.ReadLine().Split() |> Array.map int |> (fun x -> x.[0],x.[1])
let S = stdin.ReadLine()
solve N K S |> stdout.WriteLine

実装2¶

HaskellにはあってもF#にはない便利関数は数限りなくある一方, 珍しくHaskellだと前後ペアを作る便利関数がないようです. こういう場合はzipやzipWithを使うのが典型的な処理です. そしてHaskellコードの移植時に慣れていないとはまる部分でもあります. ちなみにHaskellのzipWithはF#だとSeq.map2です.

さてどうやって前後ペアを作るかというと, zipを使って二つのシーケンスをタプルのシーケンスにまとめます.

#r "nuget: FsUnit"
open FsUnit

Seq.zip [1;2] [3;4;5] |> should equal (seq [(1,3);(2,4)])

上の例のようにシーケンスのzipは二つのリストの長さが一致しなくても短い方に自動的に合わせてくれます. しかしリストや配列では長さが違うとエラーになるため注意してください.

これを使うと前後ペアは次のように作れます.

#r "nuget: FsUnit"
open FsUnit

let S = "LRLR"
(S, Seq.tail S) ||> Seq.zip |> should equal (seq [('L', 'R'); ('R', 'L'); ('L', 'R')])

あとは実装1と同じように処理すれば求める結果が得られます.