わぁい構築 あかり構築大好き
まず、パスが長くなる方が自由が利かなそうなので、一番大きい色 $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$)はどういう配置ができるかを考えると、
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$ 以外の色は、$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 ■■
上手いことできない。
その理由を考えて、空きマス数の偶奇に着目する。
グリッドの埋め方を考えると、1つの色を埋め終わると「どれか2つの行、またはどれか2つの列のみ、偶奇が反転する」ことになる。
2列型 2行型 ↓ ↓ →■ ■■ ■■ ■■ → ■
色 $N$ を埋め終わった時、
となっている。特に、空きマス数が奇数の行があるため「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$ を所定の場所に再配置することで必ず作れる。
包除原理を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
固定される数字の性質として、
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]$ の区間が被るものは同時に発生し得ない。
よって、問題は包除原理を使って更に以下に言い換えられる。
i 0 1 2 3 4 5 6 1 |-----| 2 |--------| 3 |-----------| 4 |--------| 5 |--------| 6 |--|
一見、区間ごとに長さもバラバラだし、$O(N^2)$ とかかけないと無理そうに思えるが、以下のDPを考えると
$i$ 番目の区間は少なくとも $i$ を含むので、各更新では必ず
という形になる。よって、DPは $i$ の次元を無視して破壊的に更新できる。
区間 $i$ について更新するとき、
このようにして、$DP[N]$ が答えとなる。