AtCoder Grand Contest 061 B,C問題メモ

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

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)

C - First Come First Serve

問題

店に人が $N$ 人並んでいて、$i$ 番目の人は時刻 $A_i$ に入り、$B_i$ に出る
- 時刻は $1～2N$ の整数で表現され、全て異なる
- $A$ も $B$ も単調増加、つまり先に入った人は、必ず後に入った人より先に出る。
店には客が名前を書くリストがあり、各人は、入る時か出る時のいずれかで1度だけ、リストの末尾に名前を書く
名前が書かれる順序として考えられるのが何通りあるか、$\mod{998244353}$ で求めよ
$1 \le N \le 5 \times 10^5$

解法

包除原理をDPでやる。

問題を言い換えると、$1～N$ が2回ずつ出てくる長さ $2N$ の数列があって（$i$ の出現位置は $A_i$ と $B_i$）、

1 2 3 1 4 2 5 3 4 6 5 6

ここから $1～N$ を1つずつ取ってできる部分列の種類数を求める。

重複を気にしなければ $A_i,B_i$ どっちを取るかで $2^N$ 通りあるが、同じものができるのを除かないといけない。

で、同じのがいつできるかというと、例えば“2”は、
その間の“3 1 4” が全部違う方（1は前、3,4は後）が選択される場合、どっちを選んでも変わらなくなる。
$A_i,B_i$ 単調増加なので、1つの数字の間に同じ数字が2個ある、なんてことは発生しない。

1 2 3 1 4 2 5 3 4 6 5 6
    ~~~~~                  2以外の数字の取り方がこのような状況だと
1 ?       ? 5 3 4     6    2はどちらを取っても同じ

こういうパターンは「必ず前の方を取ることにする」と決めると、重複を除ける。
なので、こういう状況で後ろの方を取ってしまうようなケースを除いていく。

2の場合、除外すべきケースは 1,2,3,4 の4つの数字の取り方が固定され、残る 5,6 の2個の自由度がある。
（包除原理の時の感覚で）他の重複は気にせず2の重複だけを考えた場合、そのケースは $2^2$ 通りあることになる。

各 $i$ につき固定される数字を整理すると、

    iの除外ケースで固定される数字
i   前     後
1:         1,2,3
2:  1      2,3,4
3:  1,2    3,4,5
4:  2,3    4,5
5:  3,4    5,6
6:  5      6

固定される数字の性質として、

前に固定される数字～後ろに固定される数字は連続した区間を為す
- $i$ に対する区間を $[L_i,R_i]$ とする
  - 上の例で $i=4$ の場合、$L_i=2,R_i=5$
ある $i,j$ について、固定される数字の中に共通するものがあってそれが「一方は前、もう一方は後に固定される」ようなことが1つでもある場合、$i,j$ の除外ケースが同時に発生することはない

2つめについて、たとえば、“3”は、2の除外ケースでは後ろ、5の除外ケースでは前に固定されるので、2と5の重複が同時に発生するのは矛盾。

特に、$i$ の除外ケースでは $[L_i,i)$ が前、$[i,R_i]$ が後ろに固定される。
$[L_i,R_i]$ と $[L_j,R_j]$ が被る場合、$i \le x \lt j$ となる $x$ があるはずで、その時 $x$ は $i$ では後ろ、$j$ では前に固定されている。
よって、前とか後ろとかは考慮せずとも、そもそも $[L_i,R_i]$ の区間が被るものは同時に発生し得ない。

よって、問題は包除原理を使って更に以下に言い換えられる。

$N$ 個の区間から重複しないものを選ぶ全ての選び方に対し、$(-1)^{区間数}2^{区間に含まれない要素数}$ を合計せよ

i   0  1  2  3  4  5  6
1      |-----|
2      |--------|
3      |-----------|
4         |--------|
5            |--------|
6                  |--|

一見、区間ごとに長さもバラバラだし、$O(N^2)$ とかかけないと無理そうに思えるが、以下のDPを考えると

$DP'[i,j] = i$ 番目の区間までを考慮し、$A_1～A_j$ を考えた時の場合の数

$i$ 番目の区間は少なくとも $i$ を含むので、各更新では必ず

$DP'[i-1, i未満のj]$ の値を元として、$DP'[i,i以降のj]$ を更新する

という形になる。よって、DPは $i$ の次元を無視して破壊的に更新できる。

$DP[i] = A_1～A_i$ を考えた時の場合の数（破壊的に更新）

区間 $i$ について更新するとき、

区間 $i$ を使わない場合
- $DP[i] += DP[i-1] \times 2$
区間 $i$ を使う場合
- $DP[R_i] += DP[L_i-1] \times -1$
- 区間を1つ追加するので、-1がかかる

このようにして、$DP[N]$ が答えとなる。