負の駆逐 - λx. x K S K ＠はてな

（これは id:KeisukeNakano:20060817:1155714034 の解答です．問題はそちらをご覧ください）

挑戦した方に前もって言っておくと「実際に操作を繰り返してその回数を数えるプログラム」というのは期待された解答ではない．もっと効率的にその回数を求めてほしいというのが出題した意図である．出典は 1986 年の国際数学オリンピック（IMO）ワルシャワ大会の 3 問目．但し，問題設定や要求する解答はやや異なる．相違点は以下の通り．

相違点	IMO の問題	今回の問題
点の個数	5個のみ	3個以上
点の値の合計	正の数	1
操作の対象	負数値の点のみ	任意の点
問題の要求	停止性の是非	停止までの最低回数

IMO の問題では，数学の問題らしく，停止性の是非だけを問いその証明を求めている．実際には，頂点が 5 個でなくても必ず停止することが証明できるが，この回の IMO では何故かそこまで要求しなかったようだ．今回のプログラミングの問題では，停止することは前提としたうえで，停止するまでの最低回数を求める問題とした．但し，問題を簡単にするため値の合計を 1 に限定している．（実はこの制限がミソなのだが）

解法のポイントは以下の通り．

合計は変化しない

3 つの列んだ点が x, k, y という値をもつとき，真ん中の点に操作を施すと x+k, -k, y+k と変化するため，合計はいずれも x+k+y となる．この点についてはコンテストで解答した全てのチームが気づいたようだった．今回の場合，全ての点の値の合計は 1 なので，「全ての点の値が正」という最終状態は，「ある点の値が 1 で他の点の値が全て 0 」という状態であることを意味する．

負の値に対して操作

解答したチームはそれぞれ実験による考察から，最小値について操作するのが最小操作回数になると（証明抜きで）判断したようだ．実際には，今回の設定の場合，最小値を探さなくとも，毎回負の値をもつどの点に操作しても最小操作回数で停止することが証明できる．この証明は，次の項目に関連する．

なぜ停止するのか考える（状態関数の発見）

停止性を証明する手法としてよくある方法は，操作によって必ず（一定量）減少し且つ最小値を持つような状態関数をうまく定義することである．今回の場合「全ての点の値の合計」は不変なのでこの状態関数は使えない．うまい状態関数を見つけることができると，全く操作を行うことなく回数を求めることが可能である．（結局どのチームも実際に操作をして回数を求めていたため，正解で示したプログラム例より遥かに遅かった）

ここでは，3 つ目のポイントとして挙げた状態関数についてどのように見つけられるかを示す．点の個数が n 個の場合，必要な状態関数 f は以下のような性質があることが望まれる．

n 引数関数 … 各点の値を受け取る関数
操作毎に減少 … f(操作前) > f(操作後)
減少幅は一定以上で最小値が存在 … 負の値がなくなったときが最小値
巡回式（？）… 状態値は見る方向によらないはず，i.e. f(x1,x2,...,xN) = f(x2,...,xN,x1).
負の値が少ないほど小さい関数 … 絶対値や平方が有効？

まず，点が 3 個のときを考える．このとき状態関数 f は 3 引数である．

f(x,y,z) = |x+y+z| ではどうか？ x+y+z が不変なので意味がない．
f(x,y,z) = |x|+|y|+|z| ではどうか？ x=3, y=-1, z=-1 の場合，どの点に操作をしても減少しないのでダメ．
f(x,y,z) = |x+y|+|y+z|+|z+x| ではどうか？ x=1, y=-1, z=1 の場合，y の点に操作すると一回で終わるが操作前も操作後も状態関数の値は 2 となるのでダメ．

このように試していくと，上の 2 つ目の状態関数でダメな場合は 3 つ目でうまくいき， 3 つ目でダメな場合は 2 つ目でうまくいくことが分かる．では，これらを単純に足して，

f(x,y,z) = |x|+|y|+|z|+|x+y|+|y+z|+|z+x|

にしてみたらどうか？仮に x に操作したとして状態関数の返す値の変化を計算してみると，

f(x,y,z) - f(-x,y+x,z+x)
= |x|+|y|+|z|+|x+y|+|y+z|+|z+x|-|-x|-|y+x|-|z+x|-|y|-|z|-|y+z+2x|
= |y+z|-|y+z+2x|
（今， x+y+z=1 なので）
= |1-x|-|1+x|
= -2 * sign(x)

となる．ここで，sign(x) は x が正のとき +1，0 のとき 0，負のとき -1 を返す関数である．すなわち，負の値の点に操作すれば（その値に関係なく）この状態関数はちょうど 2 減ることが分かる．つまり，毎回負の値の点に操作することが操作回数を最小にする方法であるといえる．

では，点が 4 個のときはどうか？上記と同様の考察により，

f(x,y,z,w) = |x|+|y|+|z|+|w|+|x+y|+|y+z|+|z+w|+|w+x|+|x+y+z|+|y+z+w|+|z+w+x|+|w+x+y|

を考えると，f(xに操作前) - f(xに操作後) = -2 * sign(x) であることが分かる．点が 5 個以上に増えても同様で，一般には，

$f(x_0,\dots,x_{n-1}) = \sum_{i=1}^{n-1}\sum_{j=0}^{n-1}\left|\sum_{k=j}^{j+i-1}x_{k\%n}\right|$ （但し，k % n は k を n で割った剰余）

と表すことができ，操作前と操作後の差は操作した点の値が x のときに -2 * sign(x) であることが確認できる．点の個数を n とすると，最終状態に対する状態関数の値は f(1,0,0,...,0)であり全ての値の合計が 1 であることから， n * (n - 1) / 2 であることがわかる．従って，与えられた点の値を x0,...,x{n-1} とすると，状態関数の返す値は各操作で 2 減るので，停止までの操作回数は，

( f(x0,...,x{n-1}) - n * (n - 1) / 2 ) / 2

で計算できる．ということで，OCaml によるプログラム例は以下の通り．実際の入力は標準入力で与えられるが，ここでは簡単のため配列として与えられているものとしている．問題の設定から操作回数は int 型を超えるため， Num.num 型を利用した((int64 型を使ってもよい))．

open Num
let sigma from upto f =
  let rec loop i acc = if i > upto then acc else loop (i+1) (acc +/ f i) in
  loop from (num_of_int 0)

let main x =
  let n = Array.length x in
  let x = Array.append x x in
  (sigma 1 (n-1)
    (fun i -> sigma 0 (n-1)
               (fun j -> abs_num (sigma j (j+i-1)
                                   (fun k -> num_of_int (x.(k)))))) -/ num_of_int (n * (n-1) / 2))
  // (num_of_int 2)

上記では冗長な計算を含んでいるが，実際に操作して回数を求める方法に比べると微々たるものである．

なお，IMO の問題に対する解答を載せている書籍などでは，頂点が 5 の場合の状態関数として，

f(x,y,z,w,v) = (x-z)^2 + (y-w)^2 + (z-v)^2 + (w-x)^2 + (v-y)^2

を採用しているものが多い．これは常に正であり，負の数に操作することで必ず減少する関数となっている．ただ，f(xに操作前) - f(xに操作後) = -2xS （S は全ての点の値の合計）となるため，操作する点によって減少分が異なってしまい，停止までの操作回数を直接求めることはできない．もちろん，この関数はA*探索などをするのに役立つかもしれないが，結局実際に操作をしなければ回数が求められないので計算コストは大きいうえ，点が 5 個でない場合には適用できない．

[06/09/08] 追記：こちらに元のIMOの問題と解答の紹介があるらしい．また，上の5個でしか適用できないという式の一般化はこちらでみることができる．ただし，この式を利用しても操作する点によって減少分が異なるので，今回のプログラミングコンテストの問題のように最低操作回数を直接求めることは難しい．