AtCoder Grand Contest 061 B問題メモ

わぁい構築あかり構築大好き

B - Summation By Construction

問題

一方が $N$ 頂点、もう一方が $N+1$ 頂点の完全二部グラフの辺は、$N(N+1)$ 本ある
この辺を、以下の条件を満たすように $N$ 色で塗り分ける（色を整数 $1～N$ で表す）
- 色 $i$ の辺はちょうど $2i$ 本ある
- 色 $i$ の辺だけを取り出したとき、単純パスになっている
  - つまり、同じ頂点を通ることなく、1本道で $2i+1$ 個の頂点を通るようになっている
このような塗り分け方ができるか判定し、可能なら塗り分け方の一例を示せ
1つの入力につき $T$ ケース与えられる
$1 \le T \le 100$
$1 \le N \le 100$

解法

まず、パスが長くなる方が自由が利かなそうなので、一番大きい色 $N$ を考える。
これは全ての頂点を巡らないといけないので、ほぼ一意に決まる。

  ,---①
①
  冫==②
②
  冫==③
③
  `---④

どの順に通るかは変更できるものの、まぁ、最初に決めるのであれば、対称性より上記の順で固定して問題ない。

これを、出力のフォーマット（左側グループ $i$、右側グループ $j$ を結ぶ辺の色を $C_{i,j}$ の行列で出力）にすると、

N=5
i\j  1 2 3 4 5 6
1    5 5
2      5 5
3        5 5
4          5 5
5            5 5

こんな感じになる。なんか綺麗なナナメラインになっている。

これを参考に、この行列上で残りの色（たとえば $c$）はどういう配置ができるかを考えると、

（行列をグリッドとして捉えるとして）
空きマスからスタートする
同じ行の空きマス→同じ列の空きマス→同じ行の空きマス･･････というように行と列を交互にたどる
- 列→行→列･･･でもよい
一度訪れた行・列は再度訪れてはいけない（1つの行に同じ色は2つまで）
$2c$ 個になるまで繰り返せたらおわり

c=4の例
i\j  1 2 3 4 5 6
1    5 5    [4]    [4] スタート
2      5 5 4-+-4   (4) ゴール
3    4-----+-4 |
4    |     | 5(4)
5    4-----4 5 5

これが、問題の辺の張り方の条件と一致する。全ての色を上手いこと埋められたら成功。

上の例は縦横無尽に駆け回りすぎてアルゴリズム的な構築がしづらいので、なるべくは色 $N$ のように、ナナメラインを作りたい。

$N$ が奇数

上手いことできる。

$N$ 以外の色は、$i$ と $N-i$ で丁度ペアが作れるので、ペアで1つのナナメラインをずらしながら埋めていける。

i\j  1 2 3 4 5 6    1と4、2と3がペア
1    5 5 1 1 2 2    ■■
2    2 5 5 4 4 2      ■■    ペアでこのような形を構成し、
3    3 3 5 5 4 4        ■■    2個ずつ右にずらす（左右はループ）
4    4 3 3 5 5 4          ■■
5    4 4 3 3 5 5            ■■

$N$ が偶数

上手いことできない。

その理由を考えて、空きマス数の偶奇に着目する。
グリッドの埋め方を考えると、1つの色を埋め終わると「どれか2つの行、またはどれか2つの列のみ、偶奇が反転する」ことになる。

2列型     2行型
↓  ↓    →■
■■        ■■
  ■■    →  ■

色 $N$ を埋め終わった時、

全ての行の残り空きマス数は、奇数
列に関しては $j=1,N+1$ のみ奇数、残りは偶数

となっている。特に、空きマス数が奇数の行があるため「2行型」を用いないといけないことがわかる。
（$N$ が奇数の時は、全ての行の残り空きマス数は偶数だったため、全て2列型で埋めることができた）

1行に少なくとも1個、2行型のスタートかゴールが存在しないといけない。
よって、試しに2行型だけで色 $N$ 以降の残り盤面を埋めていくことを考える。

$N$ 奇数の時と同様、ペアが作れたら楽だなぁと考えると、今度は「$i$ と $N-i+1$」をペアとしてナナメラインを作っていけることに気付く。（$i=2～$）

i\j  1 2 3 4 5 6 7    5と2、4と3 がペア
1    6 6 4 4 5 2      ■
2    5 6 6 4 3 2 2    ■■        ペアでこのような形を構成し、
3    5 5 6 6 3 3 2      ■■        2こずつ下にずらしていく。（上下はループ）
4    4 5 5 6 6 3 3        ■■        スタートを i 行目とすると
5    4 4 5 5 6 6 3          ■■        ゴールは i+1 行目になり、
6      4 4 5 5 6 6            ■■        2行ずつ、行の空きマス数が偶数に揃っていく
                                ■■
                                  ■

最後に右上と左下が余る。まだ使っていない色は'1'だが、このままでは'1'のみ条件を満たせない。
だが、ほとんど完成しているので、ペアを少し崩せばなんとかできないか。

いろいろ試行錯誤すると、5と2のペアを崩して以下のようにすれば、達成できる。（もっとスッキリした方法があるかも）

i\j  1 2 3 4 5 6 7
1    6 6 4 4[2]2[5]
2    5 6 6 4 3 2[5]
3   [1]5 6 6 3 3[1]
4    4 5 5 6 6 3 3
5    4 4 5 5 6 6 3
6   [5]4 4 5[2]6 6

$N=2$ の時はサンプルにあるとおり不可能だが、それ以上なら $1,2,N-1$ を所定の場所に再配置することで必ず作れる。

Python3

t = int(input())
for _ in range(t):
    n = int(input())

    if n == 2:
        print('No')
        continue

    ans = [[0] * (n + 1) for _ in range(n)]
    for i in range(n):
        ans[i][i] = n
        ans[i][i + 1] = n

    if n % 2 == 1:
        offset = 2
        for k in range(n // 2):
            k += 1
            for i in range(k):
                ans[i][(i + offset) % (n + 1)] = k
                ans[i][(i + offset + 1) % (n + 1)] = k
            for i in range(k, n):
                ans[i][(i + offset) % (n + 1)] = n - k
                ans[i][(i + offset + 1) % (n + 1)] = n - k
            offset += 2
    else:
        offset = 1
        for k in range(n - 1, n // 2, -1):
            for i in range(k):
                ans[(i + offset) % n][i] = k
                ans[(i + offset + 1) % n][i] = k
            for i in range(k, n + 1):
                ans[(i + offset) % n][i] = n - k + 1
                ans[(i + offset + 1) % n][i] = n - k + 1
            offset += 2

        ans[2][0] = 1
        ans[2][-1] = 1
        ans[0][-3] = 2
        ans[-1][-3] = 2
        ans[-1][0] = n - 1
        ans[0][-1] = n - 1
        ans[1][-1] = n - 1

    print('Yes')
    for row in ans:
        print(*row)

目次

AtCoder Grand Contest 061 B問題メモ

B - Summation By Construction

問題

解法

$N$ が奇数

$N$ が偶数