KUPC 2015 の I 問題（ハウスシャッフル）の私的解説
懇親会の最中にハウスシャッフルの解説を複数の人から求められたので、私の解答を説明しておくことにします。
まずは、シャッフルという操作を理解しましょう。たとえば σ(1) = 3 だとします。シャッフルの定義により、b[i, 1] = a[σ(i), 3] または a[3, σ(i)] なので、1 列目にはもともと 3 列目にあったお菓子が現れます。図を描くとこういうことですね。
. x
. . x .
. . x x . .
x . x . --> x . . .
. x x . . x . . . .
. . x . . . x . . . . .
同じように考えると、σ(x) = y のとき、x 列目にはもともと y 列目にあったお菓子が現れることがわかります。
このままでは少しやりにくいので、向きを反対にしましょう。たとえば 1 列目にあったお菓子がどの列に現れるのかを考えます。σ(x) = y のとき、x 列目にはもともと y 列目にあったお菓子が現れるのでした。今考えているのは y = 1 の場合ですから、σ(x) = 1 となるような x を考えればいいわけです。いちいち σ(x) = 1 を満たす x と書くのは面倒くさいので、代わりに σ'(1) と書くことにします。一般に σ(x) = y のとき σ'(y) = x ということにします。いわゆる逆置換ですね。σ' を用いると、もともと 1 列目にあったお菓子はシャッフルされると σ'(1) 列目に現れる、と言い換えることができます。σ' がわかれば σ もわかります。というか、ループを回して σ(σ'(k)) = k とするだけです。
さて、家を提示できるのは一度きりなので、それだけで σ ないし σ' が復元できるようにうまく細工しないとなりません。とはいえ、一度に全部を考えるのは難しいので、まずは σ'(1) だけでも求められる方法がないか考えてみます。すでに気づいている人も多いかと思いますが、1 列目に片方のお菓子を置いて、それ以外の列にはもう片方のお菓子を置くことにすれば、1 列目に置いたほうのお菓子がどの列に現れたかを確かめることで σ'(1) の値がわかります。ここではキャンディーを 1 列目に置くことにしましょう。要するにこういうことです（図は σ'(1) = 4 の場合）。
@ o
@ o o o
@ o o @ o o
@ o o o --> o @ o @
@ o o o o o o @ @ o
# # # # # # # # # # # #
この例について、それぞれの列にキャンディーが何個あるか数えてみると、4 列目には (N - 1) 個だけありますが、ほかの列には 1 個しかありません。なので、すぐに σ'(1) = 4 だとわかります。
σ'(1) を得られるようになりました。しかし、このままではほかの値がわかりません。そこでもう少しキャンディーを置くことにしましょう。ビスケットの真上の段に注目します。すると、座標が (2, 1)、(3, 2)、(4, 3)、…といったように値が 1 だけずれていることがわかります。試しにキャンディーを置いてみます。
@
@ o
@ o o
@ o o o
@ @ @ @ @
# # # # # #
このとき、それぞれの列のキャンディーの個数は次のようになっていることがわかります。
- 2 列目は (2, 1)、(3, 2) の 2 個。
- 3 列目は (3, 1)、(3, 2)、(4, 3) の 3 個。
- 4 列目は (4, 1)、(4, 3)、(5, 4) の 3 個。
- 以下、(N - 1) 列目までは同様。
- N 列目は (N, 1)、(N, N - 1) の 2 個。
なので、シャッフルした後の列を調べて、キャンディーが 2 個だったら、その列はもともと 2 列目だったか N 列目だったかのどちらかということになります。区別したいですね。(2, 1) のキャンディーをマシュマロにしてしまいましょう。
@
@ o
@ o o
@ o o o
o @ @ @ @
# # # # # #
こうすれば、2 列目は 1 個、N 列目は 2 個、となって区別がつきます。きっと 1 列目のキャンディーが (N - 1) 個から (N - 2) 個になっても大丈夫でしょう。念のため N の範囲を確認しますか。
6 ≤ N ≤ 200
1 列目には最低でも 6 - 2 = 4 個のキャンディーが現れます。大丈夫でしたねｗ。
これで σ'(1)、σ'(2)、σ'(N) は何とかなりました。あとは σ'(3)、…、σ'(N - 1) ということになりますが、実は σ'(3) はすぐにわかります。(2, 1) のキャンディーを取ってしまったので、2 列目には (3, 2) にしかキャンディーがありません。シャッフルすると 2 列目は σ'(2) 列目に移って、ただひとつのキャンディーは (σ'(3), σ'(2)) ないし (σ'(2), σ'(3)) に現れるわけですが、すでに σ'(2) はわかっているので、σ'(2) ではないほうの値が σ'(3) となります。
σ'(3) がわかれば、今度は σ'(3) 列目を調べて、そこにあるキャンディーのうち (σ'(3), σ'(1))、(σ'(3), σ'(2)) でないものが (σ'(4), σ'(3)) であるとわかり、先ほどと同じ理屈で σ'(4) がわかります。σ'(4) がわかると、σ'(5) もわかります。以下、同様にして σ'(N - 1) まで（あるいは σ'(N) まで）わかります。
というわけで、前出のとおりにお菓子を配置して、シャッフル後の家が提示されたらそれぞれの列のキャンディーの個数を数えて、(N - 2) 個だったらその列が σ'(1)、1 個だったら σ'(2)、あとは σ'(k) 列目を調べて σ'(k + 1) を求めて、最後に σ' から σ を求める、というのが正解（のひとつ）なのでした。
