096 D - Make Them Even

共通の入出力

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

解説1: 破壊的・命令型の処理

採用するアルゴリズム

たまには完全命令型の処理も紹介します. アルゴリズムは公式解説とは少し変えます. まずは各行を左から順に処理して右端に集め, 残った右端は上から処理する形に変えます. 文章でわかりにくい場合は以下の実装を見ればすぐにわかるでしょう.

ちなみに入力をいちいち書き換える形で実装しているため, REPLで実行するたび入力の価を読み込み直すのが面倒でした.

結果を保存する変数Xa

特に深い理由はありませんが, ここではResizeArray<string>としてはじめから最終的に返す文字列の形で積みます. ついでに文字列生成関数も作ります.

1
2
  let toStr i j k l = sprintf "%d %d %d %d" i j k l
  let Xa = ResizeArray<string>()

各行を左から処理する

入力の値が奇数な場合, そこを-1して書き換えつつ, 右の価に+1して書き換えます.

1
2
3
4
5
6
  for i in 0..H-1 do
    for j in 0..W-2 do
      if Ia.[i].[j]%2 = 1 then
        Ia.[i].[j] <- Ia.[i].[j]-1
        Ia.[i].[j+1] <- Ia.[i].[j+1]+1
        Xa.Add(toStr (i+1) (j+1) (i+1) (j+2))

F#のジェネレーター(?)は0..Hで[|0..H|]とHまで作ってくれます. PythonやRustと挙動が違うため注意してください. はじめに書いたように一筆書き形式ではなく各行は右端で処理を止めるため, 列に関して0..W-2としている点に注意してください.

他の言語では+=で簡単に+1できる部分がいちいち全て書かなくてはいけません. ただこれは2022年時点で変更可能な変数が起こしてきた事故を受け, いろいろな言語は不変な変数を導入しています. 特にF#と同じく何も書かなければ標準で不変な仕様にしている言語さえ増えています. やってほしくない処理を面倒にしてそもそも敬遠させる言語設計です. これを極端にしたのがHaskellのモナド機構です.

右端の処理

単純に右端を上から処理します.

1
2
3
4
5
  for i in 0..H-2 do
    if Ia.[i].[W-1]%2 = 1 then
      Ia.[i].[W-1] <- Ia.[1].[W-1]-1
      Ia.[i+1].[W-1] <- Ia.[i+1].[W-1]+1
      Xa.Add(toStr (i+1) W (i+2) W)

特に言うべきことはないでしょう. 強いていうならIa.[i].[W-1] <- Ia.[1].[W-1]-1の更新は不要です.

出力用処理

これも特に言うことはありません.

1
  Xa.ToArray() |> fun Xa -> Array.append [|string Xa.Length|] Xa

解説2: 公式解説に沿った実装

一筆書き経路の構成

ここでは先頭の奇数行を左から読み, 偶数行を右から読む形にします. 配列処理上は一行目が配列の零行目になるため偶奇が反転します. もちろん配列の零行目を右から読み始めても構いません.

1
2
3
4
5
  let Ja =
    Ia |> Array.mapi (fun i Ra ->
      if i%2=0 then Ra |> Array.mapi (fun j v -> ((i+1,j+1),v))
      else Ra |> Array.mapi (fun j v -> ((i+1,j+1),v)) |> Array.rev)
    |> Array.concat

反転させている部分は添字を持っていないと面倒なため, 値だけではなく添字も持たせています. ついでに添字は入力Iaの添字ではなく, 問題指示の1-originの添字に変換しています. 一筆書き仕様に変えているため, 最後にArray.concatを使って二重配列から単なる配列に変換しました.

fold処理の大枠

一筆書きのJaを使ってfoldで処理します. 値の入れ替えは文字列化してリストで記録します.

問題は値の入れ替えともとの配列の値を見た書き換え処理です. もともと偶数であったとしても隣を書き換えた結果, 奇数として処理する必要が出てきます. 入力の配列の価を書き換えずに処理するには前の項の偶奇をfoldに積みます.

これらをまとめるとfoldで取り回す値は([],true,(0,0))とすればよいでしょう. はじめの値が変更した場所を積むリスト, 次の真偽値は前の値の偶奇判定結果, 最後の値は入力の配列の添字です.

これをもとに大枠は次のように書けます.

1
2
  (([],true,(0,0)), Ja) ||> Array.fold (fun (acc,b,(i,j)) ((k,l), v) -> "適当な処理")
  |> fun (s,_,_) -> (List.length s |> string)::(List.rev s)

最終的には最小処理回数も返す必要があり, それはリストの長さであるため, 文字列化して先頭に積みます. 破壊的な処理ではResizeArrayにAddで積みましたが, 今回はリストにconsで積んだため最後にList.revが必要です.

foldの中身

前の値が偶数か奇数か, 新たな値が偶数か奇数かで四通りの判断が必要です. 言葉よりも実装を見る方が速く正確でしょう.

1
2
3
4
5
6
7
  (([],true,(0,0)), Ja) ||> Array.fold (fun (acc,b,(i,j)) ((k,l), v) ->
      match (b, v%2=0) with
        | (true,true)  -> (acc,true,(k,l))
        | (true,false) -> (acc,false,(k,l))
        | (false,true) -> ((toStr i j k l)::acc,false,(k,l))
        | _            -> ((toStr i j k l)::acc,true,(k,l)))
  |> fun (s,_,_) -> (List.length s |> string)::(List.rev s)

前の値がtrue, つまり偶数だったなら変更はなくaccに値を積みません. ただしfoldで新たに来た値にその真偽を積み, 奇数だった場合は次の処理で変更を積みます.

前の値がfalseだったときを考えます. もとの値vが偶数だと変更処理が入って奇数になるため, bにfalseを積む必要があります.