トップ «前の日記(2005-10-03) 最新 次の日記(2005-10-05)» 月表示 編集

日々の流転


2005-10-04 [長年日記]

λ. 複雑性とゲーム理論 (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 を動 かして求めている.多分間違った答えが出てくることはないと思うけどイマイ チだ.

*1 懐かしい単語だ

本日のツッコミ(全4件) [ツッコミを入れる]
ψ t15u (2005-10-05 17:05)

http://www.sampou.org/cgi-bin/haskell.cgi?Everyday%3a2004-11-25 と同じやつですか

ψ さかい (2005-10-05 18:26)

がーん、既出だったか。<br>(ついでに重さを最小にするのも忘れてた)<br><br>でも、その解答例2は間違ってるっぽいですよ。<br>例えば、solve 648 375 4002 は (49,74) にならなくてはいけないのに、(10,-6) になってしまいます。

ψ t15u (2005-10-07 12:35)

修正しますた。

ψ さかい (2005-10-11 00:44)

ぐっじょぶ!