はじめに
- また、c++やpythonで対応してるのに、swiftで対応していない関数があったので、なんとか対応したい。
- 必要性に気付いたのは、ABC363のc問題。
- やりたいことは単純で、例えば、要素が3つの配列で、中身が「a,b,c」だったときに、abc,acb,bac,bca,cab,cbaのような順番の配列6つ(=3!)を作るということ。
- そのような配列生成は、計算量を無視すれば無理やり作れそうだけど、計算量を抑えて実現するのは意外と難しそうなので、解くのを諦めた。
- 今回、計算量を抑えた手法(ヒープのアルゴリズム)を見つけたので、それを使った実装を行う。
ヒープのアルゴリズムの実装
- ちなみに、ダイクストラ法の高速化で用いた「ヒープ」(積み重なったもの、という意味)とは全く関係ない。こちらのヒープは人名(B. R. Heap)を指す。
- swiftでコードを書くと次のとおり。なお、wikiのコードでは、ダブりの消去を考慮していないので、戻り値をSetにすることで対応した。
func pmt_gen<T>(_ ary:[T])->Set<[T]>{
let N = ary.count
var A = ary
var ans_nonset = [[T]]()
rec(N,&A,&ans_nonset)
return Set(ans_nonset)
func rec<Ti>(_ n:Int , _ A:inout [Ti],_ ans:inout [[Ti]]){
if n == 1 {
ans.append(A)
} else {
for i in 0..<n {
rec(n-1,&A,&ans)
if n % 2 == 0 {
swap(&A,i,n-1)
} else {
swap(&A,0,n-1)
}
}
}
}
func swap<Ti>(_ A:inout [Ti],_ a:Int,_ b:Int){
let temp = A[a]
A[a] = A[b]
A[b] = temp
}
}
let a = ["z","z","y","y","x"]
let b = pmt_gen(a).map{$0.reduce(""){$0 + $1}}.sorted()
print(b) // ["xyyzz", "xyzyz", "xyzzy", "xzyyz", "xzyzy", "xzzyy", "yxyzz", "yxzyz", "yxzzy", "yyxzz", "yyzxz", "yyzzx", "yzxyz", "yzxzy", "yzyxz", "yzyzx", "yzzxy", "yzzyx", "zxyyz", "zxyzy", "zxzyy", "zyxyz", "zyxzy", "zyyxz", "zyyzx", "zyzxy", "zyzyx", "zzxyy", "zzyxy", "zzyyx"]
print(b.count) // 30
- 上記コードは、paizaだとエラーが発生するので注意！！
error: link command failed with exit code 1 (use -v to see invocation)とのことだけど、よくわからん。 - AtCoderのコードテストや、mycompilerだと問題なく実行できる。ちなみに、型変数Tが内側の関数ではTi(innerの意味でiにした)にしているのは、「内と外で同じ型変数名を使ったら駄目だぞ！」とmycompilerに怒られたから。現状は、メッセージは出るものの実行できるんだけど、エラーメッセージを見ると、swift6からは駄目っぽいね。
warning: generic parameter 'T' shadows generic parameter from outer scope with the same name; this is an error in Swift 6 - このヒープのアルゴリズムの肝は、再帰関数recの部分だと思うけど、やっていることは、このpdfのp379「2.交換による方法-2.1再帰的方法」に書かれている。Wellのアルゴリズムでも同じように出来るみたいだけど、ヒープのアルゴリズムだけ名前が残っているのは何でだろうね。
上記のコードはへっぽこなのでpaizaで動かなかったけど、コメント欄の@nak435さんのコードならスッキリしてて、paizaでも動きます！上記、へっぽこコードは戒めのために、このままにしておきます。
pmt_genを使って提出する
- ABC363のc問題を解いてみる。コードは公式解説をswift用に変えただけ。
let (N,K) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
var ss = Array(readLine()!).map{$0.asciiValue!}
var ans = 0
var pmt = pmt_gen(ss)
for s in pmt {
var ok = true
for i in 0...(N-K) {
var flag = true
for j in 0..<K {
if s[i+j] != s[i+K-1-j] {flag = false}
}
if(flag) {ok = false}
}
if ok {ans += 1}
}
print(ans)
- ACだったけど....1.6秒もかかって、メモリも300M以上消費....ギリギリ過ぎじゃん
- そもそも、最初、pmt_genの返り値を配列にするため、Array(Set(ans))の処理を含めたらTLEが発生したので、その処理を省いたんだよね。SetをArrayにするのも、結構な計算量を使うってことね。
おわりに
- やっぱり、swiftでコンテストに出る場合、自分で関数を事前に用意して置く必要があると実感したね。
- 夏が終わるまでに4完できるかなぁ