結果
問題 |
No.133 カードゲーム
|
ユーザー |
![]() |
提出日時 | 2020-12-02 20:02:24 |
言語 | Swift (6.0.3) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 1,440 bytes |
コンパイル時間 | 12,875 ms |
コンパイル使用メモリ | 134,056 KB |
実行使用メモリ | 9,344 KB |
最終ジャッジ日時 | 2024-09-13 10:39:58 |
合計ジャッジ時間 | 13,961 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 19 |
ソースコード
/* 方針 A君とB君のカードの出し方を順列でそれぞれ調べる. A君が勝つ回数を数える 出し方は全部で (A君の出し方の種類) * (B君の出し方の種類) 通り */ yukicoder133() func yukicoder133() { let N = Int(readLine()!)! let As: [Int] = readLine()!.split(separator: " ").map { Int($0)! } let Bs: [Int] = readLine()!.split(separator: " ").map { Int($0)! } let permA: [[Int]] = kPermutation(As, k: N) let permB: [[Int]] = kPermutation(Bs, k: N) var gameWinA = 0 permA.forEach { gameA in permB.forEach { gameB in var winA = 0 for i in 0..<N { let (a, b) = (gameA[i], gameB[i]) if a > b { winA += 1 } } if winA > N/2 { gameWinA += 1 } } } let ways = permA.count * permB.count print(Double(gameWinA) / Double(ways)) } // k-順列を得る関数 func kPermutation<Element>(_ elements: [Element], k: Int) -> [[Element]] { var ret = [[Element]]() let n = elements.count var used: [Bool] = Array(repeating: false, count: n) func dfs(_ seq: [Element]) { if seq.count == k { ret.append(seq) return } for i in 0..<n { if used[i] { continue } used[i] = true dfs(seq + [elements[i]]) used[i] = false } } dfs([]) return ret }