DouKaku? 3618 tell: * 補題 1 a, b, cについ...(水の移し替えパズル)

Comment detail

* 補題 1

a, b, cについて，b >= 3の時，
(a, b, c)から(a, b - 3, c + 3)
を得るような手順があり，それは最小3手でできる．

* 補題 2

補題1は，条件のa, b, cを任意に入れ替えても成り立つ．

* 補題 3

補題1は，a = 0であっても成り立ち，かつ題意に反しない．

* 定理 4 ( 解の存在 )

a, b, cについて，a - b, b - c, c - aの3つのうち，
少なくとも1つが3の倍数ならば，
このa, b, cに対して題意を満たすような解が存在する．

* 定理 5 ( 探索の上限 )

a, b, cに対し，cに全ての水を入れるとした時，
a - bが3の倍数ならば，題意を満たすような手数が存在し，
それはmax{a, b}.

* 定理 6 ( 手数の最小 )

a, b, cに対して，題意を満たす最小の手数は，
定理4より得られる手数のうちの最小．

証明は皆さんの宿題です:-)
とか書いてみたりして．

短い証明を考えていて，時間を無駄に使ってしまったのはココだけの秘密です:-)

ということで，実際に探索する必要は無く，入力に対する算術演算だけで最小手数を求めることができるようですね．
大きな入力であっても効率的に解けそうです．

それと，一般化できそう…

def water_puzzle_solver(a, b, c)
  [[a,b],[b,c],[c,a]].select{|x,y|(x-y)%3==0}.map{|x|x.max}.min
end

## 以下テスト

p water_puzzle_solver(1, 2, 3) # not feasible
p water_puzzle_solver(3, 6, 9)
p water_puzzle_solver(4, 2, 10)
p water_puzzle_solver(827392, 65536, 122880)

100.times {| i |
  a, b, c = rand(2**32), rand(2**32), rand(2**32)
  puts "( #{a}, #{b}, #{c} ) -> #{water_puzzle_solver(a,b,c)}"
}

あ，定理4と定理5の内容が一部被ってるな．
まあいいか．

バケツA, B, Cに入っていた水をそれぞれa, b, cと表現することにします。 AとBを空にすることを考えてみます。一般性を失わずにa <= b と仮定できます。

aとbを3で割ったあまりが一致する場合：

まずバケツAが空になるまでAとBからCに水を移します。 a, bともに1回に1リットルずつ減るので、a手後にバケツAが空になります。

次にBも空にするために、「Aに1回集めてから、Cに2回集める」という作業をします。 (+2, -1, -1), (-1, -1, +2), (-1, -1, +2)の合計で(0, -3, +3)になり、 3手でBからCに3リットルを移し替えたことになります。ここで、最初の「aとbを3で割ったあまりが一致する」という条件からb - a は3の倍数なので b - a手でBを空にできることがわかります。

合計すると、aとbの3で割ったあまりが一致する場合には b手でそれぞれ0にすることが可能だと言うことがわかります。また、バケツの水は1ステップで最大1しか減らないので、バケツBを空にするには最低b手が必要であることがわかります。よってaとbを3で割ったあまりが一致する場合には、b手で両方を0にする手が存在し、それが最小です。

aとbを3で割ったあまりが一致しない場合：

a - bに注目すると、これはCに集める場合には変化せず、AまたはBに集める場合には3増減します。 3で割ったあまりが一致しないということはa - bが3の倍数ではないということなので、 a - bを3の倍数である0にすることは不可能です。よってaとbを3で割ったあまりが一致しない場合は、aとbをともに0にすることはできません。

あとは、bとc, cとaのペアについても考えて、あまりが一致するペアが複数あるならばそのペアの大きい方が最小のものが全体の最小手数、 1個しかないのならそのペアの大きい方が最小手数、存在しないならその問題は解けない、と言えます。

このお題は「一見探索が必要な問題に見せかけて、実はよく考えると必要ない」というのがポイントでした。ちなみに一般化しようとすると http://ja.doukaku.org/53/ 仲間はずれの判定どう書く？org につながっていくかと思います。

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq