こんにちは、群論に手を染めなければならなくなった綿谷雫です。たいへんだ。今日も解説記事を書いていきます。今日はAGC037 B Balanced Neighborsを解説していきます。

問題のリンクは下に貼っておきます。

これはツイッターに流れてきたので解きました。

問題概要

短い問題文ですが一応要約すると

頂点に 1から Nの番号がついたグラフで、どこの頂点についてもその頂点に隣接する頂点の番号の値の和が同じグラフを教えてね

という問題です。いわゆる構築というものでしょうか。

解答までの道のり

まず、Nで考えるとわかりづらいので、N=6として具体的に作ることができるか試してみました。

一番大きい数の6のついた頂点はおそらく一番多くの頂点と結びつくことが予想されます。そこでとりあえず頂点6を全ての他の頂点とくっつけてみました。このとき頂点6に隣接する頂点の番号の値の和は15なので、他の頂点についても隣接する頂点の番号の値の和が15になるように考えてみます。頂点5は全ての他の頂点とくっつけると隣接する頂点の番号の値の和は16になります。なので、頂点1以外の全ての他の頂点とくっつくと、頂点5に隣接する頂点の番号の値の和を15にすることができます。頂点1が頂点5にくっつかないと分かったので、頂点1まわりについて考えてみます。頂点1が頂点5と結びつかないでそれ以外の他の頂点と隣接していると考えると隣接する頂点の番号の値の和は15になります。よって頂点1は頂点5以外の全ての頂点と結びつくとわかりました。さて、他の頂点について考えると、頂点2は頂点1,5,6とすでに隣接していますので、あとは頂点3と結びつくといいでしょう。すると、頂点3は1,2,5,6(合計14)と隣接していて隣接する頂点の番号の値の和が15にできません。困った。どうやら、隣接する頂点の番号の値の和は15にすべきじゃないみたいですね。

今度は1つ減らして14にしてみることを考えました。まず頂点6は頂点1以外の全ての他の頂点と隣接することになります。すると頂点1も6以外の全ての他の頂点と隣接することがわかります。次に頂点5について調べてみると、頂点5は頂点2以外の全ての他の頂点と隣接することになります。そして頂点2も5以外の全ての他の頂点と隣接することがわかります。さて頂点3,4についてですが、今のところ1,2,5,6と結びついているので、頂点3,4は結びつかないことがわかりました。こうしてN=6について具体的に構成することができました。

さてこれを一般化していきたいです。N=6でできたグラフをじっとみると繋がっていない頂点は足すと7になることがわかります。足すと7になる数字をペアにすると、(1,6)(2,5),(3,4)となり、各頂点は自分と同じペア以外の数字と隣接している状態になっています。そこで、足してN+1をペアにして同じペア以外の数字を隣接させることにしたらいいと思いつきました。しかし、N=3などNが奇数の時に1つ余ってしまうことに気付きます。これはどうすればいいのでしょうか。

ところでサンプルをみるとN=3についてやっています。 1は3と、 2は3と、 3は1と2と、結びついています。これは足して3になるペア以外の数字と結びついているとも取れます。ここからNが奇数のときは足してNになる組をつくり、同じ組以外の数字と隣接させればよさそうだとわかります。

こうして、構成することができました。

実装

本数を数えるのが前もって数えるのが面倒だったのでメモリの確保を多めにしました。

program am
    implicit none
    integer::N
    integer::M
    integer,allocatable,dimension(:,:)::ANS
    integer::S

    integer::i,j
    read*,N
    allocate(ANS((N**2-N)/2,2))

    M=0
    S=N+merge(1,0,mod(N,2)==0)
    do i=1,N-1
        do j=i+1,N
            if(i+j/=S)then
                M=M+1
                ANS(M,1)=i
                ANS(M,2)=j
            endif
        end do
    end do
    print"(I0)",M
    do i=1,M
        print"(I0,A,I0)",ANS(i,1)," ",ANS(i,2)
    end do
end program am

おしまい

追記

この問題、考え方がカックロに似ているような気がする。

しずくぶろぐ

競技ぷろぐらみんぐしたり、なんかしたりします

不定期解説記事企画 AGC037 B #雫ぷよ

問題概要

解答までの道のり

実装

追記