AtCoder AGC006 B - Median Pyramid Easy - あるエンジニアのAtCoder奮闘記

irisruneです。ABC-F問題の壁は厚いですね。

問題

順列をどのように構築すればよいかがわかれば、順列が存在し得るかどうかも自然とわかります。あるいは小規模なケースで試してみるのもよさそうです。

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, x := nextInt(), nextInt()

    if x <= 1 || x >= 2*n-1 {
        fmt.Println("No")
        return
    }

    values := make([]int, 0)
    for v := 2; v < 2*n-1; v++ {
        if v != x {
            values = append(values, v)
        }
    }

    fmt.Println("Yes")
    for i := 0; i < 2*n-1; i++ {
        switch {
        case i == n-2:
            fmt.Println(x)
        case i == n-1:
            switch {
            case x < n:
                fmt.Println(1)
            default:
                fmt.Println(2*n - 1)
            }
        case i == n:
            switch {
            case x < n:
                fmt.Println(2*n - 1)
            default:
                fmt.Println(1)
            }
        default:
            fmt.Println(values[0])
            values = values[1:]
        }
    }
}

直感的に考えると、 $N-1$ 段目では最小・最大の数（ $1,2N-1$ ）が存在せず、 $N-2$ 段目では $2,2N-2$ が存在せず、…といった具合で最終的に $1$ 段目には $N$ しか存在し得ないように思えます。

とはいえそうはならないだろうということも直感的に想像できると思います。例えば $N=3$ で3段目が $3,2,1,4,5$ の場合には $2$ 段目の時点で $3$ が存在しません。このとき、 $2$ 段目は $2,2,4$ となるので $1$ 段目は $2$ となります。

ここで先の例について考えると、 $2$ 段目で同じ数が2回（連続で）現れるように構成するとその数が $1$ 段目になるということがわかります。同様に考えると、 $K+1$ 段目の中央3か所のうち連続する2か所に同じ数が現れる場合 $K(\gt1)$ 段目の中央3か所のうち連続する2か所に同じ数が現れることがわかります。

つまり $N-1$ 段目の中央3か所のうち連続する2か所に $x$ が現れるよう順列を構成すれば $1$ 段目に $x$ が入ります。またそのような構成は $x=2,3,\ldots,2N-2$ に対して存在するため、 $x=1,2N-1$ を除く場合について順列を構成することができます。

順列の構成方法は様々だと思いますが、上記コードでは以下のようなアルゴリズムで実装しています。

中央の3か所以外は $2,3,\ldots,x-1,x+1,\ldots,2N-2$ を左から順番に入れる。
中央の3か所のうち左側はを入れる。残り2か所は以下のように入れる。
1. $x\lt N$ ならば中央に $1$ 、右側に $2N-1$ を入れる。
2. $x\geq N$ ならば中央に $2N-1$ 、右側に $1$ を入れる。