068 D - String Equivalence

解説1

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

 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