Hard¶

068 D - String Equivalence¶

• created: 2022-11-30
• ご意見・ご要望はissue・プルリク用のGitHubまで
• GitHub上の対応ディレクトリ
• 公式ページ, Panasonic 2020 D - String Equivalence
• 公式解説, PDF

解説1¶

• 下記方針に基づいた最終実装例
• 実装を見ると特に明確なように, 長さNの標準形は長さN-1の文字列に一文字足して作られます.
• 出題例をもとに特に小さいNで実験してもわかります.
• 追加できる文字はaを先頭に, 各文字列の中の最大の文字の一つ次までです.

ここまでの情報をもとにすれば素直に実装できます. まず補助関数を二つ作ります.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#r "nuget: FsUnit"
open FsUnit

// ある文字の次の文字
let succ (c:char) = int c |> (+) 1 |> char
// 文字列の中の最大の文字の一つ次
let m xs = List.max xs |> succ

succ 'a' |> should equal 'b'
succ 'b' |> should equal 'c'
succ 'z' |> should equal '{'

m ['a'] |> should equal 'b'
m ['a';'b'] |> should equal 'c'

今回の問題の範囲では困らないためそのままにしているものの, succ 'z'の挙動が気になるなら適切に書き換えてください.

さて, 長さ2の標準形の一つabに対して長さ3の標準形を作りましょう. 関数mによってaからcまで追加できます. 文字の追加の仕方はいろいろあって文字列の連結で素直に後ろにつなげてもいいでしょう. ここでは文字列(.NETとしては文字の配列)を文字のリストにし, リストの連結もconsを使って前に追加します.

1
2
3

let xs = ['b';'a']
xs |> ['a'..(m xs)] |> List.map (fun c -> c::xs))
|> should equal [['a';'b';'a'];['b';'b';'a'];['c';'b';'a']]

長さ2の標準形はaaとabだから両方に作用させましょう.

1
2
3

let xss = [['a';'a'];['b';'a']]
xss |> List.map (fun xs -> ['a'..(m xs)] |> List.map (fun c -> c::xs))
|> should equal [[['a'; 'a'; 'a']; ['b'; 'a'; 'a']]; [['a'; 'b'; 'a']; ['b'; 'b'; 'a']; ['c'; 'b'; 'a']]]

これで長さ3の標準形が得られました. しかしこれはchar list list listです. 実際に欲しいのはstring listで, char listをstring = char[]に変える必要もあります.

リストのネストを一つ減らすのはList.concatで, List.collect = List.map >> List.concatを使ってつなげて書けます. char list -> stringは.NETレベルのメソッドSystem.String.Concatを使います. リストはほしい文字列の逆になっているからList.revの処理も必要です.

これを再帰でまとめると次の解答が得られます.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

let solve N =
  let succ (c:char) = int c |> (+) 1 |> char
  let m xs = List.max xs |> succ
  let rec frec n =
    if n=1 then [['a']]
    else frec (n-1) |> List.collect (fun xs -> ['a'..(m xs)] |> List.map (fun c -> c::xs))
  frec N |> List.map (List.rev >> System.String.Concat)

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

解説2: 末尾再帰¶

少し書き方を変えれば末尾再帰にできます. 結論だけ書くと次の通りです.

1
2
3
4
5
6
7
8
9

let solve N =
  let succ (c:char) = int c |> (+) 1 |> char
  let m xs = List.max xs |> succ
  let rec frec n acc =
    if n=1 then acc
    else acc |> List.collect (fun xs -> ['a'..(m xs)] |> List.map (fun c -> c::xs)) |> frec (n-1)
  frec N [['a']] |> List.map (List.rev >> System.String.Concat)

stdin.ReadLine() |> int |> solve |> List.iter stdout.WriteLine

069 C - Align¶

• created: 2022-11-30
• ご意見・ご要望はissue・プルリク用のGitHubまで
• GitHub上の対応ディレクトリ
• 公式ページ, Tenka1 Programmer Contest C - Align
• 公式解説, PDF

解説¶

• 下記方針に基づいた最終実装例

はじめに¶

公式解説の他にもいくつか解答を見ていると, 偶奇で場合分けをしているコードもあれば, 一本で計算しきっているコードもありました. ただ私にはあまり直観的でなくすっと理解しにくかったため, ここではcojnaさんのコード例を参考にした実装を紹介します.

簡単な方針¶

大きな数値から小さな数値を引いた方がよいのは明らかです. ソートして大きい数のリストhsと小さい数のリストlsにわけ, 大きい数と小さい数を順に並べ続ければいいでしょう. 特に分けたリストを再帰的に先頭から取れば十分です.

問題は全要素数が奇数の場合の処理で, hsとlsから一つずつ取り続けて余った項をどこに置くかが問題です.

具体例で実装¶

入力例1で上の方針を追いかけます.

1

let N, Aa = 5, [|6L;8L;1L;2L;3L|]

まずは「ソートして大きい数のリストhsと小さい数のリストlsにわけ」の部分を実装します.

1
2
3
4
5
6

#r "nuget: FsUnit"
open FsUnit

let (xs,ys) = Aa |> Array.sort |> Array.toList |> List.splitAt (N/2)
xs |> should equal [1L; 2L]
ys |> should equal [3L; 6L; 8L]

大きい方は大きい順に取るためList.revで順序を反転します.

1
2
3
4
5

#r "nuget: FsUnit"
open FsUnit

let zs = ys |> List.rev
zs|> should equal [8L; 6L; 3L]

あとはxsとzsの先頭から再帰的に処理します. 再帰関数をfrecとして次のような呼び出しを前提にしましょう.

1
2
3
4

let (xs,ys) = Aa |> Array.sort |> Array.toList |> List.splitAt (N/2)
let (l,ls) = (List.head xs, List.tail xs)
let (h,hs) = ys |> List.rev |> fun zs -> (List.head zs, List.tail zs)
frec (h-l) l h (ls,hs)

はじめから初項を分離しなくてもいいとは思いますが, cojnaコードに合わせています. h-lの部分が結果を積むaccumlator変数です. hはhigh, lはlowで値の大小の分割を表しています. 最後の(ls,hs)はタプルにせず分けても構いません. 次の実装を前提にタプルにしています.

さて, 再帰関数の本体を考えましょう.

1
2
3
4

let rec frec acc low high = function
  | (l::ls),(h::hs) -> frec (acc + h-low + high-l) l h (ls,hs)
  | [],[h] -> acc + ???
  | _,_ -> acc

functionの部分は次の省略表記です.

1
2
3
4
5

let rec frec acc low high (xs,ys) =
  match (xs,ys) with
    | (l::ls),(h::hs) -> frec (acc + h-low + high-l) l h (ls,hs)
    | [],[h] -> acc + ???
    | _,_ -> acc

これは次のように書いても構いません.

1
2
3
4
5

let rec frec acc low high xs ys =
  match (xs,ys) with
    | (l::ls),(h::hs) -> frec (acc + h-low + high-l) l h ls hs
    | [],[h] -> acc + ???
    | _,_ -> acc

以下前者のコードを前提に考えます. まずパターンマッチのmatchの第一行から考えましょう.

1
2

let rec frec acc low high xs ys =
  (l::ls),(h::hs) -> frec (acc + h-low + high-l) l h ls hs

まさにリストを先頭と残りに分割して処理しています. 再帰呼び出しのacc + h-low + high-lの項は, 一つ前の先頭の項に対して大きい数と小さい数の差を取るそのままの処理です. low, high, xs, ysの項も分割した項をそのまま積めば問題ありません.

残り二行を確認しましょう.

1
2
3
4

let rec frec acc low high xs ys =
  match (xs,ys) with
    | [],[h] -> acc + ???
    | _,_ -> acc

[],[h]は項数が奇数の場合の余りの処理で, 最後の_,_が項数が偶数の場合の処理です. 後者は積み切った値を素直に返せばよく何も考える必要はありません. したがってあとは一つ余った項の処理だけです.

結論から言えばmax (h-low) (high-h)です. はじめにsplitAt (N/2)でわけました. この分け方で最後の項がlsとhsのどちらに入るか変わります. どうしても揺れが起こるためmaxでその揺れを吸収しています.

入力例1と新たに作った以下のもう一つの入力例をもとに確認しましょう.

入力例1での最後の余りの処理は次のようになります.

1
2
3
4
5
6
7
8
9

xs -> [1L; 2L]
ys -> [8L; 6L; 3L]

low -> 2L
high -> 6L
h -> 3L

h-low -> 1L
high-h -> 3L

したがってこちらはhigh-hを取るべきです. 具体的に全体としてどのような並び方を選んだのかを考えるのも大事です. 実際には次のようになっています.

• h-low: 8 1 6 2 3
• high-h: 1 8 2 6 3

つまり初項を大きい方から取るか, 小さい方から取るかが最後の取り方で決まります.

さて, 新たな入力例はlet Aa = [|1L;4L;5L|]とします. この余りの処理は次のようになります.

1
2
3
4
5
6
7
8
9

Aa -> [|1L;4L;5L|]
xs -> [1L]
ys -> [5L;4L]

low -> 1L
high -> 5L
h -> 4L
h-low -> 3L
high-h -> 1L

入力例1と違ってh-lowを取るべきです. 具体的に全体としてどのような並び方を選んだかと言えば次の通りです.

• h-low: 5 1 4
• high-h: 1 5 4

もちろん他の可能性がないかも考えるべきではありますが, 前の項との差を取るアルゴリズムの組み方からしてありうるのはこの二通りしかありません. あとはこれを一般的にきちんと書き切れば適切なコードができます.

070 C - Snuke Festival¶

• created: 2022-12-01
• ご意見・ご要望はissue・プルリク用のGitHubまで
• GitHub上の対応ディレクトリ
• 公式ページ, ABC 077 C - Snuke Festival
• 公式解説, PDF

自分用の記録¶

公式解説では二分探索を提案しています. それぞれ次のような解答例があります.

• F#
• Haskell

F#版はstart-1やstop+1を外して書けないかと思って轟沈し, Haskell版も番兵なしで書けないかと思って轟沈し, 自力実装もTLEではまり倒したため, CやPythonなどのコードを見つついろいろ試し, 最終的にはRustのコードを参考にしました. ここでもこれに基づいた解説をつけます.

解説¶

• 下記方針に基づいた最終実装例

参考にした命令型のRustのコードの焼き直しを説明したあと, 関数型に書き換えたバージョンを説明します.

まずは公式解説と同じく配列で入力を取ってソートします. あとの都合があるためBaもソートします.

1
2
3

  let Xa = Aa |> Array.sort
  let Ya = Ba |> Array.sort
  let Za = Ca |> Array.sort

以下ソートした配列Xa, Ya, Zaで考えます. 何も考えずRustを直移植した結果は次の通りです.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

  let Xa = Aa |> Array.sort
  let Ya = Ba |> Array.sort
  let Za = Ca |> Array.sort
  let mutable i = 0
  let mutable k = 0
  let mutable ans = 0L
  for b in Ya do
    while i<N-1 && Xa.[i+1]<b do i <- i+1
    while k<N-1 && Za.[k]<=b  do k <- k+1
    if Xa.[i]<b && b<Za.[k] then ans <- ans + (int64 (i+1) * int64 (N-k))
  ans

アルゴリズム上のポイントはBaのソートとi, kの引き継ぎです. AaとCaをソートしているため配列の引数からそのまま個数が計算できます. さらにBaのソートのおかげで, Baに関する添字をjとすれば, j+1に関する結果を計算するときjで計算したiとkから再開でき, 余計な計算が省略できます. Zaの関する計算は問題の素直な不等式ではなくZa.[k]<=bにした上でN-kを計算しています. (解説を書きながら気づいたのですが, Array.sortDescendingを使えば問題の条件のまま計算できます.)

F#コードのポイントはans <- ans + (int64 (i+1) * int64 (N-k))にもあります. ここでint64 (i+1) * (N-k)としてしまうとWAが出ます. 実際に出てはまり倒しました. 理由はintで(i+1) * (N-k)が計算されるとオーバーフローを起こす場合があり, このかけ算自体もint64で計算しないといけないからです. 配列の添字はintでint64にはできないため, 配列の添字を使った計算には注意が必要です.

命令型での焼き直しができました. 一般的には命令型の方が速くメモリ効率もよいため, これで終わらせても問題ありません. しかし関数型競技プログラミングを標榜している以上やはり関数型に書き換えます.

まずはfor b in Ya doから書き換えます. 最終的にはlet mutable ans相当の値を返したいため, foldを使って処理すればいいでしょう. 具体的には次のように書けます..

1
2
3
4
5
6
7

  let mutable i = 0
  let mutable k = 0
  let mutable ans = 0L
  (0L, Ya) |> Array.fold (fun acc b ->
    while i<N-1 && Xa.[i+1]<b do i <- i+1
    while k<N-1 && Za.[k]<=b  do k <- k+1
    if Xa.[i]<b && b<Za.[k] then acc + (int64 (i+1) * int64 (N-k)) else acc)

F#では最後に計算した式の値を返してくれるため, これを関数の最後に書けば問題ありません. ポイントはifに対してelse節を書いて値を返す部分です. そもそもelse節がないとエラーを吐いてくれるため, そこで気付けるでしょう.

あとはmutableのiとkをうまく処理する必要があります. 積んだ結果を引き回す必要があるため, accをタプルに変えて積む必要があります.

ループは一般に再帰で書き換えられます. これもelse節で値を返す必要があり, 特に次のように書けます.

1
2

  let rec a i b = if i<N-1 && Xa.[i+1]<b then a (i+1) b else i
  let rec c k b = if k<N-1 && Za.[k]<=b  then c (k+1) b else k

関数名は一文字でaとcです. 短いプログラムだからこれで十分意図は伝わるでしょう. 気にいらなければもう少し長く説明的な名前でも構いません. この関数を使うとfoldは次のように書き換えられます.

1
2
3
4
5

  ((0L,0,0),Ya) ||> Array.fold (fun (acc0,i0,k0) b ->
    let i = a i0 b
    let k = c k0 b
    let acc = if Xa.[i]<b && b<Za.[k] then acc0 + (int64 (i+1) * int64(N-k)) else acc0
    (acc,i,k)) |> fun (acc,_,_) -> acc

accが(acc,i,k)に書き換わりました. 計算結果もタプルで返します. 先程と違い, foldの最終的な返り値もタプルになってしまうため, 最後に必要な第一要素だけ取り出す関数を噛ませてあります. 最終的な全体実装は次の通りです.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

let solve N Aa Ba Ca =
  let Xa = Aa |> Array.sort
  let Ya = Ba |> Array.sort
  let Za = Ca |> Array.sort
  let rec a i b = if i<N-1 && Xa.[i+1]<b then a (i+1) b else i
  let rec c k b = if k<N-1 && Za.[k]<=b  then c (k+1) b else k
  ((0L,0,0),Ya) ||> Array.fold (fun (acc0,i0,k0) b ->
    let i = a i0 b
    let k = c k0 b
    let acc = if Xa.[i]<b && b<Za.[k] then acc0 + (int64 (i+1) * int64(N-k)) else acc0
    (acc,i,k)) |> fun (acc,_,_) -> acc

let N = stdin.ReadLine() |> int
let Aa = stdin.ReadLine().Split() |> Array.map int64
let Ba = stdin.ReadLine().Split() |> Array.map int64
let Ca = stdin.ReadLine().Split() |> Array.map int64
solve N Aa Ba Ca |> stdout.WriteLine

コードをもっと短くしたければ次のように読み込み時点でソートできます.

1
2
3

let Aa = stdin.ReadLine().Split() |> Array.map int64 |> Array.sort
let Ba = stdin.ReadLine().Split() |> Array.map int64 |> Array.sort
let Ca = stdin.ReadLine().Split() |> Array.map int64 |> Array.sort

071 C - Linear Approximation¶

• created: 2022-12-02
• ご意見・ご要望はissue・プルリク用のGitHubまで
• GitHub上の対応ディレクトリ
• 公式ページ, ABC 077 C - Snuke Festival
• 公式解説, PDF

解説¶

• 下記方針に基づいた最終実装例

公式解説通り入力Aaをシフトした配列をBaとします. 解説の便宜のためBaをソートした配列をCaとしましょう.

公式解説通りに実装すれば問題ありません. 他の人のコードを見ていると中央値の扱いにぶれがあるようです. 単にBa.[N/2]だけとしているコードもあれば, 偶奇でわけたコードもあります.

ちなみに私はさらに違う処理にしました. 選ぶべきbが整数でなければならないため, Nが奇数のときはCa.[N/2], Nが偶数のときはCa.[N/2]とCa.{N/2-1}を中央値の候補としています. もちろんNが偶数のときは二つの値を計算して小さい方を取ります.

どう書くとすっきりするかは人によるものの, 私は中央値の候補を配列にして処理しました. 具体的には次のように中央値の候補を作っています.

1
2

  let Ba = Aa |> Array.mapi (fun i a -> a - (int64 (i+1)))
  let Ma = Ba |> Array.sort |> fun Ba -> if N%2=1 then [|Ba.[N/2]|] else [|Ba.[N/2-1];Ba.[N/2]|]

最終的な悲しさの最小値は中央値の配列Maから次のように計算しています.

1

  Ma |> Array.map (fun b -> Ba |> Array.sumBy (fun x -> abs(x-b))) |> Array.min

よほど複雑な処理をかませる場合は適切な対処が必要ですが, Array.map f |> Array.sumはArray.sumByで書くとすっきりします.

私がはまり倒したため念のため書いておきます. 次のように書くとMaの値を取ってしまい正しい悲しさの最小値が得られません.

1

  Ma |> Array.minBy (fun b -> Ba |> Array.sumBy (fun x -> abs(x-b)))

おまけ¶

次の二つのコードの結果が面白いです.

• https://atcoder.jp/contests/abc102/submissions/2783376
• 言語: F# (Mono 4.0)
• 実行時間: 207 ms
• メモリ: 35328 KB

1
2
3
4

let n = int (stdin.ReadLine())
let a = stdin.ReadLine().Split() |> Array.mapi (fun i x -> int64 x - int64 i - 1L) |> Array.sort
let b = if n % 2 = 0 then (a.[n / 2] + a.[n / 2 - 1]) / 2L else a.[n / 2]
printfn "%d" (Array.sumBy (fun x -> abs (x - b)) a)

• https://atcoder.jp/contests/abc102/submissions/2783237
• 言語: F# (Mono 4.0)
• 実行時間: 207 ms
• メモリ: 31932 KB

1
2
3
4

let n = int (stdin.ReadLine())
let a = stdin.ReadLine().Split() |> Array.mapi (fun i x -> int64 x - int64 i + 1L) |> Array.sort
let b = if n % 2 = 0 then (a.[n / 2] + a.[n / 2 - 1]) / 2L else a.[n / 2]
printfn "%d" (Array.fold (fun (l : int64) k -> l + abs (k - b)) 0L a)

違うのは最後の和を取る部分でsumByなのかfoldかです. 実行時間は変わらないものの消費メモリが一割違います. 少なくともMono 4.0でメモリ効率を考えるならfoldの方がよいようです.

そしてさらに私の提出コードも見てみましょう.

• https://atcoder.jp/contests/abc102/submissions/36920080
• 言語: F# (.NET Core 3.1.201)
• 実行時間: 154 ms
• メモリ: 49092 KB

1
2
3
4
5
6
7
8

let solve N Aa =
  let Ca = Aa |> Array.mapi (fun i a -> a - (int64 (i+1)))
  let Ba = Ca |> Array.sort |> fun Ba -> if N%2=1 then [|Ba.[N/2]|] else [|Ba.[N/2-1];Ba.[N/2]|]
  Ba |> Array.map (fun b -> Ca |> Array.sumBy (fun x -> abs(x-b))) |> Array.min

let N = stdin.ReadLine() |> int
let Aa = stdin.ReadLine().Split() |> Array.map int64
solve N Aa |> stdout.WriteLine

偶数項のとき和を二回取っているため明らかにこちらの方が遅いはずですが, Mono 4.0よりも高速です. Mono 4.0のリリースが2015年, .NET core 3.1.201のリリースが2021年で後者の方が新しいため, 処理系の高速化のおかげでしょう.

072 C - 4/N¶

• created: 2022-12-02 fri
• ご意見・ご要望はissue・プルリク用のGitHubまで
• GitHub上の対応ディレクトリ
• 公式ページ, TENKA1 2017 C - 4/N

数学から決まる議論¶

特に小さいNに対して大学受験でもよくある問題です. 数学の話でもあって数学系学習と並行した議論を目指す私のスタンスからは大事なため, 公式解説の議論を簡単にくり返します.

対称性によってどれから議論してもよいためまずはhから考えましょう. 必要条件からの絞り込みでhを小さい方から増やして具体的に確認し続ければよく, まさにアルゴリズミックに次のように議論を進めます.

• h=1として4/N - 1を計算する.
  • これは1/n+1/kに等しいはずだから再びn=1として左辺に移行する.
    • 4/N-1-1と1/kが等しくなる整数kが取れるか確認する.
  • 取れなければn=2で確認する.
    • 4/N-1/2-1と1/kが等しくなる整数kが取れるか確認する.
  • 取れなければn=3で確認する.
    • 4/N-1/2-1と1/kが等しくなる整数kが取れるか確認する.
  • ...
  • 順次n=hまで確認する.
• h=2として4/N-1/2を計算する.
  • ...

と続けます. 原理的にこれしか議論しようはないものの, 時間内に解けるかが懸念点です. そして問題文でh,n,w≤3500が保証されているため, この範囲内でけりが着くはずと思って全探索します. もちろん3つ全てでループするとTLEするため, 2つ決まれば3つ目は自動的に決まる性質を使って二重ループで片付けます.

解答1: 素直なループ¶

1つ求めればよいため, 1つ決まったら計算を停止させます. 命令型的なfor文とbreakを使えればよいのですが, 残念ながらF#にはbreakがないようで, 使うならwhileとフラグ管理です.

ただし命令型として素直なforとbreakがないだけです. Haskellの遅延リスト・遅延評価と同じく, 遅延評価してくれるseqを使いましょう. 次のような適切な書き方をすれば明示的なbreakが不要です.

1
2
3
4
5

  seq {
    for h in 1L..N do
      for k in 1L..M do
        if someJudge then yield value
  } |> Seq.head

for h in 1L..N doがカウントアップのforで, 二重ループだから二つ出てきます. 条件を満たした値を取る部分がif b then yield valueです. この場合はyieldキーワードはなくてもよいようですが手癖で書いています. 詳しくは公式のシーケンスを見てください. seqとコンピュテーション式による見慣れない構文には慣れるしかありません.

seq {...}でいわば遅延リストを作り, その先頭の値をSeq.headで取れば必要な計算だけで処理が終わります. Schemeのように有理数を処理してくれる言語もありますが, F#標準で有理数はないため整数の範囲でおさまるように標準的な対処を取ります. 適当なところで打ち切った数による積で構成する三つ目の整数がintに入る保証がないため, int64で計算する点に注意すれば, あとは特に問題ないでしょう. 結論としては次のようなコードで通ります.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

let solve N =
  seq {
    for h in 1L..3500L do
      for k in 1L..h do
        let d = 4L*h*k-N*(k+h)
        if d>0L && (N*h*k)%d=0L then yield (h,k,(N*h*k)/d)
  } |> Seq.head |> fun (h,k,w) -> [|h;k;w|]

let N = stdin.ReadLine() |> int64
solve N |> Array.map string |> String.concat " " |> stdout.WriteLine

出力処理は何となく既存の出力処理を流用するために配列にしました. タプルのまま次のようにも書けます.

1

solve N |> fun (h,n,k) -> printfn "%d %d %d" h n k

解説2: 再帰¶

「競技プログラミングのためのF#入門」で無限ループを含めてループは再帰で書けると書きました. 実際ここでも再帰で書けます. 提出結果を見ると再帰の方がメモリを食っています. 2022-12時点では効率を求めるよりも通るコードを書く, さらには基本的なアルゴリズムの教育用コンテンツを作る方に主眼があるため, 別解として再帰によるコードも紹介します.

forのコードを素直に書き換えればよく, 結論としては次のように書けます.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

let solve N =
  let rec frec h k =
    let d = 4L*h*k - N*(k+h)
    if d>0L && (N*h*k)%d=0L then (h,k,(N*h*k)/d)
    elif k<h then frec h (k+1L)
    else frec (h+1L) 1L
  frec 1L 1L

let N = stdin.ReadLine() |> int64
solve N |> fun (h,k,w) -> printfn "%d %d %d" h k w

ポイントはもちろんifの条件分岐です. 最初に条件をみたして値を返すか(停止するか)判定し, 停止しなければhかkを適切にカウントアップします. ここでは上記のseq+ループアルゴリズムに合わせました.

コードが読みにくくなるためここでは勧めませんが, 例えば次のようにまとめて書けます.

1
2
3
4
5

let solve N =
  let rec frec h k = let d = 4L*h*k - N*(k+h) in if d>0L && (N*h*k)%d=0L then (h,k,(N*h*k)/d) elif k<h then frec h (k+1L) else frec (h+1L) 1L
  frec 1L 1L

stdin.ReadLine() |> int64 |> solve |> fun (h,k,w) -> printfn "%d %d %d" h k w

さらに次のようにも書けます.

1
2

let solve N = let rec frec h k = let d = 4L*h*k - N*(k+h) in if d>0L && (N*h*k)%d=0L then (h,k,(N*h*k)/d) elif k<h then frec h (k+1L) else frec (h+1L) 1L in frec 1L 1L
stdin.ReadLine() |> int64 |> solve |> fun (h,k,w) -> printfn "%d %d %d" h k w

let ... inはOCamlのコードでよく出てきます.

073 C - Strange Bank¶

• created: 2022-12-03 sat
• ご意見・ご要望はissue・プルリク用のGitHubまで
• GitHub上の対応ディレクトリ
• 公式ページ, ABC099

解答1: 公式解説, シンプルなループ処理¶

公式解説の処理をF#で単純に書き直すならこのコードのようになるでしょう.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

open System
let n : int = int(Console.ReadLine())
let mutable res = n
let mutable i = 0
while i <= n do
    let mutable cc = 0
    let mutable t = i
    while t > 0 do
        cc <- cc + t % 6
        t <- t / 6
    t <- n - i
    while t > 0 do
        cc <- cc + t % 9
        t <- t / 9
    if res > cc then
        res <- cc
    i <- i + 1
printfn "%d" res

最初のwhile i <=n doはforで簡単に書き換えられるとして, 可変変数を不変変数に置き換えつつ, 内部のwhile t > 0 doをどう関数型らしく書き換えるかがまず問題です. F#解説で書いたように再帰で書き換えます.

tは各whileの直前で設定し直していて最終的にccを返せばよいため, tは単純に関数の入力パラメータにすればよいでしょう. 6で割るwhileループを表す再帰関数は次のように書けます.

1

let rec frec cc t = if t>0 then frec (cc+t%6) (t/6) else cc

正の数を正の数で割り続けたあまりは0になるため, then節が短くなるように条件式を書き換えています. 9で割り続ける処理はmod kのkが変わるだけで同じ処理です. それもまとめた再帰関数は次のように書けます.

1

let rec frec k cc t = if t>0 then frec k (cc+t%k) (t/k) else cc

次にメインのwhile i<=n doを考えます. これは最終的に積んだ値resを返すループだからfoldを使えばよいでしょう. 結論としては次のように書けます.

1
2
3
4
5
6

let solve N =
  let rec frec k cc t = if t>0 then frec k (cc+t%k) (t/k) else cc
  (N,[|0..N|]) ||> Array.fold (fun res i ->
    let cc6 = frec 6 0 i
    let cc9 = frec 9 cc6 (N-i)
    if res <= cc9 then res else cc9)

最後のif式ではelseをつけ忘れないようにしましょう. もちろんつけないと型エラーで動きません.

最後に, そもそも意味がわからずはまり倒したため, let cc6 = frec 6 0 i; let cc9 = frec 9 cc6 (N-i)で何をしているかを説明する自分用のメモ. まず次のように書き換えて考えるといいでしょう.

1
2

    let cc6 = frec 6 0 i
    let cc9 = frec 9 0 (N-i)

こうすると次のように意味がはっきりします.

• cc6: iを6のベキだけで処理した回数
• cc9: 残りのN-iを9のベキだけで処理した回数

あとは全探索の部分です. ある数iを6のベキで処理し切ったら残りのN-iは9のベキで処理するしかありません. これを全探索で全てのiに対して確認しています.

解説2: ユーザ解説, メモ化再帰¶

ユーザ解説はDPで解いています. 私の前にF#でDPで解いている人がいます. 実行時間も短いためこれも考えてみましょう. 上記コードはちょっと長いため単純化したコードを紹介します. 2022-12時点で全てではないものの, Educational DP Contest / DP まとめコンテストにF#で取り組んだ結果があるため, こちらも参考にしてください. (2022-12時点では特にHaskell・OCamlコードを焼き直しただけで, 私は自力でDPを解く力量がありません.)

まずF#版のarray6とarray9にあたる配列生成を考えます. もちろんいくつか書き方はあり, 比較的簡潔なのは次のコードでしょうか.

1
2
3

  let rec p k x acc = if x>N then (acc-1) else p k (k*x) (acc+1)
  let array6 = [|0..(p 6 1 0)|] |> Array.map (pown 6)
  let array9 = [|0..(p 9 1 0)|] |> Array.map (pown 9)

再帰関数のpはベキを何回まで取ればいいか計算する関数です.

次は本丸のメモ化再帰です. 定型的な書き方があるため, コピペで使えるようにReference.fsxにメモしています.

まずはコードを示してそれにコメントしましょう.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

  let memorec f =
    let memo = System.Collections.Generic.Dictionary<_,_>()
    let rec frec j =
      match memo.TryGetValue j with
        | exist, value when exist -> value
        | _ -> let value = f frec j in memo.Add(j, value); value
    frec
  let count frec n =
    if n=0 then 0
    else
      let c1 = n - (array6 |> Array.findBack (fun x -> x<=n))
      let c2 = n - (array9 |> Array.findBack (fun x -> x<=n))
      1 + min (frec c1) (frec c2)
  (memorec count) N

メモ化の部分がlet memorec fです. let memo = System.Collections.Generic.Dictionary<_,_>()はF#のMapではなく.NETの辞書を読んでいます. memo.Addで破壊的に書き換わってくれた方が便利だからです. let rec frec jはメモがあればその値を返し, ない場合は値を詰めて返します.

処理の本体がcountです. 第一引数のfrecはmemorec中でfrecとして呼び出す関数で, 対応を明確にするために名前を揃えています.

まずc1から考えましょう. 6のベキで大きい方から削るため, (array6 |> Array.findBack (fun x -> x<=n))で削れる中で最大の数を取ります. c1は削って残った数で, frec c1でメモ化再帰または動的計画法でc1に辿り着くまでの最小操作回数が取れます. 実際にcount関数のelse節でprintfn "%A" (c1,c2,frec c1, frec c2)で出力して確認してみてください.

同じ計算を9に対しても適用して, 小さい方を取れば最小回数が得られます. 最後に1を足すのはmin (frec c1) (frec c2)は最終ステップ一手前の値だからです.

あとはcountにmemorecでガワをかぶせて計算すれば求める結果が得られます. メモ化のための辞書memoをクロージャーmemorecで隠蔽している分コードが読みにくいかもしれません. オリジナルは最終的に呼び出す関数が素直な再帰になっているため, こちらの方がわかりやすいかもしれません.

074 D - Harlequin¶

• created: 2022-12-03 sat
• ご意見・ご要望はissue・プルリク用のGitHubまで
• GitHub上の対応ディレクトリ
• 公式ページ, CADDI 2018
• 公式解説, PDF

解説¶

特記事項はなく, 解説通り次のように書けばいいでしょう.

1
2
3
4
5

let solve = Array.forall (fun x -> x%2=0) >> fun b -> if b then "second" else "first"

let N = stdin.ReadLine() |> int
let Aa = Array.init N (fun _ -> stdin.ReadLine() |> int)
solve Aa |> stdout.WriteLine

関数の合成としてsolveの引数を省略して書いています. 関数の合成は>>です. 数学での関数合成は$f \circ g$で$g$を作用させてから$f$を作用させます. F#でこれを書きたいならf << gです. パイプラインの発想と同じく左から右に流して書くにはg >> fです.

上記のsolveは引数をつけると次のように書けます.

1

let solve Aa = Aa |> Array.forall (fun x -> x%2=0) |> fun b -> if b then "second" else "first"

「全て偶数」の代わりに「奇数が存在する」と書きたければ次のようにも書けます.

1

let solve = Array.exists (fun x -> x%2=1) >> fun b -> if b then "first" else "second"

075 D - Face Produces Unhappiness¶

• created: 2022-12-12 mon
• ご意見・ご要望はissue・プルリク用のGitHubまで
• GitHub上の対応ディレクトリ
• 公式ページ
• 公式解説

解説¶

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

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

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

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

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

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

実装1¶

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

1
2
3
4

#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)

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

1
2
3
4
5
6
7

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を使って二つのシーケンスをタプルのシーケンスにまとめます.

1
2
3
4

#r "nuget: FsUnit"
open FsUnit

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

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

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

1
2
3
4
5

#r "nuget: FsUnit"
open FsUnit

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

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

076 C - たくさんの数式¶

• created: 2022-12-12 mon
• ご意見・ご要望はissue・プルリク用のGitHubまで
• GitHub上の対応ディレクトリ
• 公式ページ
• 公式解説

解説¶

文字列がもっと長いと気になってはくるものの, (末尾再帰ではない)再帰でさっと書いてしまえばいいでしょう. HaskellではfoldMなどで豪快な処理が書けるものの, (今の私のF#の腕前では)シンプルな移植ができないのも理由の一つです.

計算用の再帰関数は次のように実装できます.

1
2
3

  let rec frec a y = function
    | [] -> a+y
    | x::xs -> frec (a+y) x xs + frec a (y*10L + x) xs

入力の文字列を一桁数値のリストに変換する処理は次のように書けます.

1

  let ys = S |> Seq.map (fun c -> int64 c - int64 '0') |> Seq.toList

ここで1を単にint64 cだけにすると49Lが返ってきてはまり倒します. 上のようにint64 '0'を引いて整数として1Lが返るようにするか, c |> string |> int64のように文字列にしてからint64を通しましょう. 例を見るとわかるようにInt32の範囲を飛び越えるため, オーバーフロー対策でInt64を使うのは必須です.

その他¶

逐次計算していくのではなく, いったん文字列から必要な数を切り出す(ベキ集合を作る)タイプの実装でHaskellコードを見ると, replicateMを使ってブーリアンのベキ集合を使ってどの文字を取ってくるか判定しています. Reference.fsxをreplicateMかベキ集合で検索すれば対応する関数のリスト版実装があります. これを参考にHaskellコードの移植を考えてもいいでしょう.

077 A - 01 Matrix¶

• created: 2022-12-12 mon
• ご意見・ご要望はissue・プルリク用のGitHubまで
• GitHub上の対応ディレクトリ
• 公式ページ
• 公式解説

解説¶

アルゴリズムを考えるのが大変なだけで, 公式解説通りに素直に実装すればよいでしょう.

F#の文字列連結は単純な+でよく, 連続した文字からなる文字列はString.init (W-A) (fun _ -> "1")で作れます. List.iterやfor文で順次stdout.WriteLineしても構いません. あえて文字列のリスト(や配列)を作りたければ, 例えば次のような形でB行とH-B行分の文字列を生成すればいいでしょう.

1
2
3

let solve H W A B =
  List.init B (fun _ -> String.init A (fun _ -> "0") + String.init (W-A) (fun _ -> "1"))
  @ List.init (H-B) (fun _ -> String.init A (fun _ -> "1") + String.init (W-A) (fun _ -> "0"))

F#でのリストの連結はList.appendまたは@演算子です.

TODO¶

• 配列やシーケンスにしたときどれだけ速度が変わるか?

078 C - K-th Substring¶

• created: 2022-12-13 tue
• ご意見・ご要望はissue・プルリク用のGitHubまで
• GitHub上の対応ディレクトリ
• 公式ページ
• 公式解説

解説¶

公式解説の方針そのままの実装を考えます. 条件をみたす部分文字列をどう作るかがポイントで, 今回の条件ではとにかく手当たり次第に作ると諦めるのが肝心です.

文字列の各i番目からi+K-1番目までの部分文字列を作り倒すには, 例えば次のように書けばよいでしょう.

1
2
3
4
5

  let S,K = "aba",4
  let n = S.Length - 1
  [|0..n|] |> Array.map (fun i -> [|i..(min n (i+K-1))|] |> Array.map (fun j -> S.[i..j]))

  // val it: string[][] = [|[|"a"; "ab"; "aba"|]; [|"b"; "ba"|]; [|"a"|]|]

この返り値はもちろん文字列の配列の配列で, 型はstring[][]です. これをフラットにする, つまりstring[]にするにはArray.concatを作用させればよいです. しかし標準でArray.mapの結果をArray.concatしてくれる関数Array.collectがあるため, 素直にこれを使えばいいでしょう.

1
2
3
4
5

  let S,K = "aba",4
  let n = S.Length - 1
  [|0..n|] |> Array.collect (fun i -> [|i..(min n (i+K-1))|] |> Array.map (fun j -> S.[i..j]))

  // val it: string[] = [|"a"; "ab"; "aba"; "b"; "ba"; "a"|]

上の出力を見るとわかるように"a"が二つ出てきます. あとはこの重複をArray.distinctで潰し, Array.sortしてK番目を取れば終わりです.

079 D - Handstand¶

• created: 2022-12-13 tue
• ご意見・ご要望はissue・プルリク用のGitHubまで
• GitHub上の対応ディレクトリ
• 公式ページ
• 公式解説

解説¶

これも基本方針は公式解説です. 自力実装ではまり倒したため, 今回は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¶

• ユーザー解説の尺取り法実装

080 C - Remainder Reminder¶

• created: 2022-12-14 wed
• ご意見・ご要望はissue・プルリク用のGitHubまで
• GitHub上の対応ディレクトリ
• 公式ページ

解説¶

公式解説通りに素直に実装します. 強いて言うならmapしてからsumではなく, 一気にsumByしてしまうと少し速くなります. 例えば次のように書くといいでしょう.

1
2

let solve N K =
  if K=0L then N*N else [|1L..N|] |> Array.sumBy (fun b -> (N/b) * max 0L (b-K) + max (N%b-K+1L) 0L)

081 C - Boxes and Candies¶

• created: 2022-12-14 wed
• ご意見・ご要望はissue・プルリク用のGitHubまで
• GitHub上の対応ディレクトリ
• 公式ページ

解説¶

公式解説通りに素直に実装します. 競プロと言えどプログラミングである以上, 簡潔さと明確さを兼ね備えてほしいため, 条件分岐をどうすっきりまとめるかが焦点です. 特に今回はややこしい条件分岐はmaxでまとめられます. 私自身, 執筆時点でまだまだ不慣れな部分です.

さっと正解を書けたとしても, 他の人, 特にショートコードを書く人達のコードをいくつか眺めると勉強になります.

結論としては次のように書けばよいでしょう.

1
2
3
4

let solve N x Aa =
  ((0L,0L),Aa)
  ||> Array.fold (fun (acc,a0) a -> let c = max (a0+a-x) 0L in (acc+c, a-c))
  |> fst

総和がほしいタイプのループ処理だからfoldですっきり書けます.

082 C - Different Strokes¶

• created: 2022-12-14 wed
• ご意見・ご要望はissue・プルリク用のGitHubまで
• GitHub上の対応ディレクトリ
• 公式ページ

解説¶

公式解説通りに素直に実装します.

今回入出力は次のように処理する前提で解説します.

1
2
3

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

降順ソートはArray.sortDescendingとArray.sortByDescendingがあり, 今回は後者を使えばよいでしょう.

次は和を取る部分です. 配列はF#流の0はじまりとします. 公式解説では別途b_iの和を取っておくような形になっていました. しかし配列の添字が偶数ならa_iを, 奇数なら-b_iを足すようにすればb_iの和を別途用意する必要はありません.

問題は配列の添字をどう用意するかです. Array.indexedで元の配列Xaを添字づけてから処理する方法もあれば, 添字の配列でArray.foldやArray.sumByを回す方法もあります. ここでは次のようにArray.foldで添字を積む方法を取ります.

1
2
3
4
5

let solve Xa =
  Xa
  |> Array.sortByDescending (fun (a,b) -> a+b)
  |> Array.fold (fun (acc,i) (a,b) -> let c = if i%2=0 then a else -b in (acc+c, i+1)) (0L,0)
  |> fst

Array.foldで持ち回る変数として和のaccだけではなく添字のiも積みます. 添字にあたるiを削るため最後にfstで和だけを取っています.

Array.foldに食わせるラムダでlet c = hoge inを使っています. let inをうまく使うと一行でも見やすく書けて便利です. もちろん二行に分けて書いても構いません.

083 A - Darker and Darker¶

• created: 2022-12-15 thu
• ご意見・ご要望はissue・プルリク用のGitHubまで
• GitHub上の対応ディレクトリ
• 公式ページ

参考¶

• キューの効率的な実装 または私は如何にしてHaskellを止めてF#を愛するようになったか
• なぜ Haskell ではキューが軽んじられているか？

解説¶

破壊的な実装¶

公式解説通りに実装します. 今回のポイントは破壊的・非関数型的な実装です. F#には独自のキュー(関数型のキュー)がなく, .NETの破壊的なキューしかありません. 関数型のキューを自前実装するのも面倒です. 余程の強烈なこだわりでもない限り素直に.NET実装を使えばいいでしょう.

念のため書いておくと, いわゆる関数型言語でも効率が必要な場合は破壊的な実装を使います. 関数の内部など影響範囲が確実に限定されていれば問題はなく, それを突き詰めて関数とアクションの分離にまで持ち上げたのがHaskellです. AtCoderでHaskellの実装を見るとシンプルな実装はしづらいようです.

さらについでに書いておくと, 少なくともAtCoder上のOCaml勢は破壊的な実装を厭いません. 困ったらOCaml勢の実装も参考にしましょう. 今回も解説用のコードはOCamlを参考にしました.

入出力¶

入出力とその変数は次のようにします.

1
2
3
4
5

let solve H W Aa = "これから実装"

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

変数の初期化¶

まずはキューを初期化しつつ, フラグ管理・操作回数管理用の配列を作ります. F#では配列の配列ではなく二次元の配列があり, 今回は二次元の配列が便利そうなのでこちらを使います.

1
2
3

  let q = System.Collections.Generic.Queue<int*int>()
  let Da = Array2D.init H W (fun _ _ -> -1)
  Aa |> array2D |> Array2D.iteri (fun i j c -> if c='#' then Da.[j,i] <- 0; q.Enqueue(j,i))

Daが本体のループでゴリゴリ書き換える変数です. そもそもとしてF#の配列は破壊的なデータ型で, mutableをつけなくてもDa.[j,i] <- 0で破壊的に変更できます. Daは.を-1, #を0で初期化しています. 最終的に何回目の処置で黒に変わったかを表す二次元配列で, -1はまだ書き換えできていない状態を表します.

さらに#の場所もキューに積みます. ここでAaのi,jはそれぞれy座標とx座標で混乱するため, 上記のDaとqは添字を入れ変えてx,yと書けるようにしています.

本体のループ処理¶

let mutable ans = 0で最終的に返す変数を宣言します. あとは適宜qに積みつつqが尽きるまでループします. qに値があるかどうかはプロパティq.Countで判定できます.

1
2
3
4

  let mutable ans = 0
  while q.Count <> 0 do
    "いろいろな処理"
  ans

いろいろな処理の部分を考えます. 何はともあれqから値をポップします.

1

    let x0,y0 = q.Dequeue()

.NETではq.Dequeue()です. ポップした値を中心にして周囲4マスの値を確認します. 周囲4マス分の移動を表す配列Maを用意します.

1

  let Ma = [|(-1,0);(0,-1);(1,0);(0,1)|]

さらに配列の範囲外参照と訪問状態をチェックする関数を準備します.

1

  let isWhite x y (Da:int[,]) = 0<=y && y<H && 0<=x && x<W && Da.[x,y]=(-1)

ここで白(.)かどうかの判定は初期値ではなく書き換えたかどうかを判定したいため, 入力のAaではなくDaの値で判定します. 一緒に配列の範囲内か確認するべく値Da.[x,y]ではなく配列自体を渡しています.

この二つを使って次のように周辺4マスの状態を確認しつつ値を更新します.

1
2
3
4

    let x0,y0 = q.Dequeue()
    Ma |> Array.iter (fun (dx,dy) ->
      let x,y = x0+dx, y0+dy
      if isWhite x y Da then ans <- Da.[x0,y0]+1; Da.[x,y] <- ans; q.Enqueue(x,y))

Maの各値をArray.iterで参照します. 周囲4マスのどれかを表すx,yを準備してx,yの値が白(.)かどうかを判定します. 点x,yがまだ白ならDa.[x0,y0]+1でDa.[x,y]を更新します. 最後に新たに黒(#)にしたフラグ立てとしてq.Enqueue(x,y)でキューにx,yを積みます.

途中ansをバリバリ書き換えているためこれで最終的な解答になるか微妙な不安がありますが, 都度キューに積んだ値を見てループしているため, これで常に最新の変更回数が取れています.

084 C - Shopping Street¶

• created: 2022-12-16 fri
• ご意見・ご要望はissue・プルリク用のGitHubまで
• GitHub上の対応ディレクトリ
• 公式ページ
• ユーザー解説

三つの実装¶

まずはユーザー解説にあったビットマスクを使った実装を紹介します. しかし執筆時点でビットマスクに慣れていないためにいま一つ腑に落ちず, 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が必要です. 特に次のような分岐処理が入ります.