swiftだってできるもん！【競技プログラミング】

はじめに

• ABC371c問題は、c問題のくせに難解でした。後から調べたら、コンテスト時間中にACしたswift使いは皆無。元々、参加してるswift使いは10人未満だけどね。
• で、c問題がswift使いに解けなかった理由の一つに、2つのワナが仕掛けられていたから、というのもある気がしたので、それを説明したい！
• ...、いや、ゴメンなさい。単なる言い訳です。でも、一応、言わせて欲しい。

問題の紹介

• 詳細は問題文を見て貰うとして、概要はこんな感じ
  • 頂点の数が同じグラフが２つある（Ｇ，Ｈ）
  • それぞれのグラフは無指向辺をそれぞれ、Ｍg,Mh本だけ持つ
  • グラフＨの辺を削除したり追加したりして、グラフＧと同型としたい
  • 辺(i,j)《頂点iと頂点jを結ぶ辺》の追加･削除に際して、Aijのコストがかかる。
  • 最小のコストはいくらとなるか？
  • 制約は、$「N≦8」「0≦Aij≦10^6」$

罠（その１） -- swiftにはnext_permutationがない！

• 今回の問題のキモは、N≦8による、計算量を気にしない全探査だったんだよね。
• で、全探査をするに当たっては、グラフＧとグラフＨを同型とするための頂点の変換処理をする必要があるけど、頂点の数が8だから、グラフＧとグラフＨの頂点を全てマッチさせる場合でも、8!(=40320)の組み合わせで済むんだよね。
• コンテスト中は問題文見ただけで諦めたから、Nが最大８と言うことまで気がつかなかったよ。でも、仮に気がついたとしても、8!の組み合わせを作り出せるのか？c++なら関数next_permutationでサクッと作れるけど、swiftにはそんな便利な関数がないんよね。
• まぁ、僕は以前作ったけどね（ドヤァ
• 実は、どや顔出来るほどの大したものではないし、出来るのも下記程度。

let P = [0,1,2]
let Ps = pmt_gen(a)

print(b) // [[0, 1, 2], [1, 0, 2], [2, 0, 1], [0, 2, 1], [1, 2, 0], [2, 1, 0]]
print(b.count) // 6

• こんな単純な関数なんだから、標準で用意しておいてよ、swiftさん。
• でもまぁ、とりあえず、罠は回避した！

罠（その２） -- swiftの配列のcontainsメソッドはタプルを認識しないんだよ！

• ΩΩΩ < な....なんだってェ−−!!
• あ…ありのまま 今 起こった事を話すぜ！

• • で、containsがタプルを認識しないと何が問題かというと、今回の問題は、グラフ理論のように見えてグラフ理論は関係ないから、「辺」も単純なタプルで格納して扱うからです。
  • で、「グラフＧが持っている辺(タプル)の配列」と「グラフＨが持っている辺(タプル)の配列」の有無を比較して、不一致した時だけコストを発生させる簡単なお仕事です。
  • で、有無の一致を確認するときに、H、Gの配列にそれぞれ、(i,j)、(p(i)、p(j)){p in Ps(罠（その１）のPs)}の辺が含まれているかを確認し、「共に持っている、共に持ってない」ときは、コストゼロ。「片方だけ持っている」ときは、コストAijが発生と言うこと。
  • で、配列中に指定の要素が含まれているか調べるのに、containsを使用する...のに、containsメソッドはタプルを認識しないんだよ！
• まぁ、タプルをcontains対応させる一工夫で、次の呪文をマスターしたから、問題ないけどね。

extension Sequence {
    func contains<T:Equatable,U:Equatable>(_ element: (T, U)) -> Bool {
        return (self as! [(T, U)]).contains { $0 == element }
    }
}

let tpls = [(1,2),(3,4)]
print(tpls.contains((1,2))) // true
print(tpls.contains((2,3))) // false

swiftだってできるもん！

• c++陣営から仕掛けられた罠２つを解除したので、以下のとおり解くことが出来た。

func pmt_gen<T>(_ ary: [T]) -> Set<[T]> {･･･}
extension Sequence {･･･}

let N = Int(readLine()!)!

let Mg = Int(readLine()!)!
var Gs : [(Int,Int)] = []
for _ in 0..<Mg {
    let (a,b) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0]-1,$0[1]-1)}[0]
    Gs += [(a,b),(b,a)] // 変換配列pにより変換されたの座標p(i),p(j)について、p(i)<p(j)と限らないので、(b,a)も用意しておく。
}

let Mh = Int(readLine()!)!
var Hs : [(Int,Int)] = []
for _ in 0..<Mh {
    let (a,b) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0]-1,$0[1]-1)}[0]
    Hs += [(a,b)] // Hsについては、a<bでしか走査しないので、(b,a)不要。
}

var A = [[Int]](repeating:[Int](repeating:0,count:N),count:N)
for i in 0..<(N-1) {
    let vs = readLine()!.split(separator:" ").map{Int($0)!}
    for (j,v) in vs.enumerated() {
        A[i][i+1+j] = v // Aijに逆三角形の形で格納
    }
}

var P = (0..<N).map{$0} // [0,1,2,3,...]
var Ps = pmt_gen(P) // [[0,1,2,3,...], [1,0,2,3,...], [2,0,1,3,...], [...

var ans = Int.max

for p in Ps { // N!パターンの総当たり。でも、最大で8!だから大したことない。
    var sum = 0
    for i in 0..<N {
        for j in i..<N {
        
        if Hs.contains((i,j)) != Gs.contains((p[i],p[j])) { sum += A[i][j] } 
            
        }
    }
    ans = min(ans,sum)
}

print(ans)

• 上記でも計算量的には大したことない。
• 一番外側のforループで$N!$、内側のforループ２つで$N^2$、配列のcontainsがO(N)だから、全体の計算量は$O(N!･N^3)$。いつもの問題なら恐ろしい計算量に見えるけど、N=8だから、単純計算で$2×10^7$。あれ？結構ギリじゃん！でも、100ms未満でACできたよ。
• Hs,Gsを配列でなくて、集合で作ればcontainsはO(logN)になるのかな？
• よーしパパ集合で作っちゃうぞ〜...

var Gs = Set<(Int,Int)>()
- error: type '(Int, Int)' does not conform to protocol 'Hashable'

• 今度は、Hashableかよ！

さいごに

• 最後の最後にタプルがオチをつけてくれました。本当に、どうにかして欲しいね。
• あ、ちなみにタプルをhashableにするためには、hash（into：）メソッドに対応させる必要があるけど、タプルはextensionが使えないので、個別に構造体を作るしかないです。
• 以前、タプルをComparableにしたときの構造体にhashメソッドを追加すればいい。今回の問題がTLEだったら対応してたけど、結果はACだったし、今日は疲れたからもういいや。