あるエンジニアのAtCoder奮闘記

東京都港区にあるアミフィアブル株式会社のエンジニアが、AtCoderで解いた問題について振り返ったりしていく会社公認のブログです。

AtCoder ABC139 E - League (Go) 失敗例と成功例(嘘解法?)

irisruneです。今週は解説の難しい問題ばかりで少し難儀しますね。

問題

atcoder.jp

実装するだけの問題とみせかけて、アルゴリズムを考える必要がある問題です。

失敗例

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選手について試合を行えると判定できます。あとは試合の存在しない日が発生したらループを止めて出力するだけです。

この手法の何が失敗だったかについてですが、計算量は大会の日数をDとおくとO(ND)となります。一方でD\leq N(N-1)/2のため、全体の計算量はO(N^3)となってしまい流石に厳しいです。例えば以下のような入力例の場合に計算量は最悪となります。

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試合でも行えばまた全選手に対して処理を行うということを繰り返します。終了条件は失敗例の方と似ていて、試合を行う選手が一人も発生しない場合です。

この手法の計算量はO(N^2)になると思って実装したのですが、理論的に証明できていない状態です。N人の選手を一通りチェックすると少なくとも1試合は行うことになりますが、これだけでは結局計算量はO(N^3)になりそうです。考え直してみると嘘解法の可能性が高い気がします。

雑記

  • 公式解説を見ると全然思いつきもしない手法だったので、おそらく実装力よりアルゴリズム力の方が要求される問題でしたね。