AtCoder AGC 007 B - Construct Sequences (Go)

irisruneです。最近あまりAtCoderに時間を割けていません。

問題

atcoder.jp

3つ目までの条件を満たしつつ4つ目の条件を満たすためにはどうすればよいか考える問題です。

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()
    order := make([]int, n)
    for o := 1; o <= n; o++ {
        oi := nextInt()
        order[oi-1] = o
    }
    aArray, bArray := make([]int, n), make([]int, n)
    for i, o := range order {
        aArray[i] = n*i + o
        bArray[i] = n*(n-i-1) + o
    }
    for i, a := range aArray {
        fmt.Print(a)
        switch {
        case i == n-1:
            fmt.Println()
        default:
            fmt.Print(" ")
        }
    }
    for i, b := range bArray {
        fmt.Print(b)
        switch {
        case i == n-1:
            fmt.Println()
        default:
            fmt.Print(" ")
        }
    }
}

まず3番目までの条件を満たすことを考えます。それ自体は簡単で、例えばと置くことで条件を満たすことができます。

このときとなるわけですが、3番目までの条件を満たしながら4番目の条件を満たそうとすると、数列の複数の要素の値を同時に変更する必要があります。

そこで、と置くと、要素の値を1つずつ変えながら全ての条件を満たすことができるようになります。上記提出コードではの両方に対して初期値の間隔を空けていますが、どちらかに対して処理を行えば問題なく解けると思います。計算量はです。