AtCoder ABC139 E - League (Go) 失敗例と成功例(嘘解法?)
irisruneです。今週は解説の難しい問題ばかりで少し難儀しますね。
問題
実装するだけの問題とみせかけて、アルゴリズムを考える必要がある問題です。
失敗例
package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner func nextInt() int { sc.Scan() i, e := strconv.Atoi(sc.Text()) if e != nil { panic(e) } return i } func main() { sc = bufio.NewScanner(os.Stdin) sc.Split(bufio.ScanWords) n := nextInt() aMat := make([][]int, n) for i := range aMat { aRow := make([]int, n-1) for j := range aRow { aRow[j] = nextInt() - 1 } aMat[i] = aRow } day := 0 for { matched := make(map[int]struct{}) for i, aRow := range aMat { if len(aRow) == 0 { continue } _, exist1 := matched[i] if exist1 { continue } _, exist2 := matched[aRow[0]] if exist2 { continue } j := aMat[aRow[0]][0] if i == j { matched[i] = struct{}{} matched[aRow[0]] = struct{}{} aMat[i] = aMat[i][1:] aMat[aRow[0]] = aMat[aRow[0]][1:] } } if len(matched) == 0 { for _, aRow := range aMat { if len(aRow) > 0 { fmt.Println(-1) return } } fmt.Println(day) return } day++ } }
こちらは1日毎に行える試合を求めていく手法です。各選手の試合予定をキューで持っておくと先頭要素が直近で予定された対戦相手となります。そのため、その日の間にマッチングしていない選手同士でキューの先頭要素が互いに対応する2選手について試合を行えると判定できます。あとは試合の存在しない日が発生したらループを止めて出力するだけです。
この手法の何が失敗だったかについてですが、計算量は大会の日数をとおくととなります。一方でのため、全体の計算量はとなってしまい流石に厳しいです。例えば以下のような入力例の場合に計算量は最悪となります。
4 2 3 4 1 3 4 1 4 2 1 3 2
成功例
package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner func nextInt() int { sc.Scan() i, e := strconv.Atoi(sc.Text()) if e != nil { panic(e) } return i } func maxInt(a, b int) int { if a > b { return a } return b } func main() { sc = bufio.NewScanner(os.Stdin) sc.Split(bufio.ScanWords) n := nextInt() aMat := make([][]int, n) for i := range aMat { aRow := make([]int, n-1) for j := range aRow { aRow[j] = nextInt() - 1 } aMat[i] = aRow } days := make([]int, n) for { matched := false for i := range aMat { for { if len(aMat[i]) == 0 { break } other := aMat[i][0] // len(aMat[other]) > 0 if i != aMat[other][0] { break } day := maxInt(days[i], days[other]) + 1 days[i], days[other] = day, day aMat[i], aMat[other] = aMat[i][1:], aMat[other][1:] matched = true } } if !matched { for _, aRow := range aMat { if len(aRow) > 0 { fmt.Println(-1) return } } ans := 0 for _, d := range days { ans = maxInt(ans, d) } fmt.Println(ans) break } } }
こちらは各選手に対して試合日程を決定する手法です。ある選手に対して試合を行える限り行うという処理を全選手に対して行い、1試合でも行えばまた全選手に対して処理を行うということを繰り返します。終了条件は失敗例の方と似ていて、試合を行う選手が一人も発生しない場合です。
この手法の計算量はになると思って実装したのですが、理論的に証明できていない状態です。人の選手を一通りチェックすると少なくとも1試合は行うことになりますが、これだけでは結局計算量はになりそうです。考え直してみると嘘解法の可能性が高い気がします。
雑記
- 公式解説を見ると全然思いつきもしない手法だったので、おそらく実装力よりアルゴリズム力の方が要求される問題でしたね。