AtCoder Beginner Contest 296 F,Ex問題メモ

AtCoder Beginner Contest 296

F - Simultaneous Swap

• 長さ $N$ の数列 $A=(A_1,A_2,\ldots,A_N)$, $B=(B_1,B_2,\ldots,B_N)$ が与えられる
• 次の操作を好きなだけ ($0$ 回でも良い) 繰り返す事ができる
  • $1$ 以上 $N$ 以下の、どの $2$ つも互いに相異なる $3$ つの整数 $i,j,k$ を選ぶ
  • $A$ の $i$ 番目の要素と $j$ 番目の要素を交換し、$B$ の $i$ 番目の要素と $k$ 番目の要素を交換する
• うまく操作を繰り返すことによって、$A$ と $B$ を一致させる事が可能か判定せよ
• $3 \leq N \leq 2\times 10^5$
• $1\leq A_i,B_i\leq N$

まず、こういうのは2つの数列に同時に操作するよりは、 片方を固定してもう片方を合わせにいく方が楽なので、そういう言い換えができないか考える。

するとこれは、片方（たとえば $A$）の任意の3つをシフトさせる操作に言い換えられる。
（実際に問題文の通りに操作をして、$B$ の方を元の並びに直したとき、$A$ の変化を確認するとわかる）

• Kiri8128氏のユーザー解説
  • 解説 - AtCoder Beginner Contest 296

そうとわかれば実際に操作をして $A$ を $B$ に合わせにいくのは $O(N)$ でできるが、

• どんな順番でやっても大丈夫? 操作順によって結果は変わらない?
• 同じ要素が含まれると、どれを揃えにいくかで結果が変わらない?

という懸念が生じる。

この証明に有用なのが、swap回数の偶奇に着目する方法。

• 置換と偶置換・奇置換に関する基礎的なこと | 高校数学の美しい物語

要素が全て区別できる数列と、それに任意の2要素のswapを繰り返し行った数列を比べると、 どういう順番でやっても、swapを偶数回やったのか奇数回やったのかは特定できる。

3つの数をシフトするのは、swapを2回行うことに相当する。
つまり、$A$ から $B$ にするのに奇数回のswapが必要なら、この問題の操作によって一致させるのは不可能ということになる。

実際に端から $A$ を $B$ に合わせにいくと、最後から3要素目までは必ず一致させることができる。

その時、最後の2要素は、自然に揃っているか、入れ替わっているかのどちらかである。

揃っているならその事実ができるという証明になり、 入れ替わっている場合は、$A$ から $B$ にするのに奇数回のswapが必要と言うことになるので不可能となる。

この場合は必ず一致させられる。

実際に以下のようなケースを手で解いてみてもよいが、

A  1 1 2 3
B  1 1 3 2

最後が入れ替わっていても、いったん揃った 1 を崩すことで、最後の2要素を入れ替えて $B$ に合わせられる。

これは、最後の2と3のswapで奇数回となったswapの総数を、1同士でもswapすることで偶数回に戻しているとも言える。

Python3

Ex - Unite

• $N$ 行 $M$ 列のマス目があり、各マスは黒または白で塗られている
  • 初期状態で少なくとも $1$ つのマスが黒く塗られている
• 白く塗られたいくつかのマス ($0$ 個でもよい) を新しく黒く塗ることによって、黒く塗られたマス全体が連結になるようにしたい
  • 連結とは、縦横に隣接した黒マスを伝って、どの黒マス同士も行き来できる状態を指す
• 目標を達成するために新しく塗る必要のあるマスの個数としてあり得る最小値を求めよ
• $1 \leq N \leq 100$
• $1\leq M \leq 7$

連結DPと呼ばれることがある問題。

• 競技プログラミングにおける連結DP問題まとめ - はまやんはまやんはまやん

横幅 $M$ が小さいので、行の黒マス配置を $2^M$ のbitフラグで持ったDPをしそうなことは想像つく。

1つ前の行 $2^7$ 通り→今の行 $2^7$ 通りの遷移を全探索するのは $2^{14} = 16384$ なので、 これを $100$ 行繰り返すと $1.64 \times 10^6$ となり、計算量的に余裕だぜ！となる。。。

が、よく考えるとそれでは足りない。

ある離れた2マスが、より前の行で繋がっているのか、繋がってないのでこれ以降で繋げないといけないのか、区別できない。

      i  ①     ②     ③
      0  ####   #.##   #.##
prev> 1  #..#   #..#   #..#
now > 2  #..#   #..#   #..#
      3  #..#   #..#   ####

• ①は $i=0$ で既に繋がっているので、以下の行でも繋げる必要は無い
• ②は繋がっていないが、後の行で繋げるよりも $i=0$ で繋げてしまった方がよい
• ③は $i=2$ では繋がっていなくても $i=3$ で繋がるので、繋げる必要は無い

特に、②と③を区別できない。（$i=0$ で繋げたのならnowまでの最小数は1個、繋げてないのならこれ以降で繋げる必要がありつつ最小数は0個）

なので、「どのマスとどのマスが繋がっているの？」という連結状態も管理してやる必要がある。

連結状態も含めてDPの「状態」とすれば、今度こそ、全体がひとつながりになれるかどうかを区別できる。

連結状態をどう表現するかにはある程度の個人差がありそうだが、例えば以下の実装がある。

• $k$ 進数にする
• 隣接行列を添える

例えば過去の類題 Typical DP Contest S - マス目 の解説ブログの1つでは、

• Typical DP Contest : S - マス目 - kmjp's blog

bitフラグでなく $k$ 進数で状態を表し、別々の連結成分に属する黒マスには別々の数字を割り当てる、としている。

今回は最大 $7$ マスなので別々の連結成分の最大は4つで、白マスと合わせて $5$ 進数で状態を表せる。

「前の行の、連結性を含んだ状態」と「今の行の、連結性は未計算の黒マス配置」があれば、今の行の連結性は計算できる。

連結性を含めても、とある黒マス配置に対して実際に可能な連結状態は限られているので、思ったより状態数は増えない。
（実際にやってみると、320ちょっとくらい。$2^7=128$ なので、3倍にもなってない）

連結性チェックの部分は、Union-Findを使っている例もあるし、自分はDFSをおこなった。

計算量は、連結性含みの状態数を $C$ とすると、

• 1行の遷移で、$C \times 2^M$ の総当たり、その中で $O(M)$ とか $O(M^2)$ とかの連結性チェック
• $N$ 行の遷移全部で、$O(N C M 2^M)$
• 最大値を代入して $3 \times 10^7$ 程度になるので、間に合う。

連結性チェックに $O(M^2)$ かけた場合はちょっと厳しくなるが、 そもそも遷移の種類数 $C \times 2^M$ が限られているので、メモ化すれば十分間に合う。

いずれも答えは0

6 7
#######
#.....#
#.###.#
#.#.#.#
#.#...#
#.#####

5 7
#######
#.....#
#.###.#
#.#.#.#
#.#.###

Python3