日々の流転

λ. 複雑性とゲーム理論 (2)

「議会と中央銀行」や「乗っ取り屋の価格オファー」といった例にも 囚人のジレンマと同じ構造が見出せるのは面白かった。

λ. ICPC過去問: The Balance

今日の研究会のネタはICPC2004アジア予選の Problem A の The Balance だった。

<URL:http://www.teu.ac.jp/icpc/pastProblems/regional/r2004.pdf>

まず問題を単純化する。 同じ重さの錘を天秤の両側に追加しても，天秤のつりあいには影響せず錘の使 用量が増えるだけなので，ある重さの錘が天秤の両側に乗せられている場合は 除いてよい． また，錘を右側にk個乗せるのは，錘を左側にk個乗せる場合と モーメント*1の正負が丁度逆になっているので， 錘を右側にk個乗せるのは左側に-k個乗せると考えることにする． そうすると，d mgの薬を天秤の右に乗せ，a mgの錘を天秤の左にx個， b mgの錘を左にy個乗せて，つりあっている状況だけを考えればよいことになる． この状況は方程式 a*x + b*y = d で表される．

cをa,bの最大公約数として，a'=a/c, b'=b/c とすると， a*x + b*y = c*a'*x + c*b'*y = c (a'*x + b'*y) となる． a*x + b*y = d が解を持つのだから，dもcで割り切れる。 d' = d/c として，a*x + b*y = d の両辺をcで割ると a'*x + b'*y = d' となる．

ここで，a'とb'の最大公約数が1なので， 拡張ユークリッド互除法を使って a'*x + b'*y = 1 の解 (x,y) = (x1,y1) が求まる． そして，これをd'倍した(x,y) = (x1*d', y1*d') は a'*x + b'*y = d' の解になっている．これを(x2,y2)とおいておく。

a'*x + b'*y = d' の解が一つ求まったので，それを使って一般解を表す． a'*x + b'*y = a'*x2 + b'*y2 から a'(x-x2) = - b'(y-y2) となり， ここでa'とb'は互いに素なので，(y-y2)はa'で割り切れ， (x-x2)はb'で割り切れなければならない． よって，(x-x2)/b' = - (y-y2)/a' と変形できる． これをtとおくと一般解は (x,y) = (x2 + b'*t, y2 - a'*t) と表せる．

一般解が求まったので，あとは |x| + |y| を最小にするような t を探せば良 い．……のだけど，ちょっと綺麗な方法が思いつかなかった． とりあえず，t=0 から始めて |x| + |y| が小さくなる方向にひたすら t を動 かして求めている．多分間違った答えが出てくることはないと思うけどイマイ チだ．