079 D Handstand

解説

これも基本方針は公式解説です. 自力実装ではまり倒したため, 今回はPythonコードを参考にしました.

まずは前後で文字が切り替わる番地を取得しましょう. シンプルなのは次のようなfold処理です.

1
2
3
    ([0], [|0..N-2|])
    ||> Array.fold (fun acc i -> if S.[i]=S.[i+1] then acc else (i+1)::acc)
    |> List.rev |> List.toArray

公式解説の後半ではいくつかややこしい条件分岐処理があります. これをシンプルに処理するために番地にNを追加します.

1
2
3
4
5
  let Ia =
    ([0], [|0..N-2|])
    ||> Array.fold (fun acc i -> if S.[i]=S.[i+1] then acc else (i+1)::acc)
    |> fun xs -> N::xs
    |> List.rev |> List.toArray

これで公式解説で言うi_kを要素とする配列が作れました. あとはX_kの配列を作れば終わります.

配列を作ってからArray.maxを作っても構いません. ただ今回は添字に関する処理をしながら逐次最大値を計算していくだけで求める値が得られるため, はじめからfoldを使って処理します. 配列IaはNを追加していていわば余計な項を含んでいます. このため添字に関してやや面倒な処理が必要です. 具体的には次のように書きます.

1
2
3
4
5
  let l0 = Array.length Ia - 1
  (0, [|0..l0-1|])
  ||> Array.fold (fun acc i ->
    let j = min (i+2*K + (int S.[Ia.[i]] - int '0')) l0
    max acc (Ia.[j]-Ia.[i]))

foldはIa自身ではなくIaの添字の配列で回します. Nの追加があるため[|0..l0-1|]とループはIaの最後まで回らないようにします. ポイントはjの構成です. 解説のS_{i_k} = 0 or 1での添字の変化はint S.[Ia.[i]] - int '0'で対応します. さらに「k>rならi_k=N+1」の処理がまさにmin hoge l0の部分です. これで添字を作ればIa.[j]で必要な値が取れます.

TODO