AtCoder Grand Contest 068 B問題メモ

AtCoder Grand Contest 068

1個の問題をひたすら時間かけてじっくり考えられるのは、AGCでしかできない体験。（高レート帯で鎬を削っている人は別だが）

B - 01 Graph Construction

問題文

0,1 のみからなる文字列の組 $(S,T)$ が次の条件をすべて満たすとき (そしてそのときのみ) それを良い文字列組と呼ぶことにします．
- 条件
  - $S,T$ に含まれる 0 の個数は等しい．
  - $S,T$ に含まれる 1 の個数は等しい．
- 特に，良い文字列組 $(S,T)$ について，$S,T$ の長さは同じです．
良い文字列組 $(S,T)$ に対し，無向グラフ $G(S,T)$ を次のように定義します．
- $S$ の長さを $L$ とする．頂点 $1,2,\cdots,L$ からなるグラフ $g$ をつくる．
- $S$ に含まれる 0 の個数を $n$ とする．
  - $S$ に含まれる 0 の index を $1 \leq a_1 \lt a_2 \lt \cdots \lt a_n \leq L$ とする．
  - $T$ に含まれる 0 の index を $1 \leq b_1 \lt b_2 \lt \cdots \lt b_n \leq L$ とする．
  - 各 $1 \leq i \leq n$ に対し，頂点 $a_i$ と頂点 $b_i$ を結ぶ辺を $g$ に追加する．
- $S$ に含まれる 1 の個数を $m$ とする．
  - $S$ に含まれる 1 の index を $1 \leq c_1 \lt c_2 \lt \cdots \lt c_m \leq L$ とする．
  - $T$ に含まれる 1 の index を $1 \leq d_1 \lt d_2 \lt \cdots \lt d_m \leq L$ とする．
  - 各 $1 \leq i \leq m$ に対し，頂点 $c_i$ と頂点 $d_i$ を結ぶ辺を $g$ に追加する．
- 以上の手順で得た $g$ を $G(S,T)$ とする．

長さ $N$ の整数列 $A=(A_1,A_2,\cdots,A_N)$ が与えられます．
以下の条件をすべて満たす良い文字列組 $(S,T)$ を $1$ つ見つけてください．
- $S$ の長さを $L$ とする．$N \leq L \leq 10^5$ である．
- 各 $1 \leq i,j \leq N$ について，$G(S,T)$ で頂点 $i$ と頂点 $j$ が同じ連結成分に属すとき，そしてそのときのみ $A_i=A_j$ である．
なお，この問題の制約下で解が必ず存在することが証明できます．

制約

$1 \leq N \leq 100$
$1 \leq A_i \leq N$
入力される値はすべて整数

解法

問題文は長いが、丁寧に定義を書いているためなので、理解はしやすい。
$S,T$ の中の、0だけで $1,2,...$ 番目に出てきた同士、1だけで $1,2,...$ 番目に出てきた同士の indexと同じ番号の頂点を結んだグラフで、先頭 $N$ 頂点の連結・非連結関係を目的のものにする問題。

構築するグラフの頂点数 $L$ は $N$ よりかなり大きくても良い。
$N+1$ 以降でいろいろ頑張ってもいいよ、ということ。

実験

最終的な構築方法とは少し異なるものの、まずは実際に先頭から $S,T$ を $A$ に矛盾しないように決めてみる。

1手1手に説明を挟むと冗長になるが、まぁ、言葉より実例を見た方が早いので。。。

長いので折りたたみ

N=10
i:  1   2   3   4   5   6   7   8   9  10
A:  1   2   3   4   2   5   4   2   6   2

まず、先頭のi=1は同じものを置いて問題ない。

S:  0
T:  0

次のi=2、Ai=2 だが、Ai=2 の箇所は後にも出てくる。
S,Tに同じものを置くと独立な連結成分として確定してしまい、
後に出てくる他のAi=2の頂点と結べなくなる。違うものを置かないといけない。

S:  0   0
T:  0   1

今後、「$S$ には0、$T$ には1を末尾に置く」ことを「基本の置き方」とする。
$S$ の方が0の個数が多くなるように保つ前提とすると、基本の置き方は何も確定しない（いずれも、自身より後の頂点と結ばれる）。

逆にそれから外れた置き方をすると必ず結ばれる頂点が確定する。

「Sに1を置く」ことを「1を結ぶ置き方」とする。(T側の既存の1と、Sに新しく置いた1が結ばれる)
「Tに0を置く」ことを「0を結ぶ置き方」とする。(S側の既存の0と、Tに新しく置いた0が結ばれる)

0や1を結ぶ置き方をする場合に、それぞれどのindexの、何の数字と連結になるか？に着目して管理する。

$P_i$: $i+1$ 以降、次に $S$ に“1”を置いた場合に、その“1”が $n$ 番目として、$T$ 側で $n$ 番目の“1”がある $(j,A_j)$
$Q_j$: $j+1$ 以降、次に $T$ に“0”を置いた場合に、その“0”が $n$ 番目として、$S$ 側で $n$ 番目の“0”がある $(i,A_i)$

今決めようとしている $i$ に対し、$A_i$ と、$P_{i-1}$ や $Q_{i-1}$ の値が異なる場合は、非連結にしなければならない頂点が結ばれてしまうので、結ぶ置き方をすることはできない。

ひとまず、P2,Q2 は以下のようになる。
たとえばP2=(2,2)は、次にSに"1"を置くと、その"1"は1番目であり、
対になるT側の1番目の"1"は i=2 の位置にあり、
その位置の Ai=2 であることを示す。

i:  1   2   3   4   5   6   7   8   9  10
A:  1   2   3   4   2   5   4   2   6   2
S:  0   0
T:  0   1
P:     2,2
Q:     2,2

i=3,4 は、P2,Q2とAiが異なるため、結んではならず、基本の置き方しかできない。

i:  1   2   3   4   5   6   7   8   9  10
A:  1   2   3   4   2   5   4   2   6   2
S:  0   0   0   0
T:  0   1   1   1
P:     2,2 2,2 2,2
Q:     2,2 2,2 2,2

i=5 は、Ai=2 で共通するので i=2 と結べる。
だが、S,Tの両方とも結んでしまうと「i=2,5」だけで連結成分が閉じてしまい、
さらに後にある2と連結にできなくなる。
いずれか一方のみ、結ぶ置き方をすることができる。
（※今回は1を結ぶが、0を結んだり、また基本の置き方をしても矛盾はしない）

Pは、1つ進めてT側に2番目の"1"が置かれている i=3 の位置、Ai=3 となる。

i:  1   2   3   4   5   6   7   8   9  10
A:  1   2   3   4   2   5   4   2   6   2
S:  0   0   0   0   1
T:  0   1   1   1   1
P:     2,2 2,2 2,2 3,3
Q:     2,2 2,2 2,2 2,2

i=6,7 は基本の置き方しかできない。

i:  1   2   3   4   5   6   7   8   9  10
A:  1   2   3   4   2   5   4   2   6   2
S:  0   0   0   0   1   0   0
T:  0   1   1   1   1   1   1
P:     2,2 2,2 2,2 3,3 3,3 3,3
Q:     2,2 2,2 2,2 2,2 2,2 2,2

i=8 は、Tに0を置くことで、i=2 と結べる。（※ここでも、今回は結ぶが、結ばなくても矛盾はしない）
i=9 は基本の置き方しかできない。

i:  1   2   3   4   5   6   7   8   9  10
A:  1   2   3   4   2   5   4   2   6   2
S:  0   0   0   0   1   0   0   0   0
T:  0   1   1   1   1   1   1   0   1
P:     2,2 2,2 2,2 3,3 3,3 3,3 3,3 3,3
Q:     2,2 2,2 2,2 2,2 2,2 2,2 3,3 3,3

i=10, Ai=2。ここまでは2は結べてきたが、今は結べる相手はない。基本の置き方をするしかない。

i:  1   2   3   4   5   6   7   8   9  10
A:  1   2   3   4   2   5   4   2   6   2
S:  0   0   0   0   1   0   0   0   0   0
T:  0   1   1   1   1   1   1   0   1   1
P:     2,2 2,2 2,2 3,3 3,3 3,3 3,3 3,3 3,3
Q:     2,2 2,2 2,2 2,2 2,2 2,2 3,3 3,3 3,3

とりあえず $i=N=10$ まで進めたが、結構「連結にしてはいけない頂点を連結にしない」制約が厳しく、「連結にしなければならない頂点を連結にする」作業はあまり進まなかった。
$A_i=2$ である頂点のうちの一部（$i=2,5,8$）は結べたものの、他は「基本の置き方」しかできなかった。

$N$ より後を続けて考えてみる。
$N$ より後は、$A_i$ を自由に決められる、と考えることができる。
「基本の置き方」をする理由はなく、$P_{i-1},Q_{i-1}$ いずれかの値を $A_i$ に置き、結ぶ頂点を確定していくフェイズになる。

とりあえずi=10まで進めた際のP,Q両方の末尾となっている3を解消する。
3は1回しか出てこないので、両方結ぶ置き方で連結成分を閉じてよい。

i:  1   2   3   4   5   6   7   8   9  10| 11
A:  1   2   3   4   2   5   4   2   6   2|  3
S:  0   0   0   0   1   0   0   0   0   0|  1
T:  0   1   1   1   1   1   1   0   1   1|  0
P:     2,2 2,2 2,2 3,3 3,3 3,3 3,3 3,3 3,3 4,4
Q:     2,2 2,2 3,3 2,2 2,2 2,2 3,3 3,3 3,3 4,4

i=12 は Ai=4 とするが、4は i=4 以外にも出てくるので、閉じてはいけない。
いずれか一方のみ結ぶ。ここでは1を結ぶ。

i:  1   2   3   4   5   6   7   8   9  10| 11  12
A:  1   2   3   4   2   5   4   2   6   2|  3   4
S:  0   0   0   0   1   0   0   0   0   0|  1   1
T:  0   1   1   1   1   1   1   0   1   1|  0   1
P:     2,2 2,2 2,2 3,3 3,3 3,3 3,3 3,3 3,3 4,4 5,2
Q:     2,2 2,2 2,2 2,2 2,2 2,2 3,3 3,3 3,3 4,4 4,4

i=13 はAiに置く値として選択肢が 2,4 の2つあるが、
（理由は特にないがひとまず）2を置いて P の方を進めることにする。

i:  1   2   3   4   5   6   7   8   9  10| 11  12  13
A:  1   2   3   4   2   5   4   2   6   2|  3   4   2
S:  0   0   0   0   1   0   0   0   0   0|  1   1   1
T:  0   1   1   1   1   1   1   0   1   1|  0   1   1
P:     2,2 2,2 2,2 3,3 3,3 3,3 3,3 3,3 3,3 4,4 5,2 6,5
Q:     2,2 2,2 2,2 2,2 2,2 2,2 3,3 3,3 3,3 4,4 4,4 4,4

i=14 もPを進めるとする。
i=15 は、P,Q の末尾は i=4,7 と異なるものの値 4 は共通なので、Ai=4を置く。
両方結んでも連結成分が閉じてしまうことはないので、ひとまず両方結ぶ置き方をしてみる。

i:  1   2   3   4   5   6   7   8   9  10| 11  12  13  14  15
A:  1   2   3   4   2   5   4   2   6   2|  3   4   2   5   4
S:  0   0   0   0   1   0   0   0   0   0|  1   1   1   1   1
T:  0   1   1   1   1   1   1   0   1   1|  0   1   1   1   0
P:     2,2 2,2 2,2 3,3 3,3 3,3 3,3 3,3 3,3 4,4 5,2 6,5 7,4 9,6
Q:     2,2 2,2 2,2 2,2 2,2 2,2 3,3 3,3 3,3 4,4 4,4 4,4 4,4 6,5

i=16以降も、以下の法則で進めてみる。
・P,Qの末尾が異なったら、Pの方を進められるAiを置く
・P,Qの末尾が同じ数字だったら、連結成分が閉じることで破綻しない限りは、両方進める。
  破綻する場合は、Pの方を進める。

i:  1   2   3   4   5   6   7   8   9  10| 11  12  13  14  15   16   17
A:  1   2   3   4   2   5   4   2   6   2|  3   4   2   5   4    6    2
S:  0   0   0   0   1   0   0   0   0   0|  1   1   1   1   1    1    1
T:  0   1   1   1   1   1   1   0   1   1|  0   1   1   1   0    1    1
P:     2,2 2,2 2,2 3,3 3,3 3,3 3,3 3,3 3,3 4,4 5,2 6,5 7,4 9,6 10,2 11,3
Q:     2,2 2,2 2,2 2,2 2,2 2,2 3,3 3,3 3,3 4,4 4,4 4,4 4,4 6,5  6,5  6,5

ここまでで何となく、$i \ge N$ 以降に $A_i$ に置かれる値 $(3,4,2,5,4,6,2,...)$ は、当初の $A$ のうち、連結性が確定した頂点が除かれつつ、残りが順番を保って繰り返される様子となっている。
3周目に入っても同様の傾向が続き、いずれ全て除かれると、ひとまず手動での構築は完成する。

ただ、この方法は「非連結と指定された頂点が非連結」であることは（おそらく）保証されるが、「連結と指定された頂点が全て連結」となっているかは、よい証明がイマイチ見えづらい。
$A$ に“2”が12個あったとして、「6個ずつ別系統で結ばれてはいるが、系統同士は非連結だった」みたいなことが発生しないといえるか？

なので、このように先頭から積極的に結んでいく方法は、証明や実装が難しそう。。。

実験して、「連結にしてはいけない頂点を連結にしない」ための制約が結構厳しいことがわかった。
一度 $A_i=2$ である位置の $S_i$ に“0”を置くと、次に $T$ に“0”を置けるのは $A_j=2$ である位置しかないので、それ以外はずっと“1”を置き続けるしかない、みたいな箇所が多い。

だが、実験により、以下の傾向が見つかった。

実験の構築方法では、$S$ は、$i \ge N+1$ の範囲では全て1が置かれる
その際、$N$ 番目以降は $A$ がいくつか除かれつつ繰り返される

$L$ の上限は、$N^2$ より大きく余裕があることと合わせ、次の構築方法が思いつく。

構築

$S$ を、「先頭 $N$ 個を“0”、それより後を全て“1”」とする。
$T$ の側は、ほぼ“1”を置くことを基本としつつ、所々に計 $N$ 個の“0”を置く。

1周に付き1個、$T$ 側に“0”を置くことを考える。

$A_i=x$ が出現するindexを順に $I(x)=(i_1,i_2,...,i_k)$ とすると、次のように構築する。

$l$ 周目では、「$I(A_l)$ で $l$ の次に出てくるindex（最後の場合は先頭）」に相当する頂点の $T$ に“0”を置く

「1周」「相当する頂点」などの言葉の定義が曖昧だが、言葉より図で示した方が速い。以下のようにする。

周          1                   2                 3               4             5
i: 1 2 3 4 5 6 7 8 910| ....             |                |              |            |
A: 1 2 3 4 2 5 4 2 6 2| 2 3 4 2 5 4 2 6 2| 2 3 4 5 4 2 6 2| 2 4 5 4 2 6 2| 2 4 5 2 6 2|...
S: 0 0 0 0 0 0 0 0 0 0| 1 1 1 1 1 1 1 1 1| 1 1 1 1 1 1 1 1| 1 1 1 1 1 1 1| 1 1 1 1 1 1|...
T: 0 1 1 1 1 1 1 1 1 1| 1 1 1 0 1 1 1 1 1| 1 0 1 1 1 1 1 1| 1 1 1 0 1 1 1| 1 1 1 0 1 1|...

$T$ で“0”が置かれた箇所は、$A$ に登場する数字の順になっていることがわかる。
また、$T$ に“0”が置かれた数字は、$A$ の次の周回では除かれている。

$A$ に複数回出てくる“2”に注目すると、以下のようになっている。

“0”によって $A$ の「1番目」の2（$i=2$）と結ばれているのは、2周目で「2番目」に出現する“2”
“0”によって $A$ の「2番目」の2（$i=5$）と結ばれているのは、5周目で（元）「3番目」に出現する“2”
- ※2番目に出現する“2”が3周目以降除かれているため実際は2番目に出現するが、由来としては3番目

もう少し詳しく見るため、$A,S,T$ の中で $A_i=2$ に該当する箇所だけ取り出す。
1周目で出てくる順に $W,X,Y,Z$ と記号を振ると、

周    1        2       3      4      5     6    7    8   9 10    
   W X Y Z  W X Y Z  W Y Z  W Y Z  W Y Z  W Z  W Z  W Z  W  W
A: 2 2 2 2| 2 2 2 2| 2 2 2| 2 2 2| 2 2 2| 2 2| 2 2| 2 2| 2| 2|
S: 0 0 0 0| 1 1 1 1| 1 1 1| 1 1 1| 1 1 1| 1 1| 1 1| 1 1| 1| 1|
T: 1 1 1 1| 1 0 1 1| 1 1 1| 1 1 1| 1 0 1| 1 1| 1 1| 1 0| 1| 0|
            a b c d  e f g  h i j  k l m  n o  p q  r s  t  u  ┐"1"により同じ文字で
   a b c d  e   f g  h i j  k l m  n   o  p q  r s  t    u     ┘示された箇所同士が結ばれる
   w x y z                                                     ┐"0"により同じ文字で
              w                      x                y     z  ┘示された箇所同士が結ばれる

“1”によって、1周目のWと2周目のW (a)、2周目のWと3周目のW (e)、3周目のWと4周目のW (h)、、、が連結になっていく。
要するに、$W,X,Y,Z$ の記号が同じものは、全ての周を通して連結になる。
この上で、“0”を使って $W～Z$ の間を連結にする。

2周目の $T$ 側に置いた“0”（w）で、1周目のWと2周目のXが結ばれる。
つまり、全てのWと全てのXが連結になる。

5周目の $T$ 側の“0”（x）で、1周目のXと5周目のYが結ばれる。
8周目の $T$ 側の“0”（y）で、1周目のYと8周目のZが結ばれることで、全てが連結になった。

10周目の $T$ 側の“0”（z）で、1周目のZと10周目のWを結び閉じることで、これ以降、余計な箇所と連結になることを防ぎ、完結する。

この構築方法は、$L=\frac{N(N+1)}{2}$ となり、余裕を持って $L \le 10^5$ となる。

Python3

目次

AtCoder Grand Contest 068 B問題メモ

B - 01 Graph Construction

問題文

制約

解法

実験

構築