AtCoder AGC 032 B - Balanced Neighbors (Go) - あるエンジニアのAtCoder奮闘記

irisruneです。気づけばもう11月となり、今年の終わりも近づいてきました。

問題

パズル要素が強めのグラフ問題です。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

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.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n := nextInt()
    adj := make([]map[int]struct{}, n+1)
    for i := 1; i < n+1; i++ {
        adj[i] = make(map[int]struct{}, n)
        for j := 1; j < n+1; j++ {
            if i == j {
                continue
            }
            adj[i][j] = struct{}{}
        }
    }

    m := n
    if n%2 == 1 {
        m = n - 1
    }
    for i := 1; i < m-i+1; i++ {
        delete(adj[i], m-i+1)
        delete(adj[m-i+1], i)
    }

    k := 0
    for i := 1; i < n+1; i++ {
        k += len(adj[i])
    }
    fmt.Println(k / 2)
    for i := 1; i < n+1; i++ {
        for j := range adj[i] {
            if i < j {
                fmt.Println(i, j)
            }
        }
    }
}

このような問題は小さいケースで試行することで規則性を導き出すアプローチを取るのがよいです。例えば $N=4,5$ について条件を満たすグラフを考えると以下のようなグラフになります。

f:id:amifiable:20191101120029p:plain f:id:amifiable:20191101120044p:plain

間に辺を持たない頂点同士の集合について考えると、図で示すように高々2つの頂点からなる集合が構成されます。また、全ての頂点集合について集合内の頂点のラベルの和が等しくなることがわかります。

この性質より、以下のようにして問題を解くことができます。

全体を完全グラフとおく。
グラフの頂点集合を高々２つの頂点からなる頂点集合に分割する。分割の方法はの偶奇による。
1. $N$ が偶数のときは、集合内の頂点のラベルの和を $N+1$ とおく。
2. $N$ が奇数のときは、集合内の頂点のラベルの和を $N$ とおく。
各頂点集合について、集合内の頂点間の辺を削除する。