AtCoder ABC 131 E - Friendships

irisruneです。今週またABCがあるようなのでなるべく参加できるように調整したいですね。

問題

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
}

const INF = 1000000000

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n, k := nextInt(), nextInt()
    diff := (((n - 1) * (n - 2)) / 2) - k
    if diff < 0 {
        fmt.Println(-1)
        return
    }
    fmt.Println((n - 1) + diff)
    for i := 1; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if diff > 0 {
                fmt.Println(i, j)
                diff--
            }
        }
        fmt.Println(i, n)
    }
}

まず、連結グラフという条件を無視した場合とはいえグラフの辺を配置する組み合わせはとなるので、全ての場合に対して考えるのは現実的ではありません。そのため、適当なグラフを作成して条件を満たすか確認するという手順を取ることはあり得ないので、探索系のアルゴリズムを使う機会はないです。

次に、の取り得る値の範囲について考えます。

最小値については単純で、完全グラフの場合すべての頂点対について最短距離がとなるのでとなります。

一方で最大値については少しアイデアが必要なため結果だけ出すと、公式解説で触れられているようにが示せ、また等号が成立する条件としてはある1点とそれ以外すべての点を結ぶ辺以外に辺を持たないスター型のグラフであることが挙げられます。

あとはが与えられたときに条件を満たすグラフを求める手順ですが、スター型のグラフに本の辺を単純グラフとなる条件を守りながら追加するだけです。

スター型のグラフを構築するための辺も出力する必要があるため、先にスター型のグラフに必要な辺を出力してから追加の辺を出力する形の方がミスが少ないかもしれません。

雑記

• とりあえず考えた結果としてAtCoderでは再びKotlinを使うことにしました。
  • （JVM系言語の宿命として一定のタイムロスはありますが）実行速度自体はおそらく問題がないこと、Javaライブラリが使えるため機能的に不足はおそらくないこと、記述が比較的簡易なことが利点ですね。
  • 欠点は入力処理の弱さで、それを補おうとすると長めのライブラリを貼ることになる点でしょうか。