Go言語で挑む競プロ #10

前回はこちらから。

前回の投稿から、結構間が開いてしまった..
忙しくなると、やらなくなってしまうのは悪い癖だね。反省しなくちゃ。

蟻本に載っているアルゴリズムはまだまだいっぱいあるし、どんどん解いていくぞ。

ABC009Cの問題

問題文
文字列の辞書式順序による比較についてはご存知だろうか？
知らない場合は ABC007 の B 問題にその定義が載っているので読むとよいだろう。
今回は、この辞書式順序が重要な役割を果たす問題を解いてもらいたいと思う。
まず、英小文字（a-z）のみからなる N 文字の文字列 S が与えられる。
S=S1,S2,...,SN の文字を並び替えて作れるような文字列 T=T1,T2,...,TN のうち、辞書順で最小になるようなものを求めてほしい。
ただし、並び替え方には 1 つだけ制限がある。
別に整数 K が与えられ、元から位置の変わった文字の個数を K 以下にしなければならない。
つまり、Si≠Ti となるような（文字が不一致となるような） i （1≦i≦N）の個数が K 以下であるような並び替え方しかできない。

アルゴリズム

今回の問題は、なんと問題画面に「難しいよ」って書いてある...！
それほど難しいらしい...

けれど、文字列の最大サイズが100文字とのことなので、ループを結構回したごり押しでも解けそうな気がする。
ってことで、ごり押しのアルゴリズムを考えてみた。

1. x=1とする。
2. y=x+1 とする。
3. x文字目とy文字目を比較し、y文字目のほうが辞書順で小さいならば、交換してみる。
4. 交換後の文字列と元の文字列Sを比較し、文字違いの数をカウントする。
5. 違いがK文字以下ならば交換を確定し、K文字を超えるのであれば交換を取り消す。
6. yが文字列の長さ未満なら y=y+1 とし、手順3へ。
7. yが文字列の長さ以上、かつ、xが文字列の長さ-1未満ならば x=x+1 とし手順2へ。
8. 最終的にできた文字列が解答となる。

一応、上記のアルゴリズムで解けるはず。けど、文章だとよくわからないから、実際に並び替える例を見てみよう。
以下が、文字列「apple」を並び替える際の動作の流れ。

入力データ
N=5, K=2, S=apple

並び替え
1. apple ⇒ alppe　(x=2, y=4)
2. alppe ⇒ aeppl　(x=2, y=5)
3. aeppl ⇒ aeplp　(x=4, y=5)

※ 2 の後に、 aeppl ⇒ aelpp　(x=3, y=5) もあるのだが、「apple」との違いの数が3文字となってしまうので、解答になりえない。

「apple」に上記のアルゴリズムを適用するとこんな流れで並び替えがされる。うまくいってそう。

これをコードに落とそう。以下のようになる。

func betterSort(s, t string, n, k int) string {
    for i := 0; i < n; i++ {
	a := i
	for j := i + 1; j < n; j++ {
            # 並び替えてみて条件を満たすならその位置を保持
            if t[j] < t[a] && count(s, swap(t, i, j)) <= k {
		a = j
            }
	}
        # 現在位置の文字と最も辞書順が小さくなる文字を交換
	if a > i {
            t = swap(t, i, a)
	}
    }

    return t
}

上記の関数は、現在の文字列を並び替えてみて、条件を満たすかチェックし並び替えを確定するかを判定することを繰り返している。たったそれだけの単純な実装。

簡単な実装だけど、実は基本的にはこれだけで完成。あとは、入出力と文字の違いのカウント用関数を用意したら出来上がり。

解答

最終的には以下のようなコードに。

package main

import (
    "fmt"
)

func main() {
    var n, k int
    fmt.Scan(&n, &k)

    var s string
    fmt.Scan(&s)

    fmt.Println(betterSort(s, s, n, k))
}

func betterSort(s, t string, n, k int) string {
    for i := 0; i < n; i++ {
	a := i
	for j := i + 1; j < n; j++ {
            if t[j] < t[a] && count(s, swap(t, i, j)) <= k {
		a = j
            }
	}
	if a > i {
            t = swap(t, i, a)
	}
    }

    return t
}

func swap(s string, i, j int) string {
    return s[:i] + s[j:j+1] + s[i+1:j] + s[i:i+1] + s[j+1:]
}

func count(s, t string) int {
    c := 0
    for i := range s {
    	if s[i] != t[i] {
            c++
	}
    }
    return c
}

難しいと書いてあったから、身構えてしまったけれども、条件が緩いので全探索みたいな強引な手で解けてしまった。
文字数とかが大きくなると使えなくなるから、実際にはもっと効率的な方法があるんだろうなぁ。

まぁ今回はこれで完成ってことにして、次回もまた頑張ろっと。