目次

AtCoder Beginner Contest 296 F,Ex問題メモ

AtCoder Beginner Contest 296

F - Simultaneous Swap

F - Simultaneous Swap

問題

解法

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

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

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

という懸念が生じる。

swap回数の偶奇

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

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

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

AA の要素が全て異なる場合

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

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

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

AA の要素に同じものがある場合

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

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

A  1 1 2 3
B  1 1 3 2

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

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

Python3

Ex - Unite

Ex - Unite

問題

解法

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

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

1つ前の行 2727 通り→今の行 2727 通りの遷移を全探索するのは 214=16384214=16384 なので、 これを 100100 行繰り返すと 1.64×1061.64×106 となり、計算量的に余裕だぜ!となる。。。

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

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

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

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

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

連結状態の表現方法

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

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

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

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

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

連結性の判定

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

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

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

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

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

失敗しそうな入力とか

いずれも答えは0

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

Python3