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

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

# 問題の紹介
- 詳細は[問題文](https://atcoder.jp/contests/abc371/tasks/abc371_c)を見て貰うとして、概要はこんな感じ
    - 頂点の数が同じグラフが２つある（Ｇ，Ｈ）
    - それぞれのグラフは無指向辺をそれぞれ、Ｍ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にはそんな便利な関数がないんよね。
- まぁ、僕は以前[作った](https://qiita.com/kei_tnk/items/246b502200ee7cfb6ac2)けどね（ドヤァ
- 実は、どや顔出来るほどの大したものではないし、出来るのも下記程度。
```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メソッドはタプルを認識しないんだよ！
- ΩΩΩ < な....なんだってェ−−!!
- あ…ありのまま 今 起こった事を話すぜ！

https://qiita.com/kei_tnk/items/5d784b81f2a8b519581a

-
    - で、containsがタプルを認識しないと何が問題かというと、今回の問題は、グラフ理論のように見えてグラフ理論は関係ないから、「辺」も単純なタプルで格納して扱うからです。
    - で、「グラフＧが持っている辺(タプル)の配列」と「グラフＨが持っている辺(タプル)の配列」の有無を比較して、不一致した時だけコストを発生させる簡単なお仕事です。
    - で、有無の一致を確認するときに、H、Gの配列にそれぞれ、(i,j)、(p(i)、p(j)){p in Ps(罠（その１）のPs)}の辺が含まれているかを確認し、「共に持っている、共に持ってない」ときは、コストゼロ。「片方だけ持っている」ときは、コストAijが発生と言うこと。
    - で、配列中に指定の要素が含まれているか調べるのに、containsを使用する...のに、<font color="red">containsメソッドはタプルを認識しないんだよ！</font>
- まぁ、[タプルをcontains対応させる一工夫](https://qiita.com/kei_tnk/items/5d784b81f2a8b519581a)で、次の呪文をマスターしたから、問題ないけどね。
```swift
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++陣営から仕掛けられた罠２つを解除したので、以下のとおり解くことが出来た。
```swift
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)になるのかな？
- よーしパパ集合で作っちゃうぞ〜...
```swift
var Gs = Set<(Int,Int)>()
- error: type '(Int, Int)' does not conform to protocol 'Hashable'
```
- <font color="red">今度は、Hashableかよ！</font>

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